Mathematical Programming-based Models and Methods for University Course Timetabling

Abstract

University course timetabling is a large resource allocation problem faced by thousands of academic institutions worldwide. However, due to the size and complexity of modern universities, even finding a feasible timetable can be a computationally difficult problem. After decades of research, the development of algorithms for automated timetabling remains as an active research field, predominantly using metaheuristics. In this thesis we develop new mathematical programming-based models and methods for university course timetabling problems. To address large practical problems, course timetabling can be decomposed into a time assignment followed by a room assignment. For the time assignment problem, we define an integer programme which assigns each event (e.g. a lecture) to a time period in such a way that no conflicts occur. When generating a time assignment, we also consider how to ensure that a feasible room assignment will exist. This is shown to be complex for practical problems which feature an arbitrary set of room types. For the room assignment problem, we define a set packing integer programme within a lexicographic optimisation process, to consider several quality measures. An analysis of the matrix structure for this model yields insights into the practical difficulty of addressing different room assignment quality measures. We also study the minimal perturbation problem, where infeasibility in an existing timetable must be repaired with the least possible disruption. We define a heuristic which uses an integer programme to resolve infeasibility within an expanding neighbourhood of possible perturbations. In practice, this algorithm can be applied in the construction and maintenance of a timetable. The results of our methods are promising. In addition to validating against established benchmarks, we demonstrate the ability to generate high quality solutions for practical problems at the University of Auckland and the Technical University of Denmark. The applications of this work are extended by studying the analytics capability of our timetabling algorithms, which further leverage the use of exact optimisation. In addition to conducting scenario analyses, our algorithms are used to explore the quality tradeoffs inherent to the timetabling process. The provision of analytics to timetablers has significant potential for future research in this field.