Sequencing problems are mostly NP-hard, which is why scheduling software costs what it does. There is one important exception, and it is worth knowing because a surprising number of finishing operations are structurally a two-machine flow shop.

The rule

Every job must pass through machine A then machine B, in that order. You know each job's time on each machine. To minimise makespan — total time from the start of the first job to the completion of the last — do this:

  1. List every job with its time on A and its time on B.
  2. Find the smallest single time value anywhere in the list.
  3. If that value is on machine A, schedule the job as early as possible. If it is on machine B, schedule it as late as possible.
  4. Remove the job and repeat until every position is filled.

This gives the exact optimum, not an approximation. It runs in the time it takes to sort a list.

Worked example: washing then finishing

LotWash (h)Finish (h)
A52
B16
C97
D38
E104

Smallest value is 1 (lot B, machine A) so B goes first. Next smallest is 2 (lot A, machine B) so A goes last. Then 3 (lot D, machine A) goes second. Then 4 (lot E, machine B) goes second-to-last. C takes the middle. Sequence: B, D, C, E, A, makespan 30 hours against 35 for the worst ordering. Same machines, same work, five hours saved by sorting a list.

The three-machine extension

Johnson's rule extends exactly to three machines only when one of two conditions holds: the minimum time on machine A is at least the maximum on machine B, or the minimum on machine C is at least the maximum on B. In other words, when the middle machine is dominated and effectively disappears. Collapse it by setting A' = A + B and C' = B + C, then apply the two-machine rule to A' and C'.

If neither condition holds, you are in general flow-shop territory and no exact hand method exists.

What to use instead

For general shops, dispatching rules are what actually get deployed, because they are local, need no global solve, and degrade gracefully.

  • SPT (shortest processing time) minimises average flow time and average WIP. It is optimal for average lateness on a single machine. Its weakness is starving long jobs indefinitely.
  • EDD (earliest due date) minimises maximum lateness on a single machine. Use it when the penalty is a missed shipment rather than an average.
  • Critical ratio = time remaining until due date divided by work remaining. Below 1.0 means the job is already late. It balances urgency against work content and is the most defensible rule to give a supervisor.
  • Slack per remaining operation is the version to use when jobs have very different operation counts.

Choosing a rule honestly

There is no rule that wins on every objective. SPT will make your average look excellent and your worst case terrible. EDD will protect your due dates and inflate WIP. Decide which number the business is judged on, pick the matching rule, and then measure the metric you did not optimise so you know what it cost you.

One practical warning

Johnson's rule assumes no job passing, no machine breakdown, and fixed processing times known in advance. On a real floor, re-running the sequence after every disruption produces sequence churn that operators hate and that destroys setup savings. Freeze the sequence for a shift, re-solve at shift boundaries, and treat the theoretical optimum as a target rather than an instruction.