In this paper we deal with the problem of building a timetable for the courses of a university faculty. We propose an integer linear programming approach based on column generation. Each column is associated to a weekly timetable of a single course. The constraints referring to classroom occupancy and non overlapping in time of courses are in the integer linear programming matrix. The constraints and preferences related to a single course timetable are embedded in the column generation procedure. Generating a column for a course amounts to selecting the currently best time slots in the week. The interaction between the column generation procedure and the branch-and-bound method is also discussed. Some computational results are shown.
A column generation scheme for faculty timetabling
SERAFINI, Paolo
2005-01-01
Abstract
In this paper we deal with the problem of building a timetable for the courses of a university faculty. We propose an integer linear programming approach based on column generation. Each column is associated to a weekly timetable of a single course. The constraints referring to classroom occupancy and non overlapping in time of courses are in the integer linear programming matrix. The constraints and preferences related to a single course timetable are embedded in the column generation procedure. Generating a column for a course amounts to selecting the currently best time slots in the week. The interaction between the column generation procedure and the branch-and-bound method is also discussed. Some computational results are shown.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
