Scheduling Algorithms: From Dispatch Rules to Exact Solvers

“Algorithm” gets used as if it means one thing in production scheduling, and it doesn’t — a dispatch rule that picks the next job off a queue in a fraction of a second and an exact constraint solver that spends two minutes proving mathematical optimality are both, technically, algorithms, and they promise wildly different things. This page lays out the landscape as a taxonomy, from fastest-and-simplest to slowest-and-most-rigorous — the same spectrum what is production scheduling sketches from dispatch lists up to full APS — so a vendor’s claim about their engine can be placed on that spectrum rather than taken on faith.

Dispatch rules: instant, local, myopic

The simplest scheduling logic in real use isn’t really “solving” anything — it’s a dispatch rule: a fixed priority rule applied, one decision at a time, to whatever’s waiting at a resource right now. Three of the most common:

• EDD (Earliest Due Date) — run whichever waiting job has the closest due date next.
• SPT (Shortest Processing Time) — run whichever waiting job takes the least time next, which tends to clear the most jobs through a queue fastest but can leave a long job starved indefinitely if shorter jobs keep arriving ahead of it.
• Critical ratio — run whichever job has the least slack relative to how much work it still has left, a rough measure of “how much trouble is this job in.”

Dispatch rules are computed instantly, require no model of the shop beyond “what’s waiting right now,” and are genuinely useful as a floor-level tiebreaker — a printed or on-screen ranking that tells an operator what to run next without anyone having to think it through fresh every time. Their limitation is built into how they work: a dispatch rule makes each decision locally, looking only at the queue in front of it at this moment, with no visibility into how that choice affects a downstream work center three operations later, and no ability to look ahead and see that today’s “obviously correct” pick creates a collision on tomorrow’s schedule. It’s a real method, not a strawman — but it’s optimizing one decision at a time, never the whole plan at once.

Constructive heuristics: build once, don’t look back

A step up in ambition, a constructive (greedy) heuristic builds an entire schedule in one pass, typically by applying a rule like a dispatch rule repeatedly and systematically across every resource and every order, committing each placement as it goes and never revisiting an earlier decision once made. This produces a complete schedule, not just a next-job ranking, and it does so fast — a greedy pass over even a large order book is computationally cheap.

The limitation is right there in the name: greedy means every decision is locked in the moment it’s made, on the basis of whatever looked best at that point, with no mechanism for going back and improving an earlier choice once a later one reveals it was suboptimal. A greedy heuristic can paint itself into a corner exactly the way a person rushing through a big cross-referenced puzzle can — each individual step looked reasonable, and the finished result is worse than it needed to be, because nothing ever went back to check.

Metaheuristics: good, but unprovable

Metaheuristics — tabu search, genetic algorithms, simulated annealing, and similar families — take the opposite approach: instead of committing to one pass, they explore many candidate schedules, using randomized or structured moves to escape the kind of local trap a greedy heuristic falls into, and keep the best schedule found across many iterations, often stopping only when a time budget runs out. These methods can produce genuinely strong schedules, frequently much better than a single greedy pass, and they scale to large, messy real-world problems more gracefully than exact methods often do.

What a metaheuristic cannot do, by its nature, is tell you how far its answer is from the best possible one. It explored a lot of candidates and kept the best it found — but “the best of everything I tried” carries no mathematical guarantee about the gap between that answer and the true optimum, because a metaheuristic never frames the problem in a way that makes a provable bound part of the output. Two runs of the same metaheuristic on the same problem, with different random starting points, can produce two different “best” schedules — both good, neither one accompanied by proof of how good.

MILP and constraint programming: exact, and provably bounded

At the far end sit exact methods — Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP), the family constraint-based scheduling covers in depth. Both frame the scheduling problem as a precise mathematical model — variables, hard constraints, an objective to minimize — and search for a solution using methods that come with a genuine guarantee: when the solver reports a solution as optimal, that’s not “the best one we happened to try,” it’s a mathematical proof that no legal solution scores better on the stated objective. Modern CP solvers are built specifically for problems shaped like job-shop scheduling — many discrete resources, many precedence-linked operations, real calendar and capacity constraints — and report a solve status (optimal, feasible-with-a-bound, or that no legal solution exists at all) alongside every result, not just an answer.

The trade-off is computational cost. Proving optimality — or even proving a tight bound on how far a found solution could possibly be from optimal — takes real solve time, and that time grows quickly as the number of orders, operations, and resources grows, for reasons the next section makes precise. This is exactly why a well-built exact solver is typically run with a time budget: search for the best schedule it can within, say, two minutes, report whatever provable bound it reached by then, and hand back the best legal schedule found even if optimality was never formally proven — a status honestly reported as feasible, not silently upgraded to “optimal” because the clock ran out.

The same three jobs, two methods, two answers

The gap between “instant and local” and “slower and provably best” is easiest to see on one small shared machine. Three jobs are waiting: Job 1 needs 90 minutes and is due in 4 hours; Job 2 needs 20 minutes and is due in 1 hour; Job 3 needs 60 minutes and is due in 2 hours.

