Johnson's rule is an algorithm that orders a set of jobs through two machines, run in the same sequence, so the whole batch finishes as early as possible. It minimizes makespan, the elapsed time from the start of the first job on machine one to the finish of the last job on machine two.
When every job has to pass through the same two steps in the same order, saw then weld, print then laminate, mix then fill, the order you feed the jobs in changes when the batch finishes. Some sequences leave the second machine idle early and scrambling late; a better sequence keeps it fed. Johnson's rule, published by S. M. Johnson in 1954, finds the sequence that finishes soonest, and it does so with a rule simple enough to run by hand. This post walks the algorithm, works a full example, and shows the Gantt result.
What is Johnson's rule?
Johnson's rule is a scheduling method that produces the minimum-makespan order for jobs flowing through two machines in a fixed sequence. It solves a specific, common problem: you have a list of jobs, each needing time on machine one and then machine two, and you want them all done as quickly as possible. Because machine two cannot start a job until machine one has finished it, the sequence determines how much machine two sits waiting, and total idle time on that second machine is exactly what drags makespan out. Johnson's rule minimizes that drag.
The intuition is worth holding onto before the mechanics. You want jobs with a short first step early, so machine two starts working soon and stays busy. You want jobs with a short second step late, so the tail end of the schedule, where machine one is done and only machine two remains, is as small as possible. Short-first-step jobs go to the front; short-second-step jobs go to the back. That single idea is the whole rule.
When can you use Johnson's rule?
You can use it when the problem really is a two-machine flow shop: every job passes through both machines in the same order, and you know each job's processing time on each machine in advance. Those conditions matter. All jobs must follow the same route, machine one then machine two, with no job skipping a step or reversing the order. Processing times must be known and fixed, not discovered as you go. And the objective must be makespan, finishing the whole batch soonest, rather than something like meeting individual due dates, which is a different problem with different answers.
Within those bounds the rule is exact, not approximate: it returns a sequence with the lowest possible makespan, and no other order can beat it. That is unusual in scheduling, where most real problems are too tangled for a guaranteed optimum. It is also why Johnson's rule endures as the textbook starting point for production scheduling even though few plants are literally two machines. It teaches the instinct, keep the downstream resource fed, that carries into far messier schedules.
How does the algorithm work?
The algorithm is a repeated pick-the-smallest procedure that assigns each job to the front or the back of the sequence. Run it by hand on a small job set and it takes a couple of minutes.
- List each job's two times. Write down every job with its processing time on machine one and machine two.
- Find the smallest time remaining. Scan all unscheduled jobs and both machine columns for the single shortest processing time.
- Place it by which machine it fell on. If that shortest time is on machine one, put the job in the earliest open slot at the front; if it is on machine two, put it in the latest open slot at the back.
- Remove and repeat. Drop that job from the list and go back to the previous step with the jobs that remain.
- Break ties by choice. If two times are equal, either pick works; the makespan comes out the same, though the sequence may differ.
- Read off the sequence. When every job is placed, the filled slots front to back are your optimal run order.
What does a worked example look like?
Take five jobs, each with its time on machine one (say, cut) and machine two (say, finish):
| Job | Machine 1 (cut) | Machine 2 (finish) |
|---|---|---|
| A | 5 | 2 |
| B | 1 | 6 |
| C | 9 | 7 |
| D | 3 | 8 |
| E | 10 | 4 |
Apply the rule. The smallest time anywhere is B's 1 on machine one, so B goes to the front. Next smallest is A's 2 on machine two, so A goes to the back. Next is D's 3 on machine one, to the front behind B. Next is E's 4 on machine two, to the back ahead of A. Only C is left, and it takes the remaining middle slot. The optimal sequence is B, D, C, E, A.
Now lay that sequence on a timeline. Each job runs on machine one, then on machine two, and machine two can only start a job once machine one has released it and machine two is free.
The payoff is concrete: the same five jobs run in the order they happened to arrive, A, B, C, D, E, finish at time 34, while Johnson's order finishes at 30. Four time units saved on a five-job batch, with no new equipment and no faster machines, only a better order. That is the same lever a good line-balancing exercise pulls, spending sequence and layout instead of capital.
What do the numbers and sources say?
Context from standards bodies and academic references:
- Flow-shop scheduling and Johnson's rule are defined in the operations body of knowledge maintained by the Association for Supply Chain Management (ASCM/APICS) which frames the rule as the optimal method for the two-machine sequencing problem.
- The rule dates to S. M. Johnson's 1954 paper in Naval Research Logistics Quarterly, and it remains an active reference point in current scheduling research, including recent work revisiting Johnson's rule for makespan minimization in the two-machine flow shop.
- The algorithm runs in O(n log n) time because its cost is dominated by sorting the jobs, which makes it fast enough to apply to large job sets by hand or in a spreadsheet, unlike the exponential blow-up of general multi-machine scheduling.
The practical point: for the narrow two-machine case the answer is both optimal and cheap to compute, which is exactly why it survived seventy years as the entry point to scheduling theory.
What are the limits of Johnson's rule?
The hard limit is the machine count: Johnson's rule is provably optimal for two machines and, in a special extended form, for certain three-machine cases, but it does not generalize to arbitrary shops. Add a third and fourth machine with real routing, and the clean guarantee disappears; the two-machine trick no longer captures the problem. Real plants also break the other assumptions, jobs take different routes, times vary run to run, due dates compete with makespan, machines break down, so the tidy inputs the rule needs rarely exist unmodified on a live floor.
That does not make it useless; it makes it a foundation. The instinct it teaches, sequence so the constrained downstream resource is never starved, is the same logic behind the theory of constraints and behind every advanced planning and scheduling engine, which hold dozens of constraints at once and search for a good sequence where no exact rule exists. Johnson's rule is where you learn the idea; APS is where you apply it to a shop too complex to solve by hand. It also pairs with disciplined material timing, since a fast sequence still stalls if parts arrive late, the concern behind just-in-time purchasing.
Where the schedule meets the floor
Even a perfect sequence assumes the inputs are true: that the processing times are current, the machines are up, and the material is there. On a real floor those facts live in different systems and drift out of date, so the schedule on paper and the state of the plant quietly diverge, and by mid-shift nobody trusts either. Harmony is an AI-native layer that connects machines, software, and paperwork into one operational layer, with no rip-and-replace, so machine status, run times, and material availability become one live record instead of several stale ones. AI search returns cited answers across those records, so a supervisor can ask which machine is the bottleneck right now or why a job is running long, and Harmony's digital workflows keep the sequence connected to what the floor is actually doing. It does not replace your scheduling logic; it feeds that logic the current reality it needs, the same paper-to-digital move Harmony makes elsewhere on the floor (see the CLS case study), so a good sequence stays good after the shift starts.