Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem

Uwe Aickelin, Kathryn A. DowslandMinerva Access (University of Melbourne) 2000 · OpenReview

TL;DR

This paper tackles the challenge of nurse rostering, a complex scheduling problem with many conflicting constraints, using a modified genetic algorithm (GA). By incorporating problem-specific knowledge into a co-evolutionary strategy with sub-populations and adding incentives/disincentives, they transform a failing canonical GA into a practical, efficient solution.

What Problem Does This Paper Address?

Scheduling and timetabling problems, like nurse rostering, are notoriously difficult for standard genetic algorithms (GAs). These problems often involve numerous conflicting objectives and hard constraints. A "canonical" GA, which treats all individuals and constraints equally, struggles to find feasible and high-quality solutions. This paper focuses on the nurse rostering problem at a major UK hospital, where schedules must meet staffing demands for different nurse grades across various shifts, while also considering nurse preferences and fairness. The core challenge is to develop a GA that can effectively navigate this complex, constraint-heavy problem space.

Methods

The authors propose a novel GA approach that leverages problem-specific knowledge to overcome the limitations of a canonical GA. Key methodological contributions include:

  • Co-evolutionary Strategy with Sub-Populations: The population is divided into several sub-populations, each focusing on specific aspects of the problem (e.g., nurses of a particular grade). These sub-populations evolve semi-independently but interact through a "grade-based crossover" mechanism, allowing them to combine "building blocks" of good partial solutions. This is inspired by the idea of co-operative co-evolution.
  • Incentives and Disincentives: To guide the search towards better solutions, the fitness function is adjusted. Balanced solutions (where over- and under-coverage are distributed in a way that can be easily repaired) are rewarded, while unbalanced solutions (where the problem is harder to fix) are penalized.
  • Intelligent Mutation/Repair Operator: A simple hill-climber is introduced, applied to the fittest solutions. This operator attempts to locally improve solutions by making small changes to individual nurse schedules, particularly focusing on repairing balanced but not yet feasible solutions.
  • Adaptive Penalty Weight: The penalty for constraint violations is not fixed but adapts based on the number of violated constraints in the best solution found so far, aiming to dynamically adjust the search pressure.

Datasets

The research utilizes 52 real-world datasets representing 52 weeks of nurse rostering data from three different hospital wards. These datasets were used for both development and evaluation. Additionally, 52 further instances with randomly generated penalty weights were used to test the algorithm's robustness.

Key Insights and Ideas

  • Problem Structure is Key: The paper strongly emphasizes that simply applying a generic GA is insufficient for complex scheduling problems. Exploiting the inherent structure of the problem (like nurse grades) is crucial for success.
  • Co-evolutionary Approach Reduces Epistasis: By creating sub-populations focused on specific grades, the algorithm effectively reduces the impact of "epistasis" (where the effect of one gene depends on others), a common issue in GAs that hinders the combination of good partial solutions.
  • Balancing Feasibility and Quality: The introduction of incentives for balanced solutions and a repair mechanism (hill-climber) effectively bridges the gap between finding feasible solutions and improving their quality, addressing a common GA weakness.
  • Co-evolutionary Crossover is Powerful: The "grade-based crossover" allows for the strategic combination of promising partial solutions from different sub-populations, leading to more effective exploration of the solution space.

Key Results

  • A canonical GA was unsuccessful, failing to find feasible solutions for many problems.
  • The proposed co-evolutionary GA with incentives and repair significantly improved performance.
  • Feasibility: The percentage of feasible solutions increased dramatically. With all features (incentive, disincentive, repair), 89% of problems found feasible solutions, compared to 75% with no enhancements.
  • Solution Quality: The mean total penalty cost (pij) of the solutions was substantially reduced. The best approach achieved a mean pij of 10.9, down from 17.6 for the basic GA.
  • Speed: Solution times were reduced to an average of 14.9 seconds per run, making it feasible to run multiple random starts within a short period.
  • The algorithm was able to provide practical solutions acceptable to the hospital, with solutions within 3 units of the optimal penalty cost being considered acceptable.

Limitations and Future Work

  • Problem Specificity: The authors acknowledge that the specific enhancements (co-evolutionary structure, incentives) are problem-specific and cannot be directly copied to other scheduling problems. However, they suggest the underlying concepts (co-evolutionary sub-populations, incentives, local search) are broadly applicable.
  • Comparison with Tabu Search: While the GA performs well, the paper notes that a tabu search approach, when given more time, can achieve better and more consistent solution quality. However, the GA offers advantages in speed and simplicity.
  • Future Work: The authors are developing a GA with an indirect coding and heuristic decoder approach to compare against their current method, aiming to further explore the trade-offs between development effort, solution time, and quality. They also suggest that the severity parameter for penalties might need to be increased for problems with very high penalty costs for optimal solutions.

Summary updated

Abstract

There is considerable interest in the use of genetic algorithms to solve problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle the conflict between objectives and constraints that typically occurs in such problems. In order to overcome this, successful implementations frequently make use of problem specific knowledge. This paper is concerned with the development of a GA for a nurse rostering problem at a major UK hospital. The structure of the constraints is used as the basis for a co-evolutionary strategy using co-operating sub-populations. Problem specific knowledge is also used to define a system of incentives and disincentives, and a complementary mutation operator. Empirical results based on 52 weeks of live data show how these features are able to improve an unsuccessful canonical GA to the point where it is able to provide a practical solution to the problem
BibTeX
@inproceedings{aickelin2000exploiting,
  author = {Uwe Aickelin and Kathryn A. Dowsland},
  title = {{Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem}},
  booktitle = {Minerva Access (University of Melbourne)},
  year = {2000},
  url = {https://openreview.net/forum?id=Q4n8AUwhh8},
}
Figure