Models and algorithms for school timetabling [Elektronische Ressource] : a constraint programming approach / von Michael Marte

Models and Algorithms forSchool Timetabling –A Constraint-Programming ApproachDissertationan der Fakultat¨ fur¨ Mathematik, Informatik und Statistikder Ludwig-Maximilians-Universitat¨ Munchen¨vonMichael Martevorgelegt am 5. Juli 2002Berichterstatter waren Prof. Dr. Franc ¸ois Bry und Prof. Dr. Klaus U. Schulz.Das Rigorosum fand am 15. Oktober 2002 statt.AbstractIn constraint programming [JM94, Wal96, FA97, MS98], combinatorial prob-lems are specified declaratively in terms of constraints. Constraints are relationsover problem variables that define the space of solutions by specifying restrictionson the values that the variables may take simultaneously. To solve problems statedin terms of constraints, the constraint programmer typically combines chrono-logical backtracking with propagation that identifies infeasible valuecombinations and prunes the search space accordingly.In recent years, constraint programming has emerged as a key technology forcombinatorial optimization in industrial applications. In this success, global con-straints have been playing a vital role. Global constraints [AB93] are carefullydesigned abstractions that, in a concise and natural way, allow to model problemsthat arise in different fields of application. For example, the alldiff constraint[Reg94]´ allows to state that variables must take pairwise distinct values; it hasnumerous applications in timetabling and scheduling.