Applying constraints to the timetable problem
Patrick James Coston · 1992
Assignment of course sections to classrooms is a complex task because there are numerous constraints io satisfy. For example, professors who are teaching a course will ofteil specify a preference for a certain time, day, building and/or room. These preferences are translated into constraints using a constraint language developed for the scheduling domain. These constraints allow the user to specify specific constraints on a course thus limiting when and where it can be scheduled. This thesis looks at some of the successful algorithms which have been applied to the timetable problem like Monte Carlo, Simulated Annealing, Integer Programming, Heuristic, Expert Systems and Constraint Directed. The strengths and weaknesses of these algorithms is discussed. This thesis' investigates constraint satisfaction, constraint limiting search, constraint propagation, constraint representation, constraint ordering, constraint relaxation, constraint directed searching, meta-constraints and dependency directed backtracking. Examples are given of the uses of these concepts like map coloring, cross-word puzzle creating, furniture layout design and simple image recognition. It is then shown how these concepts are then applied to the timetable problem.