A meta-heurística por colônia de formigas pelo algoritmo minmaxant system aplicada ao problema de quadro de horários escolar

Abstract

ResumoA geração de quadro de horários nas escolas é um problema clássico de otimização combinatória que se constitui em um fator crítico de qualidade para qualquer instituição de ensino. O software de gestão escolar i-Educar é um projeto feito em comunidade, utilizado por diversos municípios em todo o Brasil para auxílio na gestão de escolas públicas. Considerando a complexidade na elaboração de grade horária de forma manual e a dificuldade de obtenção de soluções ótimas tem tempo computacional aceitável, o presente trabalho propõe o uso da meta-heurística de otimização por colônia de formigas para gerar quadros de horários com dados do software de gestão escolar i-Educar. Para isto, foi implementada uma API que permite ler os dados do i-Educar, e importar estes para a base de dados do protótipo. Dentre os métodos de colônia de formigas, empregou-se o algoritmo Min-Max Ant System para geração da grade horária. Os resultados foram positivos, podendo ser gerado grade horária de qualidade com tempo satisfatório, afirmando então, que método MMAS com busca local é um bom candidato para resolução de problemas de otimização combinatória, podendo gerar bons resultados e com poucas violações das restrições difíceis.