An Efficient Tabu Search Heuristic for the School Timetabling Problem

The School Timetabling Problem (STP) regards the weekly scheduling of encounters between teachers and classes. Since this scheduling must satisfy organizational, pedagogical and personal costs, this problem is recognized as a very difficult combinatorial optimization problem. This work presents a new Tabu Search (TS) heuristic for STP. Two different memory based diversification strategies are presented. Computational experiments with real world instances, comparing with a previously proposed TS found in the literature, show that the proposed method produces better solutions for all instances, as well faster times are observed in the production of good quality solutions