Schedule generation algorithms explained: greedy, fairness rebalancing, and constraints

Most people who manage a roster have at some point wondered how, exactly, scheduling software arrives at its answer. The marketing pages tend to wave their hands — "our AI", "our optimiser", "our advanced algorithm" — without explaining what is really happening under the cover. The result is a category of tools that nobody fully trusts, because nobody outside the engineering team can describe what they do.

This article is the explanation we wish we had read before building one. It is written for managers, not computer scientists; it is opinionated about the trade-offs; and it is specific to ShiftPlanning's approach, which is one of several reasonable ways to solve the problem. By the end you should be able to look at a generated schedule and have a fair idea of what the algorithm was "thinking" when it produced each assignment.

The problem in plain language

Scheduling, abstractly, is filling in a grid. Rows are slots that need to be filled (one slot per skill per shift per day). Columns are people. Each cell is a yes-or-no decision: does this person fill this slot?

For a small team — say, 6 people across 30 days with 2 shifts per day and 3 skills — the grid contains about a thousand cells. Most of them are zero (most people are not filling most slots), but the search space of possible schedules is astronomical. There are far more possible schedules than there are atoms in the visible universe. Searching all of them is not feasible; we have to be smarter.

The smart approach has three pillars:

1. Constraints rule out most of the search space.
2. A construction heuristic builds a feasible schedule quickly, even if it is not optimal.
3. An improvement loop takes the feasible schedule and trades assignments to make it better.

The rest of this article walks through each pillar, with concrete examples of what ShiftPlanning does at each stage.

Hard and soft constraints

A hard constraint is a rule that the schedule must obey. If a hard constraint is violated, the schedule is invalid — not merely worse, but flat-out unacceptable. Examples:

• You cannot assign someone to a shift on a day they are on leave.
• You cannot assign someone to a skill they do not possess.
• You cannot assign someone to two overlapping shifts on the same day.
• You cannot assign more people than the role calls for, or fewer than the minimum.
• You cannot violate the maximum consecutive days rule.

A soft constraint is a preference that the schedule should respect when it can, but that can be relaxed in favour of better overall outcomes. Examples:

• People should work close to their preferred shift type.
• The total number of shifts per person should be balanced across the team.
• Weekend shifts should be distributed evenly.
• Variety: nobody should always close on the same day-of-week.

The two are treated very differently. Hard constraints are filters: they remove impossible assignments from consideration. Soft constraints are scores: they shape a quality metric that the algorithm tries to maximise (or, equivalently, a cost it tries to minimise).

Step 1: prepare the eligibility matrix

Before any actual assignment happens, ShiftPlanning builds an eligibility matrix. For every slot in the month, it precomputes the list of employees who are eligible for that slot — meaning they pass every hard constraint that does not depend on the rest of the schedule.

For a slot on day 5, evening shift, "cashier" skill, the eligible list is the set of employees who:

• Are active.
• Have the cashier skill.
• Are not on leave on day 5.
• Are not opted out of the evening shift.

The matrix is computed once at the start of the run, and it dramatically reduces the search space. A slot with three eligible candidates is a very different problem from a slot with thirty.

Step 2: greedy assignment

With the eligibility matrix in hand, the algorithm does a single pass through the slots and assigns each one to the best available candidate. The order in which it visits the slots matters: scarce slots (few eligible candidates) are visited first, because those are the ones most likely to fail if you leave them for later.

For each slot, the algorithm scores every eligible candidate against the soft constraints:

• How many shifts has this candidate been assigned so far this month? (Lower is better — fairness.)
• How many weekend shifts? (Compared to the team average — fairness.)
• Is this their preferred shift type? (Yes is better — preference.)
• Would assigning this slot create a long consecutive-days streak? (No is better — recovery.)
• Has this same employee filled this same day-of-week recently? (No is better — variety.)

The candidate with the highest combined score gets the slot. The algorithm moves on. By the end of this pass, every slot has an assignment (or has been flagged as unfillable, which is rare and indicates a hard-constraint problem the human needs to resolve).

A greedy algorithm is fast — even for large schedules, this pass takes a fraction of a second — and produces a feasible result. But it is not optimal. Decisions made early in the pass can lock in suboptimal choices later: a slot that was easy at the start might assign the only person who could later have filled a hard slot. The next step is what fixes this.

Step 3: fairness rebalancing

