Uma nova abordagem para a heurística fix-and-optimiza aplicada à escala de professores do ensino médio

Abstract

Resumo: Um dos maiores desafios enfrentados pelas instituições de ensino no início do ano letivo é a de distribuir as turmas e dias em que cada professor deverá atuar. Apesar de todo avanço computacional, a maioria das escolas ainda realiza a construção da grade escolar manualmente, tornando o trabalho demorado e envolvendo praticamente todo o corpo docente e pedagógico, secretaria e direção na busca de otimizar e satisfazer as preferências de seus professores. O problema de construir uma grade horária escolar de ensino médio (High School Timetabling - HSTT) consiste em reunir professores, turmas e salas em um determinado período, construindo a escala semanal da instituição de ensino. Para grandes escolas, mesmo utilizando softwares, não é possível encontrar boas soluções em um tempo computacional viável utilizando métodos exatos, tornando necessária a utilização de heurísticas. A heurística fix-and-optimize decompõe o problema original em subproblemas menores ao fixar grande parte das variáveis, gerando regiões de busca menores que podem ser facilmente exploradas por softwares de forma exata, encontrando ótimos locais para o problema. A maneira com que estas regiões são exploradas impactam na velocidade de convergência do algoritmo. Neste trabalho é apresentado dois modelos matemáticos de programação inteira mista para resolver cinco instâncias clássicas da literatura buscando diminuir o número de dias trabalhados pelos professores, eliminar períodos de ociosidade e aumentar o número de aulas geminadas tanto quanto possível. A heurística fix-and-optimize foi utilizada juntamente com cinco diferentes métodos de busca em vizinhança, com o objetivo de diminuir a complexidade do algoritmo e alcançar melhores resultados. Desta forma foram encontradas soluções superiores para duas das instâncias estudadas e igualando os resultados já conhecidos para as demais instâncias. Palavras Chaves: High School Timetabling, fix-and-optimize, heurística, busca em vizinhança.

Abstract: One of the biggest challenges faced by educational institutions at the beginning of the school year is to distribute the classes and days when each teacher should act. Despite all the computational advances, most schools still carry out the construction of the school grid manually, making the work time consuming and involving practically all the teaching and pedagogical staff, secretariat and direction in the search to optimize and satisfy the preferences of their teachers. The problem of building a high school timetable (HSTT) consists of bringing together teachers, classes and classrooms in a given period, building the weekly scale of the teaching institution. For grades schools, even using software, it is not possible to find good solutions in a viable computational time using exact methods, making it necessary to use heuristics. The fix-and-optimize heuristic decomposes the original problem into smaller subproblems by fixing a large number of variables, generating smaller search regions that can be easily exploited by software accurately, finding optimal locations for the problem. The way in which these regions are exploited impacts on the convergence speed of the algorithm. In this work two mathematical models of mixed integer programming are presented to solve five classic instances of literature aiming to reduce the number of days worked by teachers, eliminate periods of idleness and increase the number of twin classes as much as possible. The fix-and-optimize heuristic was used along with five different neighborhood search methods, in order to reduce the complexity of the algorithm and achieve better results. In this way superior solutions were found for two of the studied instances and matching the results already known to the other instances. Keywords: High School Timetabling, fix-and-optimize, heuristic, neighborhood search.