The nurse scheduling problem (NSP), also called the nurse rostering problem (NRP), is the
operations research
Operations research () (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a branch of applied mathematics that deals with the development and application of analytical methods to improve management and ...
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.
[
]
While research on computer-assisted employee scheduling goes back to the 1950s,
the nurse scheduling problem in its current form was introduced in two parallel publications in 1976.
It is known to have
NP-hard
In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...
complexity.
General description
The nurse scheduling problem involves the assignment of shifts and holidays to
nurse
Nursing is a health care profession that "integrates the art and science of caring and focuses on the protection, promotion, and optimization of health and human functioning; prevention of illness and injury; facilitation of healing; and alle ...
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 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. 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 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 is ess ...
,parallel computing
Parallel computing is a type of computing, computation in which many calculations or Process (computing), processes are carried out simultaneously. Large problems can often be divided into smaller ones, which can then be solved at the same time. ...
,stochastic optimization
Stochastic optimization (SO) are optimization methods that generate and use random variables. For stochastic optimization problems, the objective functions or constraints are random. Stochastic optimization also include methods with random iter ...
,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 g ...
s,[ colony optimization,][ ]simulated annealing
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. ...
,[ quantum annealing,][ and coordinate descent.][
]
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 t ...
* Constraint programming
Constraint programming (CP) is a paradigm for solving combinatorial problems that draws on a wide range of techniques from artificial intelligence, computer science, and operations research. In constraint programming, users declaratively state t ...
* Employee scheduling software Employee scheduling software automated planning and scheduling, automates the process of creating and maintaining a Schedule (workplace), schedule. Automating the scheduling of employees increases productivity and allows organizations with hourly wo ...
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