Nurse scheduling problem

Last updated

The nurse scheduling problem (NSP), also called the nurse rostering problem (NRP), is the operations research problem of finding an optimal way to assign nurses to shifts, typically with a set of hard constraints which all valid solutions must follow, and a set of soft constraints which define the relative quality of valid solutions. [1] Solutions to the nurse scheduling problem can be applied to constrained scheduling problems in other fields. [2] [3]

Contents

While research on computer-assisted employee scheduling goes back to the 1950s, [4] the nurse scheduling problem in its current form was introduced in two parallel publications in 1976. [5] [6] It is known to have NP-hard complexity. [1]

General description

Conventionally, hospital nursing is shift work that is divided up to provide coverage 24 hours per day, 7 days per week. The hospital has restrictions and requirements for what coverage is needed, and each nurse has their own wishes and restrictions as well. The problem is described as finding a schedule that fulfills the objectives of the hospital and covers all shifts, while respecting as many of the nurses' preferences as possible.

The problem is not unique to nursing. It applies in any other profession or situation where shift coverage must be planned out.

Constraints

Creating a schedule means attempting to satisfy certain constraints on how that schedule is laid out. There are two types of constraint: hard constraints, which must be met for the schedule to be valid; and soft constraints, which are desirable but not mandatory.

Depending on the policies of a hospital, the preferences of individual nurses may be treated as either a soft constraint, [7] or as a hard constraint. [8]


Hard constraints may include physical limitations or legal requirements. Some examples of possible hard constraints are:


Soft constraints may be hospital policies or nurse preferences. Some examples of possible soft constraints are:


Solutions

Solutions to the problem use a variety of techniques, including both mathematically exact solutions [7] and a variety of heuristic solutions using decomposition, [10] parallel computing, [10] [11] stochastic optimization, [1] genetic algorithms, [7] colony optimization, [7] simulated annealing, [7] quantum annealing, [12] Tabu search, [7] and coordinate descent. [11] [13]

Burke et al. (2004) [14] summarised the state of art of academic research to the nurse rostering problem, including brief introductions of various then published solutions.

See also

References

  1. 1 2 3 Solos, Ioannis; Tassopoulos, Ioannis; Beligiannis, Grigorios (21 May 2013). "A Generic Two-Phase Stochastic Variable Neighborhood Approach for Effectively Solving the Nurse Rostering Problem". Algorithms . 6 (2): 278–308. doi: 10.3390/a6020278 .
  2. ↑ Aickelin, Uwe; Dowsland, Kathryn A. (2004). "An Indirect Genetic Algorithm for a Nurse Scheduling Problem". Computers & Operations Research. 31 (5): 761–778. arXiv: 0803.2969 . doi:10.1016/s0305-0548(03)00034-0. S2CID   8772185.
  3. ↑ Beddoe, Gareth; Petrovic, Sanja (2003). "A novel approach to finding feasible solutions to personnel rostering problems" (PDF). Proceedings of the 14th Annual Conference of the Production and Operation Management Society. Savannah, Georgia: 1–13. Archived from the original (PDF) on 29 August 2017. Retrieved 20 March 2014.
  4. ↑ Bailey, Norman T. J. (1956). "Statistics in Hospital Planning and Design" . Journal of the Royal Statistical Society Series C: Applied Statistics. 5 (3). Oxford University Press: 146–157. doi:10.2307/2985416. JSTOR   2985416 . Retrieved 14 December 2023.
  5. ↑ Miller, Holmes E.; Pierskalla, William P.; Rath, Gustave J. (1976). "Nurse Scheduling Using Mathematical Programming" . Operations Research. 24 (5). INFORMS: 857–870. doi:10.1287/opre.24.5.857 . Retrieved 14 December 2023.
  6. ↑ Warner, D. Michael (1976). "Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach" . Operations Research. 24 (5). INFORMS: 842–856. doi:10.1287/opre.24.5.842 . Retrieved 14 December 2023.
  7. 1 2 3 4 5 6 Goodman, Melissa D.; Dowsland, Kathryn A.; Thompson, Jonathan M. (2007). "A grasp-knapsack hybrid for a nurse-scheduling problem" (PDF). Journal of Heuristics. 15 (4). Springer: 351–379. doi:10.1007/s10732-007-9066-7. S2CID   8784023 . Retrieved 20 June 2020.
  8. ↑ Winstanley, Graham, A hybrid approach to staff scheduling: The Staff Work Allocation Tool (SWAT) (PDF), Brighton: University of Brighton School of Computing, Engineering and Mathematics, pp. 1–12, archived from the original (PDF) on 20 March 2014, retrieved 20 March 2014
  9. ↑ Aickelin, Uwe; White, Paul (2004). "Building Better Nurse Scheduling Algorithms". Annals of Operations Research . 128 (1–4): 159–177. arXiv: 0803.2967 . doi:10.1023/b:anor.0000019103.31340.a6. S2CID   14983974.
  10. 1 2 Lagatie, Ruben; Haspeslagh, Stefaan; De Causmaecker, Patrick (2009), Negotiation Protocols for Distributed Nurse Rostering (PDF), Eindhoven University of Technology Department of Computer Science, archived from the original (PDF) on 4 March 2016, retrieved 14 February 2014
  11. 1 2 Bäumelt, Zdeněk; Dvořák, Jan; Šůcha, Přemysl; Hanzálek, Zdeněk (2016). "A Novel Approach for Nurse Rerostering based on a Parallel Algorithm". European Journal of Operational Research . 251 (2). Elsevier: 624–639. doi:10.1016/j.ejor.2015.11.022.
  12. ↑ Humble, Travis S.; Nakamura, Yuma; Ikeda, Kazuki (2019-04-27). "Application of Quantum Annealing to Nurse Scheduling Problem". Scientific Reports. 9 (1): 12837. arXiv: 1904.12139 . Bibcode:2019NatSR...912837I. doi:10.1038/s41598-019-49172-3. PMC   6731278 . PMID   31492936.
  13. ↑ Augustine, Lizzy; Faer, Morgan; Kavountzis, Andreas; Patel, Reema (15 December 2009), A Brief Study of the Nurse Scheduling Problem (NSP) (PDF), Pittsburgh: Carnegie Mellon School of Computer Science, pp. 1–11, retrieved 20 March 2014
  14. ↑ Burke, Edmund; De Causmaecker, Patrick; Berghe, Greet Vanden; Van Landeghem, Hendrik (2004). "The state of the art of nurse rostering" . Journal of Scheduling. 7 (6): 441–499. doi:10.1023/B:JOSH.0000046076.75950.0b. S2CID   10537343 . Retrieved 10 January 2016.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.