Models and Algorithms for School Timetabling - A Constraint-Programming Approach

摘要: In constraint programming [JM94, Wal96, FA97, MS98], combinatorial problems are specified declaratively in terms of constraints. Constraints relations over problem variables that define the space solutions by specifying restrictions on values may take simultaneously. To solve stated constraints, programmer typically combines chronological backtracking with propagation identifies infeasible value combinations and prunes search accordingly. recent years, has emerged as a key technology for optimization industrial applications. this success, global constraints have been playing vital role. Global [AB93] carefully designed abstractions that, concise natural way, allow to model arise different fields application. For example, alldiff [Reg94] allows state must pairwise distinct values; it numerous applications timetabling scheduling. school timetabling, we required schedule given set meetings between students teachers s.t. resulting timetables feasible acceptable all people involved. Since schools differ their educational policies, school-timetabling occurs several variations. Nevertheless, entities among them exist common these This core still gives rise NP-complete problems. first place, thesis proposes schooltimetabling means The presentation continues series operational enhancements solver which grounded track parallelization (TPP). A TPP is task sets called tracks. solving consists scheduling tasks tracks processed parallel. We show how infer TPPs investigate two ways propagation: On one hand, utilize down-size our models. other propagate prune space. end, introduce tpp along suitable modeling finite-domain framework.