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 assitance. 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 algorihtm extends this process by iteratively adding constraints to the CSP representation. A generalized random model of timetabling problems is proposed. This model creates a iverse range of problem instances, which are use to verify our search algorithm and identify the characteristics of difficult timetabling problems.
展开▼
