A Constraint-Based Approach to High-School Timetabling Problems: A Case Study

Planning and Scheduling

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 12

Scheduling

This paper describes a case study on a general-purpose Constraint Relaxation Problem solver, COASTOOL. Using COASTOOL,~ 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.