Constraint-based timetabling : a case study

Abstract

This paper reports a case study in applying constraint satisfaction techniques to university and school timetabling. It involves the construction of a substantial, carefully specified, fully tested and fully operational system. The software engineering aspect of constraint satisfaction is emphasized. Constraint satisfaction problems are expressed in a language more familiar to the formal software engineering community. This brings constraint satisfaction one step closer to formal specification, program verification and transformation; issues extensively studied in software engineering. In problem formulation, explicit domain constraints and heuristic information are made explicit. Moreover, the user's needs are considered more closely; for instance, when the program fails to find a solution, useful indications are produced to help in relaxation or reformulation of the problem.