Optimizing an Optimizer: Fair Shift Scheduling with MIP

Shift scheduling is one of those problems that feels like spreadsheet work until you try to respect real constraints: availability, minimum staffing, different participation frequencies, and the occasional “these two people must work together”.

This post is about a small but meaningful change. I took an existing Mixed Integer Programming (MIP) scheduler that found a feasible solution and pushed it toward a fair one by changing the objective. Same constraints, different target.

The Context

This work was done for Gomo, a member-run food cooperative in São Paulo. There’s no paid staff. Members keep things running by taking shifts (opening the shop, restocking, checkout, helping other members).

They already had a working MIP scheduler (originally developed by Fernando Pimentel Silva using Gurobi). It respected the hard constraints, but the distribution was lopsided: some shifts ended up crowded while others sat right at the minimum. The goal wasn’t just feasibility. It was fairness.

The Problem

We needed to schedule 261 members across 4 weeks, 7 days per week, 4 shifts per day (06:15, 08:45, 11:15, 13:45).

The constraints:

• Each person has specific availability windows
• Each shift needs a minimum number of people (2-4 per shift)
• People work at different frequencies: weekly (4 shifts/cycle), biweekly (2 shifts/cycle), or monthly (1 shift/cycle)
• Some people must work together as pairs (parent-child duos)

The spreadsheet approach is slow, brittle, and hard to audit. You can end up with something that “looks fine” and still violate constraints.

Is This Even Solvable?

Before touching the objective, I checked basic feasibility (supply vs demand):

• Supply: 368 total allocations (188 monthly + 112 biweekly + 68 weekly)
• Demand: 220 minimum slots across all active shifts
• Balance: +148 extra allocations overall

That balance is necessary but not sufficient. What matters is whether the right people are available for the right shifts.

Why Mixed Integer Programming?

MIP fits this problem because the decisions are discrete: either someone is assigned to a shift or not. We also want hard guarantees: if the model returns a solution, it respects the constraints.

You could also tackle this with heuristics or constraint programming. I went with MIP because I wanted two things at once: strict feasibility under hard constraints and a clean fairness objective.

The Mathematical Model

Decision Variables

For each person i, week j, day k, and shift t:

x[i,j,k,t] ∈ {0,1}

Where x[i,j,k,t] = 1 means person i is assigned to work week j, day k, shift t.

Objective Functions

I tested two objectives under the same constraint set.

Baseline objective: “any feasible schedule”

Once you enforce “each person works exactly their required number of shifts”, the total number of allocations is effectively fixed. A baseline objective still needs something to minimize, but it doesn’t shape the surplus distribution in a meaningful way.

Minimax objective: minimize the worst surplus

I introduced a variable u to represent the maximum surplus across active shifts, then minimized u:

minimize u
where u ≥ (Σ x[i,j,k,t]) - demand[j,k,t]  ∀j,k,t

Intuitively: if there’s slack in the system, spread it around instead of dumping it on a handful of shifts.

Constraints

1. Availability: Only schedule people for shifts they marked as available

x[i,j,k,t] ≤ availability[i,k,t]  ∀i,j,k,t

2. Minimum coverage: Each shift must have enough people

Σ x[i,j,k,t] ≥ demand[j,k,t]  ∀j,k,t

3. Frequency: Each member has a required number of shifts in the 4-week cycle (1, 2, or 4). Biweekly members also have a periodicity rule (weeks 0↔2 and 1↔3).

4. Paired workers: Duos must work the same shifts

x[i,j,k,t] = x[partner[i],j,k,t]  ∀i∈pairs, j,k,t

Implementation: From Gurobi to Open Source, From Feasible to Fair

The original algorithm used Gurobi (commercial license required) and focused on feasibility: find any valid schedule. My goals were:

1. Make it accessible: Switch to open source (PuLP + HiGHS)
2. Make it fair: Add MINIMAX objective to balance workload

