Staff Scheduling with ILP
Employee scheduling is one of the most common and financially impactful applications of integer programming. Hospitals, call centers, retail stores, and restaurants all need to schedule staff efficiently.
Why Staff Scheduling Matters
Poor scheduling leads to:
- Overstaffing: wasted labor costs
- Understaffing: poor customer service
- Employee burnout: unfair shift distribution
- Compliance violations: exceeding maximum work hours
A 5% improvement in scheduling efficiency can save a company millions annually.
What Is Staff Scheduling?
The staff scheduling problem assigns employees to shifts while respecting:
| Constraint Type | Example | |----------------|---------| | Coverage | Minimum 3 cashiers per shift | | Preferences | Employee prefers morning shifts | | Qualifications | Only certified employees can work certain roles | | Labor laws | Max 8 hours per day, 40 hours per week | | Seniority | Senior employees get first choice | | Fairness | Equal weekend shift distribution |
How to Model Staff Scheduling with PuLP
Problem Setup
A small retail store needs to schedule 5 employees across 3 shifts per day for 7 days.
import pulp
# Data
employees = ["Alice", "Bob", "Charlie", "Diana", "Eve"]
days = list(range(1, 8)) # Monday to Sunday
shifts = ["Morning", "Afternoon", "Evening"]
# Demand: minimum staff needed per shift per day
demand = {
(1, "Morning"): 2, (1, "Afternoon"): 3, (1, "Evening"): 1,
(2, "Morning"): 2, (2, "Afternoon"): 2, (2, "Evening"): 1,
(3, "Morning"): 2, (3, "Afternoon"): 3, (3, "Evening"): 2,
(4, "Morning"): 3, (4, "Afternoon"): 3, (4, "Evening"): 2,
(5, "Morning"): 3, (5, "Afternoon"): 4, (5, "Evening"): 2,
(6, "Morning"): 2, (6, "Afternoon"): 3, (6, "Evening"): 2,
(7, "Morning"): 1, (7, "Afternoon"): 2, (7, "Evening"): 1,
}
# Employee shift preferences (1 = want, 0 = neutral, -1 = avoid)
preferences = {
("Alice", "Morning"): 1, ("Alice", "Evening"): -1,
("Bob", "Evening"): 1, ("Bob", "Morning"): -1,
("Charlie", "Afternoon"): 1,
("Diana", "Morning"): 1, ("Diana", "Afternoon"): 1,
("Eve", "Evening"): 1,
}
# Create problem
prob = pulp.LpProblem("Staff_Scheduling", pulp.LpMinimize)
# Decision variables: x[employee, day, shift] = 1 if assigned
x = {}
for e in employees:
for d in days:
for s in shifts:
x[(e, d, s)] = pulp.LpVariable(f"x_{e}_{d}_{s}", cat="Binary")
# Objective: minimize deviations from preferences + penalize overtime
# Preference cost: -1 = want (negative cost = reward), 1 = avoid (positive cost)
prob += pulp.lpSum(
-preferences.get((e, s), 0) * x[(e, d, s)]
for e in employees for d in days for s in shifts
if (e, s) in preferences
), "Minimize_Preference_Deviation"
# Constraint 1: Each employee works at most 1 shift per day
for e in employees:
for d in days:
prob += pulp.lpSum(x[(e, d, s)] for s in shifts) <= 1, f"One_shift_{e}_{d}"
# Constraint 2: Each employee works at most 5 days per week
for e in employees:
prob += pulp.lpSum(x[(e, d, s)] for d in days for s in shifts) <= 5, f"Max_days_{e}"
# Constraint 3: Coverage demand
for d in days:
for s in shifts:
prob += pulp.lpSum(x[(e, d, s)] for e in employees) >= demand[(d, s)], f"Cover_{d}_{s}"
# Constraint 4: No evening -> morning consecutive shift
for e in employees:
for d in range(1, 7):
prob += x[(e, d, "Evening")] + x[(e, d+1, "Morning")] <= 1, f"No_back_to_back_{e}_{d}"
# Solve
prob.solve()
print(f"Status: {pulp.LpStatus[prob.status]}")
print(f"Objective value: {pulp.value(prob.objective):.2f}")
print()
# Print schedule
for d in days:
print(f"--- Day {d} ---")
for s in shifts:
assigned = [e for e in employees if pulp.value(x[(e, d, s)]) == 1]
print(f" {s}: {', '.join(assigned) if assigned else 'None'}")
Advanced Constraints
Skill Requirements
# Only certified employees can work Evening shift (supervisor role)
certified = ["Alice", "Charlie"]
for d in days:
for e in employees:
if e not in certified:
prob += x[(e, d, "Evening")] == 0, f"Certification_{e}_{d}"
Minimum Rest Between Shifts
# No employee works both afternoon and evening on consecutive days
for e in employees:
for d in range(1, 7):
prob += x[(e, d, "Afternoon")] + x[(e, d+1, "Morning")] <= 1
Fair Weekend Distribution
# At most 2 weekend shifts per employee per month
# (Saturday=6, Sunday=7)
for e in employees:
prob += pulp.lpSum(x[(e, d, s)] for s in shifts for d in [6, 7]) <= 2
Real-World Applications
| Industry | Scale | Key Constraints | |----------|:-----:|----------------| | Healthcare | 1000+ nurses | Certifications, max hours, patient ratios | | Call centers | 500+ agents | Language skills, forecasted call volume | | Retail | 50-200 staff | Sales forecasts, part-time/full-time mix | | Restaurants | 20-50 staff | Peak hours, skill levels, tips distribution | | Manufacturing | 100-300 workers | Machine availability, shift rotations |
The Vibe Coding Approach
Describe your scheduling problem:
"I need to schedule 20 employees across 3 shifts for 7 days. Each shift needs minimum staff: morning=4, afternoon=5, evening=3. Employees have shift preferences. No one works more than 5 days. No back-to-back evening-to-morning shifts."
The AI will generate the complete PuLP model with all constraints.
Summary
Staff scheduling is a classic ILP application that directly impacts business costs and employee satisfaction. PuLP handles all common scheduling constraints naturally.
Key takeaways:
- Binary variables model employee-shift assignments
- Coverage constraints ensure minimum staffing
- Preference costs optimize employee satisfaction
- Max hours constraints ensure labor law compliance
- Consecutive shift restrictions prevent burnout
- Fair distribution rules improve morale
- Real-world scheduling involves hundreds of employees and dozens of constraints
What's Next: Resource Allocation
The next chapter extends scheduling to multi-project resource allocation - assigning limited resources across competing projects while respecting deadlines, budgets, and skill requirements.
Performance Considerations
| Problem Size | Employees | Days | Variables | Solve Time | |:-------------|:---------:|:----:|:---------:|:----------:| | Small | 10 | 7 | 210 | < 1 sec | | Medium | 50 | 30 | 4,500 | 5-30 sec | | Large | 200 | 30 | 18,000 | 1-10 min | | Enterprise | 1000 | 90 | 270,000 | Hours |
For enterprise-scale scheduling, specialized workforce management software (Kronos, UKG, ADP) uses more advanced algorithms.
Common Pitfalls
| Pitfall | Symptom | Solution | |---------|---------|----------| | Infeasible model | Solver returns "Infeasible" | Relax coverage constraints or add more staff | | Too many constraints | Solve time explodes | Prioritize hard vs soft constraints | | Unfair schedules | Same people always get bad shifts | Add fairness constraints or randomize | | Ignoring preferences | Low employee satisfaction | Add preference weights to objective |
Chapter Summary
Staff scheduling with ILP efficiently solves complex shift assignment problems that are impractical to solve manually.