Search Strategy for Constraint-Based Class–Teacher Timetabling

The paper deals with a scheduling problem: the computation of class–teacher timetables. Two cases are taken into consideration: high school problems and university department problems. The timetable was constructed using constraint programming techniques. The timetabling needs to take into account a variety of complex constraints and use special-purpose search strategies. The concurrent constraint language Mozart/Oz was used, which provides high-level abstraction, and allows the expression of complex constraints and the creation of a complicated, custom-tailored distribution strategy. This strategy, consisting of six stages, was crucial for finding a feasible solution. The space-based search allows the incorporation of local search into constraint programming; this is very useful for timetable optimization. Technical details and results of the implementation are presented.