Article ID: | iaor20084439 |
Country: | Netherlands |
Volume: | 176 |
Issue: | 1 |
Start Page Number: | 177 |
End Page Number: | 192 |
Publication Date: | Jan 2007 |
Journal: | European Journal of Operational Research |
Authors: | Petrovic Sanja, Meisels Amnon, Burke Edmund K., Qu Rong, McCollum Barry |
Keywords: | graphs, heuristics: tabu search, education |
This paper presents an investigation of a simple generic hyper-heuristic approach upon a set of widely used constructive heuristics (graph coloring heuristics) in timetabling. Within the hyper-heuristic framework, a tabu search approach is employed to search for permutations of graph heuristics which are used for constructing timetables in exam and course timetabling problems. This underpins a multi-stage hyper-heuristic where the tabu search employs permutations upon a different number of graph heuristics in two stages. We study this graph-based hyper-heuristic approach within the context of exploring fundamental issues concerning the search space of the hyper-heuristic (the heuristic space) and the solution space. Such issues have not been addressed in other hyper-heuristic research. These approaches are tested on both exam and course benchmark timetabling problems and are compared with the frnetuned bespoke state-of-the-art approaches. The results are within the range of the best results reported in the literature. The approach described here represents a significantly more generally applicable approach than the current state of the art in the literature. Future work will extend this hyper-heuristic framework by employing methodologies which are applicable on a wider range of timetabling and scheduling problems.