An IP-based heuristic for the post enrolment course timetabling problem of the ITC2007

J. Broek () and C. Hurkens ()

Annals of Operations Research, 2012, vol. 194, issue 1, 439-454

Abstract: Track 2 of the international timetabling competition 2007 was a post enrolment course timetabling problem. A set of events has to be assigned to a timeslot and to a room such that all students are able to attend their requested events while not violating the hard constraints. There are also soft constraints that make the timetable “nicer”. We present a deterministic heuristic that assigns events to timeslots based on an LP-solution constructed with column generation. We get an integer solution by fixing columns one at a time. This heuristic finds a solution that obeys all the hard constraint for 23 of the 24 instances of the competition. The generated solution is improved by selecting a set of events that are reassigned by solving an integer program. This IP minimizes the number of soft constraint violations under the restriction that no hard constraints are violated. Comparing the results of our heuristic with the results of the five finalists of the competition, shows that our approach is competitive. Copyright The Author(s) 2012

Keywords: Course timetabling; ITC2007; Column generation; Integer programming (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-010-0708-z (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:439-454:10.1007/s10479-010-0708-z

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

DOI: 10.1007/s10479-010-0708-z

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 ().