METAHEURISTICS FOR HIGH-SCHOOL TIMETABLING

In this paper we present the results of an investigation of the possib ilities offered by three well-known metaheuristic algorithms to solve the timetable problem, a multi-constrained, NP-hard, combinatorial opt imization problem with real-world applications. First, we present our model of the problem, including the definition of a hierarchical struc ture for the objective function, and of the neighborhood search operat ors which we apply to matrices representing timetables. Then we report about the outcomes of the utilization of the implemented systems to t he specific case of the generation of a school timetable. We compare t he results obtained by simulated annealing, tabu search and two versio ns, with and without local search, of the genetic algorithm. Our resul ts show that GA with local search and tabu search based on temporary p roblem relaxations both outperform simulated annealing and handmade ti metables.