October 15, 2002

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.

...more

View all episodes

By Ludwig-Maximilians-Universität München

11 ratings