The Course Timetabling Problem consists of the weekly scheduling of lectures of a collection of university courses, subject to certain constraints. The International Timetabling Competitions, ITC-2002 and ITC-2007, have been organized with the aim of creating a common formulation for comparison of solution proposals. This paper discusses the design and implementation of an extendable family of sorting-based mechanisms, called Sort Then Fix (STF) algorithms. Only ITC-2002 problem instances were used in this study. The STF approach is deterministic, and does not require swapping or backtracking. Almost all solutions run in less than 10% of the ITC-2002 benchmark time.
The Course Timetabling Problem consists of assigning a sequence of events (lectures) to a collection of university courses that meet within a number of rooms and time periods, usually weekly, satisfying some constraints. Course timetabling problems vary from university to university, and many researchers have shown that there is no single best solution for all situations.
Standards for comparing algorithms for solving the Course Timetabling Problem have emerged in recent years. The International Timetabling Competitions, ITC-2002 and ITC-2007, have been organized with the aim of creating a common formulation for comparing solutions, of which many have been proposed [15, 7].
While the competition is open to stochastic and deterministic approaches, virtually all the proposed solutions appearing in the competition web pages are stochastic algorithms [5]; as far as we know there is no record of a competitive and e ective deterministic approach used in the contest.
The motivation of this work was to develop a deterministic algorithm that solves the hard constraints of the 20 instances of the ITC-2002 in a timely manner, so we introduce a family of deterministic algorithms, Sort Then Fix (STF) algorithms, for solving timetabling problems. The algorithms were tested with the o cial instances of the ITC-2002.
The rest of the paper is organized as follows. We formalize the course timetabling problem in the second section; the third section describes the family of deterministic STF algorithms; the fourth section provides our results; and we conclude with some possible research directions. 2
We consider the problem of weekly scheduling a set of single events (or lectures). The problem has been discussed in [1] and it was the topic of ITC-2002 [2], where twenty arti cial instances were proposed. The instances are available from the ITC-2002 web page.
The problem consists of nding an optimal timetable within the following
framework: there is a set of events E = fE1; E2; :::; EnE g to be scheduled
in a set of rooms R = fR1; R2; :::; RnR g, where each room has 45 available
timeslots, nine for each day in a ve day week. There is a set of students
S = fS1; S2; :::; SnS g who attend the events, and a set of features F =
fF1; F2; :::; FnF g satis ed by rooms and required by events. Each event is
attended by a number of students, and each room has a given size, which is
the maximum number of students the room can accommodate. A feasible
timetable is one in which all events have been assigned a timeslot and a
room so that the following hard constraints are satis ed:
(
In contest instance les there were typically 10-11 rooms, hence there are 450-495 available places. There were typically 350-400 events, 5-10 features and 200-300 students.
The problem will penalize a timetable for each occurrence of some soft
constraint violation, which are the following:
(
The problem may be precisely formulated as: let F = fF1; F2; :::; FnF g be a set of symbols representing the features; N = fN1; :::; NnR g be a set of integer numbers indicating the maximum of students each room can accommodate; Ei = fF 00 ; F 00 ; :::; Fn00Ei g where F 00
1 2 j 2 F for j = 1; :::; nEi and nEi is the number of features required by event Ei; Si = fE10; E20; :::; En0Si g where Ej0 2 E for j = 1; :::; nSi and nSi is the number of events student Si attends; and
T = fT1; :::; T45g be a set of timeslots.
Find a feasible solution, i.e. a set of pairs f(T10; R10); :::; (Tn0 E ; Rn0E )g such that:
Ti0 2 T and Ri0 2 R (Ti0 6= Tj0) if Ei 2 Sk and Ej 2 Sk and (i 6= j) Ei
Ri0 and jfSj jj = 1; :::; nS and Ei 2 Sj gj Nk where Ri0 = Rk; 8i8j (i = j _ Ti0 6= Tj0 _ Ri0 6= Rj0 ).
The competition adds a constraint over execution time, i.e. given the information about rooms, events, features, and students, nd the best possible feasible solution within a given time limit. The time limit is given by a benchmark tool provided by the organizer. 3
ST F is a family of algorithms to solve timetabling problems, based on events and rooms sorting. Its distinguishing property is that the k-th iterate yields a schedule for the k most constrained events, where the notion of the most constrained event depends on the particular STF algorithm.
The rst step of an STF algorithm is to nd a binary matrix that represents the available rooms for every event. The following actions are performed: the number of students for each event is calculated and stored, ni = jfSj jj = 1; :::; nS and Ei 2 Sj gj a list of available rooms is created for each event, ei = fRj jEi Rj and ni Nj g
This rst step allows us to reduce the problem by eliminating the information concerning features and room capacity, de ning a new event set fe1; :::; enE g, that includes the eliminated information. The new event set will be used for de ning the most constrained event. The core strategy of the algorithms is to assign the most constrained event to the least constrained timeslot found for this event. In order to avoid strategies of movement that require backtracking to recover from mistakes, our aim is not to make mistakes of selection of placement and event. The intuitive idea is as follows: if there is at least one optimal solution where all soft and hard restrictions are satis ed, then it is possible to sort the events and placements in such a way that all the events are xed satisfying all the constraints. The general structure is as follows: 1. sort events from the most constrained to the least constrained one, 2. choose ei 2 [e1; : : : ; enE ], the next most constrained event, 3. sort the rooms of ei from the least to the most constrained one, 4. choose r 2 ei, the next least constrained room for event ei, 5. search s 2 [1 : : : 45], such that: 8j (i = j _ s 6= Tj0 _ r 6= Rj0 ) and if Ei; Ej 2 Sk and i 6= j, s 6= T 0, j 6. if (s 6= null) then Ri0 := r and Ti0 := s else go to step 4, 7. update data for the next iteration, 8. go to step 2 (or go to step 1, depending on the STF algorithm). Algorithm
The criteria of Table 1 are as follows:
(a) Number of rooms, in ascending order, where the event can be allocated.
(b) Number of students, in descending order, that attend the event.
(c) Number of free slots of all the event rooms in ascending order, where
a free slot is one which has no assigned event.
(d) Number of events, in ascending order, that can be allocated to the
event rooms, where the number of events includes assigned and
unassigned events.
(e) Number of free slots of all the event rooms in ascending order, where
a free slot is one which has no associated student attending another
event assigned to the same slot and the slot has no assigned event in
at at least one event room.
(f) Number of unassigned events, in ascending order, that can be allocated
to the event rooms.
(g) Number of free slots of all the event rooms in ascending order, where a
free slot is one which has no assigned event and no attending student
has another event placed at the same slot.
(
Our approach avoids swapping; if an event cannot be scheduled then the next most constrained event is scheduled, leaving the event in question without a room and timeslot. Thus we careful to formulate the de nition of the \most constrained event" in the STF algorithms to avoid unscheduled events.
The STF algorithms were developed in GNU Octave 3.0 on a Toshiba Satellite A105-S433 R laptop computer, with a 1.60 GHz Centrino Duo proccesor T5200, Mobile Intel R 945GM Express Chipset, 2 GB in RAM, 160 GB in HDD and the Ubuntu Linux 9.10 operating system.
All tests were done on this computer, within the time allowed by the benchmark tool provided by the organizers of the ITC-2002. This benchmark tool shows the time limit (in seconds) in which the algorithm must be executed in a particular computer, so that everybody can participate in a fair competition. In our box, the benchmark program allowed a maximum execution time of 558 seconds, time in wich the STF algorithms must be executed in order to nd feasible solutions.
Tables 2 and 3 show the results obtained by the STF algorithms on the 20 problem instances of the ITC-2002. The table displays the hard constraints violated by the algorithms running under GNU Octave 3.0 and under Matlab R R2009b.
Tables 4 and 5 display the soft constraints violated by the algorithms running on GNU Octave 3.0 and Matlab R R2009b.
In Fig. 1, we can see markedly di erent patterns of hard constraints violation. Some of them nearly nd feasible solutions for all the instances. For example, algorithm 28 and 29 violated only one hard constraint of one instance. Some of them nd feasible solutions only for a reduced number of instances, such is the case of algorithm 1, which only nds 3 of the 20 feasible solutions. It is worth noting that more re ned sorting criterions will nd a greater number of feasible solutions for all the instances. As we can see in Fig. 2, the graphs of the number of soft constraints violated by the 29 STF algorithms share a common pattern.
The Fig. 3 displays the time in seconds taken by the algorithms running on GNU Octave 3.0, and Fig. 4 shows the time taken by the algorithms running Matlab R R2009b. As we can see the both implementations of algorithms terminate within the 558 second allowed benchmark time and almost all the algorithms running on Matlab take less of the 10% of the allowed benchmark time, but the run over Octave takes much more time that Matlab. However, the purpose of Figs. 3 & 4 is to show the pattern that follows the STF algorithms in matter of time, and to prove that STF algorithms over di erent environments can compete in the ITC-2002 following the time rule.
VersionoftheSort-Then-Fixalgorithm * Problem instance * Problem instance 11 Version 1 Version 2 Version 3 Version 4 Version 5 Version 6 Version 7 Version 8 Version 9 Version 10 Version 11 Version 12 Version 13 Version 14 Version 15 Version 16 Version 17 Version 18 Version 19 Version 20 Version 21 Version 22 Version 23 Version 24 Version 25 Version 26 Version 27 Version 28 Version 29 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20
The criterions included in the algorithms deal only with hard constraints, however it is possible to extend the algorithms to handle soft constraints. search of the slots is in ascending order from 1 to 45; in the modi ed version algorithm 29', the search of slots is in ascending order from 1 to 8 then from 10 to 17 then from 19 to 26 then from 28 to 35 then 37 to 44 and nally in slots 9, 18, 27, 36 and 45. It is worth noticing that if a student takes lectures at the end of the day, i.e. in slots 9, 18, 27, 36 or 45, a soft constraint is violated. The number of violated hard constraints is the same in both versions, however the number of soft constraint violations is clearly reduced in the new version for all the instances.
In order to verify the results, the participants of the ITC-2002 provide the executable le of their implementations. 1 1 The STF implementations in source code are available by request via e-mail.
Problem instances 945 948 960 1263 1376 1377 1761 1128 973 968 1008 923 1065 1704 1501 1051 1456 924 1312 1401
The family of STF algorithms, which appear to solve timetabling problems in a natural way, has been proposed. STF algorithms de ne a notion of the most constrained event, which is used to sort events before scheduling them. Unlike other approaches to the ITC-2002 contest, STF is deterministic and avoids swapping and backtraking.
We are con dent that we will nd an STF algorithm that will nd feasible solutions for the 20 instances respecting the benchmark time. In this paper we focus on satisfying hard constraints only; soft constraints may be left unsatis ed. Nevertheless, as we showed in algorithm 29', with a slight modi cation we can considerably reduce the number of violated soft constraints in each one of the problem instances. We intend to nd an STF algorithm that nds feasible solutions satisfying both hard and soft constraints for the 20 ITC-2002 instances.
As a main contribution, the STF algorithms can be used as a preprocessing step for other optimization algorithms. For example, it can be combined with a non-deterministic approach, such as a metaheuristic, to build a hybrid algorithm that can be more robust and can nd a solution faster than a metaheuristic by itself. In fact, as far as we know all the references showing a solution to the problem only describe the metaheuristic used, but not the process to reach the initial feasible solution.
The metaheuristics used by the other participants of the contest do a pre-processing of the problem data before starting the search process, so all of the algorithms start with a di erent initial solution. To tackle this issue, the timetables generated by the STF algorithms can be used as an initial base solution to all of these metaheuristics, in order to measure the real e ectiveness of each metaheuristic with respect to the others.
The STF algorithm nds a timetable in much less than the benchmark time available. We intend future versions of the algorithm to satisfy both hard and soft constraints to nd complete solutions to the 20 ITC-2002 contest problem instances, within the time set by the benchmark program. Also, the STF algorithms will be extended and tested on the earlier instances of the International Timetabling Competition 2007, in order to manage the new constraints proposed in these instances.
We thank the Mexican Academy of Sciences (AMC) and the United StatesMexico Foundation for Science (FUMEC) for the support granted in 2009 under the Stays Summer Program.