What is job shop scheduling?

“Job shop scheduling” is one of those phrases that means two quite different things depending on who says it. To an operations researcher it is a famous combinatorial problem with a precise mathematical statement. To someone running a shop it is the thing they do on Monday morning with a spreadsheet and a phone. This is an attempt to explain both, say honestly where they overlap, and be clear about which one most people searching the phrase are actually living in.

The short version

A job shop is a production environment where work is high mix and low volume, and every order takes its own route through the shop. One job needs the 5-axis mill, then the surface grinder, then inspection. The next needs the lathe, a fixture stored in another cell, and the one operator certified to run it. Nothing flows down a fixed line, because there is no fixed line.

Job shop scheduling is deciding which job runs on which resource, and when — given that the resources are finite, the routes all differ, and the answer has to change every time something does.

That is the whole definition. The difficulty is not in stating it.

Why it is harder than it sounds

Three properties make this genuinely awkward, and they compound.

The constraints are not only machines. A job usually needs a machine and a qualified person and some tooling, all at the same time. Most planning tools model the first, assume the second, and forget the third — which is why so many shop schedules are undone by a fixture that turned out to be on another job.

Every change propagates. In a flow shop, delaying one order mostly delays that order. In a job shop, moving a rush job forward re-sequences everything behind it on every resource it touches. The plan is not a list; it is a web, and pulling one strand moves the others.

The scarce resource moves around. The bottleneck in a job shop is rarely fixed. It is the grinder this week because of the job mix, the inspector next week because two people are on holiday. A plan that assumes a permanent bottleneck will be wrong regularly, and in a way nobody notices until a date slips.

How shops actually do it

Overwhelmingly, in a spreadsheet.

That is not a slight. A spreadsheet is genuinely good at this up to a point: it is free, it is infinitely flexible, everyone can read one, and it encodes the planner’s judgement without requiring anybody to configure a system. Most shops are right to start there and many are right to stay.

The failure mode is specific rather than general. A spreadsheet has no concept of a resource being double-booked — two jobs on one machine are just two cells that happen to be adjacent. Nothing in the file objects. The conflict is discovered on the floor, by the second crew, on the morning the work was due to start.

The other failure is ownership. The planning sheet tends to be maintained by one person who understands the colour codes, and the rest of the shop works from a printout of a version that was current on Tuesday. That works until that person is on holiday, and it is a genuine business risk when it is the only copy of how the shop plans.

We wrote about where exactly that line sits, with the evidence on spreadsheet error rates, in Outgrowing the machine-shop Excel schedule.

The academic problem, and why it is not your problem

If you search the phrase, a good share of what you find will be about the job shop scheduling problem (JSP) in the operations-research sense: n jobs, m machines, each job a fixed sequence of operations with known durations, minimise the makespan.

That problem is hard in the formal sense — job shop scheduling with three or more machines is NP-hard (Garey, Johnson & Sethi, 1976), which is why it has been a benchmark for optimisation research for fifty years. Some famous small instances went unsolved for decades.

It is also not quite the problem a shop has, in three ways that matter:

The inputs are not known. JSP assumes exact processing times. Real shops have estimates, and the estimate is often the least reliable number in the plan.
Makespan is rarely the goal. Shops care about promised dates, keeping an expensive machine fed, and not having to phone a customer. “Finish everything as early as possible” is a proxy that can quietly trade away the thing you actually wanted.
The plan has to be legible. An optimal schedule that nobody can hold in their head, and that reshuffles completely when one job moves, does not survive contact with a shop floor. A plan people trust and can adjust beats a better plan they route around.

This is worth knowing mostly so you can filter your search results. If you are evaluating software and the material is about disjunctive graphs and tabu search, you have wandered into the literature rather than the market.

What “good enough” looks like

For most shops in the 10-to-250-person range, the useful bar is lower than optimisation and higher than a spreadsheet:

Every resource a job needs — machine, person, tooling — is booked together, so a missing one is visible before the job starts rather than after.
A conflict is flagged when it is created, not when it is discovered.
Everyone reads the same current plan.
You can see which resource is actually loaded, so the bottleneck is observed rather than assumed.
Changing the plan takes seconds, because it will change constantly.

Notice that none of those require solving anything. They require the plan to be shared, current, and honest about constraints. That is a much easier problem than the one in the literature, and it is the one that is actually costing shops money.

A note on where this came from

The observation that “what is job shop scheduling” is searched as a standalone question — rather than alongside a software or template search — comes from our own keyword monitoring in August 2026, over a short window. It is what prompted this article. It is an internal observation, not a published study, and should be read as the reason we wrote this rather than as evidence of anything.

If you have got this far and want the practical version, our job shop scheduling page covers how Orkyo models it, and there is a free Excel template if you would rather start where you are.

Sources

Garey, M. R., Johnson, D. S., & Sethi, R., “The Complexity of Flowshop and Jobshop Scheduling” — Mathematics of Operations Research, Vol. 1, No. 2 (May 1976), pp. 117–129. Establishes that job shop scheduling is NP-hard for three or more machines. Cited here for the complexity result only; the paper is a theoretical treatment and makes no claim about industrial practice.