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. Solutions to the nurse scheduling problem can be applied to constrained scheduling problems in other fields.

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

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, or as a hard constraint.

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

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