Skip to main content

Research Repository

Advanced Search

A graph-based hyper heuristic for timetabling problems

Burke, Edmund; MacCloumn, Barry; Meisels, Amnon; Petrovic, Sanja; Qu, Rong

A graph-based hyper heuristic for timetabling problems Thumbnail


Authors

Edmund Burke

Barry MacCloumn

Amnon Meisels

SANJA PETROVIC SANJA.PETROVIC@NOTTINGHAM.AC.UK
Professor of Operational Research

Profile Image

RONG QU rong.qu@nottingham.ac.uk
Professor of Computer Science



Abstract

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 hyperheuristic 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-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.

Citation

Burke, E., MacCloumn, B., Meisels, A., Petrovic, S., & Qu, R. (2007). A graph-based hyper heuristic for timetabling problems. European Journal of Operational Research, 176(1), https://doi.org/10.1016/j.ejor.2005.08.012

Journal Article Type Article
Publication Date Jan 1, 2007
Deposit Date Feb 28, 2007
Publicly Available Date Mar 29, 2024
Journal European Journal of Operational Research
Print ISSN 0377-2217
Electronic ISSN 0377-2217
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 176
Issue 1
DOI https://doi.org/10.1016/j.ejor.2005.08.012
Keywords Heuristics; Graph heuristics; Hyper-heuristics; Tabu search; Timetabling
Public URL https://nottingham-repository.worktribe.com/output/703857
Publisher URL http://www.sciencedirect.com/science/article/pii/S0377221705006387
Additional Information NOTICE: this is the author’s version of a work that was accepted for publication in European Journal of Operational Research. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in European Journal of Operational Research, 176(1), 177-192 (2007), doi: 10.1016/j.ejor.2005.08.012

Files





You might also like



Downloadable Citations