Marte, Michael (2002): Models and Algorithms for School Timetabling: A ConstraintProgramming Approach. Dissertation, LMU München: Faculty of Mathematics, Computer Science and Statistics 

PDF
Marte_Michael.pdf 617kB 
Abstract
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 schooltimetabling 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 NPcomplete combinatorial problems. In the first place, this thesis proposes to model the common core of schooltimetabling 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 downsize 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 finitedomain constraint programming framework. To investigate our problem solvers' behavior, we performed a largescale 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 networkflow techniques and value sweep pruning into chronological backtracking.
Item Type:  Thesis (Dissertation, LMU Munich) 

Keywords:  constraint programming, school timetabling, combinatorial optimization 
Subjects:  600 Natural sciences and mathematics 600 Natural sciences and mathematics > 510 Mathematics 
Faculties:  Faculty of Mathematics, Computer Science and Statistics 
Language:  English 
Date Accepted:  15. October 2002 
Persistent Identifier (URN):  urn:nbn:de:bvb:199369 
MD5 Checksum of the PDFfile:  cd53e607edeb0ef0cfc134277d1eab0d 
Signature of the printed copy:  0001/UMC 12989 
ID Code:  936 
Deposited On:  29. Apr 2003 
Last Modified:  16. Oct 2012 07:34 