Evaluation of a Hybrid Algorithm in the Generation of Solutions for the University Course Timetabling Problem
Abstract
The curriculum-based course timetabling problem is a classic combinatorial optimization problem. Several researches were carried out in the last decades with the purpose of investigating the performance of a variety of methodologies. The objective of this work is to evaluate a hybrid approach, composed with Biased Random-Key Genetic Algorithm and Simulated Annealing, in the set of ITC-2007 instances. The results show that the proposed algorithm is capable of producing viable quality solutions and can compete with works in the literature.
Keywords:
Curriculum-Based Course Timetabling Problem, Hybrid Algorithm, Biased Random-Key Genetic Algorithm, Simulated Annealing
References
Abdullah, S., Turabieh, H., McCollum, B., and McMullan, P. (2012). A hybrid metaheuristic approach to the university course timetabling problem. Journal of Heuristics, 18(1):1–23.
Akkan, C. and Gülcü, A. (2018). A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem. Computers Operations Research, 90:22–32.
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6(2):154–160.
Bellio, R., Ceschia, S., Di Gaspero, L., Schaerf, A., and Urli, T. (2016). Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem. Computers & Operations Research, 65:83–92.
Fajrin, A. and Fatichah, C. (2020). Multi-parent order crossover mechanism of genetic algorithm for minimizing violation of soft constraint on course timetabling problem. Register: Jurnal Ilmiah Teknologi Sistem Informasi, 6(1):43–51.
Feutrier, T., Kessaci, M.-E., and Veerapen, N. (2021). Investigating the landscape of a hybrid local search approach for a timetabling problem. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’21, page 1665–1673, New York, NY, USA. Association for Computing Machinery.
Gonçalves, J. F. and Resende, M. G. C. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Gülcü, A. and Akkan, C. (2020). Robust university course timetabling problem subject to single and multiple disruptions. European Journal of Operational Research, 283(2):630–646.
Jaengchuea, S. and Lohpetch, D. (2015). A hybrid genetic algorithm with local search and tabu search approaches for solving the post enrolment based course timetabling problem: Outperforming guided search genetic algorithm. In 2015 7th International Conference on Information Technology and Electrical Engineering (ICITEE), pages 29–34.
Kiefer, A., Hartl, R. F., and Schnell, A. (2017). Adaptive large neighborhood search for the curriculum-based course timetabling problem. Annals of Operations Research, 252(2):255–282.
Lü, Z. and Hao, J.-K. (2010). Adaptive tabu search for course timetabling. European journal of operational research, 200(1):235–244.
Monteiro, R. C., Kampke, E. H., Bissoli, D. d. C., and Mauri, G. R. (2017). Algoritmo híbrido iterated local search e simulated annealing para o problema de tabela-horário de universidades. Anais do XLIX Simpósio Brasileiro de Pesquisa Operacional, pages 1867–1878.
Müller, T. (2009). Itc2007 solver description: a hybrid approach. Annals of Operations Research, 172(1):429–446.
Segatto, E. d. A. (2017). Um estudo de estruturas de vizinhanças no grasp aplicado ao problema de tabela-horário para universidades. Master’s thesis, Universidade Federal do Espírito Santo, Vitória ES.
Song, T., Chen, M., Xu, Y., Wang, D., Song, X., and Tang, X. (2021). Competitionguided multi-neighborhood local search algorithm for the university course timetabling problem. Applied Soft Computing, 110:107624.
Susan, S. and Bhutani, A. (2019). A novel memetic algorithm incorporating greedy stochastic local search mutation for course scheduling. In 2019 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC), pages 254–259.
Akkan, C. and Gülcü, A. (2018). A bi-criteria hybrid genetic algorithm with robustness objective for the course timetabling problem. Computers Operations Research, 90:22–32.
Bean, J. C. (1994). Genetic algorithms and random keys for sequencing and optimization. ORSA Journal on Computing, 6(2):154–160.
Bellio, R., Ceschia, S., Di Gaspero, L., Schaerf, A., and Urli, T. (2016). Feature-based tuning of simulated annealing applied to the curriculum-based course timetabling problem. Computers & Operations Research, 65:83–92.
Fajrin, A. and Fatichah, C. (2020). Multi-parent order crossover mechanism of genetic algorithm for minimizing violation of soft constraint on course timetabling problem. Register: Jurnal Ilmiah Teknologi Sistem Informasi, 6(1):43–51.
Feutrier, T., Kessaci, M.-E., and Veerapen, N. (2021). Investigating the landscape of a hybrid local search approach for a timetabling problem. In Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO ’21, page 1665–1673, New York, NY, USA. Association for Computing Machinery.
Gonçalves, J. F. and Resende, M. G. C. (2011). Biased random-key genetic algorithms for combinatorial optimization. Journal of Heuristics, 17(5):487–525.
Gülcü, A. and Akkan, C. (2020). Robust university course timetabling problem subject to single and multiple disruptions. European Journal of Operational Research, 283(2):630–646.
Jaengchuea, S. and Lohpetch, D. (2015). A hybrid genetic algorithm with local search and tabu search approaches for solving the post enrolment based course timetabling problem: Outperforming guided search genetic algorithm. In 2015 7th International Conference on Information Technology and Electrical Engineering (ICITEE), pages 29–34.
Kiefer, A., Hartl, R. F., and Schnell, A. (2017). Adaptive large neighborhood search for the curriculum-based course timetabling problem. Annals of Operations Research, 252(2):255–282.
Lü, Z. and Hao, J.-K. (2010). Adaptive tabu search for course timetabling. European journal of operational research, 200(1):235–244.
Monteiro, R. C., Kampke, E. H., Bissoli, D. d. C., and Mauri, G. R. (2017). Algoritmo híbrido iterated local search e simulated annealing para o problema de tabela-horário de universidades. Anais do XLIX Simpósio Brasileiro de Pesquisa Operacional, pages 1867–1878.
Müller, T. (2009). Itc2007 solver description: a hybrid approach. Annals of Operations Research, 172(1):429–446.
Segatto, E. d. A. (2017). Um estudo de estruturas de vizinhanças no grasp aplicado ao problema de tabela-horário para universidades. Master’s thesis, Universidade Federal do Espírito Santo, Vitória ES.
Song, T., Chen, M., Xu, Y., Wang, D., Song, X., and Tang, X. (2021). Competitionguided multi-neighborhood local search algorithm for the university course timetabling problem. Applied Soft Computing, 110:107624.
Susan, S. and Bhutani, A. (2019). A novel memetic algorithm incorporating greedy stochastic local search mutation for course scheduling. In 2019 IEEE International Conference on Computational Science and Engineering (CSE) and IEEE International Conference on Embedded and Ubiquitous Computing (EUC), pages 254–259.
Published
2022-07-31
How to Cite
SENA, Daniela C.; LIBERALINO, Carlos H. P.; LIMA JÚNIOR, Francisco Chagas de.
Evaluation of a Hybrid Algorithm in the Generation of Solutions for the University Course Timetabling Problem. In: INTEGRATED SOFTWARE AND HARDWARE SEMINAR (SEMISH), 49. , 2022, Niterói.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2022
.
p. 218-223.
ISSN 2595-6205.
DOI: https://doi.org/10.5753/semish.2022.223191.
