Mathematical Programming Approaches for Optimal University Timetabling

Every semester universities are faced with the challenge of creating timetables for the courses. Creating these timetables is an important task to ensure that students can attend the courses they need for their education. Creating timetables that are feasible can be challenging, and when different preferences are taken into account, the problems become even more challenging.

Therefore, automating the processes of generating these timetables is a great help for the planners and the universities. Scheduling and timetabling has been studied before in the literature, and two international conferences are dedicated to this research field. This thesis considers a University Timetabling problem, more specifically the Curriculumbased Course Timetabling (CTT) problem.

The objective of the CTT problem is to assign a set of lectures to time slots and rooms. The literature has focused mainly on heuristic applications which are also apparent in the different surveys. The drawback of the heuristics is that they are problem specific and do not provide any information on the quality of the solutions they generate.

The objective of this thesis is to minimize the gap between the best-known upper bounds and the best-known lower bounds for CTT by using Mixed Integer Programming (MIP) based approaches. We present a total of 15 different MIP based approaches that we have implemented, ranging from Cutting Plane techniques and Lagrangian Relaxation to Benders’ Decomposition and Dantzig-Wolfe Decomposition.

Most of these implementations did not provide satisfying results. However, they provide valuable insights into the difficulties of the problem. We discuss all the approaches, the difficulties we have encountered, and suggestions on how to bring research further. Four of the implementations have led to articles submitted to international peer-reviewed journals.

The first two articles focus on exact methods and extend each other. The last two focus on generating high-quality lower bounds by applying an extended formulation, which is then decomposed. The articles in this thesis have brought us closer to the goal of closing the gap between the best-known upper and lower bounds for CTT.

Though CTT was the problem in focus, the methods implemented here are general enough to be applied for other scheduling problems as well.