Abstract
Timetabling problem is one of the most difficult operational tasks and an important step in raising the industrial productivity, capability, and capacity. Such tasks are usually tackled using metaheuristics techniques that provide an intelligent way of suggesting solutions or decision making. Swarm intelligence techniques including ant systems have proved to be effective examples. Different recent experiments showed that ant system algorithms are reliable for timetabling in many discrete-events applications such as educational and personnel timetabling, job and machine scheduling, and other similar aspects. However, obtaining an optimal solution is extremely difficult but obtaining a near-optimal solution using metaheuristic algorithms is possible. This research paper seeks the enhancement of ant system algorithm for an efficient timetabling task. This algorithm aims to generate feasible and high-quality timetables via minimizing constraints violations in a reasonable execution time. This enhanced version is a hybrid elitist-ant system metaheuristic which is tested on a round-robin tournament known as the international timetabling competition-2021 dedicated for sports timetabling. The competition includes several hard and soft constraints to be satisfied to build a feasible high-quality timetable. It consists of three categories of complexities or difficulties, namely early, test and middle instances. Results showed that the proposed elitist-ant system metaheuristic has obtained competitive timetables for almost all the instances in terms of feasibility and quality. The feasibility is measured by minimizing the violation of hard constraints to zero, while minimizing soft constraints towards zero violations as much as possible. The performance of the elitist-ant system is evaluated by the consumed computational time to produce a timetable, consistency, and robustness. The elitist-ant system showed a robust and consistent performance in producing a diversity of timetables in a reasonable computational time.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
- 2.
- 3.
- 4.
- 5.
Detailed formulations are available in: https://www.sportscheduling.ugent.be/RobinX/threeField.php.
- 6.
References
M. Dorigo, V. Maniezzo, A. Colorini, Positive feed-back as a search strategy. Tech. Rept. 91-016 (Dipartmento di Elettronica, Politecnico di Milano, Italy, 1991)
G. Jaradat, M. Ayob, An elitist-ant system for solving the post-enrolment course timetabling problem, in The 2010 International Conference on Database Theory and Application (DTA 2010) (2010), pp. 167–176
G. Jaradat, M. Ayob, I. Almarashdeh, The effect of elite pool in hybrid population-based meta-heuristics for solving combinatorial optimization problems. Appl. Soft Comput. 44, 45–56 (2016). https://doi.org/10.1016/j.asoc.2016.01.002
D. Van Bulck, D. Goossens, J. Beliën, M. Davari, International timetabling competition 2021: sports timetabling. itc2021.ugent.be
M.A. Trick, Integer and constraint programming approaches for round robin tournament scheduling (2004)
A. Aggoun, A. Vazacopoulos, Solving sports scheduling and timetabling problems with constraint programming, in Economics, Management and Optimization in Sports, ed. S. Butenko et al. (Springer-Verlag, Berlin, Heidelberg, 2004)
M.A. Trick, A schedule-then-break approach to sports timetabling, in PATAT 2000. LNCS, vol. 2079, ed. E. Burke, W. Erben (Springer, Heidelberg 2001), pp. 242–253
J. Schönberger, D.C. Mattfeld, H. Kopfer, Memetic algorithm timetabling for non-commercial sport leagues. Eur. J. Oper. Res. 153(1), 102–116 (2004). ISSN 0377-2217. https://doi.org/10.1016/S0377-2217(03)00102-4
A. Duarte, C.C. Ribeiro, S. Urrutia, A hybrid ILS heuristic to the referee assignment problem with an embedded MIP strategy. Lect. Notes Comput. Sci. 4771, 82–95 (2007)
G. Durán, Sports scheduling and other topics in sports analytics: a survey with special reference to Latin America. TOP 29, 125–155 (2021). https://doi.org/10.1007/s11750-020-00576-9
M. Grobner, P. Wilke, S. Buttcher, A standard framework for timetabling problems, in PATAT 2002, LNCS 2740, ed. E. Burke, P. De Causmaecker (2003), pp. 24–38
G. Kendall, S. Knust, C.C. Ribeiro, S. Urrutia, Scheduling in sports: an annotated bibliography. Comput. Oper. Res. 37(1), 1–19 (2010). ISSN 0305-0548
S. Knust, Classification of Literature on Sports Scheduling (2020), http://www2.inf.uos.de/knust/sportssched/sportlit_class/. Accessed 25 March 2021
D.R. Goossens, F.C.R. Spieksma, Soccer schedules in Europe: an overview. J. Sched. 15, 641–651 (2011)
G.L. Nemhauser, M.A. Trick, Scheduling a major college basketball conference. Oper. Res. 46, 1–8 (1998)
D. Van Bulck, D. Goossens, J. Schönberger, M. Davari, ITC2021—Sports Timetabling Problem Description and File Format (2020), https://www.sportscheduling.ugent.be/ITC2021/images/OrganizationITC2021_V7.pdf
D. Van Bulck, D. Goossens, J. Schönberger, M. Guajardo, An instance data repository for the round-robin sports timetabling problem. Manag. Labour Stud. 45(2), 184–200 (2020). https://doi.org/10.1177/0258042X20912108
D. Van Bulck, D. Goossens, J. Schönberger, M. Guajardo, RobinX: a three-field classification and unified data format for round-robin sports timetabling. Eur. J. Oper. Res. 280, 568–580 (2019)
T.A.M. Toffolo, J. Christiaens, F.C.R. Spieksma, G.V. Berghe, The sport teams grouping problem. Ann. Oper. Res. 275, 223–243 (2019)
R. Linfati, G. Gatica, J.W. Escobar, A flexible mathematical model for the planning and designing of a sporting fixture by considering the assignment of referees. Int. J. Ind. Eng. Comput. 10(2), 281–294 (2019). https://doi.org/10.5267/j.ijiec.2018.6.004
T. Wauters, S. Van Malderen, Decomposition and local search-based methods for the traveling umpire problem. Eur. J. Oper. Res. 238(3), (2014)
M. Triska, N. Musliu, An improved SAT formulation for the social golfer problem. Ann. Oper. Res. 194, 427–438 (2012)
C.C. Ribeiro, Sports scheduling: problems and applications. Int. Trans. Oper. Res. 19, 201–226 (2012). https://doi.org/10.1111/j.1475-3995.2011.00819.x
M. Goerigk, S. Westphal, A combined local search and integer programming approach to the traveling tournament problem. Ann. Oper. Res. 239, 343–354 (2016)
M. Ayob, G. Jaradat, Hybrid ant colony systems for course timetabling problems, in 2009 2nd Conference on Data Mining and Optimization (2009), pp. 120–126. https://doi.org/10.1109/DMO.2009.5341898.
H. Crauwels, D. Oudheusden, Ant Colony Optimization and Local Improvement (2003), https://www.researchgate.net/publication/228716201_Ant_colony_optimization_and_local_improvement
P. Chen, G. Kendall, G.V. Berghe, An ant based hyper-heuristic for the travelling tournament problem, in 2007 IEEE Symposium on Computational Intelligence in Scheduling (2007), pp. 19–26. https://doi.org/10.1109/SCIS.2007.367665
D.C. Uthus, P.J. Riddle, H.W. Guesgen, Ant colony optimization and the single round robin maximum value problem, in Ant Colony Optimization and Swarm Intelligence. ANTS 2008, ed. M. Dorigo, M. Birattari, C. Blum, M. Clerc, T. Stützle, A.F.T. Winfield. Lecture Notes in Computer Science, vol. 5217 (Springer, Berlin, Heidelberg 2008). https://doi.org/10.1007/978-3-540-87527-7_23
N. Kumyaito, P. Yupapin, K. Tamee, Planning a sports training program using adaptive particle swarm optimization with emphasis on physiological constraints. BMC Res. Notes 11, 9 (2018). https://doi.org/10.1186/s13104-017-3120-9
A. Madureira, N. Sousa, I. Pereira, Swarm Intelligence for Scheduling (2011)
R.V. Rasmussen, M.A. Trick, Round robin scheduling—a survey. Eur. J. Oper. Res. 188(3), 617–636 (2007)
G.M. Jaradat, Hybrid elitist-ant system for a symmetric traveling salesman problem: case of Jordan. Neural Comput. Appl. 29, 565–578 (2018). https://doi.org/10.1007/s00521-016-2469-3
L. Abualigah, A. Diabat, S. Mirjalili, M. Abd Elaziz, A.H. Gandomi, The arithmetic optimization algorithm. Comput. Methods Appl. Mech. Eng. 376, 113609 (2021). ISSN 0045-7825. https://doi.org/10.1016/j.cma.2020.113609
L. Abualigah, D. Yousri, M. Abd Elaziz, A.A. Ewees, M.A.A. Al-qaness, A.H. Gandomi, Aquila optimizer: a novel meta-heuristic optimization algorithm. Comput. Ind. Eng. 157, 107250 (2021). ISSN 0360-8352. https://doi.org/10.1016/j.cie.2021.107250
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Appendix
Appendix
Statistics and Box-Whisker Plot for 6 × 10 Datasets
Statistics and Box-Whisker Plot for 16 × 30 Datasets
Statistics and Box-Whisker Plot for 18 × 34 Datasets
Statistics and Box-Whisker Plot for 20 × 38 Datasets
Statistics and Box-Whisker Plot for all Datasets
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this chapter
Cite this chapter
Jaradat, G.M. (2022). Elitist-Ant System Metaheuristic for ITC 2021—Sports Timetabling. In: Houssein, E.H., Abd Elaziz, M., Oliva, D., Abualigah, L. (eds) Integrating Meta-Heuristics and Machine Learning for Real-World Optimization Problems. Studies in Computational Intelligence, vol 1038. Springer, Cham. https://doi.org/10.1007/978-3-030-99079-4_3
Download citation
DOI: https://doi.org/10.1007/978-3-030-99079-4_3
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-99078-7
Online ISBN: 978-3-030-99079-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)