A robust simulated annealing based examination timetabling system

The examination scheduling problem varies in detail from institution to institution. Thus any generic approach must be robust enough to work well over the full spectrum of problem characteristics. It is well-known that the quality of solutions produced by any simulated annealing implementation depends on the correct choice of solution space and neighbourhood, as well as the parameters that govern the cooling schedule. As these choices are sensitive to the precise problem details the design of a generic simulated annealing based approach to examination scheduling needs to address this issue carefully. This paper examines this problem with respect to an implementation that has already been shown to work well at a single institution. The basic framework is used to test different neighbourhoods and cooling schedules over a variety of problems and to examine whether or not biases in sampling have a significant effect on solution quality. The results indicate that the choice of neighbourhood is the most important decision and that neighbourhoods based on the graph-theoretic concept of Kempe chains are the most effective regardless of the objectives or size of the problem.