A Simulated Annealing approach to the
Curriculum-Based Course Timetabling problem

Ruggero Bellio1, Sara Ceschia2, Luca Di Gaspero2, Andrea Schaerf2, and Tommaso Urli2
DIES1, DIEGM2 — University of Udine, Italy

MISTA 2013 // Ghent (Belgium), August 27, 2013

Outline of the talk

Covered topics

Problem definition

Problem

Course Timetabling (CTT) deals with generating university timetables by scheduling weekly lectures, subject to conflicts and availability constraints, while minimizing costs related to resources and user discomfort In Curriculum-Based Course Timetabling (CB-CTT), conflicts originate from curricula, i.e, collections of related courses whose lectures cannot be scheduled at the same time.

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

Solution technique

Basic ideas

Cutoffs [Johnson et al., 1989]

SA (temperature decreases when n neighbors have been visited, constant decrease)

SA with cutoffs (temperature decreases when k neighbors have been accepted, i.e., much more often in the beginning because of high temperature, adaptive)

Neighborhood relations

Given a solution, we explore two possible, neighborhoods

MoveLecture
Move one lecture from its currently assigned period and room to another period and/or a free room.
SwapLectures
Take two lectures of distinct courses in different periods and swap their periods and their rooms.

At each step we choose stochastically the neighborhood to explore, where the probability of selecting the second one is a parameter of the algorithm.

Algorithm overview
(actually implemented in EasyLocal++)

best = current = randomSolution();
sampled = accepted = 0;

while (iterations <= maxIterations)
{
    current = random() < swapRate ? SwapLecture(best) : MoveLecture(best);
    sampled++;
    
    delta = cost(current) - cost(best);
    
    if (delta <= 0 or (random() < e^(-delta/T))) {
        best = current;
        accepted++;
    }
    
    if (sampled >= maxSampled or accepted >= maxAccepted) {
        T *= alpha;
        sampled = accepted = 0;
    }
}

Tuning process

Parameters

We have tuned all of our parameters at once by

Stopping condition variables

Hammersley point set

We sampled 32 parameter configurations from the Hammersley point set, which has some nice properties that make it good for parameter tuning.

F-Race

We run an F-Race among our 32 configurations on the 4200 instances from [Smith-Miles and Lopes, 2010]. The winning setup was

The whole tuning process was automated with json2run (open source tool).

Results

Validation on ITC 2007 instances

Validation on the 21 instances from the ITC 2007 competition.

Future (and current) work

Adaptive tuning

Adaptive tuning of start temperature

Adaptive tuning validation

Validation on the 21 instances from the ITC 2007 competition.

Adaptive tuning future

Thank you