Companies that operate 24 hours a day, seven days a week, such as factories or hospitals,
need to solve a common
problem: how to schedule workers in multiple daily shifts so that each shift
is staffed by enough workers to maintain operations. The schedule can have various constraints
— for example, that no employee works two consecutive shifts. The following sections
present
an example of such a problem, called the *nurse scheduling problem*, and shows how to
solve it using OR-Tools.

## A nurse scheduling problem

In the next example, a hospital supervisor needs to create a weekly schedule for four nurses, subject to the following conditions:

- Each day is divided into three 8-hour shifts.
- On each day, all nurses are assigned to different shifts and one nurse has the day off.
- Each nurse works five or six days a week.
- No shift is staffed by more than two different nurses in a week.
- If a nurse works shifts 2 or 3 on a given day, he must also work the same shift either the previous day or the following day.

There are two ways to formulate the problem:

- Assign nurses to shifts
- Assign shifts to nurses

**Assign nurses to shifts**

The table below shows one possible assignment of the nurses, who are labeled A, B, C, D, to shifts, numbered 0 - 3 (where 0 means that the nurse does not work on that day).

Sun | Mon | Tue | Wed | Thu | Fri | Sat | |
---|---|---|---|---|---|---|---|

Shift 1 | A | B | A | A | A | A | A |

Shift 2 | C | C | C | B | B | B | B |

Shift 3 | D | D | D | D | C | C | D |

**Assign shifts to nurses**

The following table shows the corresponding assignment of shifts to nurses.

Sun | Mon | Tue | Wed | Thu | Fri | Sat | |
---|---|---|---|---|---|---|---|

Nurse A | 1 | 0 | 1 | 1 | 1 | 1 | 1 |

Nurse B | 0 | 1 | 0 | 2 | 2 | 2 | 2 |

Nurse C | 2 | 2 | 2 | 0 | 3 | 3 | 0 |

Nurse D | 3 | 3 | 3 | 3 | 0 | 0 | 3 |

## A Python solution.

The following sections present a Python solution to the nurse scheduling problem.

### Declare the solver and create the variables

The following code declares the CP solver and creates two arrays of variables for the
problem: `shifts`

and `nurses`

.

from ortools.constraint_solver import pywrapcp def main(): # Creates the solver. solver = pywrapcp.Solver("schedule_shifts") num_nurses = 4 num_shifts = 4 # Nurse assigned to shift 0 means not working that day. num_days = 7 # [START] # Create shift variables. shifts = {} for j in range(num_nurses): for i in range(num_days): shifts[(j, i)] = solver.IntVar(0, num_shifts - 1, "shifts(%i,%i)" % (j, i)) shifts_flat = [shifts[(j, i)] for j in range(num_nurses) for i in range(num_days)] # Create nurse variables. nurses = {} for j in range(num_shifts): for i in range(num_days): nurses[(j, i)] = solver.IntVar(0, num_nurses - 1, "shift%d day%d" % (j,i))

The arrays define assignments as follows:

`shifts[(j, i)]`

is the shift assigned to nurse j on day i.`nurses[(j, i)]`

is the nurse assigned to shift j on day i.

`shifts_flat`

is simply the "flattened" version of `shifts`

— a single
list of the variables. This is the form for the variables required by
`Phase`

method expects the variables.
### Define the relationship between nurses and shifts

Since `shifts`

and `nurses`

express the same assignments in different
ways, we expect them to be closely related. Specifically,
if nurse j is assigned to shift s on a given day, we want shift s to be assigned to nurse j
(and vice versa).
The following code creates a constraint that expresses this relationship, using the
`IndexOf`

method (corresponding to the C++ method
MakeIndexOfConstraint).

# Set relationships between shifts and nurses. for day in range(num_days): nurses_for_day = [nurses[(j, day)] for j in range(num_shifts)] for j in range(num_nurses): s = shifts[(j, day)] solver.Add(s.IndexOf(nurses_for_day) == j)For each day,

`nurses_for_day`

contains the nurse assignments for that day.
On any given day,
s = shifts[(j, day)]means that shift s is assigned to nurse j. We want to add the constraint that nurse j is assigned to shift s — in other words, that

`nurses_for_day[s] = j`

.
You can specify this constraint by the
`IndexOf`

method: `s.IndexOf(nurses_for_day)`

returns
`nurses_for_day[s]`

