A graph-based hyper-heuristic for educational timetabling problems

By Edmund Kieran Burke, Barry McCollum, Amnon Meisels, Sanja Petrovic, Rong Qu. European Journal of Operational Research, 2007

567 citations recorded by the source corpus.

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 fine-tuned bespoke state-of-theart 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. � 2005 Elsevier B.V. All rights reserved.

Subfields: Industrial and Manufacturing Engineering, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/eb96c59aa7098dfa6a326fc81e479d5deca20908

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Industrial and Manufacturing Engineering

In Management Science and Operations Research

Citations in the corpus

A survey of metaheuristic-based techniques for University Timetabling problems (2007, methodology): “However, we appreciate that other techniques, such as Neural Networks and Hyper-heuristics, might also be considered metaheuristics by some, and it is worth mentioning that there have also been successful applications of these latter techniques to various timetabling problems in the past ( Burke et ”
Recent advances in selection hyper-heuristics (2020, background): “Constructive selection hyper-heuristics have been used to solve educational timetabling problems for over a decade Burke et al. (2007).”
A Classification of Hyper-heuristic Approaches (2010, methodology): “Several approaches have recently been proposed to generate efficient hybridisations of existing construction heuristics in domains such as bin packing [41, 55], timetabling [13, 15, 53, 54], production scheduling [63], and stock cutting [60, 61].”