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][4]

The nurse scheduling problem has been studied since before 1969,[5] and is known to have NP-hard complexity.[1]

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:

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:

Some examples of constraints are:

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.[1] Differences in qualifications between nurses also create hard constraints.[6] 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.[1] The shift preferences of individual nurses may be treated as a soft constraint,[7] or as a hard constraint.[8]

Solutions

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

Burke et al. (2004)[11] 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 4 5 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 (Multidisciplinary Digital Publishing Institute) (6): 278–308. doi:10.3390/a6020278. ISSN 1999-4893. Retrieved 14 February 2014.
  2. ↑ Ko, Young-Woong; Kim, Donghoi; Jeong, Minyeong; Jeon, Wooram; Uhmn, Saangyong; Kim, Jin (July 2013). "An Improvement Technique for Simulated Annealing and Its Application to Nurse Scheduling Problem" (PDF). International Journal of Software Engineering and Its Applications (Science & Engineering Research Support Society) 7 (4): 269–278. Retrieved 20 March 2014.
  3. ↑ Aickelin, Uwe; Dowsland, Kathryn A. (2004). "An Indirect Genetic Algorithm for a Nurse Scheduling Problem" (PDF). Computers & Operations Research (arXiv) 31 (5): 761–778. doi:10.1016/s0305-0548(03)00034-0. Retrieved 20 March 2014.
  4. ↑ 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. Retrieved 20 March 2014.
  5. 1 2 3 Lagatie, Ruben; Haspeslagh, Stefaan; De Causmaecker, Patrick (2009). "Negotiation Protocols for Distributed Nurse Rostering" (PDF). Eindhoven University of Technology Department of Computer Science. Retrieved 14 February 2014.
  6. ↑ Aickelin, Uwe; White, Paul (2004). "Building Better Nurse Scheduling Algorithms" (PDF). Annals of Operations Research (arXiv) 128: 159–177. doi:10.1023/b:anor.0000019103.31340.a6. Retrieved 20 March 2014.
  7. 1 2 3 4 5 6 Goodman, Melissa D.; Dowsland, Kathryn A.; Thompson, Jonathan M. (2009). "A GRASP-KNAPSACK HYBRID FOR A NURSE-SCHEDULING PROBLEM" (PDF). Cardiff: Cardiff University School of Mathematics: 1–31. Retrieved 4 October 2015.
  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: 1–12. Retrieved 20 March 2014.
  9. 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 (Elsevier). doi:10.1016/j.ejor.2015.11.022. Retrieved 2 December 2015.
  10. ↑ 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.
  11. ↑ Burke, Edmund; De Causmaecker, Patrick; Berghe, Greet Vanden; Van Landeghem, Hendrik. "The state of the art of nurse rostering". Journal of scheduling 7 (6): 441–499. Retrieved 10 January 2016.

External links

This article is issued from Wikipedia - version of the Saturday, April 16, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.