Nurse scheduling problem
{{Short description|Operations research problem, paradigm of constrained scheduling problems}}
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.
{{cite journal
| last1 = Solos
| first1 = Ioannis
| last2 = Tassopoulos
| first2 = Ioannis
| last3 = Beligiannis
| first3 = Grigorios
| title = A Generic Two-Phase Stochastic Variable Neighborhood Approach for Effectively Solving the Nurse Rostering Problem
| journal = Algorithms
| volume = 6
| issue = 2
| pages = 278–308
| date = 21 May 2013
| doi = 10.3390/a6020278
| doi-access = free
}} Solutions to the nurse scheduling problem can be applied to constrained scheduling problems in other fields.
{{cite journal
| last1 = Aickelin | first1 = Uwe
| last2 = Dowsland | first2 = Kathryn A.
| title = An Indirect Genetic Algorithm for a Nurse Scheduling Problem
| journal = Computers & Operations Research
| volume = 31
| issue = 5
| pages = 761–778
| date = 2004
| doi=10.1016/s0305-0548(03)00034-0| arxiv = 0803.2969| s2cid = 8772185
| last1 = Beddoe
| first1 = Gareth
| last2 = Petrovic
| first2 = Sanja
| title = A novel approach to finding feasible solutions to personnel rostering problems
| pages = 1–13
| publisher = Proceedings of the 14th Annual Conference of the Production and Operation Management Society
| location = Savannah, Georgia
| date = 2003
| url = http://pomsmeetings.org/ConfProceedings/001/Papers/PSC-08.1.pdf
| accessdate = 20 March 2014
| archive-date = 29 August 2017
| archive-url = https://web.archive.org/web/20170829183208/https://www.pomsmeetings.org/ConfProceedings/001/Papers/PSC-08.1.pdf
| url-status = dead
}}
While research on computer-assisted employee scheduling goes back to the 1950s,{{cite journal
| last1 = Bailey
| first1 = Norman T. J.
| journal = Journal of the Royal Statistical Society Series C: Applied Statistics
| volume = 5
| issue = 3
| pages = 146–157
| title = Statistics in Hospital Planning and Design
| publisher = Oxford University Press
| year = 1956
| url = https://academic.oup.com/jrsssc/article-abstract/5/3/146/6862850
| accessdate = 14 December 2023
| doi=10.2307/2985416
| jstor = 2985416
| url-access = subscription
}} the nurse scheduling problem in its current form was introduced in two parallel publications in 1976.{{cite journal
| last1 = Miller
| first1 = Holmes E.
| last2 = Pierskalla
| first2 = William P.
| last3 = Rath
| first3 = Gustave J.
| title = Nurse Scheduling Using Mathematical Programming
| publisher = INFORMS
| year = 1976
| journal = Operations Research
| volume = 24
| issue = 5
| pages = 857–870
| url = https://pubsonline.informs.org/doi/abs/10.1287/opre.24.5.857
| accessdate = 14 December 2023
| doi=10.1287/opre.24.5.857
| url-access = subscription
| last1 = Warner
| first1 = D. Michael
| title = Scheduling Nursing Personnel According to Nursing Preference: A Mathematical Programming Approach
| publisher = INFORMS
| year = 1976
| journal = Operations Research
| volume = 24
| issue = 5
| pages = 842–856
| url = https://pubsonline.informs.org/doi/abs/10.1287/opre.24.5.842
| accessdate = 14 December 2023
| doi=10.1287/opre.24.5.842
| url-access = subscription
}} It is known to have NP-hard complexity.
General description
The nurse scheduling problem involves the assignment of shifts and holidays to nurses. Each nurse has their own wishes and restrictions, as does the hospital. The problem is described as finding a schedule that both respects the constraints of the nurses and fulfills the objectives of the hospital. Conventionally, a nurse can work 3 shifts because nursing is shift work:
- day shift
- night shift
- late night shift
In this problem we must search for a solution satisfying as many wishes as possible while not compromising the needs of the hospital.
Constraints
There are two types of constraints:
- hard constraints: if this constraint fails then the entire schedule is invalid.
- soft constraints: it is desirable that these constraints are met but not meeting them does not make the schedule invalid.
Some examples of constraints are:
- A nurse does not work the day shift, night shift and late night shift on the same day (i.e. no 24-hour duties).
- A nurse may go on a holiday and will not work shifts during this time.
- A nurse does not do a late night shift followed by a day shift the next day.
- Two nurses dislike each other and thus cannot work on the same shift because of that.
- One nurse is newly qualified and must be paired with an experienced nurse.
- A shift requires a charge nurse.
Hard constraints typically include a specification of shifts (e.g. morning, afternoon, and night), that each nurse should work no more than one shift per day, and that all patients should have nursing coverage. Differences in qualifications between nurses also create hard constraints.
{{cite journal
| last1 = Aickelin
| first1 = Uwe
| last2 = White
| first2 = Paul
| title = Building Better Nurse Scheduling Algorithms
| journal = Annals of Operations Research
| volume = 128
| issue = 1–4
| pages = 159–177
| date = 2004
| doi=10.1023/b:anor.0000019103.31340.a6| arxiv = 0803.2967
| s2cid = 14983974
}}
Soft constraints may include minimum and maximum numbers of shifts assigned to a given nurse in a given week, of hours worked per week, of days worked consecutively, of days off consecutively, and so on. The shift preferences of individual nurses may be treated as a soft constraint,{{cite journal
| last1 = Goodman
| first1 = Melissa D.
| last2 = Dowsland
| first2 = Kathryn A.
| last3 = Thompson
| first3 = Jonathan M.
| title = A grasp-knapsack hybrid for a nurse-scheduling problem
| journal = Journal of Heuristics
| pages = 351–379
| publisher = Springer
| date = 2007
| volume = 15
| issue = 4
| doi = 10.1007/s10732-007-9066-7
| s2cid = 8784023
| url = https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf
| accessdate = 20 June 2020
}} or as a hard constraint.{{cite journal
| last = Winstanley
| first = Graham
| title = A hybrid approach to staff scheduling: The Staff Work Allocation Tool (SWAT)
| pages = 1–12
| publisher = University of Brighton School of Computing, Engineering and Mathematics
| location = Brighton
| url = http://www.cem.brighton.ac.uk/research/cig/papers/SWAT.pdf
| accessdate = 20 March 2014
| journal =
| archive-url = https://web.archive.org/web/20140320215801/http://www.cem.brighton.ac.uk/research/cig/papers/SWAT.pdf
| archive-date = 20 March 2014
| url-status = dead
}}
Solutions
Solutions to the problem use a variety of techniques, including both mathematically exact solutions and a variety of heuristic solutions using decomposition,{{cite journal
| last1 = Lagatie
| first1 = Ruben
| last2 = Haspeslagh
| first2 = Stefaan
| last3 = De Causmaecker
| first3 = Patrick
| title = Negotiation Protocols for Distributed Nurse Rostering
| publisher = Eindhoven University of Technology Department of Computer Science
| year = 2009
| url = http://wwwis.win.tue.nl/bnaic2009/papers/junk/bnaic2009_submission_41.pdf
| accessdate = 14 February 2014
| archive-date = 4 March 2016
| archive-url = https://web.archive.org/web/20160304190332/http://wwwis.win.tue.nl/bnaic2009/papers/junk/bnaic2009_submission_41.pdf
| url-status = dead
}} parallel computing, stochastic optimization, genetic algorithms, colony optimization, simulated annealing, quantum annealing,{{Cite journal|last1=Humble|first1=Travis S.|last2=Nakamura|first2=Yuma|last3=Ikeda|first3=Kazuki|date=2019-04-27|title=Application of Quantum Annealing to Nurse Scheduling Problem|journal=Scientific Reports|volume=9|issue=1|pages=12837|language=en|arxiv=1904.12139|bibcode=2019NatSR...912837I|doi=10.1038/s41598-019-49172-3|pmid=31492936|pmc=6731278}} Tabu search, and coordinate descent.{{cite journal
| last1 = Bäumelt | first1 = Zdeněk
| last2 = Dvořák | first2 = Jan
| last3 = Šůcha | first3 = Přemysl
| last4 = Hanzálek | first4 = Zdeněk
| title = A Novel Approach for Nurse Rerostering based on a Parallel Algorithm
| journal = European Journal of Operational Research
| volume = 251
| issue = 2
| pages = 624–639
| publisher = Elsevier
| date = 2016
| doi=10.1016/j.ejor.2015.11.022}}
| last1 = Augustine
| first1 = Lizzy
| last2 = Faer
| first2 = Morgan
| last3 = Kavountzis
| first3 = Andreas
| last4 = Patel
| first4 = Reema
| title = A Brief Study of the Nurse Scheduling Problem (NSP)
| pages = 1–11
| publisher = Carnegie Mellon School of Computer Science
| location = Pittsburgh
| date = 15 December 2009
| url = http://www.math.cmu.edu/~af1p/Teaching/OR2/Projects/P23/ORProject_Final_Copy.pdf
| accessdate = 20 March 2014}}
Burke et al. (2004){{cite journal
| last1 = Burke
| first1 = Edmund
| last2 = De Causmaecker
| first2 = Patrick
| last3 = Berghe
| first3 = Greet Vanden
| last4 = Van Landeghem
| first4 = Hendrik
| title = The state of the art of nurse rostering
| journal = Journal of Scheduling
| volume = 7
| issue = 6
| pages = 441–499
| url = https://lirias.kuleuven.be/bitstream/123456789/123829/1/JOS_
| accessdate = 10 January 2016
| doi = 10.1023/B:JOSH.0000046076.75950.0b
| year = 2004
| s2cid = 10537343
| url-access = subscription
}} summarised the state of art of academic research to the nurse rostering problem, including brief introductions of various then published solutions.
See also
References
{{reflist|2}}
External links
- {{webarchive |url=https://web.archive.org/web/20120206032112/http://www.lania.mx/~ccoello/EMOO/jan00.ps.gz |date=February 6, 2012 |title=A study on how to solve the NSP using CGA }}
- [https://www.mjc2.com/staff-planning-complexity.htm Why is Scheduling People Hard?]
- [https://www.nurse-scheduling-software.com/ A free solver for nurse scheduling problem]