. As a result,
solver.Add(s.IndexOf(nurses_for_day) == j)adds precisely the constraint that

`nurses_for_day[s] == j`

.
### Nurses work different shifts

The following code defines the constraints that nurses are assigned to
different shifts on each day, using the `AllDifferent`

method (corresponding to the C++ method
`MakeAllDifferent`

).

# Make assignments different on each day for i in range(num_days): solver.Add(solver.AllDifferent([shifts[(j, i)] for j in range(num_nurses)])) solver.Add(solver.AllDifferent([nurses[(j, i)] for j in range(num_shifts)]))

`AllDifferent`

requires that on each day, nurses are assigned to different shifts
### Nurses work five or six days per week

The following code sets the constraint that each nurse works either five or six days per week.

# Each nurse works 5 or 6 days in a week. for j in range(num_nurses): solver.Add(solver.Sum([shifts[(j, i)] > 0 for i in range(num_days)]) >= 5) solver.Add(solver.Sum([shifts[(j, i)] > 0 for i in range(num_days)]) <= 6)Since

`shifts[(j, i)]`

is greater than 0 if nurse j works on day i, and equals 0 if not,
the expression
`solver.Sum([shifts[(j, i)] > 0 for i in range(num_days)]`

equals the number days
nurse i works. So the lines
solver.Add(solver.Sum([shifts[(j, i)] > 0 for i in range(num_days)]) >= 5) solver.Add(solver.Sum([shifts[(j, i)] > 0 for i in range(num_days)]) <= 6)add the constraint that the number of days worked is between 5 and 6.

### Shifts are staffed by at most two nurses per week

To create the constraint that each shift is staffed by at most two nurses, first
create an array of Boolean variables `works_shift`

, indexed by shifts and nurses,
so that
`works_shift[(i, j)]`

is True if nurse i works shift j at least once during the week.
The following code creates the variables.

works_shift = {} # works_shift[(j, i)] is 1 if nurse i works shift j at least one day in the week. for i in range(num_nurses): for j in range(num_shifts): works_shift[(i, j)] = solver.BoolVar('shift%d nurse%d' % (i, j)) for i in range(num_nurses): for j in range(num_shifts): solver.Add(works_shift[(i, j)] == solver.Max([shifts[(i, k)] == j for k in range(num_days)]))In the last line of code above, the value of

`shifts[(i, k)] == j`

is 1 if nurse i works shift j on day k.
So `solver.Max`

works as a logical "or" operator on the values
[shifts[(i, k)] == j for k in range(num_days)]As a result,

solver.Max([shifts[(i, k)] == j for k in range(num_days)])is 1 if nurse i works shift j at least once during the week, and 0 otherwise.

Next, the following code adds the constraint that, for each shift j, the number of nurses who work shift j during the work is at most 2.

for j in range(1, num_shifts): solver.Add(solver.Sum([works_shift[(i, j)] for i in range(num_nurses)]) <= 2)

### Nurses work shift 2 or 3 on consecutive days

The final constraint is that if a nurse works shift 2 or 3 on a given day, he must also work the same shift either the previous day or the following day. To see how to express this constraint, let's look at an example for a single shift and day. If a nurse works shift 2 on a Tuesday (day 3), we require that he also work shift 2 either Monday or Wednesday. The following code adds this constraint.

solver.Add(solver.Max(nurses[(2,1)] == nurses[(2,2)], nurses[(2,2)] == nurses[(2,3)]) == 1)To see why this works, consider the two logical conditions in the code:

`nurses[(2,1)] == nurses[(2,2)]`

is True if the same nurse works shift 2 on Monday and Tuesday.`nurses[(2,2)] == nurses[(2,3)]`

is True if the same nurse works shift 2 on Tuesday or Wednesday.

`Max`

operator acts as a logical "or" between
these two condition, returning 1 if at least one of them is True.
The following code sets these contraints for shifts 2 and 3 for every day in the week.

