Applying an improved heuristic based optimiser to solve a set of challenging University timetabling problems: An experience report

Abstract

University timetabling problems (UTPs) represent a class of challenging and practical constrained optimization problems with its unique requirements when compared to school timetabling. In the past, researchers had proposed different intelligent search methods, that can be generally classified as the constructive or local search methods, to automate school and/or university timetabling. In this paper, we considered a flexible local search scheme combining both min-conflicts and look-forward heuristics to effectively solve general university timetabling problems. Our search proposal augmented with a k-reset repair operator achieved impressive results when compared to that of a general finite-domain constraint solving system, namely the ZDC, on a set of challenging UTPs obtained from an international timetabling competition. A preliminary analysis of their search results was conducted.More importantly, our search proposal of combined heuristics sheds light on various directions to effectively handle other complex or large-scale scheduling problems. © Springer-Verlag Berlin Heidelberg 2004.