Note
This is example is available as a Jupyter notebook. Download it and all
necessary data files here
.
Workforce Scheduling#
This example implements a simple workforce scheduling model: assigning workers to shifts in order to maximize a total preference score.
[1]:
import gurobipy as gp
from gurobipy import GRB
import pandas as pd
import gurobipy_pandas as gppd
pd.options.display.max_rows = 8
gppd.set_interactive()
First read in preference data. The preference data contains 3 columns: a shift date, worker name, and a preference value. If a worker is not available for a given shift, then that work-shift combination does not appear in the data (i.e. only preferenced shifts are valid).
[3]:
preferences = pd.read_csv(
"data/preferences.csv",
parse_dates=["Shift"],
index_col=['Worker', 'Shift']
)
preferences
[3]:
Preference | ||
---|---|---|
Worker | Shift | |
Amy | 2022-07-02 | 1 |
2022-07-03 | 3 | |
2022-07-05 | 2 | |
2022-07-07 | 2 | |
... | ... | ... |
Gu | 2022-07-11 | 2 |
2022-07-12 | 2 | |
2022-07-13 | 2 | |
2022-07-14 | 3 |
72 rows × 1 columns
Unstacking the data, we can see that the dataset is sparse: not all worker-shift combinations are possible. When constructing the model, we should take care that decision variables are only created for the valid combinations.
[4]:
preferences.unstack(0).head()
[4]:
Preference | |||||||
---|---|---|---|---|---|---|---|
Worker | Amy | Bob | Cathy | Dan | Ed | Fred | Gu |
Shift | |||||||
2022-07-01 | NaN | 2.0 | NaN | NaN | 1.0 | 3.0 | 2.0 |
2022-07-02 | 1.0 | 2.0 | NaN | 2.0 | 1.0 | 3.0 | 2.0 |
2022-07-03 | 3.0 | NaN | 1.0 | 3.0 | 3.0 | 1.0 | 2.0 |
2022-07-04 | NaN | NaN | 1.0 | NaN | 3.0 | NaN | NaN |
2022-07-05 | 2.0 | 3.0 | 2.0 | 2.0 | 2.0 | NaN | 3.0 |
Next load the shift requirements data, which indicates the number of required workers for each shift.
[5]:
shift_requirements = pd.read_csv(
"data/shift_requirements.csv",
parse_dates=["Shift"],
index_col="Shift"
)
shift_requirements
[5]:
Required | |
---|---|
Shift | |
2022-07-01 | 3 |
2022-07-02 | 2 |
2022-07-03 | 4 |
2022-07-04 | 2 |
... | ... |
2022-07-11 | 4 |
2022-07-12 | 5 |
2022-07-13 | 7 |
2022-07-14 | 5 |
14 rows × 1 columns
Model Formulation#
Our goal is to fill all available shifts with the required number of workers, while maximising the sum of preference values over all assignments. To do this, will create a binary variable for each valid worker-shift pairing (1 = shift assigned) and use preference values as linear coefficients in the objective.
There are three pandas indices involved in creating this model: workers, shifts, and preference pairings. While variables are added for the preference pairings, we will see that the worker and shift indexes emerge when aggregating.
[6]:
m = gp.Model()
df = (
preferences
.gppd.add_vars(
m, name="assign", vtype=GRB.BINARY, obj="Preference",
index_formatter={"Shift": lambda index: index.strftime('%a%d')},
)
)
df
[6]:
Preference | assign | ||
---|---|---|---|
Worker | Shift | ||
Amy | 2022-07-02 | 1 | <gurobi.Var assign[Amy,Sat02]> |
2022-07-03 | 3 | <gurobi.Var assign[Amy,Sun03]> | |
2022-07-05 | 2 | <gurobi.Var assign[Amy,Tue05]> | |
2022-07-07 | 2 | <gurobi.Var assign[Amy,Thu07]> | |
... | ... | ... | ... |
Gu | 2022-07-11 | 2 | <gurobi.Var assign[Gu,Mon11]> |
2022-07-12 | 2 | <gurobi.Var assign[Gu,Tue12]> | |
2022-07-13 | 2 | <gurobi.Var assign[Gu,Wed13]> | |
2022-07-14 | 3 | <gurobi.Var assign[Gu,Thu14]> |
72 rows × 2 columns
By grouping variables across the shift indices, we can efficiently construct the shift requirement constraints.
[7]:
shift_cover = gppd.add_constrs(
m,
df['assign'].groupby('Shift').sum(),
GRB.EQUAL,
shift_requirements["Required"],
name="shift_cover",
index_formatter={"Shift": lambda index: index.strftime('%a%d')},
)
shift_cover
[7]:
Shift
2022-07-01 <gurobi.Constr shift_cover[Fri01]>
2022-07-02 <gurobi.Constr shift_cover[Sat02]>
2022-07-03 <gurobi.Constr shift_cover[Sun03]>
2022-07-04 <gurobi.Constr shift_cover[Mon04]>
...
2022-07-11 <gurobi.Constr shift_cover[Mon11]>
2022-07-12 <gurobi.Constr shift_cover[Tue12]>
2022-07-13 <gurobi.Constr shift_cover[Wed13]>
2022-07-14 <gurobi.Constr shift_cover[Thu14]>
Name: shift_cover, Length: 14, dtype: object
Extracting Solutions#
With the model formulated, we solve it using the Gurobi Optimizer:
[8]:
m.optimize()
Gurobi Optimizer version 11.0.3 build v11.0.3rc0 (linux64 - "Ubuntu 22.04.3 LTS")
CPU model: Intel(R) Xeon(R) Platinum 8259CL CPU @ 2.50GHz, instruction set [SSE2|AVX|AVX2|AVX512]
Thread count: 1 physical cores, 2 logical processors, using up to 2 threads
Optimize a model with 14 rows, 72 columns and 72 nonzeros
Model fingerprint: 0xf76e3721
Variable types: 0 continuous, 72 integer (72 binary)
Coefficient statistics:
Matrix range [1e+00, 1e+00]
Objective range [1e+00, 3e+00]
Bounds range [1e+00, 1e+00]
RHS range [2e+00, 7e+00]
Found heuristic solution: objective 107.0000000
Presolve removed 14 rows and 72 columns
Presolve time: 0.00s
Presolve: All rows and columns removed
Explored 0 nodes (0 simplex iterations) in 0.01 seconds (0.00 work units)
Thread count was 1 (of 2 available processors)
Solution count 2: 96 107
Optimal solution found (tolerance 1.00e-04)
Best objective 9.600000000000e+01, best bound 9.600000000000e+01, gap 0.0000%
Extract the solution using the series accessor .gppd.X
:
[9]:
solution = df['assign'].gppd.X
solution
[9]:
Worker Shift
Amy 2022-07-02 1.0
2022-07-03 0.0
2022-07-05 1.0
2022-07-07 1.0
...
Gu 2022-07-11 1.0
2022-07-12 1.0
2022-07-13 1.0
2022-07-14 0.0
Name: assign, Length: 72, dtype: float64
Since the result is returned as a pandas series, we can easily filter down to the selected assignments:
[10]:
assigned_shifts = solution.reset_index().query("assign == 1")
assigned_shifts
[10]:
Worker | Shift | assign | |
---|---|---|---|
0 | Amy | 2022-07-02 | 1.0 |
2 | Amy | 2022-07-05 | 1.0 |
3 | Amy | 2022-07-07 | 1.0 |
4 | Amy | 2022-07-09 | 1.0 |
... | ... | ... | ... |
67 | Gu | 2022-07-10 | 1.0 |
68 | Gu | 2022-07-11 | 1.0 |
69 | Gu | 2022-07-12 | 1.0 |
70 | Gu | 2022-07-13 | 1.0 |
52 rows × 3 columns
Additionally, we can unstack the result and transform it to produce a roster table:
[11]:
shift_table = solution.unstack(0).fillna("-").replace({0.0: "-", 1.0: "Y"})
pd.options.display.max_rows = 15
shift_table
[11]:
Worker | Amy | Bob | Cathy | Dan | Ed | Fred | Gu |
---|---|---|---|---|---|---|---|
Shift | |||||||
2022-07-01 | - | Y | - | - | Y | - | Y |
2022-07-02 | Y | - | - | - | Y | - | - |
2022-07-03 | - | - | Y | - | Y | Y | Y |
2022-07-04 | - | - | Y | - | Y | - | - |
2022-07-05 | Y | - | Y | Y | Y | - | Y |
2022-07-06 | - | Y | - | Y | - | Y | Y |
2022-07-07 | Y | - | Y | - | Y | - | Y |
2022-07-08 | - | Y | - | - | Y | - | - |
2022-07-09 | Y | - | - | - | Y | - | - |
2022-07-10 | - | - | Y | Y | - | - | Y |
2022-07-11 | - | Y | - | Y | Y | - | Y |
2022-07-12 | Y | - | Y | Y | - | Y | Y |
2022-07-13 | Y | Y | Y | Y | Y | Y | Y |
2022-07-14 | Y | - | Y | Y | Y | Y | - |