Curriculum based course timetabling: new solutions to Udine benchmark instances

Gerald Lach () and Marco Lübbecke ()

Annals of Operations Research, 2012, vol. 194, issue 1, 255-272

Abstract: We present an integer programming approach to the university course timetabling problem, in which weekly lectures have to be scheduled and assigned to rooms. Students’ curricula impose restrictions as to which courses may not be scheduled in parallel. Besides some hard constraints (no two courses in the same room at the same time, etc.), there are several soft constraints in practice which give a convenient structure to timetables; these should be met as well as possible. We report on solving benchmark instances from the literature and the 2nd International Timetabling Competition which are based on real data from the university of Udine. The first set is solved to proven optimality; for the second set we give solutions which on average compete well with or beat the previously best known solutions. Our algorithm is not an overall winner, but it is very robust in the sense that it deterministically gives satisfactory lower and upper bounds in reasonable computation time without particular tuning. For slightly larger instances from the literature our approach shows significant potential as it considerably beats previous benchmarks. We further present solutions of proven quality to a few much larger instances with more elaborate hard constraints. Copyright Springer Science+Business Media, LLC 2012

Keywords: Integer programming; Decomposition; University course timetabling (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (20)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-010-0700-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:194:y:2012:i:1:p:255-272:10.1007/s10479-010-0700-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-010-0700-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().