Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems
This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyperheuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Book Section |
| Published: |
Springer
2005
|
| Subjects: | |
| Online Access: | https://eprints.nottingham.ac.uk/349/ |
| _version_ | 1848790397132734464 |
|---|---|
| author | Burke, Edmund Dror, Moshe Petrovic, Sanja Qu, Rong |
| author2 | Golden, B.L. |
| author_facet | Golden, B.L. Burke, Edmund Dror, Moshe Petrovic, Sanja Qu, Rong |
| author_sort | Burke, Edmund |
| building | Nottingham Research Data Repository |
| collection | Online Access |
| description | This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyperheuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics for solving a problem. We developed a Tabu Search based hyper-heuristic to search for heuristic lists (of graph heuristics) for solving problems and investigated the heuristic lists found by employing knowledge discovery techniques. Two hybrid approaches (involving Saturation Degree and Largest Degree) including one which employs Case Based Reasoning are presented and discussed. Both the Tabu Search based hyper-heuristic and the hybrid approaches are tested on random and real-world exam timetabling problems. Experimental results are comparable with the best state-of-the-art approaches (as measured against established benchmark problems). The results also demonstrate an increased level of generality in our approach. |
| first_indexed | 2025-11-14T18:11:58Z |
| format | Book Section |
| id | nottingham-349 |
| institution | University of Nottingham Malaysia Campus |
| institution_category | Local University |
| last_indexed | 2025-11-14T18:11:58Z |
| publishDate | 2005 |
| publisher | Springer |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | nottingham-3492020-05-04T20:30:44Z https://eprints.nottingham.ac.uk/349/ Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems Burke, Edmund Dror, Moshe Petrovic, Sanja Qu, Rong This paper is concerned with the hybridization of two graph coloring heuristics (Saturation Degree and Largest Degree), and their application within a hyperheuristic for exam timetabling problems. Hyper-heuristics can be seen as algorithms which intelligently select appropriate algorithms/heuristics for solving a problem. We developed a Tabu Search based hyper-heuristic to search for heuristic lists (of graph heuristics) for solving problems and investigated the heuristic lists found by employing knowledge discovery techniques. Two hybrid approaches (involving Saturation Degree and Largest Degree) including one which employs Case Based Reasoning are presented and discussed. Both the Tabu Search based hyper-heuristic and the hybrid approaches are tested on random and real-world exam timetabling problems. Experimental results are comparable with the best state-of-the-art approaches (as measured against established benchmark problems). The results also demonstrate an increased level of generality in our approach. Springer Golden, B.L. Raghavan, S. Wasil, E.A. 2005 Book Section PeerReviewed Burke, Edmund, Dror, Moshe, Petrovic, Sanja and Qu, Rong (2005) Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems. In: The Next Wave in Computing, Optimization, and Decision Technologies. Springer, pp. 79-91. case based reasoning exam timetabling problems graph heuristics hyperheuristics knowledge discovery tabu search |
| spellingShingle | case based reasoning exam timetabling problems graph heuristics hyperheuristics knowledge discovery tabu search Burke, Edmund Dror, Moshe Petrovic, Sanja Qu, Rong Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems |
| title | Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems |
| title_full | Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems |
| title_fullStr | Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems |
| title_full_unstemmed | Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems |
| title_short | Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems |
| title_sort | hybrid graph heuristics within a hyper-heuristic approach to exam timetabling problems |
| topic | case based reasoning exam timetabling problems graph heuristics hyperheuristics knowledge discovery tabu search |
| url | https://eprints.nottingham.ac.uk/349/ |