solver.Add(solver.Max(nurses[(2, 0)] == nurses[(2, 1)], nurses[(2, 1)] == nurses[(2, 2)]) == 1) solver.Add(solver.Max(nurses[(2, 1)] == nurses[(2, 2)], nurses[(2, 2)] == nurses[(2, 3)]) == 1) solver.Add(solver.Max(nurses[(2, 2)] == nurses[(2, 3)], nurses[(2, 3)] == nurses[(2, 4)]) == 1) solver.Add(solver.Max(nurses[(2, 3)] == nurses[(2, 4)], nurses[(2, 4)] == nurses[(2, 5)]) == 1) solver.Add(solver.Max(nurses[(2, 4)] == nurses[(2, 5)], nurses[(2, 5)] == nurses[(2, 6)]) == 1) solver.Add(solver.Max(nurses[(2, 5)] == nurses[(2, 6)], nurses[(2, 6)] == nurses[(2, 0)]) == 1) solver.Add(solver.Max(nurses[(2, 6)] == nurses[(2, 0)], nurses[(2, 0)] == nurses[(2, 1)]) == 1) solver.Add(solver.Max(nurses[(3, 0)] == nurses[(3, 1)], nurses[(3, 1)] == nurses[(3, 2)]) == 1) solver.Add(solver.Max(nurses[(3, 1)] == nurses[(3, 2)], nurses[(3, 2)] == nurses[(3, 3)]) == 1) solver.Add(solver.Max(nurses[(3, 2)] == nurses[(3, 3)], nurses[(3, 3)] == nurses[(3, 4)]) == 1) solver.Add(solver.Max(nurses[(3, 3)] == nurses[(3, 4)], nurses[(3, 4)] == nurses[(3, 5)]) == 1) solver.Add(solver.Max(nurses[(3, 4)] == nurses[(3, 5)], nurses[(3, 5)] == nurses[(3, 6)]) == 1) solver.Add(solver.Max(nurses[(3, 5)] == nurses[(3, 6)], nurses[(3, 6)] == nurses[(3, 0)]) == 1) solver.Add(solver.Max(nurses[(3, 6)] == nurses[(3, 0)], nurses[(3, 0)] == nurses[(3, 1)]) == 1)Note that the days of the week wrap around from Saturday to Sunday in the last couple of lines in both groups of constraints.

These constraints could be written more compactly by looping over the days of the week. We have written them explicitly to make the logic clearer.

### Add the decision builder and solution collector

The following code adds the decision_builder and solution collector for the problem. The decision builder contains the variables for the problem and options for the solver. The solution collector stores the solutions while the solver is running, so that you can access them later. This is convenient when there are many solutions, as in this example.

# Create the decision builder. db = solver.Phase(shifts_flat, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) # Create the solution collector. solution = solver.Assignment() solution.Add(shifts_flat) collector = solver.AllSolutionCollector(solution)

### Call the solver and display the results

The following code calls the solver and displays a few of the solutions.

solver.Solve(db, [collector]) print("Solutions found:", collector.SolutionCount()) print("Time:", solver.WallTime(), "ms") print() # Display a few solutions picked at random. a_few_solutions = [859, 2034, 5091, 7003] for sol in a_few_solutions: print("Solution number" , sol, '\n') for i in range(num_days): print("Day", i) for j in range(num_nurses): print("Nurse", j, "assigned to task", collector.Value(sol, shifts[(j, i)])) print()Even with all the constraints we have imposed, there are still over 18000 possible solutions.

Solutions found: 18144 Time: 645 msWe display four of them chosen at random.

