What is the Staff Shift Assignment Problem?
The Staff Shift Assignment Problem is a classic combinatorial optimization problem. Given a set of employees and shifts, the goal is to assign workers to shifts while satisfying various constraints — minimum staffing levels, employee availability, labor regulations, and fairness requirements.
Problem Formulation
Let’s define the variables:
- Let $E = {e_1, e_2, \ldots, e_m}$ be the set of employees
- Let $S = {s_1, s_2, \ldots, s_n}$ be the set of shifts
- Let $x_{ij} \in {0, 1}$ be a binary decision variable where $x_{ij} = 1$ if employee $i$ is assigned to shift $j$
Objective Function — minimize total cost:
$$\min \sum_{i \in E} \sum_{j \in S} c_{ij} \cdot x_{ij}$$
Subject to:
Minimum staffing per shift:
$$\sum_{i \in E} x_{ij} \geq d_j \quad \forall j \in S$$
Maximum shifts per employee per week:
$$\sum_{j \in S} x_{ij} \leq W_{max} \quad \forall i \in E$$
Availability constraint (employee $i$ cannot work shift $j$ if unavailable):
$$x_{ij} \leq a_{ij} \quad \forall i \in E, \forall j \in S$$
Concrete Example
We have 8 employees and 6 shifts over one week:
| Shift | Time | Required Staff |
|---|---|---|
| Morning Mon | 6:00–14:00 | 3 |
| Afternoon Mon | 14:00–22:00 | 2 |
| Night Mon | 22:00–6:00 | 1 |
| Morning Fri | 6:00–14:00 | 3 |
| Afternoon Fri | 14:00–22:00 | 2 |
| Night Fri | 22:00–6:00 | 1 |
Each employee has individual availability and a max of 3 shifts per week. We use PuLP to solve this Integer Linear Program.
Full Source Code
1 | # ============================================================ |
Code Walkthrough
Section 1 — Problem Data
We define 8 employees and 6 shifts. The required dictionary specifies how many workers each shift needs. The cost dictionary is a random cost matrix representing things like overtime preference or skill match — lower cost means a more preferred assignment. The avail dictionary encodes which employees are unavailable for specific shifts (set to 0), defaulting to 1 (available) for all other combinations.
Section 2 — Building the ILP Model
We use pulp.LpProblem with LpMinimize. The binary decision variable $x_{ij}$ is created via LpVariable.dicts with cat="Binary". Three sets of constraints are added:
Constraint 1 ensures that for every shift $j$, the sum of assigned employees meets or exceeds the required number:
$$\sum_{i} x_{ij} \geq d_j$$
Constraint 2 limits each employee to at most MAX_SHIFTS_PER_EMPLOYEE = 3 shifts per week:
$$\sum_{j} x_{ij} \leq 3$$
Constraint 3 enforces availability — if employee $i$ is unavailable for shift $j$, then $x_{ij} = 0$:
$$x_{ij} \leq a_{ij}$$
Section 3 — Solving
We call prob.solve() using the built-in CBC solver (free, bundled with PuLP). The solver explores the binary search tree and finds the globally optimal assignment minimizing total cost.
Section 4 — Extracting Results
We build a NumPy matrix assign_matrix of shape (n_emp, n_shift) from the solved variables and print a human-readable schedule table, followed by a check that each shift’s staffing requirement is satisfied.
Sections 5–7 — Visualizations
Three charts are produced:
Chart 1 — Heatmap shows which employee is assigned to which shift. Yellow = unassigned, orange/red = assigned. Cell text is 0 or 1. Alongside it, a bar chart shows each employee’s workload compared to the maximum allowed.
Chart 2 — Required vs Assigned Bar Chart compares how many staff were required vs actually assigned per shift. This quickly reveals if any shift is overstaffed (common since we minimize cost and constraints only require a minimum).
Chart 3 — 3D Cost Surface renders the full cost matrix as a semi-transparent surface. Red 3D bars mark the actual assigned (employee, shift) pairs, making it easy to see whether the solver picked low-cost assignments from the cost landscape.
Execution Results
1 | Status : Optimal |
All visualizations complete.
Key Takeaways
The ILP approach guarantees a globally optimal solution — no heuristic approximation. PuLP with CBC handles this small problem (8×6 binary variables) in milliseconds. For larger problems (hundreds of employees, 30-day scheduling horizons), the same model structure remains valid; you would simply swap CBC for a commercial solver like Gurobi or CPLEX, or apply decomposition techniques like column generation to keep solve times tractable.
The cost matrix can encode rich real-world preferences: overtime costs $c_{ij}^{OT}$, skill-mismatch penalties $c_{ij}^{skill}$, or employee preferences $c_{ij}^{pref}$, all summed into a single composite cost per assignment. This flexibility is one of the main reasons ILP remains the standard approach for real-world workforce scheduling.