Source-linked AI summary
Building Better Nurse Scheduling Algorithms
Uwe Aickelin, Paul White
TL;DR
The paper addresses how to compare stochastic scheduling algorithms when some runs end infeasible and ordinary summary statistics may not apply. It proposes pairwise run comparisons summarized for statistical testing, and reports using the procedure to identify successful algorithm modifications and build an improved nurse scheduler.
Problem
Comparing stochastic algorithms is difficult when infeasible runs make common summaries such as means or standard deviations illegitimate, and best or median outcomes can conceal differences.
Source: §3 · p. 6Method
The paper compares outcomes pairwise, condenses those comparisons into a single figure, and applies traditional statistical techniques to assess algorithm differences.
Source: §3 · p. 7, §5 · p. 11Results
The comparison procedure was used to identify successful modifications and build an improved nurse scheduling algorithm, with differences among variants assessed across 52 weekly problems.
Source: §4 · pp. 8, 10Takeaways & Limitations
The method supports objective algorithm improvement even when some results are missing because runs are infeasible.
Source: §4 · p. 8, §5 · p. 11Feasibility cannot be guaranteed for either genetic algorithm approach because doing so would require an unlimited supply of nurses.
Source: §2 · p. 5
Abstract
from arXiv · showhide
The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence building better scheduling algorithms by identifying successful algorithm modifications. The comparison method captures the results of algorithms in a single figure that can then be compared using traditional statistical techniques. Thus, the proposed method of comparing algorithms is an objective procedure designed to assist in the process of improving an algorithm. This is achieved even when some results are non-numeric or missing due to infeasibility. The final algorithm outperforms all previous evolutionary algorithms, which relied on human expertise for modification.
1 THE NURSE SCHEDULING PROBLEM
The problem is to build weekly nurse schedules that meet contractual and grade-specific coverage requirements while fairly accommodating staff preferences. The paper focuses on assigning nurses to day and night shift patterns, a difficult step because grades can substitute only downward and day/night contracts differ.
1 THE NURSE SCHEDULING PROBLEM
- Weekly schedules assign each nurse a feasible shift pattern while meeting staffing demand and balancing fairness through staff requests and historical information.The problem covers wards of up to 30 nurses and aims to distribute unsatisfied requests and unpopular shifts evenly.Source: §1 · pp. 2–3
- Higher-grade nurses can cover lower-grade demand but not vice versa, and differing day/night contracts make independent grade scheduling impossible.These features make maintaining feasible schedules challenging for local search.Source: §1 · p. 2
- The paper addresses the highly constrained second stage: assigning nurses to the correct numbers of day or night shifts.The broader process first ensures adequate staffing and later allocates workers to early or late shifts.Source: §1 · p. 3
- Each nurse-pattern assignment has a preference cost combining shift-pattern cost, day/night preferences, requests, continuity, rotation, and work history.The preference-cost design was developed in consultation with the hospital.Source: §1 · p. 3
- The integer program selects one feasible pattern per nurse and covers demand for every grade on every day and night.A typical instance has 30 nurses, three grades, 411 patterns, about 12,000 binary variables, and 100 constraints.Source: §1 · p. 4
2 GENETIC ALGORITHM IMPLEMENTATION
The paper uses genetic algorithms to search nurse schedules through both direct schedule encodings and an indirect ordering-plus-decoder approach. Because feasibility is not guaranteed, it evaluates completed solutions with a penalty for uncovered shifts.
2 GENETIC ALGORITHM IMPLEMENTATION
- Genetic algorithms evolve a population by selecting fitter solutions for recombination, with mutation and retention of some best solutions.The process repeats until stopping criteria are met.Source: §2 · p. 5
- The direct encoding represents a schedule as one shift-pattern index per nurse, matching each string position to a nurse.For five nurses, the example string (1, 17, 56, 67, 3) assigns one pattern index to each nurse.Source: §2 · p. 5
- The implementation explores a direct encoding of full weekly schedules and an indirect genetic algorithm that orders nurses for a heuristic decoder.In the indirect approach, the decoder builds the actual schedule while considering cost, preferences, and coverage.Source: §2 · p. 5
- The indirect approach keeps problem-specific information in the decoder while the genetic algorithm searches nurse permutations.It requires permutation-based crossover and mutation operators.Source: §2 · p. 5
- Neither approach guarantees feasibility, so the implementation uses a penalty proportional to the number of uncovered shifts.The chosen encoding automatically satisfies the constraint that each nurse works one feasible pattern.Source: §2 · p. 5
3 THE NEED FOR A COMPARISON ALGORITHM
The section motivates a comparison method for stochastic algorithms whose runs may be infeasible and whose distributions can yield conflicting judgments under means, medians, or quartiles. It develops pairwise run comparisons that can be summarized and tested across problem variants.
3 THE NEED FOR A COMPARISON ALGORITHM
- Means, medians, best outcomes, or quartiles can fail to distinguish algorithms when runs are infeasible or distribution summaries conflict.In the example, ALG1 and ALG2 share an infeasible median and best cost of 1, although the desired global ranking favors ALG1.Source: §3 · p. 6
- In the 52 weekly problems, best-cost plots suggested V6 was inferior to V2 and V4, while comparisons of distribution regions could favor V4 over V2.The section argues that a comparison should account for more than distribution location alone.Source: §3 · pp. 6–7
- The proposed comparison evaluates pairs of runs, treating a lower cost as better and allowing a feasible result to outrank an infeasible one in many cases.The treatment of feasible versus infeasible outcomes is stated as a desired interpretation in many such cases, not as a universal rule.Source: §3 · p. 7
- Averaging pairwise better, same, or worse indicators yields an algorithm-comparison score that can express ties or directional preference.The score ranges from -1 to +1; zero can reflect no difference or balanced better and worse comparisons.Source: §3 · p. 7
- Across problem variants, the method supports ranking algorithms and applying Friedman, Sign, or Wilcoxon tests to assess systematic differences.The Wilcoxon approach uses the pairwise comparison score across variants as its difference measure.Source: §3 · p. 8
4 ANALYSIS AND DISCUSSION
Statistical comparisons ranked the milestone algorithms and identified U7 as best in the expanded set, revising the earlier expertise-built result.
4 ANALYSIS AND DISCUSSION
- Each algorithm was run 20 times on each of 52 weekly problem variants, producing 52 algorithm rankings for analysis.The weekly rostering requirements covered a full calendar year.Source: §4 · p. 8
- Friedman’s test found significant differences among the milestone algorithms (S = 290.54, df = 7, p-value < 0.001), with V4 tentatively ranked best and V3 and V6 worst.The average-rank ordering was V3 < V6 < V8 < V7 < V2 < V1 < V5 < V4.Source: §4 · p. 9
- Pairwise tests found V4 significantly better than V5, followed by a significant ranking chain through V5, V1, V2, V7, V8, and V6; V6 and V3 did not differ significantly.The Wilcoxon and Sign tests both found no significant difference between V6 and V3, while both tests favored V8 over V6.Source: §4 · p. 9
- Changing α from 1.0 to 0.5, 0.6, 0.7, 0.8, or 0.9 produced the same broad conclusions.Source: §4 · p. 10
- Among the second set of algorithms, U7 was best, U1 and U5 were statistically indistinguishable, and U4 and U6 were the poorest performers.U2 and U8 were identical; U1 and U5 significantly improved on U2 and U8, while U7 significantly improved on U1 and U5.Source: §4 · p. 10
- U7 was best in the expanded set; against U8 (equal to V4), it had better worst solutions on 22 instances versus 14 and better best solutions on 9 versus 4.Median solutions favored U8 on 23 instances and U7 on 5; the medians were the same on 24 instances.Source: §4 · p. 10
- For the third algorithm set, the comparisons found no statistically significant differences, consistent with the intended robustness check.The algorithms were selected because they were expected to be similar in performance.Source: §4 · p. 10
5 CONCLUSIONS
The comparison method ranks algorithms even when some results are infeasible, and the paper argues that comparing full result distributions better reveals useful algorithm modifications than focusing only on best outcomes.
5 CONCLUSIONS
- The pairwise comparison procedure produces a single figure for traditional statistical comparison and remains applicable when some results are missing because solutions are infeasible.Source: §5 · p. 11
- Comparing full result distributions can reveal improvements affecting most trials that a best-outcome-only comparison would miss.The paper contrasts an algorithm with 19 infeasible results and one zero-cost result against one with 20 feasible, higher-cost results.Source: §5 · p. 11