ALNS Algorithm Applied to the Timetable Problem for UFES Computing Courses

• Danilo Erler Lima UFES
• Arthur Roberto Barboza Maciel UFES
• Maria Claudia Silva Boeres UFES
• Edmar Hell Kampke UFES

DOI: https://doi.org/10.5753/eries.2024.244394

Abstract

This paper addresses the University Timetabling Problem in the context of computer science courses at UFES. In addition to the formulation as an optimization problem, an algorithm resulting from the adaptation of the Adaptive Large Neighborhood Search metaheuristic is proposed to solve it. The objective is to find a feasible solution, which is one that respects the constraints that cannot be violated, and minimizes violations of the constraints whose satisfaction is desirable. In order to validate the proposed algorithm, a set of instances with real data for the problem was used in the computational experiments. The results obtained demonstrate that the proposed algorithm finds solutions, on average, 88% better than the solutions currently generated.

References

Babaei, H., Karimpour, J., and Hadidi, A. (2015). A survey of approaches for university course timetabling problem. Computers & Industrial Engineering, 86:43 – 59.

Costa, D. H. S., Coelho, I. M., and Pinto, P. E. D. (2017). Programaçao de horários e alocaçao de salas de aula no ime/uerj com simulated annealing e lahc. In Anais do XLIX SBPO, Rio de Janeiro-RJ. SOBRAPO.

Di Gaspero, L., McCollum, B., and Schaerf, A. (2007). The second international time-tabling competition (ITC-2007): Curriculum-based course timetabling (track 3). In Proceedings of The International Conference on Automated Planning and Scheduling, pages 1–5, Providence, Rhode Island, USA. ICAPS Incorporation.

Goldbarg, M. C. and Luna, H. P. L. (2005). Otimização Combinatória e programação linear: modelos e algoritmos. Elselvier, Rio de Janeiro, RJ, Brasil, 2 edition.

Kampke, E. H., Rocha, W. S., Boeres, M. C. S., and Rangel, M. C. (2015). A GRASP algorithm with path relinking for the university courses timetabling problem. In Proceeding Series of the Brazilian Society of Computational and Applied Mathematics, volume 3, pages 1081–1087, São Carlos, SP, Brasil. SBMAC.

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.

Moreira, L. V., Monteiro, R. C., Kampke, E. H., and Mauri, G. R. (2016). Meta-heurística GRASP para o Problema de Tabela-horário de Disciplinas do Departamento de Computação do CCA-UFES. In Anais do XLVIII Simpósio Brasileiro de Pesquisa Operacional, pages 2171–2182, Rio de Janeiro, RJ, Brasil. SOBRAPO.

Müller, T. (2009). ITC2007 solver description: a hybrid approach. Annals of Operations Research, 172(1):429–446.

Ropke, S. and Pisinger, D. (2006). An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows. Transportation science, 40(4):455–472.

Sales, E. S. (2015). Problema de alocação de salas e a otimização dos espaços no centro de tecnologia da ufsm. Mestrado em administração, Universidade Federal de Santa Maria.

Santos, H. G. and Souza, M. J. F. (2007). Programação de horários em instituições educacionais: formulações e algoritmos. XXXIX SBPO-Simpósio Brasileiro de Pesquisa Operacional, (1):2827–2882.

Schaerf, A. (1999). A survey of automated timetabling. Artificial Intelligence Review, 13(2):87–127.