Geração automática de horário escolar com algoritmo genético

  • Rodrigo Fontes Cruz Federal Institute of Sergipe
  • Gilson Pereira dos Santos Júnior Federal Institute of Sergipe
  • Lauro Barreto Fontes Federal Institute of Sergipe
  • Marília dos Anjos Santos Federal Institute of Sergipe
  • Brunna Lorenna Celestino da Silva Federal Institute of Sergipe

Resumo

Geração de horários escolares é uma tarefa complexa, custosa, geralmente manual e repetida periodicamente. O objetivo é alocar docentes às disciplinas considerando os recursos, os aspectos pedagógicos e organizacionais da instituição. No Xis, durante a execução deste trabalho, em 2016, a instituição possuía 10 cursos ofertados e mais de 1100 alunos matriculados. Neste cenário, 83% dos coordenadores gastavam entre 7 e 30 dias para criar os horários. Diante da problemática, foi desenvolvido um algoritmo genético para geração automática de horário. Um experimento 2k Fatorial foi executado para configurar os operadores genéticos. Constatou-se que a seleção dos melhores, em uma população de 4000 indivíduos durante 200 gerações e mutação de 3%, maximizou a aptidão. Esta configuração gerou os horários de um curso superior em 150 segundos e obteve 63% de aceitação na avaliação. Isso demonstra que é possível gerar horários rapidamente e atender às restrições.

Referências

ALMEIDA, M. W. de S. Utilização de algoritmos genéticos para montagem de horários acadêmicos com foco na blocagem de horários. 2015. 157 f. Trabalho de Conclusão de Curso (Bacharelado em Sistemas de Informação) - Universidade Federal do Rio Grande do Norte, Caicó. 2015.

COLORNI, Alberto; DORIGO, Marco; MANIEZZO, Vittorio. Genetic algorithms and highly constrained problems: The time-table case. In: International Conference on Parallel Problem Solving from Nature. Springer, Berlin, Heidelberg, 1990. p. 55-59.

COLORNI, Alberto; DORIGO, Marco; MANIEZZO, Vittorio. Metaheuristics for high school timetabling. Computational optimization and applications, v. 9, n. 3, p. 275-298, 1998.

FUCILINI, T. P.; Maruani, E.; Rebonatto, M. T. Timetabling com algoritmos genéticos: resultados, restrições e exploração do paralelismo. HÍFEN, v. 32, n. 62, 2008.

HAMAWAKI, C. D. L. Geração automática de grade horária usando algoritmos genéticos: o caso da Faculdade de Engenharia Elétrica da UFU. 2005. 104 f. Dissertação (Mestrado em Engenharias) - Universidade Federal de Uberlândia, Uberlândia, 2005.

LINDEN, R. Algoritmos genéticos. 3 ed. Rio de Janeiro: Editora Ciência Moderna Ltda., 2012.

MEDEIROS, G. F de; KRIPKA, M. Algumas aplicações de métodos heurísticos na otimização de estruturas. Revista CIATEC-UPF, v. 4, n. 1, p. 19-32, 2012.

MEFFERT, K.; ROTSTAN, N.; KNOWLES, C.; SANGIORGI, U. Jgap-java genetic algorithms and genetic programming package. URL: http://jgap. sf. net, 2012. Acesso em 20 de março de 2018.

NUNES, R. de S.; GUIMARAES, N. C.; CARVALHO, C. L. de. Planejamento de grade de horário em uma universidade brasileira usando algoritmos genéticos. In: Proceedings of the X Encontro Nacional de Inteligência Artificial e Computacional (ENIAC). Fortaleza-CE, Brazil, 2013.

PINHO, A. F. de; MONTEVECHI, J. A. B.; MARINS, F. A. S. Análise da aplicação de projeto de experimentos nos parâmetros dos algoritmos genéticos. Sistemas & Gestão, v. 2, n. 3, p. 319-331, 2009.

SCHAERF, A. A survey of automated timetabling. Artificial intelligence review, v. 13, n. 2, p. 87-127, 1999.

SOCHA, K.; SAMPELS, M.; MANFRIN, M. Ant algorithms for the university course timetabling problem with regard to the state-of-the-art. In: Workshops on Applications of Evolutionary Computation. Springer, Berlin, Heidelberg, 2003. p. 334-345.

SOUSA, V. N. de; MORETTI, A. C.; PODESTÁ, V. A. de. Programação da grade de horário em escolas de ensino fundamental e médio. Pesquisa Operacional, v. 28, n. 3, p. 399-421, 2008.

VIEIRA, F.; MACEDO, H. Sistema de alocação de horários de cursos universitários: um estudo de caso no departamento de computação da Universidade Federal de Sergipe. Scientia Plena, v. 7, n. 3, 2011.

Publicado
2019-12-17
Seção
ARTIGOS