Article Contents
Article Contents

Fair-fixture: Minimizing carry-over effects in football leagues

• * Corresponding author: Dilek Günneç
• We study a sports scheduling problem with the objective of minimizing carry-over effects in round robin tournaments.In the first part, focusing on tournaments that allow minimum number of breaks (at most one) for each team, we formulate an integer programming model and provide an efficient heuristic algorithm to solve this computationally expensive problem. We apply the algorithm to the current Turkish Professional Football League and present an alternative scheduling template. In the second part, we discuss how the carry-over effects can be further decreased if the number of breaks is allowed to be of slightly larger value and numerically represent this trade-off.

Mathematics Subject Classification: Primary: 80M50; Secondary: 90C27.

 Citation:

• Table 1.  Pattern set for a league of 8 teams

 Week 1 2 3 4 5 6 7 Pattern 1 A H A H A H A 2 A H H A H A H 3 A H A A H A H 4 A H A H H A H 5 A H A H A A H 6 H A H A H A H 7 H A A H A H A 8 H A H H A H A 9 H A H A A H A 10 H A H A H H A

Table 2.  Coe values of TPFL between 2012 and 2016

 Season Coe 2012-13 3666 2013-14 3818 2014-15 3707 2015-16 3820 Average 3752.75

Table 3.  Results of our heuristic

 Number of teams Coe Value (1-Break) Time (min) 8 104 0.20 10 192 0.44 12 318 2.73 14 446 2.73 16 626 6.30 18 944 23.90

Table 4.  Coe values and number of breaks for the heuristic with the BRK model. ($n = 18$)

 Break (Each) Random Canonical TPFL Coe Break Coe Break Coe Break $x=1$ 944 16 3876 16 3707 16 $1\leq x \leq2$ 650 31 698 29 580 32 $2\leq x \leq3$ 544 45 502 42 466 45 $2\leq x \leq4$ 544 45 502 42 466 45

Table 5.  Coe values and number of breaks when break distribution among teams is not considered

 Break (Each) 10 Teams 12 Teams 14 Teams 16 Teams 18 Teams Coe Break Coe Break Coe Break Coe Break Coe Break $x \leq 1$ 192 8 318 10 446 12 626 14 944 16 $x \leq 2$ 144 12 212 18 344 26 472 30 646 30 $x \leq 3$ 144 12 212 16 302 24 396 34 556 40

Table 6.  Comparison of our heuristic with three real league schedules for season 2015-16

 Num. of teams Coe Breaks (Each) Break Coe (H) Break (H) Decrease (%) Czech Rep. 16 742 $x=1$ 16 626 14 15.63 Germany 18 1056 $0\leq x \leq1$ 16 944 16 10.60 France 20 719 $0\leq x \leq4$ 45 530 56 26.28

Table 7.  Template for an 18-team league

 Week 1 Week 2 Week 3 Week 4 Week 5 Week 6 Week 7 Week 8 Week 9 1-11 18-1 1-8 12-1 1-14 2-1 1-17 4-1 1-5 6-2 2-7 16-2 2-9 3-2 8-3 15-2 2-11 18-2 3-14 12-3 3-13 10-3 7-4 4-6 3-4 5-3 3-17 17-4 4-5 9-4 4-16 6-5 5-9 16-5 7-6 15-4 5-10 13-6 17-5 5-7 9-8 17-7 6-8 8-18 6-9 7-13 8-17 6-12 17-6 15-10 10-11 9-7 17-9 16-7 16-8 10-9 7-10 8-15 11-13 12-15 18-10 10-16 11-8 9-12 11-15 11-18 14-11 18-12 13-16 11-12 12-14 14-10 15-18 14-16 15-14 13-18 16-17 14-18 14-13 13-15 12-13 Week 10 Week 11 Week 12 Week 13 Week 14 Week 15 Week 16 Week 17 9-1 1-7 16-1 1-6 3-1 15-1 1-10 13-1 2-13 14-2 2-12 10-2 2-8 2-5 17-2 2-4 7-3 3-6 9-3 3-16 4-13 11-3 3-15 18-3 4-18 11-4 4-14 12-4 5-12 10-4 4-8 8-5 5-11 15-5 5-18 14-5 6-14 18-6 5-13 10-6 6-16 12-8 6-15 18-7 7-15 8-7 6-11 14-7 8-14 16-9 7-11 13-8 9-18 13-9 7-12 11-9 10-12 13-10 8-10 15-9 17-10 12-16 9-14 12-17 17-15 18-17 17-13 11-17 16-11 14-17 16-18 15-16
•  [1] I. Anderson, Balancing carry-over effects in tournaments, Chapman and Hall/CRC Research Notes in Mathematics Series, 403 (1999), 1-16. [2] D. De Werra, Geography, games and graphs, Discrete Applied Mathematics, 2 (1980), 327-337.  doi: 10.1016/0166-218X(80)90028-1. [3] D. De Werra, Scheduling in sports, Studies on Graphs and Discrete Programming, 11 (1981), 381-395. [4] D. De Werra, L. Jacot-Descombes and P. Masson, A constrained sports scheduling problem, Discrete Applied Mathematics, 26 (1990), 41-49.  doi: 10.1016/0166-218X(90)90019-9. [5] F. Della Croce and D. Oliveri, Scheduling the Italian football league: An ILP-based approach, Computers & Operations Research, 33 (2006), 1963-1974. [6] T. Flatberg, E. J. Nilssen and M. Stolevik, Scheduling the topmost football leagues of Norway, in Book of abstracts of the 23rd European Conference on Operational Research, Bonn, Germany, (2009), p240. [7] D. Goossens and F. Spieksma, Does the carry-over effect exist?, in Book of abstracts of the 23rd European Conference on Operational Research, Bonn, Germany, (2009), p288. [8] D. Goossens and F. Spieksma, Soccer schedules in Europe: An overview, Journal of Scheduling, 15 (2012), 641-651. [9] A. Guedes and C. Ribeiro, A heuristic for minimizing weighted carry-over effects in round robin tournaments, Journal of Scheduling, 14 (2011), 655-667.  doi: 10.1007/s10951-011-0244-y. [10] M. Henz, Scheduling a major college basketball conference-revisited, Operations Research, 49 (2001), 163-168.  doi: 10.1287/opre.49.1.163.11193. [11] M. P. Kidd, A tabu-search for minimising the carry-over effects value of a round-robin tournament, Journal of the Operations Research Society of South Africa, 26 (2010), 125-141.  doi: 10.5784/26-2-91. [12] E. Lambrechts, A. M. C. Ficker, D. Goossens and F. Spieksma, Round-robin tournaments generated by the circle method have maximum carry-over, Proceedings of the International Conference on Integer Programming and Combinatorial Optimization, 9682 (2016), 178-189.  doi: 10.1007/978-3-319-33461-5_15. [13] R. Miyashiro and T. Matsui, Minimizing the carry-over effects value in a round robin tournament, Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, (2006), 460-463. [14] M. C. Roboredo, L. Aizemberg, A. A. Pessoa and J. C. Mello, Scheduling the Brazilian football league minimizing extended carry-over effects associated to strength groups, Engevista, 16 (2014), 102-110. [15] K. G. Russell, Balancing carry-over effects in round robin tournaments, Biometrika, 67 (1980), 127-131.  doi: 10.1093/biomet/67.1.127. [16] M. Trick, A schedule-then-break approach to sports timetabling, in Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, (2000), 242-253. doi: 10.1007/3-540-44629-X_15.

Tables(7)