3.2 Workforce shift scheduling#
Preamble: Install Pyomo and a solver#
The following cell sets and verifies a global SOLVER for the notebook. If run on Google Colab, the cell installs Pyomo and the HiGHS solver, while, if run elsewhere, it assumes Pyomo and HiGHS have been previously installed. It then sets to use HiGHS as solver via the appsi module and a test is performed to verify that it is available. The solver interface is stored in a global object SOLVER for later use.
import sys
if "google.colab" in sys.modules:
%pip install pyomo >/dev/null 2>/dev/null
%pip install highspy >/dev/null 2>/dev/null
solver = "appsi_highs"
import pyomo.environ as pyo
SOLVER = pyo.SolverFactory(solver)
assert SOLVER.available(), f"Solver {solver} is not available."
Problem Statement#
An article entitled “Modeling and optimization of a weekly workforce with Python and Pyomo” by Christian Carballo Lozano posted on Towards Data Science showed how to build a Pyomo model to schedule weekly shifts for a small campus food store. The article was primarily intended as a tutorial introduction to Pyomo (see the github repository for the code).
From the original article:
A new food store has been opened at the University Campus which will be open 24 hours a day, 7 days a week. Each day, there are three eight-hour shifts. Morning shift is from 6:00 to 14:00, evening shift is from 14:00 to 22:00 and night shift is from 22:00 to 6:00 of the next day. During the night there is only one worker while during the day there are two, except on Sunday that there is only one for each shift. Each worker will not exceed a maximum of 40 hours per week and have to rest for 12 hours between two shifts. As for the weekly rest days, an employee who rests one Sunday will also prefer to do the same that Saturday. In principle, there are available ten employees, which is clearly over-sized. The less the workers are needed, the more the resources for other stores.
Here we revisit the example with a new model demonstrating how to use of Pyomo decorators and of Pyomo sets, and how to use the model solution to create useful visualizations and reports for workers and managers.
Model formulation#
Model sets#
Assuming that we have \(N\) available workers, the problem requires the assignment of these available workers to a predetermined set of shifts with specific staffing requirements. Let \(\text{R}_{d, s}\) describe the minimum number of workers required for the day-shift pair \((d, s)\).
There are three shifts per day, seven days per week. These observations suggest the need for three ordered sets:
Wis a set with \(N\) elements representing workers.Dis the set with the 7 days of the week.Sis the set with the three daily shifts.
It is convenient to add the following additional sets to improve the readability of the model:
Tis the set of the ordered (day, shift) pairs describing all the available shifts during the week.Bis the ordered set of all overlapping 24-hour periods in the week. An element of the set contains the (day, shift) period in the corresponding period. This set will be used to limit worker assignments to no more than one for each 24-hour period.Eis the set of all (day, shift) pairs on a weekend. This set will be used to implement worker preferences on weekend scheduling.
To recap, the sets that we will be using are defined as follows:
Model parameters#
Model decision variables#
Note, in particular, that we have only binary decision variables.
Model objective#
The model objective is to minimize the overall number of workers needed to fill the shift and work requirements while also trying to meet worker preferences regarding weekend shift assignments. This is achieved here by minimizing a weighted sum of the number of workers needed to meet all shift requirements and the number of workers assigned to weekend shifts. The resulting objective function is
where the weight \(\gamma\) is a fixed positive parameter that determines the relative importance of these two measures in a desirable shift schedule.
Model constraints#
Let us now formulate all the constraints using the variables we have created.
At each day-shift we need to have enough workers to meet staffing requirements:
No worker can be assigned more than 40 hours per week, which means that the total number of day-shifts times 8 hours per each cannot be greater than 40:
No worker can be assigned more than one shift in each 24-hour period, to enforce which we need to loop over all 24h-long periods of three consecutive work-shifts and make sure that per each worker the total number of assignments is less than or equal to one:
The variable \(n_w\) needs to correctly be equal to 1 if a given worker is assigned to any of the day-shifts during the week, and 0 otherwise. Keeping in mind that \(|T| = 21\) is the total number of day-shifts during the week, we can implement this relationship as follows:
\[ \begin{align*} \sum_{d,s\in\text{ T}} a_{w,d,s} & \leq 21 \cdot n_w & \forall w\in \text{W} \end{align*} \]Indeed, whenever any of the variables \(a_{w,d,s}\) is equal to 1, \(n_w\) has to become equal to 1, while at the same time, the number 21 is big enough for the right-hand side not to be a restriction (beyond what the other constraints do) on the total number of shifts assigned to a worked in this constraint. At the same time, because in our objective function we minimize, the variable \(n_w\) will naturally become equal to \(0\) in an optimal solution where the left-hand side would be equal to 0, so the constraint correctly enforces tracking the number of employed workers during the week.
The variable \(e_w\) needs to be equal to 1 when worker \(w\) is assigned to any of the weekend day-shifts. We can formulate a constraint that will enforce this relationship correctly in the context of our problem as follows:
\[ \begin{align*} \sum_{d,s\in\text{ E}} a_{w,d,s} & \leq 6 \cdot e_w & \forall w\in \text{W} \end{align*} \]Indeed, variable \(e_w\) is forced to be equal to 1 if any day-shift on the weekend is assigned to worker \(w\) and since there are 6 day-shifts on the weekend, if that happens, this constraint does not impose extra limitations (beyond what the other constraints do) on the number of shifts assigned to \(w\) on the weekend. At the same time, since our objective is a minimization one, \(e_w\) will become equal to \(0\) in an optimal solution where \(w\) does not have any weekend day-shifts.
Pyomo implementation#
def shift_schedule(N=10, hours=40):
m = pyo.ConcreteModel("Workforce Shift Scheduling")
# ordered set of avaiable workers
m.W = pyo.Set(initialize=[f"W{i:02d}" for i in range(1, N + 1)])
# ordered sets of days and shifts
m.D = pyo.Set(initialize=["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"])
m.S = pyo.Set(initialize=["morning", "evening", "night"])
# ordered set of day, shift time slots
m.T = pyo.Set(initialize=m.D * m.S)
# ordered set of 24-hour time blocks
m.B = pyo.Set(
initialize=[
[m.T.at(i), m.T.at(i + 1), m.T.at(i + 2)] for i in range(1, len(m.T) - 1)
]
)
# ordered set of weekend shifts
m.E = pyo.Set(initialize=m.T, filter=lambda m, day, shift: day in ["Sat", "Sun"])
# parameter of worker requirements
@m.Param(m.T)
def R(m, day, shift):
if shift in ["night"] or day in ["Sun"]:
return 1
return 2
# max hours per week per worker
m.H = pyo.Param(mutable=True, default=hours)
# decision variable: a[worker, day, shift] = 1 assigns worker to a time slot
m.a = pyo.Var(m.W, m.T, domain=pyo.Binary)
# decision variables: e[worker] = 1 worker is assigned weekend shift
m.e = pyo.Var(m.W, domain=pyo.Binary)
# decision variable: n[worker] = 1
m.n = pyo.Var(m.W, domain=pyo.Binary)
# assign a sufficient number of workers for each time slot
@m.Constraint(m.T)
def required_workers(m, day, shift):
return m.R[day, shift] == sum(m.a[worker, day, shift] for worker in m.W)
# workers limited to forty hours per week assuming 8 hours per shift
@m.Constraint(m.W)
def forty_hour_limit(m, worker):
return 8 * sum(m.a[worker, day, shift] for day, shift in m.T) <= m.H
# workers are assigned no more than one time slot per 24 time block
@m.Constraint(m.W, m.B)
def required_rest(m, worker, d1, s1, d2, s2, d3, s3):
return m.a[worker, d1, s1] + m.a[worker, d2, s2] + m.a[worker, d3, s3] <= 1
# determine if a worker is assigned to any shift
@m.Constraint(m.W)
def is_needed(m, worker):
return (
sum(m.a[worker, day, shift] for day, shift in m.T) <= len(m.T) * m.n[worker]
)
# determine if a worker is assigned to a weekend shift
@m.Constraint(m.W)
def is__weekend(m, worker):
return sum(m.a[worker, day, shift] for day, shift in m.E) <= 6 * m.e[worker]
# minimize a blended objective of needed workers and needed weekend workers
@m.Objective(sense=pyo.minimize)
def minimize_workers(m):
return sum(
i * m.n[worker] + 0.1 * i * m.e[worker] for i, worker in enumerate(m.W)
)
return m
m = shift_schedule(10, 40)
_ = SOLVER.solve(m)
Visualizing the solution#
Scheduling applications generate a considerable amount of data to be used by the participants. The following cells demonstrate the preparation of charts and reports that can be used to communicate scheduling information to the store management and shift workers.
import matplotlib.pyplot as plt
from matplotlib.patches import Rectangle
def visualize(m):
bw = 1.0
workers = [worker for worker in m.W]
plt.rcParams["font.size"] = 14
fig, ax = plt.subplots(1, 1, figsize=(12, 2 + 0.3 * len(m.W)))
colormap = plt.cm.tab20c.colors
colors = [colormap[7], colormap[11], colormap[15]]
for i in range(len(m.T) + 1):
ax.axvline(i, lw=0.3)
ax.fill_between(
[i, i + 1], [0] * 2, [len(m.W)] * 2, alpha=0.8, color=colors[i % 3]
)
for i in range(len(m.D) + 1):
ax.axvline(3 * i, lw=1)
ax.set_xlim(0, len(m.T))
ax.set_xticks([3 * i + 1.5 for i in range(len(m.D))])
ax.set_xticklabels(m.D)
ax.set_xlabel("Shift")
ax.set_ylim(0, len(m.W))
for j in range(len(m.W) + 1):
ax.axhline(j, lw=0.3)
ax.set_yticks([j + 0.5 for j in range(len(m.W))])
ax.set_yticklabels(workers)
ax.set_ylabel("Worker")
# show shift assignments
for i, slot in enumerate(m.T):
day, shift = slot
for j, worker in enumerate(m.W):
if round(m.a[worker, day, shift]()):
ax.add_patch(
Rectangle((i, j + (1 - bw) / 2), 1, bw, edgecolor=colors[0])
)
ax.text(
i + 1 / 2, j + 1 / 2, worker, ha="center", va="center", color="w"
)
# display needed and weekend data
for j, worker in enumerate(m.W):
if not m.n[worker]():
ax.fill_between([0, len(m.T)], [j, j], [j + 1, j + 1], color="k", alpha=0.4)
if m.n[worker]() and not m.e[worker]():
ax.fill_between(
[15, len(m.T)], [j, j], [j + 1, j + 1], color="k", alpha=0.4
)
plt.tight_layout()
plt.show()
visualize(m)
Implementing the schedule with reports#
Optimal planning models can generate large amounts of data that need to be summarized and communicated to individuals for implementation.
Creating a master schedule with categorical data#
The following cell creates a pandas DataFrame comprising all active assignments from the solved model. The data consists of all (worker, day, shift) tuples for which the binary decision variable m.a equals one. The data is categorical consisting of a unique id for each worker, a day of the week, or the name of a shift. Each of the categories has a natural ordering that should be used in creating reports. This is implemented using the CategoricalDtype class.
import pandas as pd
schedule = pd.DataFrame(
[[w, d, s] for w in m.W for d, s in m.T if m.a[w, d, s]()],
columns=["worker", "day", "shift"],
)
# create and assign a worker category type
worker_type = pd.CategoricalDtype(categories=m.W, ordered=True)
schedule["worker"] = schedule["worker"].astype(worker_type)
# create and assign a day category type
day_type = pd.CategoricalDtype(categories=m.D, ordered=True)
schedule["day"] = schedule["day"].astype(day_type)
# create and assign a shift category type
shift_type = pd.CategoricalDtype(categories=m.S, ordered=True)
schedule["shift"] = schedule["shift"].astype(shift_type)
# demonstrate sorting and display of the master schedule
schedule.sort_values(by=["day", "shift", "worker"])
| worker | day | shift | |
|---|---|---|---|
| 23 | W06 | Mon | morning |
| 28 | W07 | Mon | morning |
| 9 | W03 | Mon | evening |
| 18 | W05 | Mon | evening |
| 13 | W04 | Mon | night |
| 24 | W06 | Tue | morning |
| 29 | W07 | Tue | morning |
| 4 | W02 | Tue | evening |
| 10 | W03 | Tue | evening |
| 14 | W04 | Tue | night |
| 19 | W05 | Wed | morning |
| 30 | W07 | Wed | morning |
| 0 | W01 | Wed | evening |
| 25 | W06 | Wed | evening |
| 15 | W04 | Wed | night |
| 20 | W05 | Thu | morning |
| 31 | W07 | Thu | morning |
| 5 | W02 | Thu | evening |
| 26 | W06 | Thu | evening |
| 1 | W01 | Thu | night |
| 16 | W04 | Fri | morning |
| 21 | W05 | Fri | morning |
| 6 | W02 | Fri | evening |
| 32 | W07 | Fri | evening |
| 27 | W06 | Fri | night |
| 2 | W01 | Sat | morning |
| 22 | W05 | Sat | morning |
| 7 | W02 | Sat | evening |
| 17 | W04 | Sat | evening |
| 11 | W03 | Sat | night |
| 3 | W01 | Sun | morning |
| 8 | W02 | Sun | evening |
| 12 | W03 | Sun | night |
Reports for workers#
Each worker should receive a report detailing their shift assignments. The reports are created by sorting the master schedule by worker, day, and shift, then grouping by worker.
# sort schedule by worker
schedule = schedule.sort_values(by=["worker", "day", "shift"])
# print worker schedules
for worker, worker_schedule in schedule.groupby("worker"):
print(f"\nWork schedule for {worker}")
if len(worker_schedule) > 0:
for s in worker_schedule.to_string(index=False).split("\n"):
print(s)
else:
print(" no assigned shifts")
Work schedule for W01
worker day shift
W01 Wed evening
W01 Thu night
W01 Sat morning
W01 Sun morning
Work schedule for W02
worker day shift
W02 Tue evening
W02 Thu evening
W02 Fri evening
W02 Sat evening
W02 Sun evening
Work schedule for W03
worker day shift
W03 Mon evening
W03 Tue evening
W03 Sat night
W03 Sun night
Work schedule for W04
worker day shift
W04 Mon night
W04 Tue night
W04 Wed night
W04 Fri morning
W04 Sat evening
Work schedule for W05
worker day shift
W05 Mon evening
W05 Wed morning
W05 Thu morning
W05 Fri morning
W05 Sat morning
Work schedule for W06
worker day shift
W06 Mon morning
W06 Tue morning
W06 Wed evening
W06 Thu evening
W06 Fri night
Work schedule for W07
worker day shift
W07 Mon morning
W07 Tue morning
W07 Wed morning
W07 Thu morning
W07 Fri evening
Work schedule for W08
no assigned shifts
Work schedule for W09
no assigned shifts
Work schedule for W10
no assigned shifts
Reports for store managers#
The store managers need reports listing workers by assigned day and shift.
# sort by day, shift, worker
schedule = schedule.sort_values(by=["day", "shift", "worker"])
for day, day_schedule in schedule.groupby("day"):
print(f"\nShift schedule for {day}")
for shift, shift_schedule in day_schedule.groupby("shift"):
print(f" {shift} shift: ", end="")
print(", ".join([worker for worker in shift_schedule["worker"].values]))
Shift schedule for Mon
morning shift: W06, W07
evening shift: W03, W05
night shift: W04
Shift schedule for Tue
morning shift: W06, W07
evening shift: W02, W03
night shift: W04
Shift schedule for Wed
morning shift: W05, W07
evening shift: W01, W06
night shift: W04
Shift schedule for Thu
morning shift: W05, W07
evening shift: W02, W06
night shift: W01
Shift schedule for Fri
morning shift: W04, W05
evening shift: W02, W07
night shift: W06
Shift schedule for Sat
morning shift: W01, W05
evening shift: W02, W04
night shift: W03
Shift schedule for Sun
morning shift: W01
evening shift: W02
night shift: W03