- Nurse scheduling problem
-
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.
Contents
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 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. 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 algorithms or local search. Like many scheduling problems this problem appears to be NP-hard.
External links
Categories:
Wikimedia Foundation. 2010.
