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

• Ano de defesa: 2013
• Autor(a) principal: Fonseca, George Henrique Godim da
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto.
• Palavras-chave em Português: Programação heurística; Otimização combinatória; Horários escolares
• Link de acesso: http://www.repositorio.ufop.br/handle/123456789/3056

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