A tabu search algorithm with efficient diversification strategy for high school timetabling problem
This addresses scheduling challenges for high schools, but appears incremental as it builds on existing tabu search methods.
The paper tackles the high school timetabling problem by developing a tabu search algorithm with a frequency-based diversification strategy, tested on real Iranian high school data, and shows it can effectively build acceptable timetables.
The school timetabling problem can be described as scheduling a set of lessons (combination of classes, teachers, subjects and rooms) in a weekly timetable. This paper presents a novel way to generate timetables for high schools. The algorithm has three phases. Pre-scheduling, initial phase and optimization through tabu search. In the first phase, a graph based algorithm used to create groups of lessons to be scheduled simultaneously; then an initial solution is built by a sequential greedy heuristic. Finally, the solution is optimized using tabu search algorithm based on frequency based diversification. The algorithm has been tested on a set of real problems gathered from Iranian high schools. Experiments show that the proposed algorithm can effectively build acceptable timetables.