Skip to main content

Research Repository

Advanced Search

Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems

Burke, Edmund; Dror, Moshe; Petrovic, Sanja; Qu, Rong

Authors

Edmund Burke

Moshe Dror

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

Profile Image

RONG QU rong.qu@nottingham.ac.uk
Associate Professor



Contributors

B.L. Golden
Editor

S. Raghavan
Editor

E.A. Wasil
Editor

Abstract

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.

Citation

Burke, E., Dror, M., Petrovic, S., & Qu, R. (2005). Hybrid Graph Heuristics within a Hyper-heuristic Approach to Exam Timetabling Problems. In S. Raghavan, B. Golden, & E. Wasil (Eds.), The Next Wave in Computing, Optimization, and Decision TechnologiesSpringer

Publication Date Jan 1, 2005
Deposit Date Dec 12, 2005
Publicly Available Date Oct 9, 2007
Peer Reviewed Peer Reviewed
Book Title The Next Wave in Computing, Optimization, and Decision Technologies
Keywords case based reasoning, exam timetabling problems, graph heuristics, hyperheuristics,knowledge discovery, tabu search
Public URL http://eprints.nottingham.ac.uk/id/eprint/349
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf

Files


rxqICS05.pdf (61 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations