A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems

This paper approximately solves the high school timetabling problem using a simulated annealing based algorithm with a newly-designed neighborhood structure. In search for the best neighbor, the heuristic performs a sequence of swaps between pairs of time slots, instead of swapping two assignments as in a standard simulated annealing. The computational results show that the proposed heuristic, which is tested on two sets of benchmark instances, performs better than existing approaches. (C) 2009 Elsevier B.V. All rights reserved.