Nurse scheduling problem
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]
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
[edit]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
[edit]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:
- All shifts require nursing coverage.
- A nurse cannot work more more than one shift at the same time.
- A nurse cannot work more than 24 hours in a day, or more than 7 days in a week.
- A nurse must not work more than a legally specified number of days in a row.
- A nurse must have a legally specified number of rest hours between shifts.
- Any newly licensed nurse must be paired with an experienced nurse.
- There must always be one charge nurse on duty.
- Certain shifts must be covered by nurses with special qualifications.[9]
Soft constraints may be hospital policies or nurse preferences. Some examples of possible soft constraints are:
- All nurses should work approximately the same number of weekend shifts.
- All nurses should work approximately the same difficulty in shift assignments.
- A nurse should not work a day shift and a night shift without a rest day in between.
- One nurse prefers to have all their work days in a row, and then have all their days off in a row.
- One nurse prefers to work no more than two consecutive days, with a day off in between.
- One nurse cannot work Wednesday each week because they have no child care available that day.
- Two nurses feel they work well together and prefer to be scheduled to work together.
Solutions
[edit]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
[edit]References
[edit]- ^ a b c 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ 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.
- ^ a b c d e f 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.
- ^ 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
- ^ 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.
- ^ a b 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
- ^ a b 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.
- ^ 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.
- ^ 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
- ^ 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.
External links
[edit]- A study on how to solve the NSP using CGA at the Wayback Machine (archived February 6, 2012)
- Why is Scheduling People Hard?
- A free solver for nurse scheduling problem