Uma abordagem de busca local utilizando GVNS para solução de problemas de programação de horários em escolas
Ulisses Rezende Teixeira1; Marcone Jamilson Freitas Souza2; Sérgio Ricardo de Souza1
1 CEFET-MG; 2 UFOP
doi:10.20906/CPS/CILAMCE2017-1240
Resumo
O objetivo deste trabalho é apresentar uma alternativa eficiente de solução para problemas de programação de horários em escolas utilizando uma abordagem de busca local com o método General Variable Neighborhood Search (GVNS). O algoritmo implementado usa a biblioteca KHE e uma estratégia de busca de ótimos locais através do método VND. O espaço de soluções é explorado utilizando os movimentos de troca de eventos, troca de recursos, troca de blocos de recursos, mudança de horários e de recursos, mudança de horários de eventos e cadeias Kempe. O algoritmo foi testado em problemas-teste da Competição Internacional de Programação de Horários ocorrida em 2011 e seus resultados foram comparados com aqueles gerados pelo algoritmo Goal Solver, vencedor da competição.
Palavras-chave: Programação de Horários Escolares; General Variable Neighborhood Search ; Metaheurísticas