Models and Algorithms for School Timetabling

In constraint programming, combinatorial problems are specified
declaratively in terms of constraints. Constraints are relations
over problem variables that define the space of solutions by
specifying restrictions on the values that variables may take
simultaneously. To solve problems stated in terms of constraints,
the constraint programmer typically combines chronological
backtracking with constraint propagation that identifies infeasible
value combinations and prunes the search space. In recent years,
constraint programming has emerged as a key technology for
combinatorial optimization in industrial applications. In this
success, global constraints have been playing a vital role. Global
constraints are carefully designed abstractions that, in a concise
and natural way, allow to model problems that arise in different
fields of application. For example, the alldiff constraint allows
to state that variables must take pairwise distinct values; it has
numerous applications in timetabling and scheduling. In school
timetabling, we are required to schedule a given set of meetings
between students and teachers s.t. the resulting timetables are
feasible and acceptable to all people involved. Since schools
differ in their educational policies, the school-timetabling
problem occurs in several variations. Nevertheless, a set of
entities and constraints among them exist that are common to these
variations. This common core still gives rise to NP-complete
combinatorial problems. In the first place, this thesis proposes to
model the common core of school-timetabling problems by means of
global constraints. The presentation continues with a series of
operational enhancements to the resulting problem solver which are
grounded on the "track parallelization problem" (TPP). A TPP is
specified by a set of task sets which are called "tracks". The
problem of solving a TPP consists in scheduling the tasks s.t. the
tracks are processed in parallel. We show how to infer TPPs in
school timetabling and we investigate two ways of TPP propagation:
On the one hand, we utilize TPPs to down-size our models. On the
other hand, we propagate TPPs to prune the search space. To this
end, we introduce the TPP constraint along with a suitable
constraint solver for modeling and solving TPPs in a finite-domain
constraint programming framework. To investigate our problem
solvers' behavior, we performed a large-scale empirical study. When
designing the experiment, the top priority was to obtain results
that are both reliable from a statistical point of view and
practically relevant. To this end, the sample sizes have been
chosen accordingly - for each school, our problem set contains 1000
problems - and the problems have been generated from detailed
models of ten representative schools. Our timetabling engine
essentially embeds network-flow techniques and value sweep pruning
into chronological backtracking.