Optimizing Staff Scheduling with Linear Programming

Overview

Imagine managing a coffee shop that operates 24/7, requiring staff to be scheduled across overlapping shifts. Because the decision variables are numbers of workers, this is naturally an integer linear program, not an ordinary continuous LP unless fractional workers are acceptable. This article demonstrates how to apply linear programming using the PuLP library in Python to find the optimal staffing solution.

The same formulation applies to call centers, hospitals, warehouses, security operations, and maintenance crews. The core task is always the same: choose staffing levels for each shift so every demand window is covered while total cost and policy violations are minimized.

Data and Problem Definition

The coffee shop's daily schedule is divided into eight time windows, each demanding a different number of staff members. These time windows are:

Staff members are scheduled into four shifts:

1. Shift 1: 00:00 - 09:00
2. Shift 2: 06:00 - 15:00
3. Shift 3: 12:00 - 21:00
4. Shift 4: 18:00 - 03:00

Scheduling Challenges

A simplistic approach would be to assign the maximum number of staff required in any overlapping time windows for each shift. However, this may lead to overstaffing and increased costs. An optimal solution minimizes the number of staff while meeting all time window requirements.

Linear Programming and PuLP

Linear programming (LP) is an effective method to find optimal solutions for such constraint-based problems. PuLP is a Python library that facilitates the application of LP.

Installation

To install PuLP, use:

1
pip install pulp

Data Preparation

We'll download the data using gdown:

1
pip install gdown

Input Parameters

We'll create a coverage matrix to indicate which shifts cover each time window, then define the demand for each window.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
time_windows = [
    "00:00-03:00", "03:00-06:00", "06:00-09:00", "09:00-12:00",
    "12:00-15:00", "15:00-18:00", "18:00-21:00", "21:00-00:00"
]

demands = [15, 20, 55, 46, 59, 40, 48, 30]
shifts = ["Shift_1", "Shift_2", "Shift_3", "Shift_4"]

coverage = {
    "Shift_1": [1, 1, 1, 0, 0, 0, 0, 0],  # 00:00-09:00
    "Shift_2": [0, 0, 1, 1, 1, 0, 0, 0],  # 06:00-15:00
    "Shift_3": [0, 0, 0, 0, 1, 1, 1, 0],  # 12:00-21:00
    "Shift_4": [1, 0, 0, 0, 0, 0, 1, 1],  # 18:00-03:00
}

Decision Variables

Decision variables represent the unknown quantities we want to determine, i.e., the number of workers per shift. In PuLP, we specify these using LpVariable.dicts:

1
2
3
4
from pulp import LpVariable

shifts = ["Shift_1", "Shift_2", "Shift_3", "Shift_4"]
workers = LpVariable.dicts("Workers", shifts, lowBound=0, cat='Integer')

Objective Function

The goal below minimizes the sum of workers assigned to shifts. That is a headcount proxy, not necessarily labor cost: if shifts have different lengths or wage premiums, the objective should use per-shift costs.

1
2
3
4
from pulp import LpProblem, LpMinimize

prob = LpProblem("Staffing_Problem", LpMinimize)
prob += sum(workers[shift] for shift in shifts)

Constraints

We need to ensure that the number of workers in each time window meets the required demand:

1
2
3
4
5
for t, demand in enumerate(demands):
    prob += (
        sum(workers[shift] * coverage[shift][t] for shift in shifts) >= demand,
        f"coverage_window_{t}"
    )

This loop is safer than writing every constraint by hand because it keeps the code aligned with the demand table.

Solving the Problem

We solve the LP problem using:

1
2
3
from pulp import PULP_CBC_CMD

prob.solve(PULP_CBC_CMD())

Results Interpretation

Upon solving, we interpret the results to ensure the staffing meets the demands:

1
2
3
4
for v in prob.variables():
    print(v.name, "=", v.varValue)

print("Total Workers =", sum(v.varValue for v in prob.variables()))

Visualizing the Solution

Visualizing the staffing schedule can help verify the solution. We can plot the number of workers scheduled in each time window to ensure demand is met.

1
2
3
4
5
6
7
8
9
10
11
12
13
import matplotlib.pyplot as plt

assigned_workers = [
    sum(workers[shift].varValue * coverage[shift][t] for shift in shifts)
    for t in range(len(time_windows))
]

plt.bar(time_windows, demands, label='Demand')
plt.bar(time_windows, assigned_workers, label='Assigned Workers', alpha=0.7)
plt.xlabel('Time Window')
plt.ylabel('Number of Workers')
plt.legend()
plt.show()

Extending the Model

The basic model minimizes total headcount, but real scheduling problems usually need richer constraints:

• different hourly costs by shift;
• maximum consecutive hours and rest periods;
• minimum staffing by skill or certification;
• part-time versus full-time worker limits;
• fairness constraints so undesirable shifts rotate across employees.

These additions usually fit naturally into the same integer programming formulation. The important step is to translate each policy into a measurable constraint before optimizing.

Conclusion

Using PuLP, we solve a small integer staffing model for a 24/7 coffee shop. The model meets coverage constraints and minimizes the stated objective. It does not prove minimum labor cost unless the objective explicitly contains the relevant wage and shift costs. Such optimization techniques can be applied to various business operations to enhance efficiency and reduce expenses.

By utilizing Python and PuLP, managers can solve complex scheduling problems with ease, ensuring optimal resource allocation and cost management. The model is intentionally small, but the pattern scales: define the decision variables, encode coverage, state the objective, add constraints, and inspect the solution against the operating reality before using it in production.

Coverage is not a complete roster

The model chooses how many workers start each shift. It does not assign named employees. A real roster usually needs binary variables

plus constraints for availability, skills, maximum hours, minimum rest, consecutive shifts, contracts, and fairness. That turns the model into a larger mixed-integer program.

Feasibility before optimality

Before discussing the optimum, check whether the constraints are feasible. Operational rules can easily conflict. Useful diagnostics include:

• unmet-demand slack variables with heavy penalties;
• constraint names that identify infeasible windows;
• solver status checks;
• sensitivity to demand and absence scenarios.

A solver returning a numerical variable vector is not enough. Always verify

for every demand window and inspect the solver's optimality status.

Uncertainty belongs outside the deterministic demand table

Staff demand is rarely known exactly. If forecasts are uncertain, one can optimize against scenarios or service-level constraints rather than pretending the point forecast is exact. For scenarios $\omega$ with demand $d_t^{(\omega)}$, a robust or stochastic formulation can trade staffing cost against undercoverage risk. The deterministic model in this article is a useful first layer, not the complete workforce-planning problem.

References

• Dantzig, G. B. (1963). Linear Programming and Extensions. Princeton University Press.
• Ernst, A. T., Jiang, H., Krishnamoorthy, M., & Sier, D. (2004). Staff scheduling and rostering: A review of applications, methods and models. European Journal of Operational Research, 153(1), 3–27.