Skip to main content

Research Repository

Advanced Search

Solving high school timetabling problems worldwide using selection hyper-heuristics

Ahmed, Leena N.; Özcan, Ender; Kheiri, Ahmed

Authors

Leena N. Ahmed

Ahmed Kheiri



Abstract

High school timetabling is one of those recurring NP-hard real-world combinatorial optimisation problems that has to be dealt with by many educational institutions periodically, and so has been of interest to practitioners and researchers. Solving a high school timetabling problem requires scheduling of resources and events into time slots subject to a set of constraints. Recently, an international competition, referred to as ITC 2011 was organised to determine the state-of-the-art approach for high school timetabling. The problem instances, obtained from eight different countries across the world used in this competition became a benchmark for further research in the field. Selection hyper-heuristics are general-purpose improvement methodologies that control/mix a given set of low level heuristics during the search process. In this study, we evaluate the performance of a range of selection hyper-heuristics combining different reusable components for high school timetabling. The empirical results show the success of the approach which embeds an adaptive great-deluge move acceptance method on the ITC 2011 benchmark instances. This selection hyper-heuristic ranks the second among the previously proposed approaches including the ones competed at ITC 2011.

Citation

Ahmed, L. N., Özcan, E., & Kheiri, A. (2015). Solving high school timetabling problems worldwide using selection hyper-heuristics. Expert Systems with Applications, 42(13), doi:10.1016/j.eswa.2015.02.059

Journal Article Type Article
Publication Date Aug 1, 2015
Deposit Date Mar 10, 2016
Publicly Available Date Mar 10, 2016
Journal Expert Systems with Applications
Print ISSN 0957-4174
Electronic ISSN 0957-4174
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 42
Issue 13
DOI https://doi.org/10.1016/j.eswa.2015.02.059
Keywords Benchmarking; Combinatorial optimization; Competition; Heuristic methods; Scheduling, Adaptive move acceptance; Adaptive operator selections; Constraint Satisfaction; Great deluge; Timetabling, Optimization
Public URL http://eprints.nottingham.ac.uk/id/eprint/32182
Publisher URL http://www.sciencedirect.com/science/article/pii/S0957417415001670
Copyright Statement Copyright information regarding this work can be found at the following address: http://creativecommons.org/licenses/by-nc-nd/4.0

Files


HHforITC.pdf (294 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://creativecommons.org/licenses/by-nc-nd/4.0





You might also like



Downloadable Citations