Bergische Universität Wuppertal Fachbereich Mathematik und Naturwissenschaften Angewandte Mathematik - Numerische Analysis (AMNA)

People Research Publications Teaching

---

Matthias Ehrhardt

Wie man gerechte Spielpläne entwirft

Fair Scheduling im Sport

Materialien für Interessierte zum Vortrag am Die Zielgruppe sind Schüler ab der 11. Klasse.

Das MATEMA-Logo (ein Luchs, copyright by Ulf Grenzer)

Beschreibung

Aus Anlass der Fussball-Weltmeisterschaft in Russland 2018 wollen wir den Fussball aus mathematischer Sicht betrachten. Wir wollen in diesem Vortrag untersuchen, wie man mithilfe der Mathematik den Spielplan z.B. in der deutschen Bundesliga gerecht entwirft.

Zur Zeit dominiert Bayern München die deutsche Bundesliga. Wenn nun eine Mannschaft im Spielplan immer gegen den vorigen (möglicherweise noch geschwächten/deprimierten, mit roten/gelben Karten versehenen) Gegner von Bayern München spielen müsste, hätte sie einen unfairen Vorteil. Beispiele gibt es hierfür schon:

• Norwegen, 2007: In der ersten Fussballliga wurde Brann Bergen vor Stabaek norwegischer Meister. Brann Bergen musste an 22 von 26 Spieltagev gegen die Mannschaft spielen, die jeweils vorher gegen das Team von Stabaek IF angetreten war.
• Belgien, Saison 2006/07: KSK Beveren musste in 29 von 34 Spielrunden jeweils gegen die Mannschaft antreten, die in der nächsten Spielrunde gegen den (übermächtigen) RSC Anderlecht spielen musste, so dass sich die gegnerischen Spieler evtl. nicht schonten, weil sie sich für das folgende Spiel keine Chancen ausrechneten. Am Ende stieg Beveren ab.
• Spanien, Saison 2012/13: Celta Vigo spielte an 33 von 38 Spieltagen jeweils gegen die Mannschaft, die am vorangegangenen Spieltag gegen den FC Barcelona gespielt hatte.

Das MATEMA-Logo (ein Luchs, copyright by Ulf Grenzer)

Referenzen für den Vortrag

