Solving examination timetabling problems through adaption of heuristic orderings

Citation

Burke E & Newall JP (2004) Solving examination timetabling problems through adaption of heuristic orderings. Annals of Operations Research, 129 (1-4), pp. 107-134. https://doi.org/10.1023/B%3AANOR.0000030684.30824.08

Abstract
Heuristic ordering based methods, very similar to those used for graph colouring problems, have long been applied successfully to the examination timetabling problem. Despite the success of these methods on real life problems, even with limited computing resources, the approach has the fundamental flaw that it is only as effective as the heuristic that is used. We present a method that adapts to suit a particular problem instance "on the fly." This method provides an alternative to existing forms of ‘backtracking,' which are often required to cope with the possible unsuitability of a heuristic. We present a range of experiments on benchmark problems to test and evaluate the approach. In comparison to other published approaches to solving this problem, the adaptive method is more general, significantly quicker and easier to implement and produces results that are at least comparable (if not better) than the current state of the art. We also demonstrate the level of generality of this approach by starting it with the inverse of a known good heuristic, a null ordering and random orderings, showing that the adaptive method can transform a bad heuristic ordering into a good one.

Keywords
examination timetabling; heuristics; graph colouring

Journal
Annals of Operations Research: Volume 129, Issue 1-4