Effective learning hyper-heuristics for the course timetabling problem

Citation

Soria-Alcaraz JA, Ochoa G, Swan J, Carpio M, Puga H & Burke E (2014) Effective learning hyper-heuristics for the course timetabling problem. European Journal of Operational Research, 238 (1), pp. 77-86. https://doi.org/10.1016/j.ejor.2014.03.046

Abstract
Course timetabling is an important and recurring administrative activity in most educational institutions. This article combines a general modeling methodology with effective learning hyper-heuristics to solve this problem. The proposed hyper-heuristics are based on an iterated local search procedure that autonomously combines a set of move operators. Two types of learning for operator selection are contrasted: a static (offline) approach, with a clear distinction between training and execution phases; and a dynamic approach that learns on the fly. The resulting algorithms are tested over the set of real-world instances collected by the first and second International Timetabling competitions. The dynamic scheme statistically outperforms the static counterpart, and produces competitive results when compared to the state-of-the-art, even producing a new best-known solution. Importantly, our study illustrates that algorithms with increased autonomy and generality can outperform human designed problem-specific algorithms.

Keywords
Timetabling; Hyper-heuristics; Heuristics; Metaheuristics; Combinatorial optimization

Journal
European Journal of Operational Research: Volume 238, Issue 1

People

Professor Gabriela Ochoa

Professor, Computing Science