Solution number 859 Day 0 Nurse 0 assigned to task 0 Nurse 1 assigned to task 2 Nurse 2 assigned to task 3 Nurse 3 assigned to task 1 Day 1 Nurse 0 assigned to task 0 Nurse 1 assigned to task 2 Nurse 2 assigned to task 3 Nurse 3 assigned to task 1 Day 2 Nurse 0 assigned to task 2 Nurse 1 assigned to task 1 Nurse 2 assigned to task 3 Nurse 3 assigned to task 0 Day 3 Nurse 0 assigned to task 2 Nurse 1 assigned to task 0 Nurse 2 assigned to task 3 Nurse 3 assigned to task 1 Day 4 Nurse 0 assigned to task 2 Nurse 1 assigned to task 0 Nurse 2 assigned to task 3 Nurse 3 assigned to task 1 Day 5 Nurse 0 assigned to task 3 Nurse 1 assigned to task 2 Nurse 2 assigned to task 0 Nurse 3 assigned to task 1 Day 6 Nurse 0 assigned to task 3 Nurse 1 assigned to task 2 Nurse 2 assigned to task 0 Nurse 3 assigned to task 1 Solution number 2034 Day 0 Nurse 0 assigned to task 0 Nurse 1 assigned to task 1 Nurse 2 assigned to task 3 Nurse 3 assigned to task 2 Day 1 Nurse 0 assigned to task 1 Nurse 1 assigned to task 2 Nurse 2 assigned to task 3 Nurse 3 assigned to task 0 Day 2 Nurse 0 assigned to task 1 Nurse 1 assigned to task 2 Nurse 2 assigned to task 0 Nurse 3 assigned to task 3 Day 3 Nurse 0 assigned to task 1 Nurse 1 assigned to task 2 Nurse 2 assigned to task 0 Nurse 3 assigned to task 3 Day 4 Nurse 0 assigned to task 1 Nurse 1 assigned to task 2 Nurse 2 assigned to task 3 Nurse 3 assigned to task 0 Day 5 Nurse 0 assigned to task 1 Nurse 1 assigned to task 0 Nurse 2 assigned to task 3 Nurse 3 assigned to task 2 Day 6 Nurse 0 assigned to task 0 Nurse 1 assigned to task 1 Nurse 2 assigned to task 3 Nurse 3 assigned to task 2 Solution number 5091 Day 0 Nurse 0 assigned to task 1 Nurse 1 assigned to task 3 Nurse 2 assigned to task 2 Nurse 3 assigned to task 0 Day 1 Nurse 0 assigned to task 0 Nurse 1 assigned to task 3 Nurse 2 assigned to task 2 Nurse 3 assigned to task 1 Day 2 Nurse 0 assigned to task 1 Nurse 1 assigned to task 0 Nurse 2 assigned to task 3 Nurse 3 assigned to task 2 Day 3 Nurse 0 assigned to task 1 Nurse 1 assigned to task 0 Nurse 2 assigned to task 3 Nurse 3 assigned to task 2 Day 4 Nurse 0 assigned to task 1 Nurse 1 assigned to task 3 Nurse 2 assigned to task 0 Nurse 3 assigned to task 2 Day 5 Nurse 0 assigned to task 0 Nurse 1 assigned to task 3 Nurse 2 assigned to task 2 Nurse 3 assigned to task 1 Day 6 Nurse 0 assigned to task 1 Nurse 1 assigned to task 3 Nurse 2 assigned to task 2 Nurse 3 assigned to task 0 Solution number 7003 Day 0 Nurse 0 assigned to task 1 Nurse 1 assigned to task 0 Nurse 2 assigned to task 3 Nurse 3 assigned to task 2 Day 1 Nurse 0 assigned to task 1 Nurse 1 assigned to task 2 Nurse 2 assigned to task 0 Nurse 3 assigned to task 3 Day 2 Nurse 0 assigned to task 1 Nurse 1 assigned to task 2 Nurse 2 assigned to task 0 Nurse 3 assigned to task 3 Day 3 Nurse 0 assigned to task 0 Nurse 1 assigned to task 2 Nurse 2 assigned to task 1 Nurse 3 assigned to task 3 Day 4 Nurse 0 assigned to task 1 Nurse 1 assigned to task 2 Nurse 2 assigned to task 3 Nurse 3 assigned to task 0 Day 5 Nurse 0 assigned to task 1 Nurse 1 assigned to task 2 Nurse 2 assigned to task 3 Nurse 3 assigned to task 0 Day 6 Nurse 0 assigned to task 1 Nurse 1 assigned to task 0 Nurse 2 assigned to task 3 Nurse 3 assigned to task 2

### The entire program

Here is the entire program for the nurse scheduling problem.

