A tabu search algorithm with efficient diversification strategy for high
  school timetabling problem
  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.
