O problema de geração de horários: um foco na eliminação de janelas e aulas isoladas

Abstract

The Timetabling problem consists in scheduling a set of classes to a fixed number of time slots subject to a great number of constraints. The manual problem solution is painful and slow and many times the results aren’t satisfactory. Even to find a feasible timetable solution is NP-hard. Consequently, the use of exact methods is not appropriate to high orders instances. Many exact methods and heuristics have been proposed to approach the timetabling problem, however, the main problem from these methods have been to handle efficiently many real world constraints and objectives. From the recent approaches, the meta-heuristics highlight to find good quality results in reasonable execution time. Tabu Search, Simulated Annealing and Genetic Algorithm are the main meta-heuristic methods utilized. However, important constraints and objectives have been neglected, making hard the use of these solutions in the real world. In this paper, two important objectives are considered: the idle time windows and isolated classes minimization, possibiliting a timetable with higher quality of accepting. The generalization proposed in this paper has demonstrated very important in the solution for two studied case schools analyzed. In context, the real utilization and acceptability of the produced solutions show the generalization importance and current proposal importance.