Algoritmos heurísticos para problemas de definição de horários escolares

Resumo

Este projeto visa o desenvolvimento de algoritmos heurísticos eficientes e eficazes para resolver problemas de escalonamento de horários escolares, uma vez que a aplicabilidade de algoritmos exatos para tal finalidade é limitada. Inicialmente, pretende-se abordar o problema de horários em escolas de ensino médio devido a sua importância teórica e prática. Em um projeto de mestrado foram desenvolvidos dois novos operadores de vizinhança em larga escala, baseados em modelos de grafo, para algoritmos de busca local aplicados ao problema. Também foi construída uma base de dados com 102 instâncias de testes. Seis algoritmos baseados em ILS (Iterated Local Search) e três versões em VNS (Variable Neighborhood Search) incorporando os operadores desenvolvidos, foram implementados e testados na base de dados proposta e em uma segunda base de dados da literatura. Os resultados obtidos foram compatíveis com os melhores resultados conhecidos na literatura. Neste projeto pretende-se estender os métodos desenvolvidos de modo a aumentar a eficácia, flexibilidade e eficiência das abordagens. De maneira pragmática, pretende-se estudar operadores de vizinhança em larga escala baseados em modelos de programação inteira. Tais operadores serão combinados com metaheurísticas de busca local para desenvolver novos algoritmos para o problema. Também se pretende incorporar novos estudos de casos (instâncias) à base de dados existente, de modo que esta seja uma compilação ainda mais representativa de situações reais.