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, in comparison with a previously proposed TS found in literature, show that the proposed method produces better solutions for all instances, as well as observed increased speed in the production of good quality solutions.
['Haroldo Gambini Santos', 'Luiz Satoru Ochi', 'Marcone Jamilson Freitas Souza']
An Efficient Tabu Search Heuristic for the School Timetabling Problem