Scheduling

Why it matters

Labour is the largest cost in hospitals, call centres, airlines, retail and policing. Schedule too few people and service collapses; schedule too many and money is wasted. Staff scheduling is one of the oldest and most profitable uses of integer programming, and the model is short enough to write in an afternoon. This lesson builds the classic shift scheduling model step by step.

The problem

A help desk is open around the clock. The day is split into six 4-hour blocks, and the minimum staff needed in each block comes from forecast call volume:

Each person works one 8-hour shift: two consecutive blocks. A shift starting at 20:00 wraps past midnight into the 00-04 block. How many people should start in each block so that every block is covered, using as few people as possible?

Step 1: decision variables

x_s = number of people whose shift starts in block s (s = 0, ..., 5). These are integers: you cannot hire 2.5 people.

A common beginner mistake is to define "people working in block t" as the variable. That is an outcome, not a choice: the same person counts in two blocks.

Step 2: the coverage matrix

People working in block t are those who started in block t or in block t - 1. Write this as a 0/1 coverage matrix A, where A[t, s] = 1 if a shift starting in block s is on duty in block t:

            start: 0  1  2  3  4  5
block 0 (00-04)    1  0  0  0  0  1
block 1 (04-08)    1  1  0  0  0  0
block 2 (08-12)    0  1  1  0  0  0
block 3 (12-16)    0  0  1  1  0  0
block 4 (16-20)    0  0  0  1  1  0
block 5 (20-24)    0  0  0  0  1  1

The 1 in the top-right corner is the midnight wrap. Using % (modulo) in code handles it: a shift starting in block s covers blocks s and (s + 1) % 6.

Step 3: objective and constraints

minimize   x_0 + x_1 + x_2 + x_3 + x_4 + x_5
subject to A @ x >= demand          (every block covered)
           x_s >= 0 and integer

For example, block 2 gives x_1 + x_2 >= 6.

Step 4: solve and sanity-check

A lower bound is easy: each person covers two blocks and the blocks need 2 + 4 + 6 + 5 + 3 + 2 = 22 person-blocks, so at least 11 people are needed. One optimal answer is

x = [0, 4, 2, 3, 0, 2]     (11 people)
coverage A @ x = [2, 4, 6, 5, 3, 2]

It meets the bound exactly, so it is optimal, and every block has exactly the staff it needs. Other schedules with 11 people may exist; a solver returns one of them. If shifts were 12 hours (three blocks), the bound becomes 22 / 3, rounded up to 8, and 8 people is achievable.

With PuLP the whole model is a few lines:

import pulp

demand = [2, 4, 6, 5, 3, 2]
n = len(demand)
prob = pulp.LpProblem("help_desk", pulp.LpMinimize)
x = [pulp.LpVariable(f"start_{s}", lowBound=0, cat="Integer") for s in range(n)]
prob += pulp.lpSum(x)
for t in range(n):
    prob += x[t] + x[(t - 1) % n] >= demand[t], f"cover_{t}"
prob.solve(pulp.PULP_CBC_CMD(msg=False))
print([int(v.value()) for v in x])

Making it realistic

The textbook model is the core; real rosters add layers.

• Weekly patterns. The classic version uses days: each person works 5 consecutive days and gets 2 off, so x_d is the number starting their week on day d.
• Different shift types and costs. Night or weekend shifts cost more: put a cost per variable in the objective.
• Labour rules. Maximum hours, minimum rest between shifts, required breaks and skills (only some agents speak Spanish).
• Soft constraints. Preferences and fairness are often modelled with penalty variables in the objective rather than hard rules, so the model stays feasible.
• Two stages. First decide how many people start when (this lesson), then assign named people to those shifts (an assignment problem).
• Forecast first. Demand comes from a call forecast plus a queueing model (next module) that turns "calls per hour" into "agents needed".

Brute-force search works for six small integer variables (the exercise uses numpy to check every combination), but real rosters with thousands of variables need a MIP solver.

Common mistakes

• Defining variables as "people on duty" instead of "people starting".
• Forgetting the wrap-around shift from the last block into the first.
• Treating fractional LP answers as staffing levels. Use integer variables, then check the MIP gap.
• Ignoring legal and union rules until the end. A schedule that breaks them is not a schedule.
• Optimizing to the exact forecast. Forecasts are uncertain; add a buffer or test the schedule in a simulation.

Quick recap

• Variables are the number of people starting each shift.
• A 0/1 coverage matrix links starts to blocks covered, including wrap-around.
• Minimize total people subject to coverage A @ x >= demand, integers.
• Simple bounds (total demand divided by shift length) check the answer.

Try it

In the Do tab, build the coverage matrix with numpy and find the smallest schedule for the help desk.