VIETNAM NATIONAL UNIVERSITY
UNIVERSITY OF SCIENCE
FACULTY OF MATHEMATICS , MECHANICS AND INFORMATICS
Nguyen Anh Hoang
TIMETABLING PROBLEM
Undergraduate Thesis
Advanced Undergraduate Program in Mathematics
Hanoi - 2012
VIETNAM NATIONAL UNIVERSITY
UNIVERSITY OF SCIENCE
FACULTY OF MATHEMATICS , MECHANICS AND INFORMATICS
Nguyen Anh Hoang
TIMETABLING PROBLEM
Undergraduate Thesis
Advanced Undergraduate Program in Mathematics
Thesis advisor: Dr. Hoang Nam Dung
Hanoi - 2012
Contents
Chapter 1. The Timetabling Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1. Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. Applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1. E x amination Timetabling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.2. Po st En rollment based Course Timetabling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2.3. Curriculum based Course Timetabling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Chapter 2. Some General Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1. Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.1. In troduction and Some Fu n damentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1.2. Main Ideas of Genetic Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2. Memetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.1. Solution Representation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.2.2. Generating the First Popu lation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

Hanoi University of Science.
Finally, I would like to thank my family and friends who always support and
give me advice during my career at school.
iii
Introduction
Nowadays, the timetabling problems are widely common in the real world.
They can be seen and considered in every university in any country. They often con-
tain some constraints that needed to be satisfied, with the purpose to set an efficient
timetable. Many algorithms are now gradually being constructed and developed ,
since finding the absolutely optimal solution is almost impossible. However, peo-
ple’s attempts for seeking the best method to solve the timetabling problems are
very important and meaning to the world.
This thesis is organised as follows:
Chapter 1 presents definitions of the timetabling problem and its applica-
tions. It can be constructed weekly timetable for a university.
Chapter 2 will give you some algorithms that can be used to solve this kind
of problems. Up to now, people have found many ways to deal with scheduling
problem, and some of those are quite effective.
Chapter 3 is devoted for the specific methods that the winners of the Interna-
tional Timetabling Competition 2007 used to solve the problems.
At last, Chapter 4 will illustrates an application at Hanoi University of Sci-
ence timetabling problem and some of writter’s ideas to tackle this problem.
iv
CHAPTER 1
The Timetabling Problem
1.1. Defin i tions
In the context of a university, a typical timetabling problems generally in-
volves assigning a set of events (lectures, exam, tutorials and so on) to a limited
number of timeslots and rooms in such a way as to satisfy a set of constraints.
The two most common forms of this problem are exam-timetabling problems and

extension of the model commonly worked on. The fundame ntal problem involves
timetabling exams into a set of periods within a defined examination session while
satisfying a number of ha rd constraint. Like other areas of timetabling, a feasible
solution is one in which all the hard constraints are satisfied. The quality of the
solution is measured in terms of soft constraints satisfaction.
The problem consists of the following:
• A list of periods covering a specified length of time. The number and length
of periods are provided.
• A set of exams that are to be scheduled into these periods.
• For each e xam, a set of enrolled students is provided. Each student is enrolled
into a number of exams.
• A set of rooms with individual capacities.
1
This section is cited from T.Muller (200 7) [5], page 2.
2
• A set of additional period (e.g., exam A after exam B ) and room (exam A must
use room R) hard constraints.
• Soft constraints which contribute to a penalty if they are violated (including
details on weightings of these constraints).
A feasible timetable is one in which all examinations have a period and a
room assigned and the following hard constraints are satisfied:
• No student sits for more than one examination at a time.
• The capacity of individual rooms is not exceeded at any time during the ex-
amination session. Note that, unlike course timetabling, exams are explicitly
allowed to share rooms.
• Period lengths are not violated.
• Additional hard constraints must be satisfied.
The problem includes the following soft constraints:
• Two exams in a row: The number of occurrances when students have to sit for
two exams in a row on the same day.

before certain others.
The aim is to try and insert each of the given events into timetable (that is,
assign each event to one of the rooms and one of the 45 timeslot) while obeying
following hard constraints:
• No students should be required to attend more than one event at the same
time.
• In each case, the room should be big enough for all of the attending students
and should satisfy all of the features required by the event.
• Only one event is put into each room in any timeslot.
2
This section is cited from T.Muller (200 7) [5], page 3-4.
4
• Events should only be assigned to timeslots that are pre-defined as available for
those events.
• Where specified, events should be scheduled to occur in the correct order dur-
ing the week.
Note that the first three hard constraints above are exactly the same as the
hard constraints used in the first problem. The last two hard constraints, however,
are new additions to the model.
In addition, to the five hard constraints given above, the following soft constraints
are included in the problem:
• Last timeslot of the day: Students should not be scheduled to attend an event
in the last timeslot of a day.
• More than two in a row: Students should not have to attend three or more
events in consecutive timeslots occuring in the same day.
• One class on a day: Students should not be required to attend only one event
in a particular day.
Note that these three soft constraints are the same as those used in the first
problem. The overall penalty is the sum of occurrances of a student in the soft con-
straints that are violated.

