A graph-based hyper heuristic for timetabling problems
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...
| Main Authors: | , , , , |
|---|---|
| Format: | Article |
| Published: |
Elsevier
2007
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/371/ |
| _version_ | 1848790401999175680 |
|---|---|
| author | Burke, Edmund MacCloumn, Barry Meisels, Amnon Petrovic, Sanja Qu, Rong |
| author_facet | Burke, Edmund MacCloumn, Barry Meisels, Amnon Petrovic, Sanja Qu, Rong |
| author_sort | Burke, Edmund |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T18:12:02Z |
| format | Article |
| id | nottingham-371 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:12:02Z |
| publishDate | 2007 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-3712020-05-04T16:26:41Z https://eprints.nottingham.ac.uk/371/ A graph-based hyper heuristic for timetabling problems Burke, Edmund MacCloumn, Barry Meisels, Amnon Petrovic, Sanja Qu, Rong 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. Elsevier 2007-01-01 Article PeerReviewed Burke, Edmund, MacCloumn, Barry, Meisels, Amnon, Petrovic, Sanja and Qu, Rong (2007) A graph-based hyper heuristic for timetabling problems. European Journal of Operational Research, 176 (1). pp. 177-192. ISSN 0377-2217 Heuristics; Graph heuristics; Hyper-heuristics; Tabu search; Timetabling http://www.sciencedirect.com/science/article/pii/S0377221705006387 doi:10.1016/j.ejor.2005.08.012 doi:10.1016/j.ejor.2005.08.012 |
| spellingShingle | Heuristics; Graph heuristics; Hyper-heuristics; Tabu search; Timetabling Burke, Edmund MacCloumn, Barry Meisels, Amnon Petrovic, Sanja Qu, Rong A graph-based hyper heuristic for timetabling problems |
| title | A graph-based hyper heuristic for timetabling problems |
| title_full | A graph-based hyper heuristic for timetabling problems |
| title_fullStr | A graph-based hyper heuristic for timetabling problems |
| title_full_unstemmed | A graph-based hyper heuristic for timetabling problems |
| title_short | A graph-based hyper heuristic for timetabling problems |
| title_sort | graph-based hyper heuristic for timetabling problems |
| topic | Heuristics; Graph heuristics; Hyper-heuristics; Tabu search; Timetabling |
| url | https://eprints.nottingham.ac.uk/371/ https://eprints.nottingham.ac.uk/371/ https://eprints.nottingham.ac.uk/371/ |