After the greedy pass, ShiftPlanning runs a rebalancing loop. The loop looks at the schedule as a whole, identifies imbalances (the person with the most shifts is two more than the person with the fewest, say), and looks for swaps that would reduce those imbalances without violating any hard constraints.

A typical swap: employee A is on Tuesday morning; employee B is on Wednesday morning; both are eligible for both slots; A has more shifts than average and B has fewer. Swapping them moves A's count down by one and B's up by one, narrowing the gap. The algorithm proposes the swap, checks that no hard constraint is broken (A is not on leave Wednesday; B has the right skill; neither now exceeds consecutive-days limits), and accepts it.

The loop repeats with multiple passes — typically up to 100 — accepting any swap that reduces total imbalance and stopping when no more beneficial swaps exist. In practice the gain is largest in the first dozen passes, with diminishing returns afterwards. The total cost of the rebalancing phase, even for large schedules, is usually under a second.

Step 4: validation

Before the schedule is presented to the user, the algorithm runs one final pass that verifies all hard constraints are still satisfied and computes the final fairness metrics: shift counts per person, weekend distribution, consecutive-days streaks, preferred-shift hit rate. These metrics are returned alongside the schedule itself, so the manager can see at a glance whether the run produced a tightly-balanced result or one with visible imbalances that should be smoothed manually.

If a hard constraint cannot be satisfied — typically because the team is genuinely understaffed for the demand — the validator reports it explicitly: which slots are unfilled, why no candidate was eligible, and what the user could change to resolve the gap (often a cross-training decision or a leave-request renegotiation).

Why not full optimisation?

A fair question: why not formulate the entire problem as an integer linear programme and let a solver find the mathematically optimal schedule?

The answer is partly practical and partly philosophical. Practically, browser-based environments do not have great open-source ILP solvers, and full optimisation can take many seconds or minutes for non-trivial schedules — long enough to be a noticeable wait, and far longer than the "greedy plus rebalancing" approach which usually finishes before the user has finished blinking.

Philosophically, "optimal" is a brittle concept. The objective function is a weighted sum of soft constraints, and the weights are educated guesses. A schedule that is technically optimal under one set of weights can be visibly worse under a slightly different set. The greedy + rebalancing approach produces schedules that are within a few percent of the optimum and far more robust to small changes in the weights — which is the property that matters in practice.

Reading the output

Once you understand the four steps, you can read a generated schedule with sharper eyes. When the algorithm makes a non-obvious choice — putting this person on Sunday instead of that one — the reason is usually one of three things:

1. The other person was ineligible. They were on leave, missing a skill, or would have exceeded a consecutive-days limit.
2. The greedy step picked the highest-scoring candidate at that moment.Lower shift count, weekend balance, preference fit — one or more of these tipped the choice.
3. A rebalancing swap moved the assignment. The original greedy choice was replaced because moving it improved the overall fairness metrics.

If the result still looks wrong, the right response is to inspect the inputs: are the skill assignments correct? Are the leave requests entered? Are the soft constraint weights what you expected? In ShiftPlanning, every assignment in the grid can be locked or replaced manually, so the human always has the last word — but the algorithm's reasoning is at least visible enough to argue with.

Where this approach falls short

It would be dishonest to claim greedy + rebalancing handles every scheduling problem gracefully. Cases it struggles with:

• Highly interdependent constraints. When the value of an assignment depends on three or four other unrelated assignments simultaneously, greedy + rebalancing can get stuck in local optima that an ILP solver would jump out of.
• Many-to-many shift bidding.If your model is "employees declare bids on shifts and the system has to assign by some auction rule," this is a different problem and benefits from purpose-built algorithms.
• Multi-week optimisation. Optimising across 8 weeks at once is a much bigger search than 4 weeks, and the rebalancing loop scales by squared problem size. ShiftPlanning targets a single month at a time and accepts that decisions cross the month boundary as carry-over input.

For the small-team problem these caveats are usually invisible. For larger or more exotic scheduling problems, the right tool is a different approach — and acknowledging the boundary is more honest than pretending one algorithm fits all.

The takeaway

Schedule generation is not magic. It is a structured search through a vast but tractable space, made tractable by ruling things out aggressively (hard constraints), getting to a feasible answer fast (greedy), and then iterating it into a balanced one (rebalancing). Knowing the steps gives you the language to evaluate, defend, and override the results — and that language is the difference between a tool you trust and one you nervously hope is right.