Workforce shift scheduling#
# install dependencies and select solver
%pip install -q amplpy matplotlib
SOLVER = "highs"
from amplpy import AMPL, ampl_notebook
ampl = ampl_notebook(
modules=["highs"], # modules to install
license_uuid="default", # license to use
) # instantiate AMPL object and register magics
Using default Community Edition License for Colab. Get yours at: https://ampl.com/ce
Licensed to AMPL Community Edition License for the AMPL Model Colaboratory (https://colab.ampl.com).
Problem Statement#
An article entitled “Modeling and optimization of a weekly workforce with Python and Pyomo” by Christian Carballo Lozano posted on the Towards Data Science blog showed how to build a Pyomo model to schedule weekly shifts for a small campus food store.
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 indexed sets in AMPL, and how to use the model solution to create useful visualizations and reports for workers and managers.
Model formulation#
Model sets#
This problem requires assignment of an unspecified number of workers to a predetermined set of shifts. There are three shifts per day, seven days per week. These observations suggest the need for three ordered sets:
WORKERSwith \(N\) elements representing workers. \(N\) is as input to a function creating an instance of the model.DAYSwith labeling the days of the week.SHIFTSlabeling the shifts each day.
The problem describes additional considerations that suggest the utility of several additional sets.
SLOTSis an ordered set of (day, shift) pairs describing all of the available shifts during the week.BLOCKSis an 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.WEEKENDSis a the set of all (day, shift) pairs on a weekend. This set will be used to implement worker preferences on weekend scheduling.
These additional sets improve the readability of the model.
Model parameters#
Model decision variables#
Model constraints#
Assign workers to each shift to meet staffing requirement.
Assign no more than 40 hours per week to each worker.
Assign no more than one shift in each 24 hour period.
Do not assign any shift to a worker that is not needed during the week.
Do not assign any weekend shift to a worker that is not needed during the weekend.
Model objective#
The model objective is to minimize the overall number of workers needed to fill the shift and work requirements while also attempting to meet worker preferences regarding weekend shift assignments. This is formulated here as an objective for 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 positive weight \(\gamma\) determines the relative importance of these two measures of a desirable shift schedule.
AMPL implementation#
%%writefile shift_schedule.mod
# sets
# ordered set of avaiable workers
set WORKERS ordered;
# ordered sets of days and shifts
set DAYS ordered;
set SHIFTS ordered;
# set of day, shift time slots
set SLOTS within {DAYS, SHIFTS};
# set of 24 hour time blocks
set BLOCKS within {SLOTS, SLOTS, SLOTS};
# set of weekend shifts
set WEEKENDS within SLOTS;
# parameters
# number of workers required for each slot
param WorkersRequired{SLOTS};
# max hours per week per worker
param Hours;
# weight of the weekend component in the objective function
param gamma default 0.1;
# variables
# assign[worker, day, shift] = 1 assigns worker to a time slot
var assign{WORKERS, SLOTS} binary;
# weekend[worker] = 1 worker is assigned weekend shift
var weekend{WORKERS} binary;
# needed[worker] = 1
var needed{WORKERS} binary;
# constraints
# assign a sufficient number of workers for each time slot
s.t. required_workers {(day, shift) in SLOTS}:
WorkersRequired[day, shift] == sum{worker in WORKERS} assign[worker, day, shift];
# workers limited to forty hours per week assuming 8 hours per shift
s.t. forty_hour_limit {worker in WORKERS}:
8 * sum{(day, shift) in SLOTS} assign[worker, day, shift] <= Hours;
# workers are assigned no more than one time slot per 24 time block
s.t. required_rest {worker in WORKERS, (d1, s1, d2, s2, d3, s3) in BLOCKS}:
assign[worker, d1, s1] + assign[worker, d2, s2] + assign[worker, d3, s3] <= 1;
# determine if a worker is assigned to any shift
s.t. is_needed {worker in WORKERS}:
sum{(day, shift) in SLOTS} assign[worker, day, shift] <= card(SLOTS) * needed[worker];
# determine if a worker is assigned to a weekend shift
s.t. is_weekend {worker in WORKERS}:
6 * weekend[worker] >= sum{(day, shift) in WEEKENDS} assign[worker, day, shift];
# choose(uncomment) one of the following objective functions
# minimize a blended objective of needed workers and needed weekend workers
#minimize minimize_workers:
#sum{worker in WORKERS} needed[worker] + gamma * sum{worker in WORKERS} weekend[worker];
# weighted version: since we are minimizing the objective function a smaller weight will give higher
# priority to a given worker
# weight is obtained with the ord function, that returns the index of a given worker in the weights SET
minimize minimize_workers:
sum{worker in WORKERS} ord(worker) * needed[worker] +
gamma * sum{worker in WORKERS} ord(worker) * weekend[worker];
Overwriting shift_schedule.mod
def shift_schedule(N=10, hours=40):
"""return a solved model assigning N workers to shifts"""
workers = [f"W{i:02d}" for i in range(1, N + 1)]
days = ["Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"]
shifts = ["morning", "evening", "night"]
slots = [(d, s) for d in days for s in shifts]
blocks = [(slots[i] + slots[i + 1] + slots[i + 2]) for i in range(len(slots) - 2)]
weekends = [(d, s) for (d, s) in slots if d in ["Sat", "Sun"]]
workers_required = {
(d, s): (1 if s in ["night"] or d in ["Sun"] else 2)
for d in days
for s in shifts
}
m = AMPL()
m.read("shift_schedule.mod")
m.set["WORKERS"] = workers
m.set["DAYS"] = days
m.set["SHIFTS"] = shifts
m.set["SLOTS"] = slots
m.set["BLOCKS"] = blocks
m.set["WEEKENDS"] = weekends
m.param["WorkersRequired"] = workers_required
m.param["Hours"] = hours
m.option["solver"] = SOLVER
m.solve()
return m
m = shift_schedule(10, 40)
HiGHS 1.5.3: HiGHS 1.5.3: optimal solution; objective 29.5
12934 simplex iterations
7 branching nodes
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):
workers = m.set["WORKERS"].to_list()
slots = m.set["SLOTS"].to_list()
days = m.set["DAYS"].to_list()
assign = m.var["assign"].to_dict()
needed = m.var["needed"].to_dict()
weekend = m.var["weekend"].to_dict()
bw = 1.0
fig, ax = plt.subplots(1, 1, figsize=(12, 1 + 0.3 * len(workers)))
ax.set_title("Shift Schedule")
# x axis styling
ax.set_xlim(0, len(slots))
colors = ["teal", "gold", "magenta"]
for i in range(len(slots) + 1):
ax.axvline(i, lw=0.3)
ax.fill_between(
[i, i + 1], [0] * 2, [len(workers)] * 2, alpha=0.1, color=colors[i % 3]
)
for i in range(len(days) + 1):
ax.axvline(3 * i, lw=1)
ax.set_xticks([3 * i + 1.5 for i in range(len(days))])
ax.set_xticklabels(days)
ax.set_xlabel("Shift")
# y axis styling
ax.set_ylim(0, len(workers))
for j in range(len(workers) + 1):
ax.axhline(j, lw=0.3)
ax.set_yticks([j + 0.5 for j in range(len(workers))])
ax.set_yticklabels(workers)
ax.set_ylabel("Worker")
# show shift assignments
for i, slot in enumerate(slots):
day, shift = slot
for j, worker in enumerate(workers):
if round(assign[worker, day, shift]):
ax.add_patch(Rectangle((i, j + (1 - bw) / 2), 1, bw, edgecolor="b"))
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(workers):
if not needed[worker]:
ax.fill_between(
[0, len(slots)], [j, j], [j + 1, j + 1], color="k", alpha=0.3
)
if needed[worker] and not weekend[worker]:
ax.fill_between(
[15, len(slots)], [j, j], [j + 1, j + 1], color="k", alpha=0.3
)
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.assign 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
# get the schedule from AMPL and convert to pandas DataFrame with defined columns
schedule = m.var["assign"].to_list()
schedule = pd.DataFrame(
[[s[0], s[1], s[2]] for s in schedule if s[3]], columns=["worker", "day", "shift"]
)
# create and assign a worker category type
worker_type = pd.CategoricalDtype(
categories=m.set["WORKERS"].to_list(), ordered=True
)
schedule["worker"] = schedule["worker"].astype(worker_type)
# create and assign a day category type
day_type = pd.CategoricalDtype(
categories=m.set["DAYS"].to_list(), ordered=True
)
schedule["day"] = schedule["day"].astype(day_type)
# create and assign a shift category type
shift_type = pd.CategoricalDtype(
categories=m.set["SHIFTS"].to_list(), 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 | |
|---|---|---|---|
| 1 | W01 | Mon | morning |
| 8 | W02 | Mon | morning |
| 42 | W06 | Mon | morning |
| 49 | W07 | Mon | morning |
| 7 | W02 | Mon | evening |
| 16 | W03 | Mon | evening |
| 31 | W05 | Mon | evening |
| 41 | W06 | Mon | evening |
| 24 | W04 | Mon | night |
| 32 | W05 | Mon | night |
| 28 | W04 | Tue | morning |
| 46 | W06 | Tue | morning |
| 51 | W07 | Tue | morning |
| 5 | W01 | Tue | evening |
| 12 | W02 | Tue | evening |
| 38 | W05 | Tue | night |
| 22 | W03 | Wed | morning |
| 47 | W06 | Wed | morning |
| 52 | W07 | Wed | morning |
| 6 | W01 | Wed | evening |
| 13 | W02 | Wed | evening |
| 23 | W03 | Wed | night |
| 29 | W04 | Wed | night |
| 37 | W05 | Thu | morning |
| 45 | W06 | Thu | morning |
| 4 | W01 | Thu | evening |
| 11 | W02 | Thu | evening |
| 50 | W07 | Thu | evening |
| 21 | W03 | Thu | night |
| 27 | W04 | Thu | night |
| 14 | W03 | Fri | morning |
| 30 | W05 | Fri | morning |
| 0 | W01 | Fri | evening |
| 39 | W06 | Fri | evening |
| 48 | W07 | Fri | evening |
| 15 | W03 | Fri | night |
| 40 | W06 | Fri | night |
| 17 | W03 | Sat | morning |
| 25 | W04 | Sat | morning |
| 34 | W05 | Sat | morning |
| 43 | W06 | Sat | morning |
| 2 | W01 | Sat | evening |
| 9 | W02 | Sat | evening |
| 33 | W05 | Sat | evening |
| 35 | W05 | Sat | night |
| 19 | W03 | Sun | morning |
| 26 | W04 | Sun | morning |
| 3 | W01 | Sun | evening |
| 18 | W03 | Sun | evening |
| 44 | W06 | Sun | evening |
| 10 | W02 | Sun | night |
| 20 | W03 | Sun | night |
| 36 | W05 | 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"\n Work 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 Mon morning
W01 Tue evening
W01 Wed evening
W01 Thu evening
W01 Fri evening
W01 Sat evening
W01 Sun evening
Work schedule for W02
worker day shift
W02 Mon morning
W02 Mon evening
W02 Tue evening
W02 Wed evening
W02 Thu evening
W02 Sat evening
W02 Sun night
Work schedule for W03
worker day shift
W03 Mon evening
W03 Wed morning
W03 Wed night
W03 Thu night
W03 Fri morning
W03 Fri night
W03 Sat morning
W03 Sun morning
W03 Sun evening
W03 Sun night
Work schedule for W04
worker day shift
W04 Mon night
W04 Tue morning
W04 Wed night
W04 Thu night
W04 Sat morning
W04 Sun morning
Work schedule for W05
worker day shift
W05 Mon evening
W05 Mon night
W05 Tue night
W05 Thu morning
W05 Fri morning
W05 Sat morning
W05 Sat evening
W05 Sat night
W05 Sun night
Work schedule for W06
worker day shift
W06 Mon morning
W06 Mon evening
W06 Tue morning
W06 Wed morning
W06 Thu morning
W06 Fri evening
W06 Fri night
W06 Sat morning
W06 Sun evening
Work schedule for W07
worker day shift
W07 Mon morning
W07 Tue morning
W07 Wed morning
W07 Thu evening
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: W01, W02, W06, W07
evening shift: W02, W03, W05, W06
night shift: W04, W05
Shift schedule for Tue
morning shift: W04, W06, W07
evening shift: W01, W02
night shift: W05
Shift schedule for Wed
morning shift: W03, W06, W07
evening shift: W01, W02
night shift: W03, W04
Shift schedule for Thu
morning shift: W05, W06
evening shift: W01, W02, W07
night shift: W03, W04
Shift schedule for Fri
morning shift: W03, W05
evening shift: W01, W06, W07
night shift: W03, W06
Shift schedule for Sat
morning shift: W03, W04, W05, W06
evening shift: W01, W02, W05
night shift: W05
Shift schedule for Sun
morning shift: W03, W04
evening shift: W01, W03, W06
night shift: W02, W03, W05
Suggested Exercises#
How many workers will be required to operate the food store if all workers are limited to four shifts per week, i.e., 32 hours? How about 3 shifts or 24 hours per week?
Add a second class of workers called “manager”. There needs to be one manager on duty for every shift, that morning shifts require 3 staff on duty, evening shifts 2, and night shifts 1.
Add a third class of workers called “part_time”. Part time workers are limited to no more than 30 hours per week.
Modify the problem formulation and objective to spread the shifts out amongst all workers, attempting to equalize the total number of assigned shifts, and similar numbers of day, evening, night, and weekend shifts.
Find the minimum cost staffing plan assuming managers cost 30 euros per hour + 100 euros per week in fixed benefits, regular workers cost 20 euros per hour plus 80 euros per week in fixed benefits, and part time workers cost 15 euros per week with no benefits.