Nurse scheduling problem
Encyclopedia
The Nurse scheduling problem (NSP) is the problem of determining a work schedule for nurses that is both reasonable (or fair) and efficient. Despite seeming trivial, this is a complex problem due to its many constraints and many possible combinations.
It is a good example of the difficulties encountered in constraint programming
.
:
In this problem we must search for a solution satisfying as many wishes as possible while not compromising the needs of the hospital.
Some examples of constraints are:
s or local search
. Like many scheduling problems this problem appears to be NP-hard
.
It is a good example of the difficulties encountered in constraint programming
Constraint programming
Constraint programming is a programming paradigm wherein relations between variables are stated in the form of constraints. Constraints differ from the common primitives of imperative programming languages in that they do not specify a step or sequence of steps to execute, but rather the properties...
.
General description
The Nurse scheduling problem (NSP) problem is all about assignment of shifts and holidays to nurses. A nurse has her/his wishes/restrictions. 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 workShift work
Shift work is an employment practice designed to make use of the 24 hours of the clock. The term "shift work" includes both long-term night shifts and work schedules in which employees change or rotate shifts....
:
- 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.
Some examples of constraints are:
- A nurse doesn't work the day shift, night shift and late night shift on the same day (for obvious reasons).
- A nurse may go on a holiday and will not work shifts during this time.
- A nurse doesn't do a late night shift followed by a day shift the next day.
Constraints
We have 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 doesn't make the schedule invalid.
Computing efforts
Due to its high number of constraints and the many possible solutions, this problem is probably best solved by using a heuristic, like cooperate genetic algorithmGenetic algorithm
A genetic algorithm is a search heuristic that mimics the process of natural evolution. This heuristic is routinely used to generate useful solutions to optimization and search problems...
s or local search
Local search (optimization)
In computer science, local search is a metaheuristic 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...
. Like many scheduling problems this problem appears to be NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
.