A genetic algorithm approach to a nurse rerostering problem

The nurse rerostering problem occurs when one or more nurses cannot work in shifts that were previously assigned to her or them. If no pool of reserve nurses exists to replace those absent, then the current roster must be rebuilt. This new roster must comply with the labour rules and institutional constraints. Moreover, it must be as similar as possible to the current one. The present paper describes constructive heuristics, besides several versions of genetic algorithms based on specific encoding and operators for sequencing problems applied to the nurse rerostering problem, defined with hard constraints. In the genetic algorithms described, each individual in the population is associated with a pair of chromosomes, representing permutations of tasks and nurses. Those permutations are used as input to a procedure that generates rosters. The fitness of individuals is given by the similarity between the roster generated from the permutations and the current one. The authors developed several versions of the genetic algorithm, whose difference lay in the encoding of permutations and in the genetic operators used for each encoding. These heuristics were tested with real data from a Lisbon hospital and yielded good quality solutions. Scope and purpose The research reported is part of a project designed to develop a system for the management of nurse schedules for implementation in Portuguese public hospitals. The specific problem of rebuilding nurse schedules is addressed when unexpected staff absences arise. The complexity of the problem led the authors to design heuristic procedures. The tests performed so far with real data have shown that the algorithms attain good quality solutions at a computing time within the bounds stipulated by the hospital. (c) 2005 Elsevier Ltd. All rights reserved.