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

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. [7] 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, [8] or as a hard constraint. [9]

Solutions

Solutions to the problem use a variety of techniques, including both mathematically exact solutions [8] and a variety of heuristic solutions using decomposition, [10] parallel computing, [10] [11] stochastic optimization, [1] genetic algorithms, [8] colony optimization, [8] simulated annealing, [8] quantum annealing [12] Tabu search, [8] 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

Related Research Articles

<span class="mw-page-title-main">Travelling salesman problem</span> NP-hard problem in combinatorial optimization

The travelling salesman problem, also known as the travelling salesperson problem (TSP), asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?" It is an NP-hard problem in combinatorial optimization, important in theoretical computer science and operations research.

Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize a multivariate quadratic function subject to linear constraints on the variables. Quadratic programming is a type of nonlinear programming.

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

<span class="mw-page-title-main">Simulated annealing</span> Probabilistic optimization technique and metaheuristic

Simulated annealing (SA) is a probabilistic technique for approximating the global optimum of a given function. Specifically, it is a metaheuristic to approximate global optimization in a large search space for an optimization problem. For large numbers of local optima, SA can find the global optima. It is often used when the search space is discrete. For problems where finding an approximate global optimum is more important than finding a precise local optimum in a fixed amount of time, simulated annealing may be preferable to exact algorithms such as gradient descent or branch and bound.

Constraint satisfaction problems (CSPs) are mathematical questions defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint satisfaction methods. CSPs are the subject of research in both artificial intelligence and operations research, since the regularity in their formulation provides a common basis to analyze and solve problems of many seemingly unrelated families. CSPs often exhibit high complexity, requiring a combination of heuristics and combinatorial search methods to be solved in a reasonable time. Constraint programming (CP) is the field of research that specifically focuses on tackling these kinds of problems. Additionally, the Boolean satisfiability problem (SAT), satisfiability modulo theories (SMT), mixed integer programming (MIP) and answer set programming (ASP) are all fields of research focusing on the resolution of particular forms of the constraint satisfaction problem.

In computer science, local search is a heuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions. Local search algorithms move from solution to solution in the space of candidate solutions by applying local changes, until a solution deemed optimal is found or a time bound is elapsed.

<span class="mw-page-title-main">Combinatorial optimization</span> Subfield of mathematical optimization

Combinatorial optimization is a subfield of mathematical optimization that consists of finding an optimal object from a finite set of objects, where the set of feasible solutions is discrete or can be reduced to a discrete set. Typical combinatorial optimization problems are the travelling salesman problem ("TSP"), the minimum spanning tree problem ("MST"), and the knapsack problem. In many such problems, such as the ones previously mentioned, exhaustive search is not tractable, and so specialized algorithms that quickly rule out large parts of the search space or approximation algorithms must be resorted to instead.

Multi-disciplinary design optimization (MDO) is a field of engineering that uses optimization methods to solve design problems incorporating a number of disciplines. It is also known as multidisciplinary system design optimization (MSDO), and multidisciplinary design analysis and optimization (MDAO).

In computer science and mathematical optimization, a metaheuristic is a higher-level procedure or heuristic designed to find, generate, tune, or select a heuristic that may provide a sufficiently good solution to an optimization problem or a machine learning problem, especially with incomplete or imperfect information or limited computation capacity. Metaheuristics sample a subset of solutions which is otherwise too large to be completely enumerated or otherwise explored. Metaheuristics may make relatively few assumptions about the optimization problem being solved and so may be usable for a variety of problems.

A memetic algorithm (MA) in computer science and operations research, is an extension of the traditional genetic algorithm (GA) or more general evolutionary algorithm (EA). It may provide a sufficiently good solution to an optimization problem. It uses a suitable heuristic or local search technique to improve the quality of solutions generated by the EA and to reduce the likelihood of premature convergence.

Employee scheduling software automates the process of creating and maintaining a schedule. Automating the scheduling of employees increases productivity and allows organizations with hourly workforces to re-allocate resources to non-scheduling activities. Such software will usually track vacation time, sick time, compensation time, and alert when there are conflicts. As scheduling data is accumulated over time, it may be extracted for payroll or to analyze past activity. Although employee scheduling software may or may not make optimization decisions, it does manage and coordinate the tasks. Today's employee scheduling software often includes mobile applications. Mobile scheduling further increased scheduling productivity and eliminated inefficient scheduling steps. It may also include functionality including applicant tracking and on-boarding, time and attendance, and automatic limits on overtime. Such functionality can help organizations with issues like employee retention, compliance with labor laws, and other workforce management challenges.

<span class="mw-page-title-main">Vehicle routing problem</span> Optimization problem

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.

Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution. It is related to, but often distinguished from, probabilistic optimization methods such as chance-constrained optimization.

Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. Arc routings problems are NP hard, as opposed to route inspection problems that can be solved in polynomial-time.

The scenario approach or scenario optimization approach is a technique for obtaining solutions to robust optimization and chance-constrained optimization problems based on a sample of the constraints. It also relates to inductive reasoning in modeling and decision-making. The technique has existed for decades as a heuristic approach and has more recently been given a systematic theoretical foundation.

<span class="mw-page-title-main">Ravindra K. Ahuja</span> American computer scientist

Ravindra K. Ahuja is an Indian-born American computer scientist and entrepreneur. He is currently Professor of Industrial and Systems Engineering at the University of Florida in Gainesville, Florida, and CEO of the automation and optimization solutions provider Optym, which he founded in 2000 as Innovative Scheduling, Inc.

Ellis Lane Johnson is the Professor Emeritus and the Coca-Cola Chaired Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology in Atlanta, Georgia.

In the mathematical modeling of job shop scheduling problems, disjunctive graphs are a way of modeling a system of tasks to be scheduled and timing constraints that must be respected by the schedule. They are mixed graphs, in which vertices may be connected by both directed and undirected edges. The two types of edges represent constraints of two different types:

Unrelated-machines scheduling is an optimization problem in computer science and operations research. It is a variant of optimal job scheduling. We need to schedule n jobs J1, J2, ..., Jn on m different machines, such that a certain objective function is optimized. The time that machine i needs in order to process job j is denoted by pi,j. The term unrelated emphasizes that there is no relation between values of pi,j for different i and j. This is in contrast to two special cases of this problem: uniform-machines scheduling - in which pi,j = pi / sj, and identical-machines scheduling - in which pi,j = pi.

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 . 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). Savannah, Georgia: Proceedings of the 14th Annual Conference of the Production and Operation Management Society: 1–13. Retrieved 20 March 2014.{{cite journal}}: Cite journal requires |journal= (help)
  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. ↑ 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.
  8. 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.
  9. ↑ 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)
  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.{{cite journal}}: Cite journal requires |journal= (help)
  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: 1–11. Retrieved 20 March 2014.{{cite journal}}: Cite journal requires |journal= (help)
  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.