An indirect Genetic Algorithm for a nurse-scheduling problem

Uwe Aickelin, Kathryn A. DowslandComput. Oper. Res 2004 · DOI · OpenReview

TL;DR

This paper introduces an "indirect" Genetic Algorithm (GA) approach to the complex nurse scheduling problem, where the GA operates on a permutation of nurses and a separate "decoder" builds the actual schedule. This method effectively balances competing objectives like feasibility and cost, outperforming previous direct GA and Tabu Search approaches, and achieving near-optimal solutions.

What Problem Does This Paper Address?

The core challenge is creating weekly nurse schedules that satisfy numerous constraints: ensuring adequate staff coverage for all shifts, meeting contractual obligations, and considering nurse preferences and fairness. Traditional Genetic Algorithms struggle with incorporating these constraints directly, often relying on complex penalty functions or repair mechanisms that are problem-specific and can hinder performance. This paper tackles the problem of efficiently and effectively solving this highly constrained optimization task, aiming for solutions that are both feasible and minimize costs (e.g., unmet nurse requests).

Methods

The paper proposes an indirect Genetic Algorithm. Instead of the GA's "genes" directly representing schedule components, they represent a permutation of nurses. This permutation is then fed into a heuristic decoder (a "schedule builder") that constructs the actual nurse schedule. This separation allows the GA to work on an unconstrained problem space, while the decoder incorporates the problem-specific knowledge and constraints.

Key methodological aspects include:

  • Indirect Encoding: Permutations of nurses are used as the GA's genotype.
  • Heuristic Decoder: A separate module translates the GA's output (nurse permutation) into a feasible or near-feasible schedule. Three decoders were developed and compared:
  • 'Cover' Decoder: Prioritizes schedule feasibility.
  • 'Contribution' Decoder: Balances feasibility with nurse preferences (cost).
  • 'Combined' Decoder: A hybrid approach aiming for a better balance.
  • Permutation Crossover Operators: Standard operators like PMX, C1, and uniform order-based crossover were evaluated, along with a novel parameterized uniform order crossover (PUX).
  • Simple Bounds: A mechanism was introduced to prune the search space by preventing nurses from being assigned shift patterns with costs exceeding the best feasible solution found so far.

Datasets

The experiments were conducted using 52 weeks of real-world data provided by a major UK hospital. This data included weekly requirements for shifts and grade combinations, as well as nurse availability, preference costs, and qualifications.

Key Insights and Ideas

  • Decoupling GA and Constraints: Separating the GA from constraint handling by using a decoder significantly improves flexibility and adaptability. The GA can remain canonical, while problem-specific knowledge is encapsulated in the decoder.
  • Decoder Design is Crucial: The performance of the indirect GA is highly dependent on the decoder's ability to balance feasibility and solution quality. The 'Combined' decoder, which integrates elements of feasibility and cost, proved most effective.
  • Novel Crossover Operator (PUX): The proposed PUX operator, which balances disrupting gene order with maintaining parent gene positions, significantly improved results, particularly in reducing solution cost while maintaining high feasibility.
  • Simple Bounds Enhance Efficiency: The introduction of a simple bound, based on the cost of the best feasible solution found, effectively pruned the search space and accelerated the optimization process without sacrificing feasibility.

Key Results

  • The enhanced indirect GA, particularly the 'Combined' decoder with the PUX crossover and simple bounds, achieved near-optimal solutions for 51 out of 52 data sets, with the remaining set being very close to optimal.
  • The final algorithm was within 2% of optimality on average.
  • The indirect GA was faster and more flexible than a previously published Tabu Search approach.
  • The 'Combined' decoder with PUX and simple bounds achieved a feasibility of 96.6% and a cost of 9.4, outperforming other combinations and direct GA approaches.
  • The average solution time was accelerated by using the simple bound, reducing it from around 15 seconds to less than 10 seconds per run.

Limitations and Future Work

  • Decoder Weights: The paper notes that the arbitrary choice of weights in the decoder (e.g., for preference cost vs. coverage) might not be satisfactory for more complex problems, suggesting future research into automatically finding these weights.
  • Ideal Transformation: The authors acknowledge that their indirect approach violates some conditions for an ideal transformation between solution and search spaces as suggested by Palmer and Kershenbaum [11].
  • Sophisticated Backtracking: The paper mentions that a more sophisticated backtracking mechanism could be employed to correct infeasible solutions, but this would require exponential time complexity and is outside the scope of the current research.
  • Generalizability: While the core idea of an indirect GA with a decoder is presented as applicable to other constrained scheduling problems, further research is suggested for applying this approach to other difficult problems in scheduling and beyond.

Summary updated

Abstract

This paper describes a Genetic Algorithms (GAs) approach to a manpower-scheduling problem arising at a major UK hospital. Although GAs have been successfully used for similar problems in the past, they always had to overcome the limitations of the classical GAs paradigm in handling the conflict between objectives and constraints. The approach taken here is to use an indirect coding based on permutations of the nurses, and a heuristic decoder that builds schedules from these permutations. Computational experiments based on 52 weeks of live data are used to evaluate three different decoders with varying levels of intelligence, and four well-known crossover operators. Results are further enhanced by introducing a hybrid crossover operator and by making use of simple bounds to reduce the size of the solution space. The results reveal that the proposed algorithm is able to find high quality solutions and is both faster and more flexible than a recently published Tabu Search approach.
BibTeX
@inproceedings{aickelin2004indirect,
  author = {Uwe Aickelin and Kathryn A. Dowsland},
  title = {{An indirect Genetic Algorithm for a nurse-scheduling problem}},
  booktitle = {Comput. Oper. Res},
  year = {2004},
  doi = {10.1016/s0305-0548(03)00034-0},
}
Figure