satisfied:
• All lectures of a course must be scheduled, and they must be assigned to dis-
tinct periods.
• Two lectures cannot take place in the same room in the same period.
3
This section is cited from T.Muller (200 7) [5], page 4-5.
6
• Lectures of courses in the same curriculum, or taught by the same teacher,
must be scheduled in different periods.
• If the teacher of the course is not available to teach that course in a given pe-
riod, then no lectures of the course can be scheduled in that period.
The problem includes the following soft constraints:
• Room capacity: For each lecture, the number of students that attend the course
must be less than or equal to the seats in all the rooms that host its lectures.
Each student above the capacity counts as 1 point of penalty.
• Minimum working days: The lectures of each course must be spread into the
given minimum number of days. Each day below the minimum counts as 5
points of penalty.
• Curriculum compactness: Lectures belonging to a curriculum should be ad-
jacent to each other (i.e. in consecutive periods). For a given curriculum we
account for a violation everytime there is one lecture that is not ad jacent to any
other lecture within the same day. Each isolated lecture in a curriculum counts
as 2 points of penalty.
• Room stability: All lectures of a course should be given in the same room.
Each distinct room used for the lectures of a course, beside the first, counts as
1 point of penalty.
7
CHAPTER 2
Some General Algorithms
Nowadays, there are many algorithms produced to tackle the time prob-

first one is direct encoding, which directly represents a solution by a chromosome.
However, since it is too simple, sometimes it caused troubles and make the solution
infeasible. In this case, indirect encoding is applied to perform the solution, where
each chromosome now is encode only the instruction of building a solution, not a
solution itself.
Fitness of a Solution
In genetic algorithm, fitness function is used to measure how good a chro-
mosome will be. The fitness function is a specific problem. For instance, if we want
to minimize a function, or in other words, minimize its cost, then the fitness func-
tion is the cost itself. In the most timetabling problems, quality of a chromosome is
measured by number of constraints satisfied.
2.1.2. Main Ideas of Gene t ic Algorithm
In genetic algorithm, the main ideas consist of 3 steps. The first step is cre-
ating a set of solutions (a population) randomly. The next step is selecting chromo-
somes from the initial population for the next generation. This selection is based on
some criterias and there are some different methods to cope with it. Finally, the last
step is recombining the selected chromosomes from step 2 to create the n ew popu-
lation.
9
Now we focusing on the second step, that is the step of selecting chromo-
somes from the initial population. Here fitness function is used to decice which
parents will be chosen by evaluating the quality of solutions represented by those
chromosomes in the population. Those with higher fitness value will have a greater
chance of being chosen than those with lower fitness value. There are many differ-
ent methods of selection in genetic algorithm. One of them is a standard method
which called Roulette Wheel. In this kind of method, each chromosome will be de -
scribed as a slice in a circular wheel, and the chromosome with higher fitness value
will ha ve larger slice in the wheel. For example, if there are N chromosomes in the
population, the wheel will rotate N times. Each time the wheel rotate, it will stop at
any chromosome, and that chromosome will be chosen as parents to the next gener-

the length of chromosome will be selected randomly as the crossover point. Then
the genetic material before the crossover point will remain unchanged, while the ge-
netic material after the crossover point is exchanged between the parents. The idea
of one-point crossover can be generalized to N-point crossover by using N crossover
point rather than just one. For instance, in two-point crossover, 2 numbers less than
the length of chromosome will be selected randomly and represent crossover points.
Then the genetic material between these two points will be swapped, while others
remain unchanged. An example of two-point crossover method is given in Figure
2.1.
Figure 2.1: Two-point crossover
Uniform Crossover In uniform crossover a swapping probability is defined in order
to give a chance for an allele to be exchanged with the gene of the other parent. This
11
probability usually takes the value of 0.5.
Partially Matched Crossover (PMX) In partially matched crossover, two parents
are randomly selected and two crossover points are generated randomly. Alleles
within the two crossover points of a parent are exchanged with the alleles corre-
sponding to those mapped by the other parent. Figure 2.2 illustrates an e xample
of partially matched crossover. According to the example, firstly the genes between
two crossover points are swapped between two parents. Then the first gene value in
Parent 1 within the two crossover points, 7 , maps to 9 in Parent 2. Therefore, genes
7 and 9 are swapped i n Parent 1. Similarly, 8 and 2, also 4 and 1 a re exchanged
to create the offspring Offspring 1. Corresponding changes are done in Parent 2 to
create the offspring Offspring 2 [2].
Figure 2.2: Partially matched crossover
Mutation
In genetic algorithms, most chromosomes in the population seem like each other
after a number of generations. What it means is that, no crucial changes in the pop-
ulation, therefore in the search space do not occur. To overcome this problem and
add diversity to the population mutation operator is used. Mutation operator has

