Local Search Techniques and Tools for Scheduling Problems

xii Introduction
Aims and Contributions
This work aims at studying and applying Local Search techniques for scheduling problems. The goal
of this thesis is threefold. First, we aim at studying and developing new Local Search algorithms by
means of new method combinations. Then, we plan to apply these algorithms for solving scheduling
problems of both academic and practical interest. At last, we intend to realize a general-purpose
software tool that will help us in the development and experimentation of the algorithms.
The goal of the first research consists in devising and investigating Local Search algorithms
based on the combination of different neighborhoods and techniques. We try to systematize the
approaches for algorithm combination in a common framework called Multi-Neighborhood Search.
We define a set of neighborhood operators that, given a collection of basic moves, automatically
create a new compound neighborhood and prescribe the strategies for its exploration. Furthermore,
we define also a solving strategy that combines algorithms based on different neighborhoods and
generalizes previous approaches.
We look carefully into the Multi-Neighborhood approach to examine the range of applicability
to scheduling problems. Specifically, we perform an extensive case study in the application of Multi-
Neighborhood techniques to the Course Timetabling problem, i.e., the problem of scheduling
a set of lectures for a set of university courses within a given number of rooms and time periods.
However, this approach has been used also in the solution of other problems throughout the
thesis. In fact, the second research line considers some other scheduling problems as testbeds. In
detail, the problems taken into account include:
• Examination Timetabling [114] is the problem of assigning examinations to time slots
in such a way that individuals (students and teachers) are not involved in more than one
examination at a time. The scheduling must consider also constraints about the availability
of resources (e.g., rooms or invigilators). The objective is to minimize students’ workload.
• min-Shift Design [128] is one of the stages of scheduling a workforce in an organization.
Once given a set of requirements for a certain period of time, along with constraints about
the possible start times and the length of shifts, the problem consists in designing the shifts
and in determining the number of employees needed for each shift.
As a by product of this investigation, we obtained solvers that compete fairly well with state-
of-the-art solvers developed ad hoc for the specific problem. Other problems have been taken
into account across our study, but the results on these problems are still preliminary and are only
summarized in this thesis.
The last research line concerns the design and the development of an Object-Oriented framework
as a general tool for the development of Local Search algorithms. Our goal is to obtain a system
that is flexible enough for solving combinatorial problems using a variety of algorithms based on
Local Search.
The framework should help the user deriving a neat conceptual scheme of the application and
it should support also the design and the rapid implementation of new compound techniques
developed along the lines explained above.
This research line has led to the implementation of two versions of the system, called Easy-
Local++ [39, 43, 44], which is written in the C++ language2. The first, abridged, version of
the framework has been made publicly available from the web page http://tabu.dimi.uniud.
it/EasyLocal. At the time of publication of this thesis, this version has been downloaded (and
hopefully used) by more than 200 users.
The complete version of EasyLocal++, instead, is currently available only on request and it
has been used for the implementation of all the Local Search algorithms presented in this thesis.
2The design and development of EasyLocal++ has been partly supported by the University of Udine, under
the grant “Progetto Giovani Ricercatori 2000”.
Introduction xiii
Thesis Organization
The thesis is subdivided into three main parts, which roughly correspond to the three goals out-
lined above. The first part illustrates the general topics of combinatorial optimization and the
Local Search domain. Furthermore, it contains the description of the Multi-Neighborhood Search
framework, which is one of the main contributions of this research.
Specifically, in Chapter 1 we present the basic concepts of combinatorial optimization and
scheduling problems and we introduce the terminology and the notation used throughout the
thesis. Chapter 2 describes in detail the basic Local Search techniques and some lines of research
that aim at improving the efficacy of Local Search. Chapter 3 concludes the first part of the thesis
and formally introduces the Multi-Neighborhood framework.
The second part of the thesis deals with the application of both basic and novel Local Search
techniques to selected scheduling problems. In Chapter 4 we present a comprehensive case study in
the application of Multi-Neighborhood techniques to the Course Timetabling problem. Chap-
ter 5 contains our research about the solution of the Examination Timetabling problem, while
Chapter 6 presents some results on the min-Shift Design problem. Preliminary results on other
problems, namely Job-Shop Scheduling and Resource-Constrained Scheduling, are pre-
sented in Chapter 7.
The third part of the thesis is devoted to the description of EasyLocal++, an Object-Oriented
framework for Local Search. In Chapter 8 we describe thoroughly the software architecture of the
framework and the classes that make up EasyLocal++. Finally, in Chapter 9 we present a case
study in the development of applications using EasyLocal++.
At the end of the thesis we draw some conclusions about this research. Furthermore, we describe
the lines of research that can be further investigated on the basis of the results presented in this
work.
IGeneral Concepts
1Introduction to Scheduling Problems
Combinatorial Optimization [106] is the discipline of decision making in case of discrete alterna-
tives. Specifically, combinatorial problems arise in many areas where computational methods are
applied, such as artificial intelligence, bio-informatics or electronic commerce, just to mention a few
cases. Noticeable examples of this kind of problems include resource allocation, routing, packing,
planning, scheduling, hardware design, and machine learning.
The class of scheduling problems is of specific interest for this study, since we apply the tech-
niques we have developed on this kind of problems. Essentially, a scheduling problem can be
defined as the problem of assigning resources to activities over a time period.
In this chapter we define the basic framework for dealing with scheduling problems and we
introduce the terminology and the notation used throughout the thesis.
1.1 Combinatorial Problems
The formal definition of the concept of problem is a very complex task. In fact, for formally
defining what a problem is, we should introduce concepts of formal languages that are beyond the
scope of this thesis. For this reason we resort to an intuitive definition and we define a problem
as a general and abstract statement of a question/answer relation, in which some elements are left
as a parameter. As an example, “can you compute the square root of a number n?” is a problem
according to this informal definition, because the sentence is a question with a yes/no answer
and the value of n is a parameter. Furthermore, we can define a problem instance as a specific
question/answer statement where all elements are specified. For example, “can you compute the
square root of 2?” is an instance of the previous problem. Problems can be grouped according to
similar question statements in homogeneous problem classes. In this thesis, we focus on a specific
class of problems that have a precise mathematical formulation, namely we deal with combinatorial
problems.
Combinatorial problems typically involve finding groupings, orderings, or assignments of a dis-
crete set of objects which satisfy certain conditions or constraints. These elements are generally
modeled by means of a combinatorial structure and represented through a vector of decision vari-
ables which can assume values within a finite or a countably infinite set. Within these settings, a
solution for a combinatorial problem is a value assignment to the variables that meets a specified
criterion.
The class of combinatorial problems can be subdivided into three main subclasses, that differ
by the goals they consider. The class of optimization problems is characterized by the aim of
finding a solution that optimizes a quality criterion and fulfills the given constraints. For decision
problems, the goal is again to find a solution that satisfies all the conditions. However, in this case
we accept all the solutions for which the quality measure is under a certain threshold. Finally, the
class of search problems simply aims at finding a valid solution, regardless of any quality criterion.
Looking at combinatorial problems from the computational complexity point of view, it has
been shown that most of the problems in this class (or the corresponding decision versions) are
4 1. Introduction to Scheduling Problems
g
h
c(a)
.
.
.
?
?
f(c)
d
c e
f
1
2
3
4
5
a
b
Figure 1.1: The family of Graph Coloring problems
NP -hard1. Therefore, unless P = NP, they cannot be solved to optimality in polynomial time.
For this reason there is much interest in heuristics or in approximation algorithms that lead to
near-optimal solutions in reasonable running times.
In the remaining of this section we formally present the problem classes outlined above, and
we provide an example of a family of combinatorial problems.
1.1.1 Optimization Problems
A combinatorial optimization problem is either a minimization or a maximization problem over
a discrete combinatorial structure. Optimality relates to some cost criterion, which measures the
quality of each element of the working set. An answer to the problem is one element of the working
set that optimizes the cost criterion.
Now we present a more formal definition of combinatorial optimization problems. Without loss
of generality, in the following we restrict to minimization problems. However, the modifications
for dealing with maximization problems are straightforward.
Definition 1.1 (Combinatorial Optimization Problem)
We define an instance pi of a combinatorial optimization problem Π as a triple 〈S,F , f〉, where S
is a finite set of solutions or answers, F ⊆ S is a set of feasible solutions, and f : S → R denotes
an objective function that assesses the quality of each solution in S.
The issue is to find a global optimum, i.e., an element x∗ ∈ F such that f(x∗) ≤ f(x) for all
x ∈ F .
In these settings, the set F is called feasible set and its elements feasible solutions, whereas the
elements of the set S \ F are called infeasible solutions. The relation x ∈ F is called constraint.
An example of a combinatorial optimization problem that will be used throughout the thesis
is the so-called min-Graph Coloring problem [57, Prob. GT4, page 191]. A pictorial represen-
tation of the problem is provided in Figure 1.1, whereas its statement is as follows:
Example 1.1 (The min-Graph Coloring problem)
Given an undirected graph G = (V,E), the min-Graph Coloring problem consists in finding
the minimum number of colors, needed to color each vertex of the graph, such that there is no
edge e ∈ E connecting two vertices that have been assigned the same color.
In this case an instance pi of the problem is defined as follows: any element of S represents
a coloring of G, hence it is a function c : V → {1, . . . , |V |}. The set of feasible solutions, F , is
1For a comprehensive reference on the classification of computational problems see, e.g., [57]
1.1. Combinatorial Problems 5
composed of the valid colorings only, i.e., the functions c such that c(v) 6= c(w) if (v, w) ∈ E. The
objective function simply accounts for the overall number of colors used by c, i.e., f(c) = |{c(v) :
v ∈ V }|.
The decision variables correspond to the vertices of the graph (i.e., the domain of c), and can
assume values in the set {1, . . . , |V |}.
1.1.2 Decision Problems
Given a combinatorial optimization problem, a family of related (and possibly easier) problems is
the class of so-called decision problems. In this case we are not interested in optimizing a cost
criterion, but we look for a solution for which the cost measure remains under a reasonable level.
The formal definition of this class of problems is as follows.
Definition 1.2 (Decision Problems)
Under the same hypotheses of combinatorial optimization problems, once fixed a bound k on the
value of the objective function, the decision problem 〈S,F , f, k〉 is the problem of stating whether
there exists an element x? ∈ F such that f(x?) ≤ k.
An example of a decision problem related to the Graph Coloring problem presented above
is the following:
Example 1.2 (The k-Graph Coloring problem)
The decision problem corresponding to the min-Graph Coloring problem is known as k -Graph
Coloring. In the decision problem formulation, we are interested in solutions where the number
of colors used by the function c is less than or equal to k. All the other components of the problem
remain unchanged.
It is worth noticing that a given optimization problem can be translated into a sequence of
decision problems. The translation strategy employs a binary search for the optimal bound k on
the cost function, and it introduces a small overhead that is logarithmic in the size of the optimal
solution value f(x∗).
1.1.3 Search Problems
The class of search problems differs from the other classes of combinatorial problems presented
so far, by the absence of a cost criterion. In fact, in this case we are only interested in finding a
solution that meets a set of prespecified conditions.
The formal definition of search problems is as follows.
Definition 1.3 (Search Problems)
Given a pair 〈S,F〉 where S is the set of solutions and F ⊆ S is the set of feasible solutions, a
search problem consists in finding a feasible solution, i.e., an element x¦ ∈ F .
Notice that a search problem can also be viewed as an instance of a decision problem, where
the cost function f(x) = c is constant.
The k -Graph Coloring problem can alternatively be viewed as an instance of a search prob-
lem, once fixed the possible colors to be used. Its statement is as follows.
Example 1.3 (The k-Graph Coloring problem as a Search Problem)
In the search formulation of k -Graph Coloring we restrict the colors to the set {0, . . . , k − 1}.
As in the previous cases, the set of variables corresponds to the set of vertices to be colored
(S = {v|v ∈ V }) and the feasible set is {c : V → {0, . . . , k − 1}|c(u) 6= c(v)∀(u, v) ∈ E}.
6 1. Introduction to Scheduling Problems
1.2 Constraint-based Formulation
As mentioned above, usually the combinatorial structure S and the feasible set F can be repre-
sented, respectively, through a vector of decision variables and by means of a set of mathematical
relations among the variables. In such cases, we can formulate the combinatorial problem exploiting
the concepts of constraint satisfaction (or optimization) problems.
Definition 1.4 (Constraint Satisfaction Problem)
A constraint satisfaction problem is defined by means of a triple 〈X ,D, C〉, where X is a set of n
variables, and for each variable xi ∈ X there is a corresponding (finite) set Di ∈ D that represents
its domain. The set C is a set of constraints, i.e., relations that are assumed to hold between the
values of the variables.
The problem is to assign a value d?i ∈ Di to each variable xi in such a way that all constraints
are fulfilled, i.e., d¯? = (d?1, . . . , d?n) ∈ cj for each cj ∈ C. We call the assignment d¯? a feasible
assignment.
It is easy to recognize that this definition is an instance of the Definition 1.3, where the role
of variables, domains and constraints is made explicit. In detail, S = D1 × . . . × Dn and F is
intensionally defined by the constraint relations, i.e., d¯ = (d1, . . . , dn) ∈ F if and only if, for each
i = 1, . . . , n and each constraint cj , di ∈ cj .
In order to represent the combinatorial optimization problems in a constraint satisfaction formu-
lation we must again take into account a cost criterion for evaluating the quality of the assignments.
The formal definition of optimization problems in this formulation is as follows:
Definition 1.5 (Constrained Optimization Problem)
Under the same hypotheses of the constraint satisfaction problem, a constrained optimization
problem 〈X ,D, C, f〉 consists in finding a feasible assignment d¯∗ = (d∗1, . . . , d∗n) that optimizes a
cost function f : D1 × · · · ×Dn → R.
Furthermore, for the definition of the decision problem within the constraint satisfaction frame-
work, we add a bound k to the objective function. This definition is straightforward and we do
not provide the details of its statement.
In the following chapters we will indifferently use the combinatorial and the constrained satis-
faction formulation of the problems.
1.3 Search Paradigms
A noticeable class of computational approaches for solving hard combinatorial problems is essen-
tially based on search algorithms. The basic idea behind these approaches is to iteratively generate
and evaluate candidate solutions.
The search approaches can be mainly divided into two broad categories depending on the strat-
egy used to provide a solution. We can distinguish between constructive and selective techniques,
as we are going to describe.
The so-called constructive methods deal with partial assignments and iteratively build the
solution in a step-by-step manner by carefully assigning a value to a decision variable. The selection
is driven both by the objective function and by the requirement to come to a feasible solution at
the end of the process. Among these techniques we may further distinguish between exhaustive
techniques, which involve some kind of backtracking (e.g., Branch & Bound [106]), and non-
exhaustive ones like ad hoc heuristic greedy methods (e.g., the “most-difficult-first” heuristic [12]).
Example 1.4 (Constructive algorithms for k-Graph Coloring)
For example, in the case of the k -Graph Coloring problem a complete constructive algorithm
starts from a solution where all the vertices are unassigned and proceeds iteratively in levels until
1.3. Search Paradigms 7
a feasible coloring has been found. A state of the search, for this algorithm, is a partial function
c : V → {0, . . . , k − 1}.
At each level i the algorithm selects a still uncolored vertex vi and tries to assign it a color
from the set {0, . . . , k − 1}. If no color can be assigned to vi without violating the constraint2
∀u ∈ adj(vi) c(u) 6= c(vi), then the assignment made at the previous level is undone and a new
assignment for the vertex vi−1 is tried.
Again, if no new feasible assignment at level i− 1 can be found, the algorithm “backtracks” at
level i− 2 and so on. Conversely, once the algorithm reaches a complete assignment the search is
stopped and the solution is returned.
The worst-case time performance of this algorithm is clearly exponential in the size of the graph.
Nevertheless, it is possible to obtain reasonable running times by employing a clever ordering of
the sequence of vertices explored. For example, one of the best constructive algorithms for Graph
Coloring is the DSATUR algorithm by [12] which is based on the aforementioned schema and
employs a dynamic ordering of the vertices based on their constrainedness.
If we remove the backtracking mechanism from the proposed algorithm we obtain a so-called
heuristic search technique, which, in turn, gives rise to an incomplete method.
The other class of search approaches is composed of the category of selective methods. These
approaches are based on the exploration of a search space composed of all the possible complete
assignments of values to the decision variables, including the infeasible ones. For this reason these
methods are also called iterative repairing techniques. Among others, the Local Search paradigm,
which is the topic of this thesis, belongs to this family of methods. This paradigm is described in
more detail in Chapter 2. We now provide a sketch of a selective algorithm for k -Graph Coloring
based on Local Search. A complete description of the algorithm is provided in Chapter 9.
Example 1.5 (A selective algorithm for k-Graph Coloring)
A selective algorithm for k -Graph Coloring iteratively explores a search space made up of the
complete functions c : V → {0, . . . , k − 1}.
Starting from a randomly generated solution, at each step i of the search, the algorithm tries to
repair one violated constraint by changing the color assignment for one vertex vi, i.e., it modifies
the value of the function c on vi.
The strategy for selecting the candidate vertex at each step is inspired by different philosophies,
and depends on the technique at hand. We refer to the next chapter for a comprehensive discussion
of some possible strategies.
However, regardless of the selection strategy employed, it is clear that this algorithm may, in
principle, not come to a feasible solution (for example, because the candidate selection strategy
indefinitely cycles by choosing always the same vertices). For this reason, the described method is
incomplete. Nevertheless, the techniques based on this schema are very appealing because of their
effectiveness in practice.
As mentioned, in this thesis we are dealing with incomplete search techniques, most of the times
characterized also by some randomized element. For this reason, the performance evaluation of
the algorithms is not a simple task, since the well established worst-case analysis is not applicable
with these techniques. Moreover, all the decision versions of the problems taken into account in
this work are at least NP-complete, therefore we already know the theoretical performance of the
algorithms in the worst case, but rather we aim to empirically look into their behavior on a set of
benchmark instances.
The experimental analysis is performed by running the algorithms on a set of instances for a
number of trials, recording some performance indicators (such as the running time and the quality
of the solutions found). Then a measure of the algorithms behavior can be obtained by employing
a statistical analysis over the collected values.
2We use the notation adj(v) to denote the set of vertices adjacent to v, i.e., adj(v) = {u|(u, v) ∈ E}
8 1. Introduction to Scheduling Problems
Here we have just sketched the general lines of the methodology employed, but the experi-
mental analysis of heuristics is itself a growing research area. Johnson [75] recently tries to fill
the gap between the theoretical analysis and the experimental study of algorithms. On the latter
subject, among others, Taillard [125] recently proposes a precise methodology for the comparison
of heuristics based on non-parametric statistical tests.
1.4 Scheduling Problems
Now we move to the description of an important class of combinatorial problems, which has been
chosen as the applicative domain for this research. We present the class of scheduling problems,
which deal with the issue of associating one or several resources to activities over a certain time
period, subject to specific constraints (we refer to [110] for a recent comprehensive book on the
subject).
Scheduling problems arise in several different domains as production planning, personnel plan-
ning, product configuration, and transportation. Concrete problems in these domains are, for
example, manufacturing production scheduling, airport runways scheduling, and workforce assign-
ment.
The goal is to optimize some objective function depending on the applicative domain at hand.
For example in manufacturing environments the function to optimize is usually the total processing
time, i.e., the time elapsed since the beginning of the first task till the end of the last one.
The discipline of scheduling in manufacturing started at the beginning of the 20th century
with the pioneering works of Henry Gantt, after the theory of scientific management of Frederick
Winslow Taylor.
Since the early 1950s [72, 79, 121], over the years the theory and application of scheduling
has grown into an important field of research and several instances of scheduling problems have
been described in the literature (see [91] for a review). We will discuss some of those concrete
instances throughout this thesis. In the following, instead, we provide a formal statement of a
general scheduling model.
Definition 1.6 (General Scheduling Problem)
We are given a set of n tasks T = {T1, . . . , Tn}, a set of m processors (or machines) P =
{P1, . . . , Pm}, and a set of q resources R = {R1, . . . , Rq}.
Each task Ti ∈ T has associated an integer measure of its processing time τi, and we represent
its starting time through the integer decision variable σi (i.e., we deal with discrete time points
called time slots) and its assigned processor Pj by means of the binary decision variables pij (that
is pij = 1 if and only if task Ti is scheduled on processor Pj).
The general scheduling problem consists in assigning a starting time σi and a processor Pj to
each task Ti. The assignment 〈σ¯, p¯〉 is called a schedule. We require that the schedule meets the
following conditions.
(1) Respected deadlines: for each task Ti there is a deadline time di which indicates that the
task must have completed execution di time units after the beginning of the first task. Without
loss of generality, we assume that the first task begins at the time slot 0. This way, the absolute
deadline of each task can be expressed as σi + τi ≤ di for all i = 1, . . . , n.
(2) Processor compatibility: the tasks cannot be executed on all the variety of processors but
only on a specific subset of them. More formally, there is a binary compatibility matrix Cij
that states whether or not task Ti can be executed on processor Pj . This condition can be
expressed as: pij = 1 only if Cij = 1.
(3) Mutual exclusion: no pair of tasks (Ti, Ti′) can be executed simultaneously on the same
processor Pj . This is usually called disjunction constraint and is expressed as pij = pi′j ⇒
σi + τi ≤ σi′ ∨ σi′ + τi′ ≤ σi.
1.4. Scheduling Problems 9
(4) Resource capacity: there is an integer valued matrix Aik that accounts for the amount of
the resource Rk needed for each task Ti. For each resource Rk, at most bk units are available
at all times. Thus, at each time slot, and for each resource Rk, the amount of Rk allocated to
the tasks currently executed must not exceed the overall bound bk.
(5) Schedule order: there is a precedence relation (T ,≺) on the set of tasks such that Ti ≺ Ti′
means that Ti is a prerequisite for Ti′ . In other words, Ti must complete its execution before
Ti′ starts its own. This corresponds to the condition σi + τi ≤ σi′ .
In addition to the satisfaction of the above constraints, we require also that an objective function
is optimized. A natural choice for this function is to account for the overall finishing time (called
makespan). In this case the function can be defined as f(σ¯, p¯) = max{σi + τi|i = 1, . . . , n}.
Alternative formulations of the objective function include flow time, lateness, tardiness, ear-
liness or weighted sums of these criteria to reflect the relative importance of tasks. We do not
define these criteria here but we refer again to [110] for a formal definition of these concepts. The
problem then becomes the following:
The proposed model makes the assumption that the tasks are atomic and there is no possibility
of preemption, i.e., once a task is allocated to a processor, it must be entirely performed and no
interleaving with other tasks is allowed. However, we may relax this requirement and allow the
preemption of tasks.
Definition 1.7 (General Preemptive Scheduling Problem)
In the same settings as for the general scheduling problem we define a preemptive scheduling
problem by allowing a task Ti to be split into any arbitrary number of subtasks ti1 , . . . , tid that
must be executed in sequence.
In other words, the subdivision of each task Ti induces a total order among its subtasks:
tih ≺ tih+1. Furthermore, we must add the condition that the sum of the subtask durations equals
exactly the processing time of the whole task, i.e., ∑dh=1 τih = τi.
An important instance of the scheduling model, that conceptually stands between the non-
preemptive and the preemptive scheduling, is the so-called shop scheduling described in the fol-
lowing example.
Example 1.6 (The Family of Shop Scheduling problems)
The class of shop scheduling problem is characterized by a fixed subdivision of a task into subtasks.
The subtasks are a priori determined in terms of their number and duration.
In the shop scheduling settings, the whole coarse-grain task is called job, and is compound of a
totally ordered set of operations. For this problem family, each operation is atomic, whereas a job
can be preempted.
Noticeable instances of this class of problems are Job-Shop, Flow-Shop and Open-Shop
scheduling, outlined in the following.
The Job-Shop Scheduling problem just consists in an instantiation of the scheduling problem
within the shop environment. The only difference is that the compatibility matrix has only one
non-zero entry for each task, i.e., a task must be assigned to a single and given processor.
The Flow-Shop problem differs from Job-Shop by the fact that we schedule the jobs in
a pipeline. That is, the processors are arranged in a ordered sequence, and each job should be
completed on a given processor before being assigned to the next one.
Finally, in the Open-Shop problem the precedence relation is dropped. Specifically, neither
the order of jobs, nor the order of the tasks within each job are determined.
In Figure 1.2 we report an example of a solution for a generic shop scheduling problem, repre-
sented as a processor schedule Gantt chart. This kind of schedule visualization is quite common
in practice.
10 1. Introduction to Scheduling Problems
time
p
r
o
c
e
s
s
o
r
s
t 21 t 12 t 32
t 31 t 22 t 13
t 11 t 23 t 33p3
p2
p1
t 12σ(     )
t 33σ(     )
j 1
j 2
j 3
t 23τ(     )
makespan
Figure 1.2: A Gantt chart representation of a schedule for a Shop scheduling problem
The diagram should be read as follows. The X axis represents the time scale and each time
slot is delimited by means of vertical dashed lines. On the Y axis are reported the processors
schedules, each on a separate row. On each row there are a set of bars that represent the set of
tasks scheduled on that processor. Each bar spans for a variable length, which is equal to the
length of the task. The arrangement of the tasks on a processor line is made accordingly to their
starting times σ.
As a final remark, we want to emphasize that in this thesis we deal with deterministic schedul-
ing, which means that all the entities of the scheduling problem are known in advance. Another
class of scheduling problems, that is not taken into account in this thesis, is the class of stochastic
scheduling. This class of problems is characterized by the presence of uncertainty in some schedul-
ing element. For example, the processing times in some manufacturing environments cannot be
completely predicted in advance, but are subject to a probability distribution.
1.5 Timetabling Problems
An interesting subclass of scheduling problems is the category of timetabling problems, which is
characterized by the fact that the precedence relation (T ,≺) is empty. This means that, in this
case, the problem is to schedule the tasks regardless of their mutual time assignment, but looking
only at the constraints for the assignment of resources. Furthermore, in most cases, timetabling
problems deal with tasks having unitary length, i.e., each task is uniquely associated to a single
time slot.
Even the terminology for this problem class reflects these changes. In fact, we refer to events
and periods instead of, respectively, tasks and processors. Moreover, the basic kind of resources
are usually individuals who have to attend to events.
We present now the basic version of the timetabling problem, also known as periods/events
timetabling.
Definition 1.8 (General Timetabling Problem)
Given a set of n events E = {e1, . . . , en}, a set of m resources R = {r1, . . . , rm}, a set of p periods
P = {1, . . . , p}, and an m×n matrix of resource requirements ρij , the general timetabling problem
consists in assigning a period τi to each event ei in such a way that the following conditions are
met:
(1) no individual resource is required to be present for two or more events at the same time, i.e.,
τi = τi′ ⇔ ρij 6= ρi′j (j = 1, . . . ,m);
1.5. Timetabling Problems 11
(2) there must be sufficient other resources to service all the events at the times they have been
scheduled.
The assignment τ is called a timetable.
The general timetabling problem can easily be modeled within the already presented Graph
Coloring framework. The graph encoding is as follows: each event is associated to a vertex of the
graph, and there is an edge between two vertices if they clash, i.e., the events cannot be scheduled
in the same period because at least one individual has to attend both of them. Then, periods are
regarded as colors, and the scheduling of events to periods is simply a coloring of the graph.
Considerable attention has been devoted to automated timetabling during the last forty years.
Starting with [67], many papers related to automated timetabling have been published in conference
proceedings and journals. In addition, several applications have been developed and employed with
good success.
Example 1.7 (The family of Educational Timetabling problems)
In this thesis we focus on the class of Educational Timetabling problems. These kind of
problems consists in scheduling a sequence of events (typically lectures or examinations), involving
teachers and students, in a prefixed period of time.
The schedule must satisfy a set of constraints of various types, which involve, among others,
avoiding the overlap of events with common participants, and not excessing the capacity of rooms.
Usually the goal is to obtain solutions that minimize student and teacher’s workload.
A large number of variants of Educational Timetabling problems have been proposed in
the literature, which differ from each other by the type of events, the kind of institution involved
(university or school) and the type and the relative influence of constraints. Noticeable examples
of this class of problems are School Timetabling, Course Timetabling and Examination
Timetabling. The latter two problems are discussed in detail in the applicative part of the thesis
The common ground of these problems is that they all are combinatorial problems (search or
optimization ones), are NP -hard, and are subject to similar types of constraints (overlap, availabil-
ity, capacity, etc.). Additionally, almost all of them have been recognized to be genuinely “difficult
on the average” in practical real-life cases.
For this reason, such problems have not been addressed in a complete and satisfactory way yet,
and are still a matter of theoretical research and experimental investigation.