Case Study: Course Timetabling in “La Sapienza”

Course timetabling consists in scheduling a set of lectures for each course over a set of time-slots and within a set of classrooms. This is done for a prefixed period of time (usually one week). Several sets of constraints having different nature should be respected (e.g. Schaerf for a survey). Such problems are a frequent database application. They generally turn out to be very computationally demanding. Moreover, in the case of the Faculty of Engineering of "La Sapienza" University of Rome, two very different sets of courses should be scheduled in the same classrooms: extensive courses, lasting one year with extensive-type time-slots, and intensive courses, lasting one semester with intensive-type time-slots. A global discrete model of the problem is developed. Due to its dimension, the problem is solved by decomposing it into a fist assignment of lectures to time-slots, and a second assignment of lecture-time-slots to classrooms. As in many real world problems, several constraints had to be relaxed in order to make the problem feasible.