A constraint-based approach to high-school timetabling problems: a case study

This paper describes a case study on a general-purpose Constraint Relaxation Problem solver, COASTOOL. Using COASTOOL, a problem can be solved merely by declaring "what is the problem," without programming "how to solve it." The problem is solved by a novel method that generates a high-quality initial assignment using arc-consistency, and refines it using hill-climbing. This approach has been evaluated successfully by experiments with practical high-school timetabling problems in Japan. Consequently, COASTOOL is shown to be efficient at applications in high-school timetabling problems.