IDEAS home Printed from https://ideas.repec.org/p/zbw/cauman/623.html
   My bibliography  Save this paper

A branching scheme based on First-Break-Then-Schedule decomposition

Author

Listed:
  • Briskorn, Dirk
  • Drexl, Andreas

Abstract

Single round robin tournaments are a well known class of sports leagues schedules. We consider leagues with a set T of n teams where n is even. Costs are associated to each possible match. The goal is to find the minimum cost tournament among those having the minimum number of breaks. We pick up structural properties of home-away-pattern sets having the minimum number of breaks. An branching idea using these properties is developed in order to guide branching steps on the first levels of a branch-and-bound tree in order to avoid nodes corresponding to infeasible subproblems.

Suggested Citation

  • Briskorn, Dirk & Drexl, Andreas, 2007. "A branching scheme based on First-Break-Then-Schedule decomposition," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 623, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    • Handle: RePEc:zbw:cauman:623
    as

    Download full text from publisher

    File URL: https://www.econstor.eu/bitstream/10419/147676/1/manuskript_623.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Rasmussen, Rasmus V. & Trick, Michael A., 2007. "A Benders approach for the constrained minimum break problem," European Journal of Operational Research, Elsevier, vol. 177(1), pages 198-213, February.
    2. Briskorn, Dirk & Drexl, Andreas, 2006. "Scheduling sports leagues using branch- and price," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 609, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    3. Drexl, Andreas & Knust, Sigrid, 2007. "Sports league scheduling: Graph- and resource-based models," Omega, Elsevier, vol. 35(5), pages 465-471, October.
    4. Briskorn, Dirk, 2007. "Feasibility of Home-Away-Pattern sets: A necessary condition," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 616, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Briskorn, Dirk & Knust, Sigrid, 2008. "On Circular 2-Factorizations of the Complete Tripartite Graph," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 636, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. D Briskorn & A Drexl, 2009. "A branch-and-price algorithm for scheduling sport leagues," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 84-93, January.
    2. Briskorn, Dirk & Drexl, Andreas, 2009. "A branching scheme for finding cost-minimal round robin tournaments," European Journal of Operational Research, Elsevier, vol. 197(1), pages 68-76, August.
    3. D Briskorn, 2011. "A branching scheme for minimum cost tournaments with regard to real-world constraints," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(12), pages 2133-2145, December.
    4. Rasmussen, Rasmus V. & Trick, Michael A., 2008. "Round robin scheduling - a survey," European Journal of Operational Research, Elsevier, vol. 188(3), pages 617-636, August.
    5. Briskorn, Dirk & Horbach, Andrei, 2009. "A Lagrangian approach for minimum cost tournaments," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 647, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    6. Nicolau, Juan L., 2012. "The effect of winning the 2010 FIFA World Cup on the tourism market value: The Spanish case," Omega, Elsevier, vol. 40(5), pages 503-510.
    7. Riise, Atle & Mannino, Carlo & Lamorgese, Leonardo, 2016. "Recursive logic-based Benders’ decomposition for multi-mode outpatient scheduling," European Journal of Operational Research, Elsevier, vol. 255(3), pages 719-728.
    8. Yi, Xiajie & Goossens, Dries & Nobibon, Fabrice Talla, 2020. "Proactive and reactive strategies for football league timetabling," European Journal of Operational Research, Elsevier, vol. 282(2), pages 772-785.
    9. Briskorn, Dirk, 2009. "A branching scheme for minimum cost tournaments with regard to real world constraints," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 643, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    10. Hoshino, Richard & Kawarabayashi, Ken-ichi, 2011. "A multi-round generalization of the traveling tournament problem and its application to Japanese baseball," European Journal of Operational Research, Elsevier, vol. 215(2), pages 481-497, December.
    11. Roel Lambers & Dries Goossens & Frits C. R. Spieksma, 2023. "The flexibility of home away pattern sets," Journal of Scheduling, Springer, vol. 26(5), pages 413-423, October.
    12. Knust, Sigrid, 2010. "Scheduling non-professional table-tennis leagues," European Journal of Operational Research, Elsevier, vol. 200(2), pages 358-367, January.
    13. Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre (Ed.), 2007. "Jahresbericht 2006," Manuskripte aus den Instituten für Betriebswirtschaftslehre der Universität Kiel 614, Christian-Albrechts-Universität zu Kiel, Institut für Betriebswirtschaftslehre.
    14. Elvin Coban & J. Hooker, 2013. "Single-facility scheduling by logic-based Benders decomposition," Annals of Operations Research, Springer, vol. 210(1), pages 245-272, November.
    15. Rasmussen, Rasmus V., 2008. "Scheduling a triple round robin tournament for the best Danish soccer league," European Journal of Operational Research, Elsevier, vol. 185(2), pages 795-810, March.
    16. M B Wright, 2009. "50 years of OR in sport," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 60(1), pages 161-168, May.
    17. Alex Krumer & Reut Megidish & Aner Sela, 2020. "The optimal design of round-robin tournaments with three players," Journal of Scheduling, Springer, vol. 23(3), pages 379-396, June.
    18. G Kendall, 2008. "Scheduling English football fixtures over holiday periods," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(6), pages 743-755, June.
    19. David Van Bulck & Dries Goossens, 2022. "Optimizing rest times and differences in games played: an iterative two-phase approach," Journal of Scheduling, Springer, vol. 25(3), pages 261-271, June.
    20. Yun-Chia Liang & Yen-Yu Lin & Angela Hsiang-Ling Chen & Wei-Sheng Chen, 2021. "Variable Neighborhood Search for Major League Baseball Scheduling Problem," Sustainability, MDPI, vol. 13(7), pages 1-18, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:zbw:cauman:623. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: ZBW - Leibniz Information Centre for Economics (email available below). General contact details of provider: https://edirc.repec.org/data/ibkiede.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.