Hybrid CP+LNS for the
Curriculum-Based Course Timetabling Problem

Tommaso Urli
Scheduling and Time-Tabling Group
DIEGM — University of Udine, Italy

CP 2013 Doctoral Program // Uppsala (Sweden), September 16, 2013

Outline of the talk

Covered topics

Problem definition

Course Timetabling

In general, Course Timetabling (CTT) [Schaerf, 1999] deals with

Curriculum-Based Course Timetabling

In Curriculum-Based Course Timetabling (CB-CTT) [Bonutti et al., 2012]

Entities

CB-CTT involves several entities

Courses & Lectures.
A course is composed by several lectures to be scheduled at different times. Each course is taught by a teacher, who might be unavailable at certain times, and its lectures must be scattered over a minimum number of working days.
Curricula.
Each student enrols in a curriculum, i.e., a collection of courses whose lectures must be all attended by the enrolled students.

Entities

Days × Timeslots = Periods.
Lectures can be scheduled over a set of days, each one subdivided in fixed a number of timeslots. A (day, timeslot) pair identifies a period, unique within a week, in which a lecture can be scheduled.
Rooms & Roomslots.
In addition to a period, a valid schedule must specify a room for each lecture. A room has a fixed capacity, i.e. a maximum number of seats. Additionally, a (room, period) is typically called a roomslot.

Hard constraints

A feasible solution must satisfy the following hard constraints

Lectures.
Each lecture must be scheduled (in one and only one roomslot).
Conflicts.
Lectures pertaining to courses in the same curriculum or taught by the same teacher must be assigned different periods.
Room Occupancy.
Two lectures cannot take place in the same roomslot.
Availability.
Each lecture must be scheduled when the teacher teaching it is available.

Soft constraints (cost components)

Room Capacity.
When a lecture with n students gets scheduled in a room of capacity k < n, the cost of the solution increases by n-k.
Room Stability.
All the lectures of a course should be scheduled in the same room, every extra room increases the cost of the solution by one.
Minimum Working Days.
Every time a course with w minimum working days is scheduled over k < w days, the cost of the solution increases by 5 * (w-k).
Isolated Lectures.
Every time a scheduled lecture is not preceded or followed by lectures of courses in the same curriculum, the cost of the solution increases by 2.

CP model

CP model

Variables

Constraints

Constraints

Cost

For each soft constraint we added an extra variable to count the violations. The counting is carried out by various constraints

Cost

Solution technique

Large Neighborhood Search [Shaw, 1998]

Main ideas

Main ideas

Main ideas

Cutoffs [Johnson et al., 1989]

In classic SA, the temperature t decreases when n neighbors have been visited

In SA with cutoffs, the temperature decreases when k neighbors have been accepted (which occurs much often at the beginning, so adaptively wrt. search history)

Parameter tuning

Parameter tuning

Tuning outcome

Find best configuration by running F-Race [Birattari et al., 2010] over a heterogeneous set of instances using json2run. Best configuration

Results & Conclusions

Validation on ITC 2007 instances

Validation on the 21 instances from the ITC 2007 competition.

Conclusions

Thank you