Título: Programação De Horários Escolares Através De SAT E Metaheurísticas
Autores: Fonseca, George H. G.; Ribeiro, Rodrigo G.; Martins, Flávio V. Cruzeiro
Resumo: 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.
Palavras-chave: Programação de Horários Escolares; Satisfazibilidade Proposicional; Busca Tabu; Simulated Annealing
Páginas: 8
Código DOI: 10.21528/CBIC2011-11.2
Artigo em pdf: st_11.2.pdf
Arquivo BibTex: st_11.2.bib