Nurse scheduling problem

<h2 id="general-description">General description</h2>
The nurse scheduling problem involves the assignment of shifts and holidays to <a href="/facts/Nurse/xbmA4GNC">nurses</a>. 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 <a href="/facts/Shift_work/I2DeU84Q">shift work</a>:

<ul><li>day shift</li>
<li>night shift</li>
<li>late night shift</li></ul>
In this problem we must search for a solution satisfying as many wishes as possible while not compromising the needs of the hospital.

<h2 id="constraints">Constraints</h2>
There are two types of constraints:

<ul><li>hard constraints: if this constraint fails then the entire schedule is invalid.</li>
<li>soft constraints: it is desirable that these constraints are met but not meeting them does not make the schedule invalid.</li></ul>
Some examples of constraints are:

<ul><li>A nurse does not work the day shift, night shift and late night shift on the same day (i.e. no 24-hour duties).</li>
<li>A nurse may go on a holiday and will not work shifts during this time.</li>
<li>A nurse does not do a late night shift followed by a day shift the next day.</li>
<li>Two nurses dislike each other and thus cannot work on the same shift because of that.</li>
<li>One nurse is newly qualified and must be paired with an experienced nurse.</li>
<li>A shift requires a <a href="/facts/Charge_nurse/vPAYawc1">charge nurse</a>.</li></ul>
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.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> Differences in qualifications between nurses also create hard constraints.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a> 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.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> The shift preferences of individual nurses may be treated as a soft constraint,<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a> or as a hard constraint.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a>