1. A. Anagnostopoulos, L. Michel, P. van Hentenryck, Y. Vergados, A simulated annealing approach to the traveling tournament problem, in: Proceedings of CPAIOR'03, 2003.
2. A. Anagnostopoulos, L. Michel, P. van Hentenryck, Y. Vergados, A simulated annealing approach to the traveling tournament problem, Journal of Scheduling 9 (2006), 177-193.
3. I. Anderson, Balancing carry-over effects in tournaments, in: F. Holroyd, K. Quinn, C. Rowley, B. Webb (eds.), Combinatorial Designs and Their Applications, CRC Research Notes in Mathematics, pp. 1-16. Chapman & Hall, 1999.
4. J. Armstrong, R. J. Willis, Scheduling the cricket World Cup - A case-study, Journal of the Operational Research Society 44 (1993), 1067-1072.
5. B.C. Ball, D.B. Webster, Optimal scheduling for even-numbered team athletic conferences, AIIE Transactions 9 (1977), 161-169.
6. T. Bartsch, A. Drexl, S. Kröger, Scheduling the professional soccer leagues of Austria and Germany, Comput. Oper. Res. 33(7) (2006), 1907-1937.
7. J.C. Bean, J.R. Birge, Reducing travelling costs and player fatigue in the National Basketball Association, Interfaces 10 (1980), 98-102.
8. R. Bhattacharyya, A note on complexity of traveling tournament problem, 2009.
9. D. Briskorn, Sport Leagues Scheduling: Models, Combinatorial Properties, and Optimization Algorithms, Springer, Berlin, 2008.
10. A.E. Brouwer, G. Post, G. J. Woeginger, Tight bounds for break minimization, Journal of Combinatorial Theory A 115 (2008), 1065-1068.
11. W.O. Cain, The computer-aided heuristic approach used to schedule the Major League Baseball clubs, in: S.P. Ladany, R.E. Machol (eds.), Optimal Strategies in Sports, pp. 33-41. North Holland, Amsterdam, 1977.
12. R.T. Campbell, D.-S. Chen, A minimum distance basketball scheduling problem, in: R.E. Machol, S.P. Ladany, D.G. Morrison (eds.), Management Science in Sports, Studies in the Management Sciences 4, North-Holland, Amsterdam, 1976, pp. 15-25.
13. K.K.H. Cheung, Solving mirrored traveling tournament problem benchmark instances with eight teams, Discrete Optimization 5 (2008), 138-143.
14. G. Cocchi, A. Galligari, F.P. Nicolino, V. Piccialli, F. Schoen, M. Sciandrone, Scheduling the Italian National Volleyball Tournament, Interfaces (2018), 271-284.
15. D. Costa, An evolutionary tabu search algorithm and the NHL scheduling problem, INFOR, 33 (1995), 161-178.
16. F.N. Costa, S. Urrutia, C.C. Ribeiro, An ILS heuristic for the traveling tournament problem with predefined venues, Annals of Operations Research.
17. F. Della Croce, D. Oliveri, Scheduling the Italian football league: An ILP-based approach, Comput. Oper. Res. 33(7) (2006), 1963-1974.
18. D. De Werra, Geography, games and graphs, Discrete Appl. Math. 2 (1980), 327-337.
19. D. de Werra, Scheduling in sports, in: P. Hansen (ed.), Studies on Graphs and Discrete Programming, North Holland, Amsterdam, 1981, pp. 381-395.
20. D. de Werra, Minimizing irregularities in sports schedules using graph theory, Discrete Applied Mathematics 4 (1982), 217-226.
21. D. de Werra, Some models of graphs for scheduling sports competitions, Discrete Applied Mathematics 21 (1988), 47-65.
22. D. de Werra, J.L. Descombes, P. Masson, A constrained sports scheduling problem, Discrete Applied Mathematics 26 (1990), 41-49.
23. F. Della Croce, D. Oliveri, Scheduling the Italian football league: An ILP-based approach, Computers & Operations Research 33 (2006), 1963-1974.
24. J.H. Dinitz, Starters, in: C.J. Colbourn, J. H. Dinitz (eds.), The CRC Handbook of Combinatorial Designs, The CRC Press Series on Discrete Mathematics and its applications, CRC Press, Boca Raton, 1996, pp. 467-473.
25. A.R. Duarte, C.C. Ribeiro, Referee assignment in sports leagues: Approximate and exact multi-objective aproaches, in: 19th International Conference on Multiple Criteria Decision Making, Auckland, 2008, pp. 58-60.
26. A.R. Duarte, C.C. Ribeiro, S. Urrutia, A hybrid ILS heuristic to the referee assignment problem with an embedded MIP strategy, in: T. Bartz-Beielstein, M.J.B. Aguilera, C. Blum, B. Naujoks, A. Roli, G. Rudolph, M. Sampels (eds.), Hybrid Metaheuristics, Lecture Notes in Computer Science 4771, Springer, Berlin, 2007, pp. 82-95.
27. A.R. Duarte, C.C. Ribeiro, S. Urrutia, E.H. Haeusler, Referee assignment in sports leagues, in: E.K. Burke, H. Rudová, (eds.), Practice and Theory of Automated Timetabling VI, Lecture Notes in Computer Science 3867, Springer, Berlin, 2007, pp. 158-173.
28. G. Durán, M. Guajardo, J. Miranda, D. Sauré, S. Souyris, A. Weintraub, R. Wolf, Scheduling the Chilean soccer league by integer programming, Interfaces 37(6) (2007), 539-552.
29. G. Durán, T.F. Noronha, C.C. Ribeiro, S. Souyris, A. Weintraub, Branch-and cut for a real-life highly constrained soccer tournament scheduling problem, in: E. Burke, H. Rudová (eds.), Practice and Theory of Automated Timetabling VI, Lecture Notes in Computer Science 3867, Springer, 2007, pp. 174-186.
30. G. Durán, M. Guajardo, A. Weintraub, R. Wolf, O.R. & Soccer: Scheduling the Chilean league using mathematical programming, OR/MS Today, 36 (2009), 4247.
31. K. Easton, G. Nemhauser, M.A. Trick, The travelling tournament problem: Description and benchmarks, in: T. Walsh (ed.), Principles and Practice of Constraint Programming, Lecture Notes in Computer Science 2239, Springer, Berlin, 2001, pp. 580-585.
32. K. Easton, G.L. Nemhauser, M.A. Trick, Solving the travelling tournament problem: A combined integer programming and constraint programming approach, in: E.K. Burke, P. de Causmaecker (eds.), Practice and Theory of AutomatedTimetabling IV, volume 2740 of Lecture Notes in Computer Science, pp. 100-109, Berlin, 2003. Springer.
33. J.R. Evans, A microcomputer-based decision support system for scheduling umpires in the American Baseball League, Interfaces 18 (1988), 42-51.
34. J.R. Evans, J.E. Hebert, R.F. Deckro, Play ball - The scheduling of sports officials, Perspectives in Computing 4 (1984), 18-29.
35. A. Farmer, J.S. Smith, L.T. Miller, Scheduling umpire crews for professional tennis tournaments, Interfaces 37 (2007), 187-196.
36. J.A. Ferland, C. Fleurent, Computer aided scheduling for a sport league, INFOR 29 (1991), 14-25.
37. J. Fiallos, J. Pérez, F. Sabillón, M. Licona, Scheduling soccer league of Honduras using integer programming, in: A. Johnson, J. Miller (eds.), Proceedings of the 2010 Industrial Engineering Research Conference, San Carlos, 2010.
38. T. Flatberg, E. Nilssen, M. Stlevik, Scheduling the topmost fotball leagues of Norway, in: Book of Abstracts of the 23rd European Conference on Operational Research, page 240, Bonn, 2009.
39. C. Fleurent, J.A. Ferland, Allocating games for the NHL using integer programming, Operations Research 41 (1993), 649-654.
40. D. Froncek, Scheduling the Czech national basketball league, Congressus Numerantium 153 (2001), 5-24.
41. C. Goodbread, SEC aims to fix schedule problem by month's end, 2010.
42. D. Goossens, F. Spieksma, Scheduling the Belgian Soccer League, Interfaces 39(2) (2009), 109-118.
43. D. Goossens, F. Spieksma, Does the carry-over effect exist?, in: Book of Abstracts of the 23rd European Conference on Operational Research, page 288, Bonn, 2009.
44. A. Guedes, C.C. Ribeiro, A hybrid heuristic for minimizing weighted carry-over effects in round robin tournaments, in: Proceedings of the 4th Multidisciplinary International Conference on Scheduling Theory and Applications, Dublin, 2009, pp. 115-129.
45. M. Henz, Scheduling a major college basketball conference - Revisited, Operations Research 49 (2001), 163-168.
46. M. Henz, T. Müller, S. Thiel, Global constraints for round robin tournament scheduling, European Journal of Operational Research 153 (2004), 92-101.
47. R. Hoshino, K. Kawarabayashi, The multi-round balanced traveling tournament problem, in: 21st International Conference on Automated Planning and Scheduling, Freiburg, 2011.
48. R. Hoshino, K. Kawarabayashi, The inter-league extension of the traveling tournament problem and its application to sports scheduling, in: 25th AAAI Conference on Artificial Intelligence, San Francisco, 2011.
49. R. Hoshino, K. Kawarabayashi, The distance-optimal inter-league schedule for Japanese pro baseball, in: Workshop on Constraint Satisfaction Techniques for Planning and Scheduling Problem, 21st International Conference on Automated Planning and Scheduling, Freiburg, 2011.
50. S. Irnich, A new branch-and-price algorithm for the traveling tournament problem, European Journal of Operational Research 204 (2010), 218-228.
51. G. Kendall, S. Knust, C.C. Ribeiro, S. Urrutia, Scheduling in sports: An annotated bibliography, Computers and Operations Research 37 (2010), 1-19.
52. T. Kirkman, On a problem in combinations, Cambridge Dublin Math Journal 2 (1847), 191-204.
53. S. Knust, Scheduling non-professional table-tennis leagues, Technical Report 270, Osnabrücker Schriften zur Mathematik, 2007.
54. S. Knust, Scheduling non-professional table-tennis leagues, European Journal of Operational Research 200 (2010), 358-367.
55. P. Laliena, F.J. López, Fair draws for group rounds in sport tournaments, Int. Trans. in Oper. Res. (2018).
56. A. Lamghari, J.A. Ferland, in: D. Srinivasan (ed.), Proceedings of IEEE Symposium on Computational Intelligence in Scheduling, pp. 238-245, Honolulu, 2007.
57. A. Lamghari, J.A. Ferland, European Journal of Operational Research, 210 (2010), 694-705.
58. A. Lamghari, J.A. Ferland, Annals of Operational Research 180 (2010), 33-61.
59. R.A. Melo, S. Urrutia, C.C. Ribeiro, The traveling tournament problem with predefined venues, Journal of Scheduling 12 (2009), 607-622.
60. R. Miyashiro, T. Matsui, A polynomial-time algorithm to find an equitable home-away assignment, Operations Research Letters 33 (2005), 235-241.
61. R. Miyashiro, T. Matsui, Minimizing the carry-over effects value in a round robin tournament, in: Proceedings of the 6th International Conference on the Practice and Theory of Automated Timetabling, pp. 460-463, Brno, 2006.
62. R. Miyashiro, H. Iwasaki, T. Matsui, Characterizing feasible pattern sets with a minimum number of breaks, in: E.K. Burke, P. de Causmaecker (eds.), Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science 2740, Springer, Berlin, 2003, pp. 78-99.
63. G.L. Nemhauser, M.A. Trick, Scheduling a major college basketball conference, Operations Research 46 (1998), 1-8.
64. K. Nurmi, D. Goossens, T. Bartsch et al., A framework for a highly constrained sports scheduling problem, in: Proceedings of the International Multi-Conference of Engineers and Computer Scientists, volume III, pp. 1991-1997, Hong-Kong, 2010.
65. R. Ordonez, T.W. Knowles, Solving the American League umpire crew scheduling problem as a constraint satisfaction problem, in: Proceedings of the 29th Annual Meeting of the Decision Sciences Institute, volume 2, pp. 1058-1061, Las Vegas, 1998.
66. G. Post, G.J. Woeginger, Sports tournaments, home-away assignments, and the break minimization problem, Discrete Optimization 3 (2006), 165-173.
67. R.V. Rasmussen, Scheduling a triple round robin tournament for the best Danish soccer league, Europ. J. Oper. Res. 185(2) (2008), 795-810.
68. R.V. Rasmussen, M.A. Trick, Round robin scheduling - A survey, Europ. J. Oper. Res. 188(3) (2008), 617-636.
69. R.V. Rasmussen, M.A. Trick, The timetable constrained distance minimization problem, in: J.C. Beck, B.M. Smith (eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science 3990, pp. 167-181. Springer, 2006.
70. R.V. Rasmussen, M.A. Trick, A Benders approach for the constrained minimum break problem, European Journal of Operational Research 177 (2007), 198-213.
71. J.-C. Regin, Minimization of the number of breaks in sports scheduling problems using constraint programming, in: E. Freuder, R. Wallace (eds.), Constraint Programming Large Scale Discrete Optimization, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 57, pp. 115-130, 2001.
72. C.C. Ribeiro, S. Urrutia, Scheduling the Brazilian soccer championship with fairness and broadcast objectives, in: E.K. Burke, H. Rudová (eds.), Practice and Theory of Automated Timetabling VI, Lecture Notes in Computer Science 3867, Springer, Berlin/Heidelberg, 2007, pp. 147-157.
73. C.C. Ribeiro, S. Urrutia, Heuristics for the mirrored traveling tournament problem, European Journal of Operational Research, 179 (2007), 775-787.
74. C.C. Ribeiro, S. Urrutia, Bicriteria integer programming approach for scheduling the Brazilian national soccer tournament, In Proceedings of the Third International Conference on Management Science and Engineering Management, pp. 46-49, Bangkok, 2009.
75. C.C. Ribeiro, S. Urrutia, Soccer scheduling goaaaaal!, OR/MS Today, 37(2) (2010), 54-59.
76. C.C. Ribeiro, S. Urrutia, Scheduling the Brazilian soccer tournament: Solution approach and practice, Interfaces, 2011.
77. C.C. Ribeiro, Sports scheduling: Problems and applications, Intl. Trans. in Oper. Res. (2013).
78. K.G. Russell, Balancing carry-over effects in round robin tournaments, Biometrika 67(1) (1980), 127-131
79. R.A. Russell, J.M. Leung, Devising a cost effective schedule for a baseball league, Operations Research 42 (1994), 614-625.
80. J. Schönberger, D. C. Mattfeld, H. Kopfer, Memetic algorithm timetabling for non-commercial sport leagues, European Journal of Operational Research 153 (2004), 102-116.
81. J.A.M. Schreuder, Combinatorial aspects of construction of competition Dutch professional football leagues, Discrete Appl. Math. 35(3) (1992), 301-312.
82. J.A.M. Schreuder, Constructing timetables for sport competitions, Mathematical Programming Study 13 (1980), 58-67.
83. C. Thielen, S. Westphal, Complexity of the traveling tournament problem, Theoretical Computer Science 412 (2011), 345-351.
84. M.A. Trick, A schedule-then-break approach to sports timetabling, in: E.K. Burke, W. Erben (eds.), Selected papers from the Third International Conference on Practice and Theory of Automated Timetabling III, Lecture Notes in Computer Sciences 2079, pp. 242-253, Springer, 2000.
85. M.A. Trick, Integer and constraint programming approaches for round robin tournament scheduling, in: E. Burke, P. de Causmaecker (eds.), Practice and Theory of Automated Timetabling IV, Lecture Notes in Computer Science 2740, pp. 63-77, Berlin, 2003. Springer.
86. M.A. Trick, Formulations and reformulations in integer programming, in: R. Barták, M. Milano (eds.), Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science 3524, Springer, 2005, pp. 833-836.
87. M.A. Trick, Challenge traveling tournament instances, 2010.
88. S. Urrutia, C.C. Ribeiro, Maximizing breaks and bounding solutions to the mirrored traveling tournament problem, Discrete Applied Mathematics 154 (2006), 1932-1938.
89. G. Kendall, S. Knust, C.C. Ribeiro, S. Urrutia, Scheduling in sports: An annotated bibliography, Computers & Operations Research 2009.
90. S. Urrutia, C.C. Ribeiro, R.A. Melo, A new lower bound to the traveling tournament problem, in: Proceedings of the IEEE Symposium on Computational Intelligence in Scheduling, Honolulu, 2007, IEEE, pp. 15-18.
91. D.C. Uthus, P.J. Riddle, H.W. Guesgen, Solving the traveling tournament problem with iterative-deepening A*, Journal of Scheduling, 2011.
92. P. van Hentenryck, Y. Vergados, Traveling tournament scheduling: A systematic evaluation of simulated annealling, in: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, Lecture Notes in Computer Science 3990, Springer, Berlin, 2006, pp. 228-243.
93. R.J. Willis, B.J. Terrill, Scheduling the Australian state cricket season using simulated annealing, Journal of the Operational Research Society 45 (1994), 276-280.
94. M. Wright, Scheduling English cricket umpires, Journal of the Operational Research Society 42 (1991), 447-452.
95. M.Wright, A fair allocation of county cricket opponents, Journal of the Operational Research Society 43 (1992), 195-201.
96. M. Wright, Scheduling fixtures for New Zealand cricket, IMA Journal of Management Mathematics 16 (2005), 99-112.
97. M. Wright, Scheduling fixtures for basketball New Zealand, Computers & Operations Research 33 (2006), 1875-1893.
98. M. Yavuz, U.H. Inan, A. Figlali, Fair referee assignments for professional football leagues, Computers & Operations Research 35 (2008), 2937-2951.