Métodos de busca heurística para problemas de programação de horários modelados em XHSTT.

Abstract

O Problema da Programação de Horários Escolares é alvo de diversas pesquisas em Pesquisa Operacional e Inteligência Artificial devido a sua dificuldade de resolução e import^ancia prática. Uma solução para esse problema consiste basicamente na alocação de aulas a horários e na alocação dos recursos para essas aulas. Essa alocação deve atender a várias restrições especificadas a priori. O presente trabalho considera a solução do problema proposto pela Third Interntional Timetabling Competition (ITC2011), a qual inclui um amplo conjunto de inst^ancias originadas de diversas instituições educacionais ao redor do mundo. O presente trabalho prop~oe diversas técnicas de busca local para solucionar o problema. O formato de especificação de inst^ancias considerado foi o XHSTT, permitindo que qualquer inst^ancia especificada no referido formato possa ser manipulada pelos algoritmos propostos. Uma característica estrutural importante da nossa abordagem é o uso da plataforma KHE para gerar soluções iniciais, combinada com uma abordagem de busca multi-vizinhança. Os resultados obtidos incluem o desenvolvimento do algoritmo vencedor da competição. Fomos ainda capazes de encontrar soluções factíveis para treze de dezoito inst^ancias e melhorar quinze de dezesseis melhores soluções conhecidas