Skip to content
Tutorials Center
My learning

Topics

Lesson 37 of 38 ยท Projects and Practice

Project: Staff Rostering

Build a weekly staff schedule with integer programming: cover daily demand with five-day shifts, compare LP and MILP, derive demand from Erlang C queueing, and add weekend costs.

Every organization with shifts, from hospitals to call centers, must answer the same question each week: how many people should start working on each day so that enough are present every day, at the lowest cost? In this project you will solve a classic version, the days-off scheduling problem, with integer programming. Then you will connect it with the queueing models of the previous chapter, so that demand for staff comes from a service-level target rather than a guess.

The problem

A service center is open seven days a week. On day d at least r_d agents must be on duty. Each agent works five consecutive days and then has two consecutive days off. The pattern repeats each week (a cyclic schedule, so a shift starting on Thursday works Thursday through Monday). Minimize the number of agents.

Let z_s be the number of agents whose shift starts on day s (Monday = 0 ... Sunday = 6). A shift starting on day s covers days s, s+1, s+2, s+3, s+4 (mod 7). The model is a covering problem:

TEXT
minimize    sum_s z_s
subject to  sum_{s covering day d} z_s >= r_d     for each day d
            z_s >= 0, integer

The coverage matrix A has A[d, s] = 1 if shift s works on day d. It is a circulant 0/1 matrix, and it does not have the totally unimodular property of network problems, so the LP relaxation can be fractional.

flowchart LR
    R["Required staff<br/>per day r_d"] --> M["Cover constraints<br/>A z >= r"]
    Z["Shift starts<br/>z_s integer"] --> M
    M --> O["Minimize<br/>total staff"]

Step 1: Solve with MILP and compare with the LP

Python Five-day shifts: LP relaxation versus integer solution

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The LP says 22.33 agents would do, which is impossible, so the integer optimum is 23 (the next integer up, matching the bound ceil(22.33)). The coverage line shows where the schedule over-covers: Friday has 21 on duty against 14 needed, an unavoidable consequence of the "five days on, two off" rule.

When the objective coefficients are all 1, the optimum is at least the LP value rounded up. Here the bound is tight. In general, always compare the MILP result with the relaxation bound to know how close to optimal you are.

Step 2: Get the demand from a queueing model

How did we know r_d? In real service systems it comes from the workload and a service target. A call center expects lambda_d calls per hour at the busiest time on day d, an agent handles mu = 12 calls an hour, and management wants at most 10% of callers to wait more than 20 seconds. The Erlang C analysis from Multi-Server Queues and Simulation gives the number of agents needed per day; the roster model then turns those numbers into shifts.

We also add a cost: shifts that include weekend days carry a premium of 5% of a normal agent per weekend day worked, so the optimizer is encouraged to cover weekends efficiently.

Python From call volume to Erlang C staffing to a weekly roster

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Peak volumes of 90 calls an hour on Monday need 12 agents, but only 7 are needed on a quiet Sunday. The roster covers every day and uses a few extra people on days where the five-day pattern leaves slack. Changing the service target (say 5% waiting more than 20 seconds) changes need, and the roster follows automatically.

Step 3: Make it realistic

Real rosters need more constraints. Each is a modest extension:

  1. Different shift types. Add variables for early, late and night shifts per day and require coverage per shift type: sum x_{s,t} >= r_{d,t}.
  2. Skills. Employees have qualifications; a constraint per skill requires enough qualified people on duty. This produces a multi-commodity structure.
  3. Individual rosters. Instead of counts, assign named people with binary x_{e,d} (employee e works day d). Add rules: at most 5 days in a row, at least 2 days off after a night shift, preferences, fairness of weekend work. This is the nurse rostering problem, and is hard in general.
  4. Fairness. Minimize the maximum number of weekend days worked by anyone (a minimax objective, see Finance and Data Fitting with LP).
  5. Part-time and overtime. Different contract lengths and an overtime variable with a higher cost.
  6. Uncertainty. Demand forecasts are wrong. Add a buffer from the queueing model (higher utilization limits) or solve with several demand scenarios.

Step 4: Check your work

  • Feasibility check. Multiply the matrix by your solution and compare with requirements: A @ z >= need.
  • Lower bound. Total person-days needed divided by 5 (each agent gives five days a week): sum(need) / 5. For the first example this is 105 / 5 = 21, below the true optimum 23, and the LP bound 22.33 is better.
  • Sensitivity. Change one day's demand by one and re-solve to see which days drive the total.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In the days-off model, what does the decision variable z_s count?

    z_s is the number of agents starting their five consecutive working days on day s; the coverage matrix then maps starts to daily headcount.
  2. 2. Why can the LP relaxation of this model be fractional?

    The circulant 0/1 coverage matrix does not have the network structure that guarantees integer vertices.
  3. 3. How does the queueing model enter the rostering project?

    Erlang C converts call volume and service goals into minimum staff, which become the right-hand sides of the cover constraints.
  4. 4. Which model change would let you handle individual preferences and fairness among named employees?

    Employee-level binary variables allow personal rules, preferences and fairness objectives, at the price of a harder model.

Summary

  • Days-off scheduling is a covering MILP: z_s counts shift starts, A z >= r guarantees daily coverage.
  • Compare the MILP with its LP relaxation bound; here 22.33 versus 23.
  • Queueing models (Erlang C) turn service targets into the staffing requirements that feed the roster model.
  • Costs for weekend work, shift types, skills and fairness extend the model with small changes.
  • Always verify feasibility and check against simple lower bounds.

Next: Practice Problem Set