Nurse scheduling problem

From Wikipedia, the free encyclopedia

The Nurse scheduling problem (NSP) is the problem of efficiently scheduling when nurses ought to work, while remaining reasonable. However it seems trivial of nature it is complex due to its many constraints and many possible combinations. It is a nice example of the difficulties we face in Constraint programming.

1 General description
2 Mathematic description
3 Constraints
4 Computing efforts
5 References

[edit] General description

The Nurse scheduling problem (NSP) problem is all about assigment of shifts and holidays to nurses. A nurse has her/his wishes/restrictions. The problem is described as finding a schedule that respects the constraints of the nurses and fulfilling 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 search a solution satisfying as much wishes as possible while not threspassing 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, they won't be doing shifts then.
A nurse doesn't do a late night shift followed by a day shift the next day.

[edit] Mathematic description

Let N represent the number of nurses. Let M represent the number of days we want to schedule for. Let w represent the shift, 1, 2, 3 being day shift, night shift, late night shift and 4 being a day off.
We must find a matrix where each element X_ijw is defined as: X_ijw = 1 if nurse i works shift w on day j. X_ijw = 0 otherwise.

[edit] 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.

[edit] Computing efforts

Due to its high amount of constraints and the many possible combinations this problem is probably best solved by using a heuristic, like coorperate genetic algorithms. Like many scheduling problems this problem appears to be NP (complexity).