PROBLEMA DE ALOCAÇÃO DE PROFESSORES DO ENSINO MÉDIO CONSIDERANDO RESTRIÇÕES DE INTERVALO
Alisson Segatto de Souza1; José Eduardo Pécora Junior1; Adriana Alves Fressato1; Gustavo Valentim Loch1
1 Universidade Federal do Paraná
doi:10.20906/CPS/CILAMCE2017-1191
Resumo
O problema de construir uma grade horária escolar de ensino médio (High School Timetabling - HSTT) consiste em reunir professores, classes e salas em um determinado período, construindo a escala semanal de uma instituição de ensino. O grande número de variáveis e restrições tornam a resolução manual deste problema muito difícil. Além disso, para instâncias grandes não é possível encontrar boas soluções em um tempo computacional viável via métodos exatos, tornando necessária a utilização de heurísticas. Neste trabalho, usaremos a heurística de fix-and-optimize para resolver um problema variante do HSTT que busca minimizar os períodos de ociosidade e gerar o maior número de aulas geminadas possíveis, considerando os intervalos escolar no processo. Também apresentamos duas novas abordagens ao problema: na primeira adiciona-se uma nova restrição ao modelo diminuindo a área de busca do algoritmo e na segunda modificamos a heurística de fix-and-optimize para diminuir o número de vizinhanças exploradas. As duas novas abordagens foram capazes de obter melhores soluções em menor tempo computacional para as cinco instancias estudadas.
Palavras-chave: Timetabling; Fix-And-Optimize; Programação Linear Inteira Mista