EDD (earliest due date) looks only at due dates and runs Job 2 first (due soonest), then Job 3, then Job 1 — finishing Job 2 at 20 minutes (on time), Job 3 at 80 minutes (on time), and Job 1 at 170 minutes (on time, with room to spare). On this particular set of three, EDD happens to land every job on time, in one pass, with no lookahead needed at all.

Change one fact — Job 2 is actually due in 15 minutes, not an hour, and can’t realistically make it regardless of what runs first — and EDD’s local logic still dutifully runs it first anyway, because “earliest due date” is the entire rule; it has no way to notice that sacrificing a few minutes of Job 2’s now-unavoidable lateness could instead let Job 3 and Job 1 both finish comfortably on time in a different order. An exact solver evaluating the same three jobs isn’t following a fixed rule — it’s searching the small space of possible orderings for the one that minimizes total lateness across all three, and it can find (and prove) that running Job 3 first, then Job 1, then Job 2 last minimizes total tardiness across the group even though it “sacrifices” the due-soonest job — a trade a purely local, one-decision-at-a-time rule structurally cannot make, because making it requires weighing all three jobs against each other at once, not deciding on whichever one looks most urgent right now.

Neither method is “wrong” — EDD is instant and needs no model of the other jobs’ trade-offs; the exact method needs a moment to search, and needs the jobs’ relative priorities expressed as an objective before it can decide anything. The difference is exactly the taxonomy above, made concrete: local-and-fast vs. global-and-considered, on three jobs small enough to work out by hand.

Why this is hard: job-shop scheduling is NP-hard

It’s worth being precise about why exact methods cost more, rather than treating it as an implementation detail. Classical job-shop scheduling — many jobs, each a sequence of operations, competing for a limited set of machines — belongs to a category computer science calls NP-hard: informally, a problem where no known method can guarantee finding the provably best answer to every possible input in a practical amount of time as the problem grows, and where even just checking whether a proposed guess is correct doesn’t get meaningfully easier than solving the problem outright. This isn’t a statement about any one product’s engineering — it’s a property of the problem itself, established well before modern scheduling software existed, and it’s the honest reason “optimal, instantly, no matter how big the shop” isn’t a claim any legitimate method can make once the number of orders and machines gets large enough.

What this means in practice: exact methods handle real-world-sized problems by searching intelligently rather than exhaustively — modern CP and MILP solvers are vastly better than naive brute force at pruning huge swaths of the search space without ever having to check them individually — and by accepting a time budget with an honestly reported status, rather than promising an instant, guaranteed-optimal answer to every input regardless of size. A vendor claiming otherwise is making a claim the underlying mathematics doesn’t support, independent of how well-built their software is.

How to read a vendor’s algorithm claims

None of the methods above is universally “better” in the abstract — each is a genuine, defensible engineering choice for a given problem size and time budget, and the honest evaluation question isn’t “which algorithm is best” but “which claim is this vendor actually making, and does the language match the mathematics.” A few patterns worth knowing:

• “Advanced heuristics” or “AI-powered optimization” usually describes a metaheuristic or a sophisticated constructive method — capable of strong results, but without a provable bound on how close to optimal the answer is, whatever the marketing language around it implies. That’s not a disqualifying weakness; it’s a specific, nameable trade-off worth understanding rather than glossing over.
• “Optimal” or “provably optimal” should mean exactly what it means in the exact-methods section above: a mathematical proof, not a confident adjective. It’s a fair, specific question to ask any vendor making this claim: does your engine report a solve status, and does it distinguish a proven-optimal result from a best-effort one that ran out of time?
• “Real-time” or “instant” optimization at meaningful shop scale is a strong signal the method underneath is a dispatch rule or a fast constructive heuristic, not an exact solver — genuine exact optimization at real-world scale costs real solve time, for the NP-hard reasons above, and a vendor offering both true optimality guarantees and sub-second results on a large problem is describing something the underlying mathematics doesn’t support.

None of this is a case against heuristic methods, which are a legitimate, often-correct engineering choice — it’s a case for reading algorithm claims for what they actually promise, the same way a careful reader checks what a nutrition label actually states rather than what the front of the box implies. Choosing an APS for Business Central turns this same reading skill into a fuller evaluation checklist, algorithm claims included.

What matters more than the algorithm: the capacity model underneath it

Here’s the honest caveat that belongs on this page and gets skipped in most vendor material: the algorithm family is not the biggest lever on schedule quality — the fidelity of the capacity model feeding it usually is. An exact solver running against a shop calendar with a missing holiday, or a work center’s parallel-machine count that hasn’t been updated since a line was added, produces a mathematically rigorous, confidently wrong schedule. A simple dispatch rule running against accurate, current capacity data produces a rougher but fundamentally trustworthy one. What is an APS system covers this same point from the product-category angle; the algorithm-specific version of it is simple: no algorithm, however mathematically sophisticated, can see past bad input data, and the honest evaluation of any scheduling tool starts with the accuracy of what it’s being fed, not the cleverness of what it does with it.

Key terms

New to the vocabulary? Dispatch rule, heuristic, NP-hard, and constraint programming are defined in the glossary.