Combining constraint satisfaction and local improvement algorithms to construct anaesthetists´ rotas

A system for compiling weekly rotas for anaesthetists in a large hospital is described. The rota compilation problem is an optimization problem where the number of tasks which cannot be assigned to an anaesthetist must be minimized and is formulated as a constraint satisfaction problem (CSP). The forward checking algorithm is used to find a feasible rota, but, because of the size of the problem, it cannot find an optimal solution in an acceptable time. Instead, an algorithm is devised which makes local improvements to a feasible solution. The algorithm makes use of the constraints as expressed in the CSP to ensure that feasibility is maintained, and it produces very good rotas which are being used by the hospital involved in the project