Combining Constraint Satisfaction and Local Improvement Algorithms to Construct Anaesthetists’ Rotas

Practical Approaches to Scheduling and Planning

Volume

Practical Approaches to Scheduling and Planning

Contents

A system is described which has been built to compile weekly rotas for the anaesthetists in a large hospital. The rota compilation problem is an optimization problem (the number of tasks which cannot be assigned to an anaesthetist must be minimized) and has been forraulated as a constraint satisfaction problem. The forward checking algorithm is used to find a feasible rota, but because of the size of the problem, it cannot find an optimal (or even a good enough) solution in an acceptable time. Instead, an algorithm has been devised which makes local improvements to a feasible solution. The algorithm makes use of the constraints as ezpressed in the CSP to ensure that feasibility is maintained, and produces very good rotas which are being used by the hospital involved in the project. It is argued that formulation as a constraint satisfaction problem may be a good approach to solving discrete optimization problems, even if the resulting CSP is too large to be solved ezactly in an acceptable time. A CSP algorithm may be able to produce a feasible solution which can then be improved, giving a good, if not provably optimal, solution.