(PDF) Don Banks, Peter van Beek, and Amnon Meisels. A heuristic incremental modeling approach to course timetabling. Proceedings of the Twelfth Canadian Conference on Artificial Intelligence, Vancouver, British Columbia, 16-29, June, 1998.


The general timetabling problem is an assignment of activities to fixed time intervals, adhering to a predefined set of resource availabilities. Timetabling problems are difficult to solve and can be extremely time-consuming without some computer assistance. In this paper the application of constraint-based reasoning to timetable generation is examined. Specifically, we consider how a timetabling problem can be represented as a Constraint Satisfaction Problem (CSP), and propose an algorithm for its solution which improves upon the basic idea of backtracking. Normally, when a backtracking routine fails to find a solution, there is nothing of value returned to the user; however, our algorithm extends this process by iteratively adding constraints to the CSP representation. A generalized random model of timetabling problems is proposed. This model creates a diverse range of problem instances, which are used to verify our search algorithm and identify the characteristics of difficult timetabling problems.

Return to Publications