The concept of a memetic algorithm was first introduced by Moscato and
Norman to describe evolutionary algorithms in which local search is used to a large
extent. This ide a has further been formalised by Radcliffe and Surrey and a compar-
ison between memetic and genetic algorithms made. A meme can be thought as a
unit of information that reproduces itself as people exchange ideas. A meme differs
from a gene in that as it is passed between individuals, each individual adapts the
meme as it sees best whereas genes are passed unaltered [1].
2.2.1. Solution Representation
Each solution in the population is represented as a number of memes. Each
meme contains information on what exams are scheduled in which rooms for a par-
ticular period. A further meme is used to hold exams which could not be scheduled
in the prescribed period. Figure 2.4 shows an example of an encoded solution, where
e
i
is exam number i.
2
See E.K.Burke, J.P.Newall and R.F.Weare [1]for more precisely details.
14
Figure 2.4: The problem encoding
2.2.2. Generating the First Population
The initial population will be created by a weighted roulette wheel which
used to decide which period will be assigned for an selected event e based on the
scheduled events. This idea consists of 3 following steps:
• Step 1: Choosing randomly an event e from those events which are unassigned.
• Step 2: Decide which period will be assigned for that selected event by the
following fitness function (note that the chosen period must be legal for the
selected event)
numCommon + Size + 1
penalty + 1
(1)

j (with j is not equal to i) are fixed. Calculate the penalty caused by events
which are assigned to period i.
• If this pe nalty is lower than the average penalty then the probability of being
destroyed of that period is measured as follows.
P (disr upt) =
penalty + 0.2
2.averag e
(2)
16
Figure 2.5: The evolutionary operator
• If this penalty is greater than the average penalty, then there are 2 cases. Case
1, if the la st period was not destroyed then destroy the next period instead of
the current considered period. Case 2, if the last period was destroyed, then
destroy the current considered period.
After the destroyed periods are deciced, ea ch exam in these periods will
be considered to move to the first other legal period. Followed by Hill Climbing
method, one can hope that improvements will be made . This method uses a tech-
nique of calculating the penalty caused by scheduling a particular event to a partic-
ular method, given the other events are fixed. This has advantage when trying to
reschedule individual event, the improvement can be found in a fraction of time that
it would take to perform a full evaluation. The idea of this method can be described
as follows.
• Choose a period i in turn. For each event e in this period, schedule it to each
period in the timetable. If no hard violation is made, then calculate the penalty
caused by this arrangement.
• Choose the period which increase the total penalty the least.
• Try to schedule the unscheduled events.
17
In order to ascertain the value of a solution the evaluation function is appied
to it to calculate its fitness, and therefore its ability to survive in the total popula-

Timetabling Competition
3.1. Algori thm
1
Here is an algorithm given by an competitor in the second International
Timetabling competition. The algorithm consists of several phases. In the first
phase, a complete solution is found by using an Iterative Forward Search algorithm.
This algorithm make use of Conflict-based Statistics to prevent itself from cycling. In
the next phase, a local optimum is found by using a Hill Climbing algorithm. once a
solution can no longer be improved using this m ethod, the Great Deluge technique
is used. The Great Deluge algorithm is altered so that it allows some oscillations of
the bound that is imposed on the overall solution value. Optionally, Simulated An-
nealling can also be used between bound oscillations of the Great Deluge algorithm.
The search ends after a predetermined time limit ha s been reached. The best
solution found within that limit is returned.
3.1.1. Construction Phase
Initially, a complete solution is found using Iterative Forward Search algo-
rithm. It starts with all variables unassigned. In e ach iteration, an unassigned vari-
able will be chosen and assigned to a value in its domain. If any hard violation
is made, then the conflicting variables are unassigned. For example, if there is an-
other class in the selected room and selected time, that class will be unassigned. The
1
SeeT.Muller (2007) [5], p age 5-7 f or more precisely details.
19