Using heuristics for constraint satisfaction problems in scheduling

Scheduling problems such as job shop scheduling and timetabling can be expressed as constraint satisfaction problems (CSPs) and so are, at least in theory, amenable to solution by standard constraint satisfaction algorithms. Unfortunately, CSPs (and most scheduling problems) are in general NP-complete. Hence we should expect the time required to solve a CSP to increase exponentially with the size of the problem, so that in practice there will be a limit to the size of problem which can be solved in a reasonable time. One approach to tackling a problem which is too large to be solved exactly by a standard search algorithm is to devise algorithms which abandon the idea of a systematic search of the entire search space. Typically these algorithms form an initial solution which is deficient in some way (infeasible or suboptimal), and attempt to improve it by making local changes or repairs. The algorithm moves through a sequence of solutions, each of which is a neighbour, in some sense, of the preceding one. Several papers have described repair-based heuristic methods of this kind for constraint satisfaction and related problems. The author describes a heuristic of the same type, originally developed as part of the ROSA system (B.M. Smith, S. Bennett, 1992), which produces weekly anaesthetists´ rotas for a hospital anaesthetics department