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