Algoritmo ALNS Aplicado ao Problema de Tabela-Horário para Cursos de Computação da UFES
Resumo
Neste trabalho é abordado o Problema de Tabela-Horário de Universidades no contexto dos cursos da área de computação da UFES. Além da formulação como um problema de otimização, um algoritmo resultante da adaptação da meta-heurística Adaptive Large Neighborhood Search, é proposto para resolvê-lo. O objetivo é encontrar uma solução viável, ou seja, que respeite as restrições que não podem ser violadas, e que minimize as violações das restrições cuja satisfação é desejável. Com o propósito de validar o algoritmo proposto foi utilizado nos experimentos computacionais, um conjunto instâncias com dados reais para o problema. Os resultados obtidos demonstram que o algoritmo proposto encontra soluções, em média, 88% melhores que as soluções geradas atualmente.Referências
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.
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.
Publicado
17/10/2024
Como Citar
LIMA, Danilo Erler; MACIEL, Arthur Roberto Barboza; BOERES, Maria Claudia Silva; KAMPKE, Edmar Hell.
Algoritmo ALNS Aplicado ao Problema de Tabela-Horário para Cursos de Computação da UFES. In: ESCOLA REGIONAL DE INFORMÁTICA DO ESPÍRITO SANTO (ERI-ES), 9. , 2024, Vitória/ES.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2024
.
p. 51-60.
DOI: https://doi.org/10.5753/eries.2024.244394.