from __future__ import print_function import sys from ortools.constraint_solver import pywrapcp def main(): # Creates the solver. solver = pywrapcp.Solver("schedule_shifts") num_nurses = 4 num_shifts = 4 # Nurse assigned to shift 0 means not working that day. num_days = 7 # [START] # Create shift variables. shifts = {} for j in range(num_nurses): for i in range(num_days): shifts[(j, i)] = solver.IntVar(0, num_shifts - 1, "shifts(%i,%i)" % (j, i)) shifts_flat = [shifts[(j, i)] for j in range(num_nurses) for i in range(num_days)] # Create nurse variables. nurses = {} for j in range(num_shifts): for i in range(num_days): nurses[(j, i)] = solver.IntVar(0, num_nurses - 1, "shift%d day%d" % (j,i)) # Set relationships between shifts and nurses. for day in range(num_days): nurses_for_day = [nurses[(j, day)] for j in range(num_shifts)] for j in range(num_nurses): s = shifts[(j, day)] solver.Add(s.IndexOf(nurses_for_day) == j) # Make assignments different on each day for i in range(num_days): solver.Add(solver.AllDifferent([shifts[(j, i)] for j in range(num_nurses)])) solver.Add(solver.AllDifferent([nurses[(j, i)] for j in range(num_shifts)])) # Each nurse works 5 or 6 days in a week. for j in range(num_nurses): solver.Add(solver.Sum([shifts[(j, i)] > 0 for i in range(num_days)]) >= 5) solver.Add(solver.Sum([shifts[(j, i)] > 0 for i in range(num_days)]) <= 6) # Create works_shift variables. works_shift[(i, j)] is True if nurse # i works shift j at least once during the week. works_shift = {} for i in range(num_nurses): for j in range(num_shifts): works_shift[(i, j)] = solver.BoolVar('shift%d nurse%d' % (i, j)) for i in range(num_nurses): for j in range(num_shifts): solver.Add(works_shift[(i, j)] == solver.Max([shifts[(i, k)] == j for k in range(num_days)])) # For each shift (other than 0), at most 2 nurses are assigned to that shift # during the week. for j in range(1, num_shifts): solver.Add(solver.Sum([works_shift[(i, j)] for i in range(num_nurses)]) <= 2) # If s nurses works shifts 2 or 3 on, he must also work that shift the previous # day or the following day. solver.Add(solver.Max(nurses[(2, 0)] == nurses[(2, 1)], nurses[(2, 1)] == nurses[(2, 2)]) == 1) solver.Add(solver.Max(nurses[(2, 1)] == nurses[(2, 2)], nurses[(2, 2)] == nurses[(2, 3)]) == 1) solver.Add(solver.Max(nurses[(2, 2)] == nurses[(2, 3)], nurses[(2, 3)] == nurses[(2, 4)]) == 1) solver.Add(solver.Max(nurses[(2, 3)] == nurses[(2, 4)], nurses[(2, 4)] == nurses[(2, 5)]) == 1) solver.Add(solver.Max(nurses[(2, 4)] == nurses[(2, 5)], nurses[(2, 5)] == nurses[(2, 6)]) == 1) solver.Add(solver.Max(nurses[(2, 5)] == nurses[(2, 6)], nurses[(2, 6)] == nurses[(2, 0)]) == 1) solver.Add(solver.Max(nurses[(2, 6)] == nurses[(2, 0)], nurses[(2, 0)] == nurses[(2, 1)]) == 1) solver.Add(solver.Max(nurses[(3, 0)] == nurses[(3, 1)], nurses[(3, 1)] == nurses[(3, 2)]) == 1) solver.Add(solver.Max(nurses[(3, 1)] == nurses[(3, 2)], nurses[(3, 2)] == nurses[(3, 3)]) == 1) solver.Add(solver.Max(nurses[(3, 2)] == nurses[(3, 3)], nurses[(3, 3)] == nurses[(3, 4)]) == 1) solver.Add(solver.Max(nurses[(3, 3)] == nurses[(3, 4)], nurses[(3, 4)] == nurses[(3, 5)]) == 1) solver.Add(solver.Max(nurses[(3, 4)] == nurses[(3, 5)], nurses[(3, 5)] == nurses[(3, 6)]) == 1) solver.Add(solver.Max(nurses[(3, 5)] == nurses[(3, 6)], nurses[(3, 6)] == nurses[(3, 0)]) == 1) solver.Add(solver.Max(nurses[(3, 6)] == nurses[(3, 0)], nurses[(3, 0)] == nurses[(3, 1)]) == 1) # Create the decision builder. db = solver.Phase(shifts_flat, solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE) # Create the solution collector. solution = solver.Assignment() solution.Add(shifts_flat) collector = solver.AllSolutionCollector(solution) solver.Solve(db, [collector]) print("Solutions found:", collector.SolutionCount()) print("Time:", solver.WallTime(), "ms") print() # Display a few solutions picked at random. a_few_solutions = [859, 2034, 5091, 7003] for sol in a_few_solutions: print("Solution number" , sol, '\n') for i in range(num_days): print("Day", i) for j in range(num_nurses): print("Nurse", j, "assigned to task", collector.Value(sol, shifts[(j, i)])) print() if __name__ == "__main__": main()