<h2 id="solutions">Solutions</h2>
Solutions to the problem use a variety of techniques, including both mathematically exact solutions<a class="footnote-ref" id="fnref:13" href="#fn:13">13</a> and a variety of heuristic solutions using <a href="/facts/Decomposition_(computer_science)/oAQ7l0VA">decomposition</a>,<a class="footnote-ref" id="fnref:14" href="#fn:14">14</a> <a href="/facts/Parallel_computing/nQzcpzQt">parallel computing</a>,<a class="footnote-ref" id="fnref:15" href="#fn:15">15</a><a class="footnote-ref" id="fnref:16" href="#fn:16">16</a> <a href="/facts/Stochastic_optimization/LXvQU1BM">stochastic optimization</a>,<a class="footnote-ref" id="fnref:17" href="#fn:17">17</a> <a href="/facts/Genetic_algorithm/WP2AFWuW">genetic algorithms</a>,<a class="footnote-ref" id="fnref:18" href="#fn:18">18</a> <a href="/facts/Ant_colony_optimization_algorithms/SXGYs630">colony optimization</a>,<a class="footnote-ref" id="fnref:19" href="#fn:19">19</a> <a href="/facts/Simulated_annealing/JCmHqd3t">simulated annealing</a>,<a class="footnote-ref" id="fnref:20" href="#fn:20">20</a> <a href="/facts/Quantum_annealing/maR034Gr">quantum annealing</a>,<a class="footnote-ref" id="fnref:21" href="#fn:21">21</a> <a href="/facts/Tabu_search/olw8qTSl">Tabu search</a>,<a class="footnote-ref" id="fnref:22" href="#fn:22">22</a> and <a href="/facts/Coordinate_descent/wnU1rHLp">coordinate descent</a>.<a class="footnote-ref" id="fnref:23" href="#fn:23">23</a><a class="footnote-ref" id="fnref:24" href="#fn:24">24</a>
Burke et al. (2004)<a class="footnote-ref" id="fnref:25" href="#fn:25">25</a> summarised the state of art of academic research to the nurse rostering problem, including brief introductions of various then published solutions.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Assignment_problem/dIMpM0aW">Assignment problem</a></li>
<li><a href="/facts/Constraint_programming/rgkCK5bD">Constraint programming</a></li>
<li><a href="/facts/Employee_scheduling_software/LHvYPUzp">Employee scheduling software</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://web.archive.org/web/20120206032112/http://www.lania.mx/~ccoello/EMOO/jan00.ps.gz">A study on how to solve the NSP using CGA</a> at the <a href="/facts/Wayback_Machine/nmQ3a6JC">Wayback Machine</a> (archived February 6, 2012)</li>
<li><a href="https://www.mjc2.com/staff-planning-complexity.htm">Why is Scheduling People Hard?</a></li>
<li><a href="https://www.nurse-scheduling-software.com/">A free solver for nurse scheduling problem</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">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. <a href="https://doi.org/10.3390%2Fa6020278" target="_blank">https://doi.org/10.3390%2Fa6020278</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="/wiki/ArXiv_(identifier)" target="_blank">/wiki/ArXiv_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Beddoe, Gareth; Petrovic, Sanja (2003). "A novel approach to finding feasible solutions to personnel rostering problems" (PDF). Savannah, Georgia: Proceedings of the 14th Annual Conference of the Production and Operation Management Society: 1–13. Archived from the original (PDF) on 29 August 2017. Retrieved 20 March 2014. {{cite journal}}: Cite journal requires |journal= (help) <a href="https://web.archive.org/web/20170829183208/https://www.pomsmeetings.org/ConfProceedings/001/Papers/PSC-08.1.pdf" target="_blank">https://web.archive.org/web/20170829183208/https://www.pomsmeetings.org/ConfProceedings/001/Papers/PSC-08.1.pdf</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="https://academic.oup.com/jrsssc/article-abstract/5/3/146/6862850" target="_blank">https://academic.oup.com/jrsssc/article-abstract/5/3/146/6862850</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="https://pubsonline.informs.org/doi/abs/10.1287/opre.24.5.857" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/opre.24.5.857</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="https://pubsonline.informs.org/doi/abs/10.1287/opre.24.5.842" target="_blank">https://pubsonline.informs.org/doi/abs/10.1287/opre.24.5.842</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">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. <a href="https://doi.org/10.3390%2Fa6020278" target="_blank">https://doi.org/10.3390%2Fa6020278</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">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. <a href="https://doi.org/10.3390%2Fa6020278" target="_blank">https://doi.org/10.3390%2Fa6020278</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn: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. <a href="/wiki/Annals_of_Operations_Research" target="_blank">/wiki/Annals_of_Operations_Research</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">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. <a href="https://doi.org/10.3390%2Fa6020278" target="_blank">https://doi.org/10.3390%2Fa6020278</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">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. <a href="https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf" target="_blank">https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">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: 1–12. Archived from the original (PDF) on 20 March 2014. Retrieved 20 March 2014. {{cite journal}}: Cite journal requires |journal= (help) <a href="https://web.archive.org/web/20140320215801/http://www.cem.brighton.ac.uk/research/cig/papers/SWAT.pdf" target="_blank">https://web.archive.org/web/20140320215801/http://www.cem.brighton.ac.uk/research/cig/papers/SWAT.pdf</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
<li id="fn:13">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. <a href="https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf" target="_blank">https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf</a> <a href="#fnref:13" class="footnote-back-ref">↩</a></li>
<li id="fn:14">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. {{cite journal}}: Cite journal requires |journal= (help) <a href="https://web.archive.org/web/20160304190332/http://wwwis.win.tue.nl/bnaic2009/papers/junk/bnaic2009_submission_41.pdf" target="_blank">https://web.archive.org/web/20160304190332/http://wwwis.win.tue.nl/bnaic2009/papers/junk/bnaic2009_submission_41.pdf</a> <a href="#fnref:14" class="footnote-back-ref">↩</a></li>
<li id="fn:15">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. {{cite journal}}: Cite journal requires |journal= (help) <a href="https://web.archive.org/web/20160304190332/http://wwwis.win.tue.nl/bnaic2009/papers/junk/bnaic2009_submission_41.pdf" target="_blank">https://web.archive.org/web/20160304190332/http://wwwis.win.tue.nl/bnaic2009/papers/junk/bnaic2009_submission_41.pdf</a> <a href="#fnref:15" class="footnote-back-ref">↩</a></li>
<li id="fn:16">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. <a href="/wiki/European_Journal_of_Operational_Research" target="_blank">/wiki/European_Journal_of_Operational_Research</a> <a href="#fnref:16" class="footnote-back-ref">↩</a></li>
<li id="fn:17">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. <a href="https://doi.org/10.3390%2Fa6020278" target="_blank">https://doi.org/10.3390%2Fa6020278</a> <a href="#fnref:17" class="footnote-back-ref">↩</a></li>
<li id="fn:18">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. <a href="https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf" target="_blank">https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf</a> <a href="#fnref:18" class="footnote-back-ref">↩</a></li>
<li id="fn:19">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. <a href="https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf" target="_blank">https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf</a> <a href="#fnref:19" class="footnote-back-ref">↩</a></li>
<li id="fn:20">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. <a href="https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf" target="_blank">https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf</a> <a href="#fnref:20" class="footnote-back-ref">↩</a></li>
<li id="fn:21">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. <a href="https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6731278" target="_blank">https://www.ncbi.nlm.nih.gov/pmc/articles/PMC6731278</a> <a href="#fnref:21" class="footnote-back-ref">↩</a></li>
<li id="fn:22">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. <a href="https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf" target="_blank">https://link.springer.com/content/pdf/10.1007/s10732-007-9066-7.pdf</a> <a href="#fnref:22" class="footnote-back-ref">↩</a></li>
<li id="fn:23">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. <a href="/wiki/European_Journal_of_Operational_Research" target="_blank">/wiki/European_Journal_of_Operational_Research</a> <a href="#fnref:23" class="footnote-back-ref">↩</a></li>
<li id="fn:24">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: 1–11. Retrieved 20 March 2014. {{cite journal}}: Cite journal requires |journal= (help) <a href="http://www.math.cmu.edu/~af1p/Teaching/OR2/Projects/P23/ORProject_Final_Copy.pdf" target="_blank">http://www.math.cmu.edu/~af1p/Teaching/OR2/Projects/P23/ORProject_Final_Copy.pdf</a> <a href="#fnref:24" class="footnote-back-ref">↩</a></li>
<li id="fn:25">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. <a href="https://lirias.kuleuven.be/bitstream/123456789/123829/1/JOS_" target="_blank">https://lirias.kuleuven.be/bitstream/123456789/123829/1/JOS_</a> <a href="#fnref:25" class="footnote-back-ref">↩</a></li>
</ol>

Nurse scheduling problem open-in-new

Nurse scheduling problem