Avaliação de um Algoritmo Híbrido na Geração de Soluções para o Problema de Horários de Cursos Universitários
Resumo
O problema de horário de curso baseado em currículo é um problema clássico de otimização combinatória. Diversas pesquisas foram realizadas nas últimas décadas com o propósito de investigar o desempenho de uma variedade de metodologias. O objetivo deste trabalho é avaliar uma abordagem híbrida, composta com Biased Random-Key Genetic Algorithm e Simulated Annealing, no conjunto de instâncias do ITC-2007. Os resultados mostram que o algoritmo proposto é capaz de produzir soluções viáveis de qualidade podendo competir com trabalhos da literatura.
Palavras-chave:
Problema de Horários de Cursos baseado em Currículo, Algoritmo Híbrido, Algoritmo Genético de Chaves Aleatórias Viciadas, Recozimento Simulado
Referências
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.
Publicado
31/07/2022
Como Citar
SENA, Daniela C.; LIBERALINO, Carlos H. P.; LIMA JÚNIOR, Francisco Chagas de.
Avaliação de um Algoritmo Híbrido na Geração de Soluções para o Problema de Horários de Cursos Universitários. In: SEMINÁRIO INTEGRADO DE SOFTWARE E HARDWARE (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.
