A Nurse Staffing and Scheduling Problem with Bounded Flexibility and Demand Uncertainty

Si Zhang, Paul Mingzheng Tang, Hoong Chuin LauarXiv 2025 · DOI · arXiv

TL;DR

This paper introduces "bounded flexibility," a framework that balances nurse work-life preferences with strict hospital rostering rules. By modeling the problem as a multi-stage stochastic program and solving it with a Generative AI-guided algorithm (Generative Flow Networks), the authors demonstrate significant cost savings and a dramatic boost in nurse satisfaction with only minor compromises to schedule regularity.

What Problem Does This Paper Address?

Healthcare systems worldwide are grappling with chronic nursing shortages, often exacerbated by rigid schedules and unpredictable patient demand. Hospital managers face a difficult "tug-of-war": they need strict "time regularity" (e.g., keeping a nurse on the same shift type to ensure stability) to maintain operational standards, but nurses increasingly demand flexibility to manage their personal lives.

Existing scheduling tools often fail because they treat patient demand as a fixed number (deterministic) or assume all uncertainty is revealed at once (two-stage stochastic). In reality, demand evolves day-by-day. This paper tackles the integrated problem of staffing (how many nurses to hire/assign) and scheduling (which shifts they work) while accounting for this evolving uncertainty and the complex "soft rules" of human preference.

Methods

The authors propose a sophisticated mathematical and algorithmic pipeline:

  1. Multi-stage Stochastic Programming: They model the planning horizon in stages. Decisions are split into "here-and-now" (initial staffing) and "wait-and-see" (short-term adjustments made as actual patient demand is revealed).
  2. Block-Separable Recourse: To prevent the model from becoming computationally impossible to solve, they prove a structural property called "block-separable recourse." This allows them to reformulate a complex multi-stage problem into a more manageable two-stage structure without losing accuracy.
  3. Generative AI (GNS Approach): The core innovation is the Generative Nurse Scheduling (GNS) algorithm. It utilizes Generative Flow Networks (GFNs). Unlike traditional Reinforcement Learning that seeks a single "best" path, GFNs learn to sample a diverse set of high-quality candidate schedules proportional to their "reward" (low cost/high satisfaction). This diversity makes the final schedule more robust to unexpected changes in demand.

Datasets

The study is grounded in high-fidelity, real-world data:

  • Tan Tock Seng Hospital (TTSH), Singapore: Anonymized data from a 60-nurse surgical ward.
  • Data Scope: 5 months of data including predicted daily patient demand, 12 different shift types (ranging from 6 to 12 hours), and specific nurse profiles (skills, seniority, and work-time preferences).
  • Synthetic Scaling: To test the algorithm's limits, the authors generated 28 test cases by scaling the number of nurses and the intensity of patient demand.

Key Insights and Ideas

  • The "Bounded Flexibility" Sweet Spot: The most striking insight is that the relationship between schedule regularity and nurse flexibility is not linear. The authors found that a slight reduction in strict regularity requirements can lead to a remarkable increase in the satisfaction of nurse requests.
  • Generative AI as an Optimizer: While GFNs are often used in drug discovery or molecule synthesis, this paper shows they are highly effective for combinatorial optimization in logistics. By "training" on expected values and then "evaluating" against real scenarios, the GFN can find near-optimal schedules much faster than traditional solvers for large-scale problems.
  • The Value of "Waiting": By using a multi-stage approach, the model captures the value of sequential decision-making. It proves that making staffing adjustments after some demand is revealed (but before it's too late) is significantly cheaper than trying to create a "perfect" static plan upfront.

Key Results

  • Cost Efficiency: The stochastic model achieved significant cost savings compared to deterministic models. The "Value of Stochastic Solution" (VSS) was positive across all cases, proving that accounting for uncertainty prevents expensive over-staffing or under-staffing penalties.
  • Computational Speedup: For large-scale instances (e.g., 40 nurses), the GNS algorithm outperformed commercial solvers like Gurobi. In some cases, Gurobi could not find an optimal solution within a two-hour limit, while the GNS approach provided high-quality candidates efficiently.
  • Flexibility Gains: In the case studies, reducing the "regularity level" from 0.6 to 0.4 (a 20% drop) improved the nurse request satisfaction rate from roughly 30% to nearly 80%.

Limitations and Future Work

The authors identify a few areas for further exploration:

  • Supply-Side Uncertainty: The current model focuses on demand uncertainty (patients). However, "supply-side" uncertainty—such as sudden nurse sick leave—also has a massive impact on hospital operations.
  • Skill-Based Granularity: While the model considers five skill levels, future work could incorporate more nuanced nurse-specific features (like specific experience with certain medical procedures) to further refine the "right-sizing" of the workforce.
  • Hybrid Solvers: There is potential to combine the GFN approach with exact MILP (Mixed-Integer Linear Programming) solvers to get the "best of both worlds": the speed of AI and the provable optimality of traditional math.

Summary updated

Abstract

Nurse staffing and scheduling are persistent challenges in healthcare due to demand fluctuations and individual nurse preferences. This study introduces the concept of bounded flexibility, balancing nurse satisfaction with strict rostering rules, particularly a real-world time regularity policy from a major hospital in Singapore. We model the problem as a multi-stage stochastic program to address evolving demand, optimizing both aggregate staffing and detailed scheduling decisions. A reformulation into a two-stage structure using block-separable recourse reduces computational burden without loss of accuracy. To solve the problem efficiently, we develop a Generative AI-guided algorithm. Numerical experiments with real hospital data show substantial cost savings and improved nurse flexibility with minimal compromise to schedule regularity. Numerical experiments based on real-world nurse profiles, nurse preferences, and patient demand data are conducted to evaluate the performance of the proposed methods. Our results demonstrate that the stochastic model achieves significant cost savings compared to the deterministic model. Notably, a slight reduction in the regularity level can remarkably enhance nurse flexibility.
BibTeX
@misc{zhang2025nurse,
  author = {Si Zhang and Paul Mingzheng Tang and Hoong Chuin Lau},
  title = {{A Nurse Staffing and Scheduling Problem with Bounded Flexibility and Demand Uncertainty}},
  year = {2025},
  eprint = {2505.22124},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2505.22124},
  howpublished = {arXiv},
}
Figure