Programação de Horários Escolares Através de SAT e Metaheurísticas

Published in X Simpósio Brasileiro de Inteligência Computacional, 2011

O Problema da Programação de Horários Escolares (PPHE) é classificado como NP-Difícil e heurísticas para sua solução são alvo de diversas pesquisas na área de computação, matemática e pesquisa operacional. Normalmente, o problema é resolvido através de metaheurísticas como Algoritmos Genéticos, Simulated Annealing e GRASP. O presente trabalho propõe uma abordagem alternativa. Pretende-se reduzir do problema ao problema da Satisfazibilidade Proposicional (SAT) e resolvê- lo usando um resolvedor SAT para geração de uma solução inicial. Como não é viável tratar todos os requisitos PPHE através de satisfazibilidade, posteriormente, aplicar-se-á as metaheurísticas Busca Tabu e Simulated Annealing para otimização da solução obtida. Por fim serão apresentados os resultados de cada algoritmos e uma comparação com outro trabalho do gênero.

Download paper here