Solving examination timetabling problems through adaptation of heuristic orderings

Solving examination timetabling problems through adaptation of heuristic orderings

0.00 Avg rating0 Votes
Article ID: iaor20043621
Country: Netherlands
Volume: 129
Issue: 1
Start Page Number: 107
End Page Number: 134
Publication Date: Jul 2004
Journal: Annals of Operations Research
Authors: ,
Keywords: graphs
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.

Reviews

Required fields are marked *. Your email address will not be published.