Hybrid cp+lns for the curriculum-based course timetabling problem

Abstract. Course Timetabling (CTT) [11] is a popular combinatorial optimization problem, which deals with generating university timetables by scheduling weekly lectures, subject to conflicts and availability con-straints, while minimizing costs related to resources and user discomfort. In CB-CTT, students enrol to curricula i.e., (possibly overlapping) col-lections of courses. Lectures of courses pertaining to the same curriculum must therefore be scheduled at different times, so that students can at-tend all courses. In this paper we propose (i) a Constraint Programming (CP) model for CB-CTT and (ii) a Large Neighborhood Search (LNS) [10] strategy exploiting constraint propagation to solve hard instances of the problem. We then compare our findings against the current best results on the ITC2007 [7] testbed.