Post-Enrollment Course Timetabling

The Course Timetabling Problem

The Course Timetabling Problem (CTT) consists in scheduling a sequence of events or lectures of university courses in a prefixed period of time (typically a week), satisfying a set of various constraints on rooms and students. Many formulations have been proposed for the CTT problem over the years. Nevertheless, two formulations have recently received more attention than others, mainly thanks to the two timetabling competitions, ITC 2002 and ITC 2007 (see McCollum et al, 2010 ), which have used them as competition ground. These are the so-called curriculum-based course timetabling (CB-CTT) and post-enrolment course timetabling (PE-CTT). The main difference between the two formulations is that in the CB-CTT all constraints and objectives are related to the concept of curriculum, which is a set of courses that form the complete workload for a set of students. On the contrary, in PE-CTT this concept is absent and the constraints and objectives are based on the student enrolments to the courses.

The formulation of the PE-CTT consists of the following entities and constraints:

Events:
Each events is attendend by some students and it can require a room with a particular feature (e.g. the projector). In addition, there can be a precedence relation between two events such that an event has to be scheduled before the other. It is also defined an availabily relation that states which timeslots are suitable for each event.
Rooms:
Each room has different features and a fixed capacity, expressed in terms of seats for students.
Timeslots:
The planning horizon is composed by a given number of days. Each day is is divided in a fixed number of teaching timeslots that have to be assigned to events.

The (hard) constraints of the problem are the following ones:

H1. Conflicts:
Events that share common students cannot be scheduled in the same timeslot.
H2. Compatibility:
An event cannot be allocated in a room that is missing one of the features needed by the event, or in a room whose capacity is less than the number of students attending the event.
H3. Occupancy:
No more than one event per room per timeslot is allowed.
H4. Availability:
Timeslots must be assigned to events according to the availability relation.
H5. Precedences:
Timeslots must be assigned to events according to the precedence relation

In addition, the definition given for ITC 2007 includes the distinction between valid and feasible timetables (see Lewis et al., 2007 ). In a valid timetable all hard constraints must be satisfied, but it is allowed to leave some events unscheduled (i.e., they have no timeslot assigned). A feasible timetable is a valid one in which all events are scheduled. We thus introduce a new hard constraint type, that accounts for the unscheduled events, which can be violated to some extent:

H6. Unscheduled Events:
Events cannot be unscheduled.

The (soft) constraints of the problem are the following ones:

S1. Late Events:
A student should not attend an event in the last timeslot of a day.
S2. Consecutive Events:
A student should not attend more than two consecutive events in a day (i.e., the last timeslot of a day and the first one of the following day are not considered as consecutive).
S3. Isolated Events:
A student should not attend only one single event in the whole day.

The problem consist in finding an assignment of events to timeslots and rooms that satisfies the all hard constraints. The quality of the solution is evaluated with a cost function that is composed by two measures: the distance to feasibility (which counts the unscheduled events) and the objective function, which is a composition of the soft contraints. The cost function is hierarchical, in the sense that valid solutions with the lower distance to feasibility are better solution. If two valid solutions have the same distance to feasibility, then the solution with the minimum value of the objective function is preferred.

Publications

Instances

The problem formulation presented above is the one defined by Lewis et al. (2007) and used in the ITC 2007. Two other versions have been considered in the literature, which are obtained from the above one by removing some of the constraints. Four sets of instances are publicly available and have been used in our experimental analyses. These three formulations and the set of instances, are summarised in the following tables:

FormulationH1H2H3H4H5H6S1S2S3
FULL (ITC 2007)
ORIGINAL (ITC 2002)
HARD-ONLY

Instance FamilyFormulation#InstancesYear
ITC 2007 FULL 24 2007
Lewis & Paechter HARD-ONLY 60 2005
ITC2002 ORIGINAL 20 2002
Metaheuristics Network ORIGINAL 12 2001

The following tables summarize the features of the instances and allow to download them. They also report the best solutions found by our solver.

Source Code

The C++ source code of the simulated annealing algorithm for the PE-CTT, is available for download through the public subversion repository:

git clone git@bitbucket.org:satt/pe-ctt.git

The code has to be compiled against the release 2.0 of the EasyLocal++ framework, obtainable from:

git clone http://satt.diegm.uniud.it/git/EasyLocalpp.git EasyLocal++
cd EasyLocal++
git checkout 2.0

Best results on ITC 2007 instances

Instance Timeslots Events Rooms Students Avg Room Occupancy Conflict Density Our Best solution
1 45 400 10 500 0.88 0.34 0
2 45 400 10 500 0.88 0.37 0
3 45 200 20 1000 0.22 0.47 31
4 45 200 20 1000 0.22 0.51 21
5 45 400 20 300 0.44 0.30 0
6 45 400 20 300 0.44 0.30 0
7 45 200 20 500 0.22 0.53 0
8 45 200 20 500 0.22 0.51 0
9 45 400 10 500 0.88 0.34 0
10 45 400 10 500 0.88 0.38 0
11 45 200 10 1000 0.44 0.50 39
12 45 200 10 1000 0.44 0.58 0
13 45 400 20 300 0.44 0.32 0
14 45 400 20 300 0.44 0.32 0
15 45 200 10 500 0.44 0.53 0
16 45 200 10 500 0.44 0.45 0
17 45 100 10 500 0.22 0.70 0
18 45 200 10 500 0.44 0.65 0
19 45 300 10 1000 0.66 0.47 0
20 45 400 10 1000 0.88 0.27 543
21 45 500 20 300 0.55 0.23 5
22 45 600 20 500 0.66 0.26 5
23 45 400 20 1000 0.44 0.44 1292
24 45 400 20 1000 0.44 0.31 0

