Employee Scheduling

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.
You can solve this problem using the constraint programming solver.

There are two ways to formulate the problem:

  • Assign nurses to shifts
  • Assign shifts to nurses
As it turns out, the best way to solve the problem is to use both formulations at the same time.

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.
As with the previous constraint, the 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 ms
We 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()

Enviar comentarios sobre…