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, 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.

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

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

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

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

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.

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

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

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

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

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]

Louis Caccetta, Syarifah Z. Nordin. Mixed integer programming model for scheduling in unrelated parallel processor system with priority consideration. Numerical Algebra, Control & Optimization, 2014, 4 (2) : 115-132. doi: 10.3934/naco.2014.4.115

[2]

Elham Mardaneh, Ryan Loxton, Qun Lin, Phil Schmidli. A mixed-integer linear programming model for optimal vessel scheduling in offshore oil and gas operations. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1601-1623. doi: 10.3934/jimo.2017009

[3]

Zhiguo Feng, Ka-Fai Cedric Yiu. Manifold relaxations for integer programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 557-566. doi: 10.3934/jimo.2014.10.557

[4]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

[5]

Wan Nor Ashikin Wan Ahmad Fatthi, Adibah Shuib, Rosma Mohd Dom. A mixed integer programming model for solving real-time truck-to-door assignment and scheduling problem at cross docking warehouse. Journal of Industrial & Management Optimization, 2016, 12 (2) : 431-447. doi: 10.3934/jimo.2016.12.431

[6]

Yu-Jen Chang, Ming-Jong Yao. New heuristics for solving the economic lot scheduling problem with reworks. Journal of Industrial & Management Optimization, 2011, 7 (1) : 229-251. doi: 10.3934/jimo.2011.7.229

[7]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353

[8]

Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial & Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811

[9]

Renato Bruni, Gianpiero Bianchi, Alessandra Reale. A combinatorial optimization approach to the selection of statistical units. Journal of Industrial & Management Optimization, 2016, 12 (2) : 515-527. doi: 10.3934/jimo.2016.12.515

[10]

Ye Tian, Cheng Lu. Nonconvex quadratic reformulations and solvable conditions for mixed integer quadratic programming problems. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1027-1039. doi: 10.3934/jimo.2011.7.1027

[11]

Zhenbo Wang, Shu-Cherng Fang, David Y. Gao, Wenxun Xing. Global extremal conditions for multi-integer quadratic programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 213-225. doi: 10.3934/jimo.2008.4.213

[12]

Jing Quan, Zhiyou Wu, Guoquan Li. Global optimality conditions for some classes of polynomial integer programming problems. Journal of Industrial & Management Optimization, 2011, 7 (1) : 67-78. doi: 10.3934/jimo.2011.7.67

[13]

Mohamed A. Tawhid, Ahmed F. Ali. A simplex grey wolf optimizer for solving integer programming and minimax problems. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 301-323. doi: 10.3934/naco.2017020

[14]

Simone Göttlich, Oliver Kolb, Sebastian Kühn. Optimization for a special class of traffic flow models: Combinatorial and continuous approaches. Networks & Heterogeneous Media, 2014, 9 (2) : 315-334. doi: 10.3934/nhm.2014.9.315

[15]

Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269

[16]

Jiayu Shen, Yuanguo Zhu. An uncertain programming model for single machine scheduling problem with batch delivery. Journal of Industrial & Management Optimization, 2018, 13 (5) : 1-17. doi: 10.3934/jimo.2018058

[17]

Min-Fan He, Li-Ning Xing, Wen Li, Shang Xiang, Xu Tan. Double layer programming model to the scheduling of remote sensing data processing tasks. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 1515-1526. doi: 10.3934/dcdss.2019104

[18]

René Henrion, Christian Küchler, Werner Römisch. Discrepancy distances and scenario reduction in two-stage stochastic mixed-integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 363-384. doi: 10.3934/jimo.2008.4.363

[19]

Edward S. Canepa, Alexandre M. Bayen, Christian G. Claudel. Spoofing cyber attack detection in probe-based traffic monitoring systems using mixed integer linear programming. Networks & Heterogeneous Media, 2013, 8 (3) : 783-802. doi: 10.3934/nhm.2013.8.783

[20]

Pooja Louhan, S. K. Suneja. On fractional vector optimization over cones with support functions. Journal of Industrial & Management Optimization, 2017, 13 (2) : 549-572. doi: 10.3934/jimo.2016031

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (36)
  • HTML views (378)
  • Cited by (0)

Other articles
by authors

[Back to Top]