Algoritmos Simulated Annealing e Grasp para o planejamento de aulas de um departamento

  • Alexandre Xavier Martins Universidade Federal de Ouro Preto
  • Raphael Reis Mauro de Castro Universidade Federal de Ouro Preto
  • Marcone Jamilson Freitas Souza Universidade Federal de Ouro Preto
Palavras-chave: Prgramação de horários em escolas, simulated annealing, GRASP

Resumo

Este trabalho trata do problema de programação de horários em escolas. Dada sua natureza combinatória, ele é resolvido por meio de dois algoritmos metaeurísticos, um baseado em Simulated Annealing e outro em GRASP Ambos possuem parâmetros auto-adaptativos, dispensando, assim, a calibragem destes. Para testá-los são utilizados dados reais do departamento de uma universidade. São apresentados resultados computacionais, comparando-se as soluções produzidas pelos algoritmos propostos com aquelas geradas manualmente pela instituição de ensino. Os resultados obtidos mostram a eficiência dos métodos desenvolvidos perante as soluções manuais e a superioridade do Simulated Annealing, em comparação com o GRASP para as instâncias tratadas.