October  2019, 15(4): 1565-1577. doi: 10.3934/jimo.2018110

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

1. 

Department of Industrial Engineering, Özyeğin University, Istanbul, 34794, Turkey

2. 

BSH Home Appliances Corporation, Istanbul, 34771, Turkey

* Corresponding author: Dilek Günneç

Received  December 2016 Revised  January 2018 Published  July 2018

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.

Citation: Dilek Günneç, Ezgi Demir. Fair-fixture: Minimizing carry-over effects in football leagues. Journal of Industrial & Management Optimization, 2019, 15 (4) : 1565-1577. doi: 10.3934/jimo.2018110
References:
[1]

I. Anderson, Balancing carry-over effects in tournaments, Chapman and Hall/CRC Research Notes in Mathematics Series, 403 (1999), 1-16.   Google Scholar

[2]

D. De Werra, Geography, games and graphs, Discrete Applied Mathematics, 2 (1980), 327-337.  doi: 10.1016/0166-218X(80)90028-1.  Google Scholar

[3]

D. De Werra, Scheduling in sports, Studies on Graphs and Discrete Programming, 11 (1981), 381-395.   Google Scholar

[4]

D. De WerraL. 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.  Google Scholar

[5]

F. Della Croce and D. Oliveri, Scheduling the Italian football league: An ILP-based approach, Computers & Operations Research, 33 (2006), 1963-1974.   Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

D. Goossens and F. Spieksma, Soccer schedules in Europe: An overview, Journal of Scheduling, 15 (2012), 641-651.   Google Scholar

[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.  Google Scholar

[10]

M. Henz, Scheduling a major college basketball conference-revisited, Operations Research, 49 (2001), 163-168.  doi: 10.1287/opre.49.1.163.11193.  Google Scholar

[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.  Google Scholar

[12]

E. LambrechtsA. M. C. FickerD. 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.  Google Scholar

[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.   Google Scholar

[14]

M. C. RoboredoL. AizembergA. 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.   Google Scholar

[15]

K. G. Russell, Balancing carry-over effects in round robin tournaments, Biometrika, 67 (1980), 127-131.  doi: 10.1093/biomet/67.1.127.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

I. Anderson, Balancing carry-over effects in tournaments, Chapman and Hall/CRC Research Notes in Mathematics Series, 403 (1999), 1-16.   Google Scholar

[2]

D. De Werra, Geography, games and graphs, Discrete Applied Mathematics, 2 (1980), 327-337.  doi: 10.1016/0166-218X(80)90028-1.  Google Scholar

[3]

D. De Werra, Scheduling in sports, Studies on Graphs and Discrete Programming, 11 (1981), 381-395.   Google Scholar

[4]

D. De WerraL. 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.  Google Scholar

[5]

F. Della Croce and D. Oliveri, Scheduling the Italian football league: An ILP-based approach, Computers & Operations Research, 33 (2006), 1963-1974.   Google Scholar

[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. Google Scholar

[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. Google Scholar

[8]

D. Goossens and F. Spieksma, Soccer schedules in Europe: An overview, Journal of Scheduling, 15 (2012), 641-651.   Google Scholar

[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.  Google Scholar

[10]

M. Henz, Scheduling a major college basketball conference-revisited, Operations Research, 49 (2001), 163-168.  doi: 10.1287/opre.49.1.163.11193.  Google Scholar

[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.  Google Scholar

[12]

E. LambrechtsA. M. C. FickerD. 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.  Google Scholar

[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.   Google Scholar

[14]

M. C. RoboredoL. AizembergA. 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.   Google Scholar

[15]

K. G. Russell, Balancing carry-over effects in round robin tournaments, Biometrika, 67 (1980), 127-131.  doi: 10.1093/biomet/67.1.127.  Google Scholar

[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.  Google Scholar

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
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
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
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
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
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
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
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]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102

[2]

Guo Zhou, Yongquan Zhou, Ruxin Zhao. Hybrid social spider optimization algorithm with differential mutation operator for the job-shop scheduling problem. Journal of Industrial & Management Optimization, 2021, 17 (2) : 533-548. doi: 10.3934/jimo.2019122

[3]

Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021013

[4]

Tomáš Smejkal, Jiří Mikyška, Jaromír Kukal. Comparison of modern heuristics on solving the phase stability testing problem. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1161-1180. doi: 10.3934/dcdss.2020227

[5]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020174

[6]

Onur Şimşek, O. Erhun Kundakcioglu. Cost of fairness in agent scheduling for contact centers. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021001

[7]

Wei Feng, Michael Freeze, Xin Lu. On competition models under allee effect: Asymptotic behavior and traveling waves. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5609-5626. doi: 10.3934/cpaa.2020256

[8]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054

[9]

Hua Zhong, Xiaolin Fan, Shuyu Sun. The effect of surface pattern property on the advancing motion of three-dimensional droplets. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020366

[10]

Pablo Neme, Jorge Oviedo. A note on the lattice structure for matching markets via linear programming. Journal of Dynamics & Games, 2020  doi: 10.3934/jdg.2021001

[11]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012

[12]

Tengfei Yan, Qunying Liu, Bowen Dou, Qing Li, Bowen Li. An adaptive dynamic programming method for torque ripple minimization of PMSM. Journal of Industrial & Management Optimization, 2021, 17 (2) : 827-839. doi: 10.3934/jimo.2019136

[13]

Chueh-Hsin Chang, Chiun-Chuan Chen, Chih-Chiang Huang. Traveling wave solutions of a free boundary problem with latent heat effect. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021028

[14]

Shudi Yang, Xiangli Kong, Xueying Shi. Complete weight enumerators of a class of linear codes over finite fields. Advances in Mathematics of Communications, 2021, 15 (1) : 99-112. doi: 10.3934/amc.2020045

[15]

Min Xi, Wenyu Sun, Jun Chen. Survey of derivative-free optimization. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 537-555. doi: 10.3934/naco.2020050

[16]

Nalin Fonseka, Jerome Goddard II, Ratnasingham Shivaji, Byungjae Son. A diffusive weak Allee effect model with U-shaped emigration and matrix hostility. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020356

[17]

Ali Mahmoodirad, Harish Garg, Sadegh Niroomand. Solving fuzzy linear fractional set covering problem by a goal programming based solution approach. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020162

[18]

Shin-Ichiro Ei, Hiroshi Ishii. The motion of weakly interacting localized patterns for reaction-diffusion systems with nonlocal effect. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 173-190. doi: 10.3934/dcdsb.2020329

[19]

Thazin Aye, Guanyu Shang, Ying Su. On a stage-structured population model in discrete periodic habitat: III. unimodal growth and delay effect. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2021005

[20]

Juntao Sun, Tsung-fang Wu. The number of nodal solutions for the Schrödinger–Poisson system under the effect of the weight function. Discrete & Continuous Dynamical Systems - A, 2021  doi: 10.3934/dcds.2021011

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (566)
  • HTML views (1744)
  • Cited by (0)

Other articles
by authors

[Back to Top]