Portal de Administração de Conferências - CEFET-MG, 15ª Semana de Ciência & Tecnologia 2019 - CEFET-MG

Tamanho da fonte: 
ABORDAGEM HEURÍSTICA PARA O PROBLEMA DA PROGRAMAÇÃO DE HORÁRIO ESCOLAR
Rosana Tonetti Massahud, Silfarley Gonçalves

Última alteração: 2019-08-30

Resumo


O problema da programação de horário é um problema de otimização combinatória e consiste na definição do quadro de horário de cursos e na alocação de salas de aula respeitando-se um conjunto de restrições, tais como a capacidade das salas, demandas das turmas, indisponibilidades dos professores etc. É um problema complexo, considerado em muitos trabalhos NP-Completo. Este trabalho consistiu na elaboração do horário escolar para um caso real numa instituição de ensino. Considerou-se apenas a distribuição das disciplinas do curso de graduação e para o período noturno. A implementação do programa foi dividida em duas etapas: a elaboração da solução inicial e a utilização de uma meta heurística para melhoria da qualidade da solução. A construção da solução inicial baseou-se no algoritmo de coloração de grafos proposto por Welsh e Powell, com adaptações para o caso estudado. A meta heurística utilizada na segunda fase foi o Simulated Annealing, o qual permite escapar de ótimos locais. As simulações foram consideradas satisfatórias para a complexidade do problema. A solução final revelou-se muito próxima da solução inicial, provavelmente devido as muitas restrições nos dados de entrada. Apesar de complexo, o projeto foi importante para introdução ao estudo de problemas de otimização combinatória. Para o programa gerado, um trabalho futuro é a implementação de uma interface gráfica para melhor aproveitamento do material desenvolvido.

Palavras-chave


Programação de horário. Otimização. Heurística.