Adaptive Learning Modified Great Deluge Hyper-Heuristics
DOI:
https://doi.org/10.47839/ijc.23.2.3549Keywords:
Combinatorial Optimization, Sport Scheduling, Adaptive Learning Modified Great Deluge, Hyper-HeuristicsAbstract
The International Timetabling Competition (ITC) 2021 focuses on sports scheduling, a domain intricately connected to optimizing combinatorics problems. Within the framework of the ITC 2021 challenge, a crucial task is to precisely allocate matches to their designated time slots. Addressing this challenge involves the utilization of the Adaptive Learning Modified Great Deluge (ALMGD) algorithm, which belongs to the realm of hyper-heuristics. This algorithm represents an evolutionary step from the foundational great deluge algorithm, incorporating an acceptance mechanism intricately woven with self-adaptive learning. To assess its efficacy, the performance of the ALMGD algorithm is scrutinized through a comparative analysis with the hill climbing and great deluge algorithms. As a result, the proposed algorithm can produce a solution that is superior to the comparison algorithm. The modified great deluge algorithm can reduce the penalty by 36%, while the hill climbing algorithm can only reduce the penalty by 29% and the great deluge algorithm reaches 34%.
References
L. Zeng and S. Mizuno, “On the generalized mirrored scheme for double round robin tournaments in sports scheduling,” Asia-Pacific J. Oper. Res., vol. 30, no. 3, pp. 1–16, 2013, https://doi.org/10.1142/S0217595913400083.
M. A. Trick, “Sports scheduling,” Springer Optim. Its Appl., vol. 45, pp. 489–508, 2011, https://doi.org/10.1007/978-1-4419-1644-0_15.
T. Januario, S. Urrutia, C. C. Ribeiro, and D. De Werra, “Edge coloring: A natural model for sports scheduling,” Eur. J. Oper. Res., vol. 254, no. 1, pp. 1–8, 2016, https://doi.org/10.1016/j.ejor.2016.03.038.
A. Daliri, M. Alimoradi, M. Zabihimayvan, and R. Sadeghi, “World Hyper-Heuristic: A novel reinforcement learning approach for dynamic exploration and exploitation,” Expert Syst. Appl., vol. 244, p. 122931, 2024, https://doi.org/10.1016/j.eswa.2023.122931.
D. Van Bulck and D. Goossens, “Handling fairness issues in time-relaxed tournaments with availability constraints,” Comput. Oper. Res., vol. 115, p. 104856, 2020, https://doi.org/10.1016/j.cor.2019.104856.
X. Yi, D. Goossens, and F. T. Nobibon, “Proactive and reactive strategies for football league timetabling,” Eur. J. Oper. Res., vol. 282, no. 2, pp. 772–785, 2020, https://doi.org/10.1016/j.ejor.2019.09.038.
D. Van Bulck and D. Goossens, “A traditional Benders’ approach to sports timetabling,” Eur. J. Oper. Res., vol. 307, no. 2, pp. 813–826, 2023, https://doi.org/10.1016/j.ejor.2022.10.044.
S. Knust, “Scheduling non-professional table-tennis leagues,” Eur. J. Oper. Res., vol. 200, no. 2, pp. 358–367, 2010, https://doi.org/10.1016/j.ejor.2009.01.015.
G. Durán, S. Durán, J. Marenco, F. Mascialino, and P. A. Rey, “Scheduling Argentina’s professional basketball leagues: A variation on the Travelling Tournament Problem,” Eur. J. Oper. Res., vol. 275, no. 3, pp. 1126–1138, 2019, https://doi.org/10.1016/j.ejor.2018.12.018.
M. B. Wright, “Scheduling fixtures for Basketball New Zealand,” Comput. Oper. Res., vol. 33, no. 7, pp. 1875–1893, 2006, https://doi.org/10.1016/j.cor.2004.09.024.
F.-C. Yang, “NBA Sports Game Scheduling Problem and GA-Based Solver,” Proceedings of the 2017 International Conference on Industrial Engineering, Management Science and Application (ICIMSA), 2017, pp. 1–5. https://doi.org/10.1109/ICIMSA.2017.7985598.
C. C. Ribeiro and S. Urrutia, “Heuristics for the mirrored traveling tournament problem,” Eur. J. Oper. Res., vol. 179, no. 3, pp. 775–787, 2007, https://doi.org/10.1016/j.ejor.2005.03.061.
M. Khelifa, D. Boughaci, and E. Aïmeur, “Evolutionary Harmony Search Algorithm for Sport Scheduling Problem,” In: Thanh Nguyen, N., Kowalczyk, R. (eds) Transactions on Computational Collective Intelligence XXX. Lecture Notes in Computer Science, 2018, vol 11120, pp. 93–117. Springer, Cham. https://doi.org/10.1007/978-3-319-99810-7_5.
R. Lewis and J. Thompson, “On the application of graph colouring techniques in round-robin sports scheduling,” Comput. Oper. Res., vol. 38, no. 1, pp. 190–204, 2011, https://doi.org/10.1016/j.cor.2010.04.012.
D. Van Bulck and D. Goossens, “The international timetabling competition on sports timetabling (ITC2021),” Eur. J. Oper. Res., vol. 308, no. 3, pp. 1249–1267, 2023, https://doi.org/10.1016/j.ejor.2022.11.046.
D. Van Bulck, D. Goossens, J. Schönberger, and M. Guajardo, “RobinX: A three-field classification and unified data format for round-robin sports timetabling,” Eur. J. Oper. Res., vol. 280, no. 2, pp. 568–580, 2020, https://doi.org/10.1016/j.ejor.2019.07.023.
P. Kostuch, “The university course timetabling problem with a three-phase approach,” Proceedings of the International Conference on the Practice and Theory of Automated Timetabling, 2004, pp. 109–125. https://doi.org/10.1007/11593577_7.
T. Müller, “ITC2007 solver description: A hybrid approach,” Proceedings of the 7th Int. Conf. Pract. Theory Autom. Timetabling, PATAT 2008, pp. 1–15, 2008. https://doi.org/10.1007/s10479-009-0644-y.
G. H. G. Fonseca, H. G. Santos, T. A. M. Toffolo, S. S. Brito, and M. J. F. Souza, “A SA-ILS approach for the High School Timetabling Problem,” Proceedings of the PATAT 2012 9th Int. Conf. Pract. Theory Autom. Timetabling, August 2012, pp. 493–496.
G. Dueck, “New optimization heuristics the great deluge algorithm and the record-to-record travel,” J. Comput. Phys., vol. 104, pp. 86–92, 1993. https://doi.org/10.1006/jcph.1993.1010.
E. K. Burke and Y. Bykov, “An adaptive flex-deluge approach to university exam timetabling,” INFORMS J. Comput., vol. 28, no. 4, pp. 781–794, 2016, https://doi.org/10.1287/ijoc.2015.0680.
V. Ravi, “Optimization of complex system reliability by a modified great deluge algorithm,” Asia-Pacific J. Oper. Res., vol. 21, no. 4, pp. 487–497, 2004, https://doi.org/10.1142/S0217595904000357.
E. K. Burke and Y. Bykov, “The late acceptance Hill-Climbing heuristic,” Eur. J. Oper. Res., vol. 258, no. 1, pp. 70–78, 2017, https://doi.org/10.1016/j.ejor.2016.07.012.
Y. Wang, B. Li, T. Weise, J. Wang, B. Yuan, and Q. Tian, “Self-adaptive learning based particle swarm optimization,” Inf. Sci. (Ny)., vol. 181, no. 20, pp. 4515–4538, 2011, https://doi.org/10.1016/j.ins.2010.07.013.
Q. K. Pan, M. Fatih Tasgetiren, P. N. Suganthan, and T. J. Chua, “A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem,” Inf. Sci. (Ny)., vol. 181, no. 12, pp. 2455–2468, 2011, https://doi.org/10.1016/j.ins.2009.12.025.
A. Muklason, “Automatic Exam Scheduler Solver With Maximal Clique Algorithm and Hyper-heuristics,” Semin. Nas. Technol. Information, Commun. and Ind. 9, pp. 18–19, 2017. (in Indonesian).
T. Dokeroglu, T. Kucukyilmaz, and E.-G. Talbi, “Hyper-heuristics: A survey and taxonomy,” Comput. Ind. Eng., vol. 187, p. 109815, 2024, https://doi.org/10.1016/j.cie.2023.109815.
A. Muklason, “Hyper-heuristics and fairness in examination timetabling problems,” no. December, pp. 1–12, 2017, [Online]. Available: http://eprints.nottingham.ac.uk/42912/.
R. R. Hutama and A. Muklason, “Formation of Initial Solutions for the 2021 International Timetabling Competition,” J. Tech. Inform. and Sys. Inf., vol. 8, no. 4, pp. 1939–1944, 2021, https://doi.org/10.35957/jatisi.v8i4.1155. (in Indonesian).
L. Di Gaspero and A. Schaerf, “A composite-neighborhood tabu search approach to the traveling tournament problem,” J. Heuristics, vol. 13, no. 2, pp. 189–207, 2007, https://doi.org/10.1007/s10732-006-9007-x.
Downloads
Published
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.
