Timetabling at Utrecht University

Abstract

In this thesis we examined the possibilities to automate the roomscheduling of the lectures given at Utrecht University. The amount of lectures that has to be given at Utrecht University in combination with the complexity of the problem (NP-Complete) makes this problem hard to solve with the current system, which uses a greedy algorithm. We successfully implemented a local search to solve the original problem including extra constraints that were desired by the schedulers at Utrecht University. To decrease the running time and at the same time fulfilling the regularity constraint we applied a 2-phase approach: first a stamp is created, which consists of the lectures that should be repeated every week. This stamp is then applied for every week to ensure the regularity of the lectures. In the second part of the approach the incidental lectures are scheduled to create a complete timetable. In this thesis we examined several algorithms for generating the initial timetable, as well as a Branch and Bound heuristic in the local search, accompanied by other problem-specific operators. This resulted in an algorithm that is far more superior than a greedy algorithm such as the algorithm of Syllabus Plus.