Resumo: Esta dissertação aborda o problema de horários em escolas. Este é um problema combinatório clássico que possui muitas variantes. Ele é NP - Completo e geralmente é resolvido por métodos heurísticos. O trabalho apresentado propõe algoritmos de busca local para resolver uma variante do problema originado de treze escolas públicas de ensino médio brasileiras. No trabalho é realizado um estudo comparativo entre dois operadores de vizinhança propostos para o problema e um operador da literatura. Os algoritmos propostos implementam estes operadores e são baseados nas metaherísticas ILS e VNS. Experimentos computacionais foram realizados aplicando estes algoritmos para resolver instâncias de uma base de dados extraída de casos reais destas escolas. Os resultados obtidos mostraram que algoritmos de busca local baseada nos operadores propostos são mais eficientes que algoritmos de busca local baseada no operador da literatura. Além disso, foi observado que os algoritmos ILS e VNS usando combinações de heurísticas de busca local baseadas nos operadores propostos produziram os melhores resultados e que estes resultados são satisfatórios.
Abstract: This paper addresses the high school timetabling problem. This is a classical problem and has many combinatorial variations. It is NP-Complete and is usually tackled using heuristic methods. In this work we propose local search algorithms to solve a variant of the problem faced on thirteen brazilian public high schools. The work performs a comparative study among two proposed neighborhood operators and an operator from literature. The proposed algorithms are based on metaherísticas ILS and VNS and incorporates these operators. We have performed computational experiments by applying these algorithms to solve real instances of a database we have taken from these schools. The results have shown that local search algorithms using our operators are more efficient than algorithms using the literature operator. Furthermore, we have observed that ILS and VNS algorithms using combinations of local search heuristics based in our operators have produced the best results and these results are satisfactory to the problem. |