Nurse scheduling problem

The nurse scheduling problem (NSP), also called the nurse rostering problem (NRP), is the operations research problem of finding an optimal way to assign nurses to shifts, typically with a set of hard constraints which all valid solutions must follow, and a set of soft constraints which define the relative quality of valid solutions.^[1] Solutions to the nurse scheduling problem can be applied to constrained scheduling problems in other fields.^[2][3]

While research on computer-assisted employee scheduling goes back to the 1950s,^[4] the nurse scheduling problem in its current form was introduced in two parallel publications in 1976.^[5][6] It is known to have NP-hard complexity.^[1]

Conventionally, hospital nursing is shift work that is divided up to provide coverage 24 hours per day, 7 days per week. The hospital has restrictions and requirements for what coverage is needed, and each nurse has their own wishes and restrictions as well. The problem is described as finding a schedule that fulfills the objectives of the hospital and covers all shifts, while respecting as many of the nurses' preferences as possible.

The problem is not unique to nursing. It applies in any other profession or situation where shift coverage must be planned out.

Creating a schedule means attempting to satisfy certain constraints on how that schedule is laid out. There are two types of constraint: hard constraints, which must be met for the schedule to be valid; and soft constraints, which are desirable but not mandatory.

Depending on the policies of a hospital, the preferences of individual nurses may be treated as either a soft constraint,^[7] or as a hard constraint.^[8]

Hard constraints may include physical limitations or legal requirements. Some examples of possible hard constraints are:

• All shifts require nursing coverage.
• A nurse cannot work more than one shift at the same time.
• A nurse cannot work more than 24 hours in a day, or more than 7 days in a week.
• A nurse must not work more than a legally specified number of days in a row.
• A nurse must have a legally specified number of rest hours between shifts.
• Any newly licensed nurse must be paired with an experienced nurse.
• There must always be one charge nurse on duty.
• Certain shifts must be covered by nurses with special qualifications.^[9]

Soft constraints may be hospital policies or nurse preferences. Some examples of possible soft constraints are:

• All nurses should work approximately the same number of weekend shifts.
• All nurses should work approximately the same difficulty in shift assignments.
• A nurse should not work a day shift and a night shift without a rest day in between.
• One nurse prefers to have all their work days in a row, and then have all their days off in a row.
• One nurse prefers to work no more than two consecutive days, with a day off in between.
• One nurse cannot work Wednesday each week because they have no child care available that day.
• Two nurses feel they work well together and prefer to be scheduled to work together.

Solutions to the problem use a variety of techniques, including both mathematically exact solutions^[7] and a variety of heuristic solutions using decomposition,^[10] parallel computing,^[10][11] stochastic optimization,^[1] genetic algorithms,^[7] colony optimization,^[7] simulated annealing,^[7] quantum annealing,^[12] Tabu search,^[7] and coordinate descent.^[11][13]

Burke et al. (2004)^[14] summarised the state of art of academic research to the nurse rostering problem, including brief introductions of various then published solutions.

• Assignment problem
• Constraint programming
• Employee scheduling software

• A study on how to solve the NSP using CGA at the Wayback Machine (archived February 6, 2012)
• Why is Scheduling People Hard?
• A free solver for nurse scheduling problem