Hybrid variable neighbourhood approaches to university exam timetabling

Citation

Burke E, Eckersley AJ, McCollum B, Petrovic S & Qu R (2010) Hybrid variable neighbourhood approaches to university exam timetabling. European Journal of Operational Research, 206 (1), pp. 46-53. https://doi.org/10.1016/j.ejor.2010.01.044

Abstract
In this paper, we investigate variable neighbourhood search (VNS) approaches for the university examination timetabling problem. In addition to a basic VNS method, we introduce variants of the technique with different initialisation methods including a biased VNS and its hybridisation with a Genetic Algorithm. A number of different neighbourhood structures are analysed. It is demonstrated that the proposed technique is able to produce high quality solutions across a wide range of benchmark problem instances. In particular, we demonstrate that the Genetic Algorithm, which intelligently selects appropriate neighbourhoods to use within the biased VNS, produces the best known results in the literature, in terms of solution quality, on some of the benchmark instances. However, it requires relatively large amount of computational time. Possible extensions to this overall approach are also discussed.

Keywords
Examination timetabling; Meta-heuristics; Variable neighbourhood search; Genetic Algorithms

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