What Is an Optimality Gap in Production Scheduling?

An optimality gap is the proven maximum distance between the schedule a solver returned and the best schedule that could possibly exist for the same goal: "proven within 3% of optimal" means no schedule, tried or untried, can beat this one by more than 3%, and a gap of 0% means the schedule is mathematically proven optimal. The gap is what separates mathematical optimization from sophisticated guessing: a heuristic can report the best plan it found, but only a solver with a lower bound can tell you how good the plans it never examined might have been.

This entry belongs to the EDGEBIC glossary; the general dictionary is at the manufacturing glossary.

How It Works

An exact solver works both ends of the problem at once:

1. From above, it searches for better and better real schedules. Each one it finds becomes the incumbent, with a measurable objective value: total weighted lateness, overall finish time, whatever goal the planner chose.
2. From below, it computes a lower bound: a value provably better than or equal to every schedule that could exist, derived from relaxations of the problem's mathematics rather than from trying candidates.

The gap is the distance between the two, divided by the objective value, as a percentage. The two numbers squeeze toward each other as the solve runs: better incumbents pull the top down, tighter bounds push the floor up. When they meet, the incumbent is proven optimal, and the search can stop with certainty rather than exhaustion.

The crucial property: the gap is a statement about all schedules, including the astronomically many the solver never constructed. "Best of 40 tried" and "proven within 3%" sound similar and are categorically different claims.

A Worked Example

From the EDGEBIC by User Solutions documentation, a three-job problem small enough to see whole. Two machines (cut, then mill), one shared 8-hour day shift. Job A: 6 hours cut, 2 mill, due Tuesday noon. Job B: 2 cut, 6 mill, due Tuesday noon. Job C: 3 cut, 3 mill, due Tuesday 16:00.

The standard engine dispatches A first, and A's long cut blocks the saw all Monday morning while the mill sits idle for 6 hours. Result: B finishes 2 hours late, C late as well, 3 total hours of tardiness.

The solver finds the ordering B, A, C: the short cut feeds the mill by 10:00, all three jobs finish on time, and the overall span shrinks 18%. Then comes the part a heuristic cannot do: the solver's bound confirms zero tardiness is the floor, so the result is proven optimal, gap 0%. Not "we tried 6 orderings and this won," but "no ordering beats this." The optimizer guide walks the same example with the full comparison table.

How EDGEBIC Implements It

EDGEBIC ships two optimizer layers, and the gap is exactly what separates their claims:

Details that keep the number honest:

• The certificate is data. Every result carries whether a gap is available, the bound, and the percentage; the badge in the comparison screen reads those fields directly. Switching engines upgrades the badge automatically because the certificate changes, not because the wording does.
• Never worse, either way. Both layers compare their candidate directly against the baseline schedule and return the baseline unless the candidate strictly wins, so chasing a gap can never cost you your current plan. When the baseline stands, that can itself be the correct answer; see why the optimizer returns the same schedule.
• The proof covers what the model covers. Jobs using features outside the exact model are locked to the standard engine's schedule and listed with reasons; when everything is locked, no optimality is claimed at all.
• Interruptions keep their meaning. A solve stopped at its time budget still returns the incumbent plus the current bound, so a 10-second run reports a wider, but still true, gap.
• External anchors. The solver stack re-proves the published optimum of 55 on the classic ft06 job-shop benchmark as a standing correctness check, tying the internal math to results the scheduling literature has verified for decades.

For a planner, the gap converts optimization from faith to arithmetic: it is the maximum prize still on the table, which is precisely the number that tells you whether to keep searching, and it turns "trust the algorithm" into "read the certificate."