Nurse scheduling problem

From Wikipedia, the free 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.

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 both respects the constraints of the nurses and fulfils 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.

[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 number of constraints and the many possible solutions, this problem is probably best solved by using a heuristic, like cooperate genetic algorithms. Like many scheduling problems this problem appears to have NP (complexity).