The nurse scheduling problem (NSP), also called the nurse rostering problem (NRP), is the
operations research
Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve decis ...
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.
[
] Solutions to the nurse scheduling problem can be applied to constrained scheduling problems in other fields.
[
][
]
The nurse scheduling problem has been studied since before 1969,
and is known to have
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
complexity.
General description
The nurse scheduling problem involves the assignment of shifts and holidays to
nurse
Nursing is a profession within the health care sector focused on the care of individuals, families, and communities so they may attain, maintain, or recover optimal health and quality of life. Nurses may be differentiated from other health ...
s. 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 lazy and must be paired with a hard worker.
* 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. 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,
or as a hard constraint.
Solutions
Solutions to the problem use a variety of techniques, including both mathematically exact solutions
[ and a variety of heuristic solutions using ]decomposition
Decomposition or rot is the process by which dead organic substances are broken down into simpler organic or inorganic matter such as carbon dioxide, water, simple sugars and mineral salts. The process is a part of the nutrient cycle and ...
,parallel computing
Parallel computing is a type of computation in which many calculations or processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. There are several different f ...
,stochastic optimization
Stochastic optimization (SO) methods are optimization methods that generate and use random variables. For stochastic problems, the random variables appear in the formulation of the optimization problem itself, which involves random objective functi ...
,genetic algorithm
In computer science and operations research, a genetic algorithm (GA) is a metaheuristic inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA). Genetic algorithms are commonly used to ge ...
s,[ colony optimization,][ simulated annealing,][ quantum annealing ]Tabu search Tabu search is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986
and formalized in 1989.
Local (neighborhood) searches take a potential solution to a pro ...
,[ and ]coordinate descent Coordinate descent is an optimization algorithm that successively minimizes along coordinate directions to find the minimum of a function. At each iteration, the algorithm determines a coordinate or coordinate block via a coordinate selection rule, ...
.[
]
See also
* Assignment problem
The assignment problem is a fundamental combinatorial optimization problem. In its most general form, the problem is as follows:
:The problem instance has a number of ''agents'' and a number of ''tasks''. Any agent can be assigned to perform any ta ...
* Constraint programming
* Employee scheduling software
References
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
Why is Scheduling People Hard?A free solver for nurse scheduling problem
Nursing informatics
Constraint programming
Time management
Optimal scheduling