Nurse Rostering with Genetic Algorithms

Uwe Aickelin

TL;DR

This paper tackles the complex problem of nurse rostering using a family of enhanced genetic algorithms (GAs). By addressing the limitations of standard GAs with specialized operators, dynamic penalty weights, and sub-population structures, the authors achieve significant improvements in both the feasibility and quality of generated nurse schedules, rivaling existing tabu search methods.

What Problem Does This Paper Address?

The paper addresses the challenging task of creating weekly nurse rosters for a major UK hospital. This isn't just about filling slots; it involves balancing numerous constraints. These include ensuring minimum staff coverage across three daily shifts, respecting individual nurses' working contracts and preferences (like avoiding unpopular shifts), and maintaining fairness. Additionally, qualifications and special conditions for senior staff must be considered. The core difficulty lies in the combinatorial complexity and the need to satisfy both "hard" constraints (like minimum staffing) and "soft" constraints (like nurse preferences) simultaneously, a task that traditional, unmodified genetic algorithms struggle with.

Methods

The authors start with a classical genetic algorithm framework, employing rank-based selection, n-point crossover, and single-bit mutation. However, they quickly identify its shortcomings in handling the complex constraints of nurse rostering. To overcome these, they introduce a series of enhancements:

  • Parameter Optimization and Dynamic Weights: They explore tuning GA parameters and, crucially, implement dynamic penalty weights for constraint violations. This means the penalty for infeasible solutions adjusts based on the quality of the best solution found so far, pushing the population towards feasible regions.
  • Sub-Population, Special Crossover, and Migration: Recognizing the problem's "epistatic" nature (where the interaction between genes is more important than individual genes), they introduce a sub-population structure. Different sub-populations focus on specific nurse grades, each with its own fitness function. A "main" population then combines insights from these sub-populations. They also develop a "grade-based" crossover that respects nurse qualifications and combine it with uniform crossover. Migration allows individuals to move between sub-populations, preventing information loss.
  • Incentives and Local Search/Repair: To address day/night shift imbalances, they introduce incentives for balanced solutions and disincentives for unbalanced ones. This is coupled with a local search/repair mechanism that refines balanced solutions.
  • Delta Coding and Swaps: Delta coding is used to seed the GA with populations around a previously found good solution, potentially speeding up convergence. Shift swaps are introduced as a mechanism to improve solution quality by exchanging shifts between nurses with similar qualifications, provided it improves overall satisfaction.

Datasets

The paper states that results are based on "several months' real data" from a major UK hospital. No specific benchmark datasets are mentioned, nor are any new benchmarks introduced.

Key Insights and Ideas

  • Epistacity is a Major Hurdle: The paper highlights that the nurse rostering problem exhibits significant epistacity, meaning simple combinations of good individual assignments don't necessarily lead to a good overall schedule. This is exacerbated by the penalty function approach.
  • Standard GAs Aren't Enough: A "basic GA cannot solve the problem." The real power comes from tailoring the GA to the problem's specific structure and constraints.
  • Dynamic Penalties are Crucial: Simply increasing penalties for constraint violations doesn't guarantee better solutions. Dynamically adjusting these penalties based on the current solution quality is key to guiding the search effectively.
  • Sub-populations for Specialization: Breaking down the problem into specialized sub-populations (e.g., by nurse grade) allows for more focused optimization and better handling of grade-specific constraints.
  • Local Search/Repair Complements GA: While GAs are good at global exploration, local search and repair operators are effective at fine-tuning solutions and resolving specific issues like shift imbalances.

Key Results

The paper reports significant improvements through the various enhancements:

  • The enhanced GA family was able to "compete with a tabu search approach currently employed at the hospital."
  • With sub-populations, crossover, and migration, "feasibility and solution quality more than doubled."
  • Incentives and local search/repair "immediately improve solution quality" and further enhance it when combined.
  • The initial implementation achieved only 28.6% feasible solutions with an average objective value of 38.2, whereas the enhanced methods significantly improved these metrics.

Limitations and Future Work

  • Limitations:
    • The paper notes that delta coding "does not work for a discontinuous solution space" and can have "problems with discrete variables."
    • Determining the optimal size of the hypercube for delta coding and whether a local optimum has been found is difficult.
  • Parameter/strategy optimization of the basic GA had "little effect," underscoring the need for specialized operators.
  • Future Work:
    • Changes to the GA: Explore "Intelligent Mutation" and "Dynamic Parameters."
    • Changes to the Coding: Consider "order based coding," keep the GA simple, and leverage problem-specific information within the decoder. They also question whether to "Concentrate on day/night problem?"
    • Apply to Other Problems: Extend the modified GA to "Generalised assignment problems" and "Other multiple choice problems."

Summary updated

Abstract

In recent years genetic algorithms have emerged as a useful tool for the heuristic solution of complex discrete optimisation problems. In particular there has been considerable interest in their use in tackling problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle constraints and successful implementations usually require some sort of modification to enable the search to exploit problem specific knowledge in order to overcome this shortcoming. This paper is concerned with the development of a family of genetic algorithms for the solution of a nurse rostering problem at a major UK hospital. The hospital is made up of wards of up to 30 nurses. Each ward has its own group of nurses whose shifts have to be scheduled on a weekly basis. In addition to fulfilling the minimum demand for staff over three daily shifts, nurses' wishes and qualifications have to be taken into account. The schedules must also be seen to be fair, in that unpopular shifts have to be spread evenly amongst all nurses, and other restrictions, such as team nursing and special conditions for senior staff, have to be satisfied. The basis of the family of genetic algorithms is a classical genetic algorithm consisting of n-point crossover, single-bit mutation and a rank-based selection. The solution space consists of all schedules in which each nurse works the required number of shifts, but the remaining constraints, both hard and soft, are relaxed and penalised in the fitness function. The talk will start with a detailed description of the problem and the initial implementation and will go on to highlight the shortcomings of such an approach, in terms of the key element of balancing feasibility, i.e. covering the demand and work regulations, and quality, as measured by the nurses' preferences. A series of experiments involving parameter adaptation, niching, intelligent weights, delta coding, local hill climbing, migration and special selection rules will then be outlined and it will be shown how a series of these enhancements were able to eradicate these difficulties. Results based on several months' real data will be used to measure the impact of each modification, and to show that the final algorithm is able to compete with a tabu search approach currently employed at the hospital. The talk will conclude with some observations as to the overall quality of this approach to this and similar problems.
BibTeX
@misc{aickelin2010nurse,
  author = {Uwe Aickelin},
  title = {{Nurse Rostering with Genetic Algorithms}},
  year = {2010},
  eprint = {1004.2870},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1004.2870},
}
Figure