×

zbMATH — the first resource for mathematics

Minimization of rest mismatches in round robin tournaments. (English) Zbl 1458.90251
Summary: In sports tournaments, an occurrence of a difference in the rest periods of opponent teams in a game, which we refer to as a rest mismatch, will disadvantage the less rested team. Thus, it is only fair to expect opposing teams to have rested equally before their game. In this work, we introduce and study the rest mismatch problem where the goal is to minimize the number of rest mismatches in a round robin tournament. Two integer linear formulations and a constraint programming formulation are provided, and their computational performances are compared for several problem instances. Moreover, a heuristic algorithm is developed which finds a single round robin schedule with zero mismatches when the number of teams in the tournament is a multiple of 8, and four mismatches when it is a multiple of 4 but not 8.

MSC:
90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
Software:
Gurobi; OPL
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Anderson, I., Combinatorial designs and tournaments, (1997), Oxford University Press · Zbl 0881.05001
[2] Blest, D.; Fitzgerald, D., Scheduling sports competitions with a given distribution of times, Discret. Appl. Math., 22, 1, 9-19, (1988) · Zbl 0656.90059
[3] Briskorn, D., Combinatorial properties of strength groups in round Robin tournaments, Eur. J. Oper. Res., 192, 3, 744-754, (2009) · Zbl 1157.90503
[4] Briskorn, D.; Drexl, A., IP models for round Robin tournaments, Comput. Oper. Res., 36, 3, 837-852, (2009) · Zbl 1179.90127
[5] Briskorn, D.; Knust, S., Constructing fair sports league schedules with regard to strength groups, Discret. Appl. Math., 158, 2, 123-135, (2010) · Zbl 1233.90150
[6] Easton, K.; Nemhauser, G.; Trick, M., The traveling tournament problem: description and benchmarks, (Walsh, T., Principles and Practice of Constraint Programming, Lecture Notes in Computer Science. 2239, (2001), Springer), 580-584 · Zbl 1067.68627
[7] Goossens, D.; Kempeneers, J.; Koning, H. R.; Spieksma, F. C., Winning in straight sets helps in grand slam tennis, Int. J. Perform. Anal. Sport, 15, 3, 1007-1021, (2015)
[8] Goossens, D.; Spieksma, F. C., Soccer schedules in Europe: an overview, J. Sched., 15, 5, 641-651, (2012)
[9] Gurobi Optimization, Inc., 2016. Gurobi optimizer reference manual. http://www.gurobi.com.
[10] Haselgrove, J.; Leech, J., A tournament design problem, Am. Math. Month., 84, 3, 198-201, (1977) · Zbl 0355.05013
[11] van Hentenryck, P., Constraint and integer programming in OPL, INFORMS J. Comput., 14, 4, 345-372, (2002) · Zbl 1238.90102
[12] van’t Hof, P.; Post, G.; Briskorn, D., Constructing fair round Robin tournaments with a minimum number of breaks, Oper. Res. Lett., 38, 6, 592-596, (2010) · Zbl 1202.90151
[13] Knust, S., Scheduling sports tournaments on a single court minimizing waiting times, Oper. Res. Lett., 36, 4, 471-476, (2008) · Zbl 1155.90387
[14] Knust, S., Scheduling non-professional table-tennis leagues, Eur. J. Oper. Res., 200, 2, 358-367, (2010) · Zbl 1177.90167
[15] Lambrechts, E.; Ficker, A. M.; Goossens, D.; Spieksma, F. C., Round-Robin tournaments generated by the circle method have maximum carry-over, Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, 178-189, (2016), Springer · Zbl 1416.90008
[16] Rasmussen, R.; Trick, M., Round Robin scheduling - a survey, Eur. J. Oper. Res., 188, 3, 617-636, (2008) · Zbl 1144.90396
[17] Russell, K., Balancing carry-over effects in round Robin tournaments, Biometrika, 67, 1, 127-131, (1980)
[18] Russell, R.; Urban, T., A constraint programming approach to the multiple-venue, sport-scheduling problem, Comput. Oper. Res., 33, 7, 1895-1906, (2006) · Zbl 1090.90093
[19] Sanchez, J.; Sanchez, M.; Hernandez, D.; Ramirez-Campillo, R.; Martínez, C.; Nakamura, F. Y., Fatigue in U12 soccer-7 players during repeated one-day tournament games - a pilot study, J. Strength Cond. Res, (2017)
[20] Schellenberg, P.; Van Rees, G.; Vanstone, S., The existence of balanced tournament designs, Ars Comb., 3, 303-318, (1977) · Zbl 0401.05029
[21] Schönberger, J.; Mattfeld, D. C.; Kopfer, H., Memetic algorithm timetabling for non-commercial sport leagues, Eur. J. Oper. Res., 153, 1, 102-116, (2004) · Zbl 1137.90517
[22] Suksompong, W., Scheduling asynchronous round-Robin tournaments, Oper. Res. Lett., 44, 1, 96-100, (2016)
[23] Trick, M. A., Integer and constraint programming approaches for round-Robin tournament scheduling, Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, 63-77, (2002), Springer
[24] Wallis, W., One-factorizations, (1997), Kluwer Academic Publishers · Zbl 0863.05064
[25] de Werra, D., Scheduling in sports, (Hansen, P., Studies on Graphs and Discrete Programming, (1981), North-Holland), 381-395 · Zbl 0469.90042
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.