Here’s the core idea of the fairness optimization:

import pulp

# Create model
model = pulp.LpProblem("shift_scheduler", pulp.LpMinimize)

# Decision variables
x = pulp.LpVariable.dicts(
    "x",
    ((i, j, k, t) for i in people
                  for j in weeks
                  for k in days
                  for t in shifts),
    cat="Binary"
)

# For MINIMAX: add variable for peak surplus
u = pulp.LpVariable("u", lowBound=0, cat="Integer")

# For each active shift: u >= surplus
for j in weeks:
    for k in days:
        for t in shifts:
            if demand[j][k][t] > 0:
                model += u >= (
                    pulp.lpSum(x[i, j, k, t] for i in people)
                    - demand[j][k][t]
                )

# Objective: minimize peak surplus
model += u

# Add constraints...
model.solve(pulp.HiGHS(msg=1, time_limit=300))

The minimax part adds one constraint per active shift (88 in this setup). That’s small compared to the size of the full model.

Results

The optimizer solves in seconds at this size (261 people across a 4×7×4 shift grid). In the runs I’m reporting here, it allocated all 368 member shifts and didn’t require any external coverage.

The Optimization: Baseline vs Minimax

The original algorithm (BASELINE) meets the constraints quickly, but surplus distribution can be noisy. In my data, some shifts ended up heavily overstaffed while others hugged the minimum.

The minimax objective changes that. Same constraints, different objective: push down the worst-case shift.

Here’s the visual difference for Week 0:

What changed (baseline → minimax):

• Maximum surplus: 11 → 2
• Shifts with ≥3 surplus: 21 → 0
• P95 surplus: 6.65 → 2.00

The schedule still has slack, but slack stops concentrating in a few unlucky shifts.

Full Schedule Distribution

The complete 4-week schedule maintains this fairness across all weeks:

Blue indicates surplus above minimum demand, dark gray means exactly at minimum, red would indicate deficit (none exist in this solution). The consistent blue pattern shows the optimizer successfully balanced workload across all active shifts.

What This Gets You

• Hard constraints enforced by construction
• A fairness metric you can explain (“we minimized the worst surplus”)
• Fast iteration when constraints change

When to Use MIP for Scheduling

MIP tends to work well when decisions are discrete (yes/no assignments), constraints are truly hard, you have an objective you actually care about, and the problem is in the “thousands of variables” range rather than “millions”.

MIP is overkill when constraints are soft, you need real-time scheduling, or the problem structure is simple enough for greedy algorithms.

Lessons Learned

Constraints mattered more than code. Most of my time went into fixing the formulation and the preprocessing, not writing PuLP.

Start with toy data. If you can’t make a 3-people / 2-shifts instance behave, a 261-person instance won’t fix itself.

Validate the output. Don’t trust the solver output blindly. Check:

• Are allocations within declared availability?
• Does each shift meet minimum coverage?
• Do paired workers actually work together?
• Does each person meet their required number of shifts (and the biweekly periodicity rule)?

I found issues here that weren’t obvious while staring at constraints.

The objective function is the product. The baseline model solved quickly, but the schedule quality depended on solver choices you don’t control. Minimax took a bit longer on my machine (about 0.24s vs 0.1s) and removed the worst overstaffing.

One underrated benefit of MIP: you can answer “why this schedule?” with something other than vibes.

The Code

The implementation uses PuLP for MIP modeling with HiGHS as the solver (both are free and open source), Polars for fast data manipulation, and Jupyter notebooks for interactive development.

Source code and notebooks: github.com/olavocarvalho/otimizador-escalas-mip

Beyond Shifts

The same approach applies to many allocation problems: class scheduling with room constraints, delivery routes, resource allocation in cloud infrastructure, tournament brackets, task assignment in project management.

If you can express it as binary variables with linear constraints, MIP can likely solve it.

---

Have a scheduling problem you’re solving? Find me on LinkedIn or Twitter.