Best results on Lewis & Paechter instances

Instance Timeslots Events Rooms Students Avg Room Occupancy Conflict Density Our Best solution
M1 45 400 10 400 0.88 0.27 0
M2 45 390 10 400 0.86 0.29 0
M3 45 390 10 400 0.86 0.29 0
M4 45 410 10 400 0.91 0.26 0
M5 45 410 10 450 0.91 0.29 0
M6 45 410 11 450 0.82 0.35 0
M7 45 410 11 450 0.82 0.43 0
M8 45 400 10 400 0.88 0.41 0
M9 45 400 10 400 0.88 0.41 0
M10 45 400 10 500 0.88 0.25 0
M11 45 400 10 800 0.88 0.35 0
M12 45 400 10 800 0.88 0.26 0
M13 45 400 10 800 0.88 0.35 0
M14 45 400 10 1000 0.88 0.32 0
M15 45 425 10 500 0.94 0.28 0
M16 45 400 10 1000 0.88 0.50 0
M17 45 400 10 800 0.88 0.43 0
M18 45 400 10 1000 0.88 0.63 0
M19 45 410 10 1000 0.91 0.56 0
M20 45 410 10 1000 0.91 0.47 0
B1 45 1000 28 1000 0.79 0.10 0
B2 45 1000 25 1000 0.88 0.12 0
B3 45 1000 25 900 0.88 0.11 0
B4 45 1050 25 800 0.93 0.12 0
B5 45 1075 25 1000 0.95 0.12 0
B6 45 1075 25 1000 0.95 0.14 0
B7 45 1050 25 1100 0.93 0.19 19
B8 45 1025 25 1000 0.91 0.12 0
B9 45 1050 25 800 0.93 0.12 0
B10 45 1075 25 1000 0.95 0.13 0
B11 45 1075 25 1000 0.95 0.12 0
B12 45 1000 26 1000 0.85 0.12 0
B13 45 1000 25 1000 0.88 0.14 0
B14 45 1000 25 1000 0.88 0.12 0
B15 45 1000 25 1000 0.88 0.20 1
B16 45 1000 25 1000 0.88 0.17 0
B17 45 1000 25 1200 0.88 0.25 11
B18 45 1000 25 1000 0.88 0.20 3
B19 45 1000 25 1000 0.88 0.23 36
B20 45 1000 28 1000 0.88 0.21 5

Best results on ITC 2002 instances

Instance Timeslots Events Rooms Students Avg Room Occupancy Conflict Density Our Best solution
1 45 400 10 200 0.88 0.40 38
2 45 400 10 200 0.82 0.41 14
3 45 400 10 200 0.88 0.46 36
4 45 400 10 300 0.88 0.45 76
5 45 350 10 300 0.77 0.62 56
6 45 350 10 300 0.77 0.52 1
7 45 350 10 350 0.77 0.41 2
8 45 400 10 250 0.88 0.33 6
9 45 440 11 220 0.75 0.34 8
10 45 400 10 200 0.88 0.40 41
11 45 400 10 220 0.81 0.40 19
12 45 400 10 200 0.81 0.40 61
13 45 400 10 250 0.83 0.41 51
14 45 350 10 350 0.77 0.49 13
15 45 350 10 300 0.77 0.49 3
16 45 440 11 220 0.88 0.36 4
17 45 350 10 300 0.77 0.61 35
18 45 400 10 200 0.88 0.42 11
19 45 400 10 300 0.88 0.40 46
20 45 350 10 300 0.77 0.49 0

Best results on instances of the Metaheuristics Network

Instance Timeslots Events Rooms Students Avg Room Occupancy Conflict Density Our Best solution
easy01 45 100 5 80 0.44 0.52 0
easy02 45 100 5 80 0.44 0.66 0
easy03 45 100 5 80 0.44 0.49 0
easy04 45 100 5 80 0.44 0.31 0
easy05 45 100 5 80 0.44 0.63 0
medium01 45 400 10 200 0.88 0.37 9
medium02 45 400 10 200 0.88 0.37 8
medium03 45 400 10 200 0.88 0.40 30
medium04 45 400 10 200 0.88 0.37 10
medium05 45 400 10 200 0.88 0.29 1
hard01 45 400 10 400 0.88 0.54 190
hard02 45 400 10 400 0.88 0.54 133

Solution validator

A C++ source code of the solution validator for the ORIGINAL (and HARD-ONLY) formulation can be downloaded from the ITC 2002 website, whereas for the COMPLETE formulation it can be downloaded from the ITC 2007 website.