Scheduling the professional soccer leagues of Austria and Germany. (English) Zbl 1090.90072
Summary: Generating a regular season schedule is a demanding task for any sports league. In Europe, the creation of a suitable schedule for every national top soccer league not only has to address numerous conflicting inner-league requirements and preferences. Additionally, the games of the European Cup matches (Champions League, UEFA Cup, National Cup Winners) have to be taken into account. In this paper we consider the case of Austria and Germany, that is the planning problem the “Deutsche Fußball-Bund” (DFB) and the “Österreichische Fußball-Bund” (ÖFB) are confronted with. For both leagues we develop models and algorithms which yield reasonable schedules quickly. The models borrow their expressive power from so-called partially renewable resources. Our approach generates schedules which have been accepted for play once by the DFB and six times by the ÖFB.
Software:
WSAT(OIP)References:
| [1] | Wren, A., Scheduling, timetabling and rostering—a special relationship?, (Burke, E.; Ross, P., Practice and theory of automated timetabling (1996), Springer: Springer Berlin), 46-75 |
| [2] | Burke, E.; Petrovic, S., Recent research directions in automated timetabling, European Journal of Operational Research, 140, 266-280 (2002) · Zbl 1001.90030 |
| [3] | de Werra, D., Some models of graphs for scheduling sports competitions, Discrete Applied Mathematics, 21, 47-65 (1988) · Zbl 0656.90060 |
| [4] | Elf, M.; Jünger, M.; Rinaldi, G., Minimizing breaks by maximizing cuts, Operations Research Letters, 31, 343-349 (2003) · Zbl 1033.90039 |
| [5] | Miyashiro R, Matsui T. Semidefinite programming based approaches to the break minimization problem. Working paper 2003-28, University of Tokyo, Department of Mathematical Informatics, Japan.; Miyashiro R, Matsui T. Semidefinite programming based approaches to the break minimization problem. Working paper 2003-28, University of Tokyo, Department of Mathematical Informatics, Japan. · Zbl 1090.90154 |
| [6] | Cain Jr, W. O., The computer-assisted heuristic approach used to schedule the major league baseball clubs, (Ladany, S. P.; Machol, R. E., Optimal strategies in sports (1977), North-Holland: North-Holland Amsterdam), 33-41 |
| [7] | Russell, R. A.; Leung, J. M., Devising a cost effective schedule for a baseball league, Operations Research, 42, 614-625 (1993) · Zbl 0815.90111 |
| [8] | Campbell, R. T.; Chen, D. S., A minimum distance basketball scheduling problem, (Machol, R. E.; Ladany, S. P.; Morrison, D. G., Management science in sports (1976), North-Holland: North-Holland Amsterdam), 15-25 · Zbl 0384.90055 |
| [9] | Bean, J. C.; Birge, J. R., Reducing travelling costs and player fatigue in the national basketball association, Interfaces, 10,3, 98-102 (1980) |
| [10] | de Werra, D.; Jacot-Descombes, L.; Masson, P., A constrained sports scheduling problem, Discrete Applied Mathematics, 26, 41-49 (1990) · Zbl 0691.90040 |
| [11] | Nemhauser, G. L.; Trick, M. A., Scheduling a major college basketball conference, Operations Research, 46, 1-8 (1998) |
| [12] | Henz, M., Scheduling a major college basketball conference—revisited, Operations Research, 49, 163-168 (2001) · Zbl 1163.90491 |
| [13] | Henz M, Müller T, Thiel S. Global constraints for round robin tournament scheduling. European Journal of Operational Research 2004;153:92-101.; Henz M, Müller T, Thiel S. Global constraints for round robin tournament scheduling. European Journal of Operational Research 2004;153:92-101. · Zbl 1053.90037 |
| [14] | Wright, M. B., A fair allocation of county cricket opponents, Journal of the Operational Research Society, 43, 195-201 (1992) |
| [15] | Armstrong, J.; Willis, R. J., Scheduling the cricket world cup—a case study, Journal of the Operational Research Society, 44, 1067-1072 (1993) · Zbl 0800.90662 |
| [16] | Willis, R. J.; Terrill, B. J., Scheduling the australian state cricket season using simulated annealing, Journal of the Operational Research Society, 45, 276-280 (1994) · Zbl 0800.90664 |
| [17] | Wright, M. B., Timetabling county cricket fixtures using a form of tabu search, Journal of the Operational Research Society, 45, 758-770 (1994) |
| [18] | Ferland, J. A.; Fleurent, C., Computer aided scheduling for a sport league, INFOR, 29, 14-25 (1991) |
| [19] | Schreuder, J. A.M., Combinatorial aspects of construction of competition dutch professional football leagues, Discrete Applied Mathematics, 35, 301-312 (1992) · Zbl 0800.90563 |
| [20] | Böttcher, J.; Drexl, A.; Kolisch, R.; Salewski, F., Project scheduling under partially renewable resource constraints, Management Science, 45, 543-559 (1999) · Zbl 1231.90178 |
| [21] | Bartsch T. Sportligaplanung—Ein Decision Support System zur Spielplanerstellung. Deutscher Universitäts-Verlag, Wiesbaden, 2001.; Bartsch T. Sportligaplanung—Ein Decision Support System zur Spielplanerstellung. Deutscher Universitäts-Verlag, Wiesbaden, 2001. |
| [22] | Schreuder, J. A.M., Constructing timetables for sport competitions, Mathematical Programming Study, 13, 58-67 (1980) · Zbl 0441.90043 |
| [23] | Anderson, I., Combinatorial designs and tournaments (1977), Clarendon Press: Clarendon Press Oxford |
| [24] | Schaerf, A., Scheduling sport tournaments using constraint logic programming, ConstraintsAn International Journal, 4, 43-65 (1999) · Zbl 0949.90045 |
| [25] | Trick, M. A., A schedule-then-break approach to sports timetabling, (Burke, E.; Erben, W., Practice and theory of automated timetabling (2000), Springer: Springer Berlin), 242-252 · Zbl 0982.68531 |
| [26] | Walser JP. Integer optimization by local search—a domain independent approach. Lecture notes in artificial intelligence, vol. 1637. Berlin-Heidelberg: Springer; 1999.; Walser JP. Integer optimization by local search—a domain independent approach. Lecture notes in artificial intelligence, vol. 1637. Berlin-Heidelberg: Springer; 1999. · Zbl 0934.90053 |
| [27] | Kolisch, R.; Drexl, A., Adaptive search for solving hard project scheduling problems, Naval Research Logistics, 43, 23-40 (1996) · Zbl 0870.90069 |
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
