Please use this identifier to cite or link to this item:
Appears in Collections:Computing Science and Mathematics Book Chapters and Sections
Peer Review Status: Refereed
Title: An adaptive tie breaking and hybridisation hyper-heuristic for exam timetabling problems
Author(s): Burke, Edmund
Qu, Rong
Soghier, Amr
Contact Email:
Editor(s): Pelta, Da
Krasnogor, N
Dumitrescu D, D
Chira, C
Lung, R
Citation: Burke E, Qu R & Soghier A (2011) An adaptive tie breaking and hybridisation hyper-heuristic for exam timetabling problems. In: Pelta D, Krasnogor N, Dumitrescu D D, Chira C & Lung R (eds.) Nature Inspired Cooperative Strategies for Optimization (NICSO 2011) Studies in Computational Intelligence, 387. Heidelberg: Springer, pp. 205-223.;
Keywords: Graph theory
Issue Date: 2011
Date Deposited: 1-Jul-2013
Series/Report no.: Studies in Computational Intelligence, 387
Abstract: Graph colouring heuristics have long been applied successfully to the exam timetabling problem. Despite the success of a few heuristic ordering criteria developed in the literature, the approaches lack the ability to handle the situations where ties occur. In this paper, we investigate the effectiveness of applying tie breakers to orderings used in graph colouring heuristics. We propose an approach to construct solutions for our problem after defining which heuristics to combine and the amount of each heuristic to be used in the orderings. Heuristic sequences are then adapted to help guide the search to find better quality solutions. We have tested the approach on the Toronto benchmark problems and are able to obtain results which are within the range of the best reported in the literature. In addition, to test the generality of our approach we introduced an exam timetabling instance generator and a new benchmark data set which has a similar format to the Toronto benchmark. The instances generated vary in size and conflict density. The publication of this problem data to the research community is aimed to provide researchers with a data set which covers a full range of conflict densities. Furthermore, it is possible using the instance generator to create random data sets with different characteristics to test the performance of approaches which rely on problem characteristics. We present the first results for the benchmark and the results obtained show that the approach is adaptive to all the problem instances that we address. We also encourage the use of the data set and generator to produce tailored instances and to investigate various methods on them.
Rights: The publisher does not allow this work to be made publicly available in this Repository. Please use the Request a Copy feature at the foot of the Repository record to request a copy directly from the author. You can only request a copy if you wish to use this work for your own research or private study.
DOI Link: 10.1007/978-3-642-24094-2_15
Licence URL(s):

Files in This Item:
File Description SizeFormat 
An adaptive tie breaking and hybridisation hyper-heuristic.pdfFulltext - Published Version371.11 kBAdobe PDFUnder Embargo until 3000-12-01    Request a copy

Note: If any of the files in this item are currently embargoed, you can request a copy directly from the author by clicking the padlock icon above. However, this facility is dependent on the depositor still being contactable at their original email address.

This item is protected by original copyright

Items in the Repository are protected by copyright, with all rights reserved, unless otherwise indicated.

The metadata of the records in the Repository are available under the CC0 public domain dedication: No Rights Reserved

If you believe that any material held in STORRE infringes copyright, please contact providing details and we will remove the Work from public display in STORRE and investigate your claim.