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 |
[edit] 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.
[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] Validity constraint on the run
The harder generic constraints come with running time: Buffer capacity is required at hands. Otherwise as soon as the scheduled period starts, the changes apart from the starting conditions come into effect. Without feedback the missing of re-scheduling leads to a bad service quality, if no jump-free role is made available. Then without buffer capacity the scheduled sequence will not be fulfilled in due time.
- Staffing outages come into effect. From the moment of the first outage becoming effective, the other subsequent part of the schedules will fail to serve completely or at least in punctuality with the given tasks.
- Time excess comes into effect with the first slip and the following finalization overruns. Each of the sequenced tasks will relay the achieved slip to the next, until additional workforce comes into the team.
[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 or local search. Like many scheduling problems this problem appears to be NP-hard.
