Dissemin is shutting down on January 1st, 2025

Published in

Springer, Studies in Computational Intelligence, p. 205-223, 2011

DOI: 10.1007/978-3-642-24094-2_15

Links

Tools

Export citation

Search in Google Scholar

An adaptive tie breaking and hybridisation hyper-heuristic for exam timetabling problems

Proceedings article published in 2011 by Edmund K. Burke, Rong Qu ORCID, Amr Soghier
This paper is available in a repository.
This paper is available in a repository.

Full text: Download

Green circle
Preprint: archiving allowed
Orange circle
Postprint: archiving restricted
Red circle
Published version: archiving forbidden
Data provided by SHERPA/RoMEO

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.