New integer linear programming approaches for course timetabling

TitleNew integer linear programming approaches for course timetabling
Publication TypeJournal Article
Year of Publication2008
AuthorsBoland N, Hughes BD, Merlot LTG, Stuckey PJ
JournalComputers & Operations Research
Volume35
Pagination2209 - 2233
ISSN0305-0548
KeywordsInteger linear programming
Abstract

The most complete form of academic timetabling problem is the population and course timetabling problem. In this problem, there may be multiple classes of each subject, and the decision on which students are to constitute each class is made in concert with the decision on the timetable for each class. In order to solve this problem, it is normally simplified or decomposed in some fashion. One simplification commonly used in practice is known as blocking: it is assumed that the classes can be partitioned into sets of classes (or blocks) that will be timetabled in parallel. This restricts clashing to occur only between classes in the same block, and essentially removes the timetabling aspect of the problem, which can be carried out once the blocks are constituted and the classes populated. The problem of constituting the blocks and populating the classes, known as the course blocking and population problem, is nevertheless a challenging problem, and provides the focus of this paper. We demonstrate, using data provided by a local high school, that integer linear programming approaches can solve the problem in a matter of seconds. Key features include remodelling to remove symmetry caused by students with identical subject selection, and the observation that in practice, only integrality of the block composition variables needs to be enforced; the class population aspects of the model have strong integrality properties.

URLhttp://www.sciencedirect.com/science/article/pii/S0305054806002784
DOI10.1016/j.cor.2006.10.016
Timetabling Category: