Integer programming for solving the course timetabling problem

The Course Timetabling Problem (CTP) is the problem of scheduling a set of meetings between lecturers and students over a period of time, requiring some resources (i.e., classrooms) and satisfying some additonal constraints. The problem is known to be NP-hard. It happens most of the time that it is impossible to meet all the requirements, so the objective of the problem is often to produce the timetable that satisfies the greatest number of constraints. It is customary to speak of a satisfactory solution rather than of an optimal solution. In this paper we describe a system based on an integer linear programming approach and on a graphical user interface that allows a user to build a course timetable using an Internet browser. We show that by decomposing the Course Timetabling Problem using human expertise it is possible to reduce the CPU time and to implicitly satisfy additional constraints. The resulting decision support system is not only fast, but also simple to use. With modern programming tools, the implementation of a GUI is now an easy task: we briefly describe our experience. We solve four real world instances, using data from the University of Padova (School of Statistics and School of Mathematics), in a few seconds.