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.

Journal Article Type Article
Publication Date Aug 1, 2015
Journal Expert Systems with Applications
Print ISSN 0957-4174
Electronic ISSN 0957-4174
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 42
Issue 13
APA6 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
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
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

;