Lesson 14: Sequencing: n Jobs Through 2 Machines¶
14.1 Learning Outcomes¶
By the end of this hour a student will be able to:
- State the assumptions of the classical sequencing problem.
- Apply Johnson's rule to sequence \(n\) jobs on 2 machines.
- Construct the in–out table and compute total elapsed time.
- Compute idle time on each machine and job waiting time.
- Explain why Johnson's rule is optimal and where it stops applying.
14.2 The Sequencing Problem¶
Statement. \(n\) jobs must each be processed on 2 machines, in the same order (Machine 1 then Machine 2). Job \(i\) takes \(A_i\) on machine 1 and \(B_i\) on machine 2. In what order should the jobs be processed to minimise the total elapsed time (makespan)?
The assumptions¶
| Assumption | Meaning |
|---|---|
| Same technological order | every job visits M1 then M2; no job may skip or reverse |
| No passing | the sequence on M2 is the same as on M1 |
| Deterministic times | all \(A_i, B_i\) are known constants |
| One job at a time | each machine processes a single job |
| No pre-emption | once started, a job runs to completion |
| Jobs available at time 0 | no release dates |
| Transport time negligible | movement between machines is instantaneous |
Definition (Total elapsed time / makespan). The time from the start of the first job on M1 to the completion of the last job on M2.
Definition (Idle time). Time a machine is available but not working. Machine 2 is idle at the start (waiting for the first job) and possibly between jobs.
Why the order matters¶
There are \(n!\) possible sequences. For \(n = 10\) that is \(3.6\times10^{6}\); for \(n = 20\), \(2.4\times10^{18}\).
14.3 Johnson's Rule (1954)¶
1. Find the SMALLEST processing time among ALL 2n values {A_i} and {B_i}
2. If it belongs to MACHINE 1 -> schedule that job as EARLY as possible (leftmost free slot)
If it belongs to MACHINE 2 -> schedule that job as LATE as possible (rightmost free slot)
3. Delete that job; repeat with the remaining jobs
4. Break ties arbitrarily (any choice gives an optimal makespan)
The intuition¶
- A small \(A_i\) means the job clears machine 1 quickly, so putting it first gets machine 2 started as early as possible — minimising M2's initial idle time.
- A small \(B_i\) means the job clears machine 2 quickly, so putting it last means the final wait is short — minimising the tail.
Why it is optimal — the exchange argument¶
Theorem (Johnson). The rule produces a sequence of minimum makespan.
Proof sketch. Consider any optimal sequence in which jobs \(i\) and \(j\) are adjacent, with \(i\) before \(j\). One can show that this ordering is at least as good as the reverse iff
This condition defines a total order on the jobs, and sorting by it is exactly what Johnson's rule does. Any sequence violating it can be improved by a pairwise swap, so the sorted sequence is optimal. \(\blacksquare\)
(This "adjacent pairwise interchange" technique is the standard tool for proving scheduling rules optimal, and it appears again in the SPT rule for minimising mean flow time.)
14.4 The In–Out Table¶
Once the sequence is fixed, compute times in one left-to-right pass:
The \(\max\) captures the two ways M2 can be delayed: the job is not ready yet, or M2 is still busy.
Idle time on M2 \(=\) total elapsed time \(-\sum_i B_i\). Idle time on M1 \(=\) total elapsed time \(-\sum_i A_i\).
14.5 Worked Example¶
Five jobs, processing times in hours:
| Job | M1 (\(A_i\)) | M2 (\(B_i\)) |
|---|---|---|
| A | 5 | 2 |
| B | 1 | 6 |
| C | 9 | 7 |
| D | 3 | 8 |
| E | 10 | 4 |
Applying Johnson's rule¶
Sequence slots: [ _ , _ , _ , _ , _ ]
Pass 1. Smallest of all ten values: \(A_B = \mathbf{1}\) (machine 1) ⟹ place B first.
[ B , _ , _ , _ , _ ] — remaining: A, C, D, E
Pass 2. Smallest remaining: \(B_A = \mathbf{2}\) (machine 2) ⟹ place A last.
[ B , _ , _ , _ , A ] — remaining: C, D, E
Pass 3. Smallest remaining: \(A_D = \mathbf{3}\) (machine 1) ⟹ place D as early as possible.
[ B , D , _ , _ , A ] — remaining: C, E
Pass 4. Smallest remaining: \(B_E = \mathbf{4}\) (machine 2) ⟹ place E as late as possible.
[ B , D , _ , E , A ] — remaining: C
Pass 5. Only C left.
The in–out table¶
| Job | M1 in | M1 out | M2 in | M2 out | M2 idle before |
|---|---|---|---|---|---|
| B | 0 | 1 | 1 | 7 | 1 |
| D | 1 | 4 | 7 | 15 | 0 |
| C | 4 | 13 | 15 | 22 | 0 |
| E | 13 | 23 | 23 | 27 | 1 |
| A | 23 | 28 | 28 | 30 | 1 |
Sample calculations.
Job D on M2: \(\max(\text{D's M1 finish} = 4,\ \text{B's M2 finish} = 7) = 7\). M2 is the bottleneck here — D waits 3 hours.
Job E on M2: \(\max(\text{E's M1 finish} = 23,\ \text{C's M2 finish} = 22) = 23\). M1 is the bottleneck — M2 idles 1 hour.
Idle time analysis¶
Cross-check on M2's idle time. From the table: 1 (before B) + 1 (before E) + 1 (before A) \(= 3\) ✓.
A lower bound on the makespan.
Also, makespan \(\ge A_{\text{first}} + \sum_i B_i = 1 + 27 = 28\).
We achieved 30 against a bound of 28 — within 7 %. The 2-hour gap is unavoidable structural idle time, because M1 must finish job E (10 hours, ending at 23) before M2 can start it.
14.6 Solved Problems¶
Problem 1 — Complete sequencing with full analysis¶
Five jobs with times (hours):
| Job | M1 | M2 |
|---|---|---|
| 1 | 3 | 8 |
| 2 | 12 | 10 |
| 3 | 5 | 9 |
| 4 | 2 | 6 |
| 5 | 9 | 3 |
Find the optimal sequence, total elapsed time, idle times and each job's waiting time.
Solution.
Step 1 — Johnson's rule.
| Pass | Smallest value | Machine | Action | Sequence |
|---|---|---|---|---|
| 1 | \(A_4 = 2\) | M1 | job 4 first | [4,_,_,_,_] |
| 2 | \(A_1 = 3\) | M1 | job 1 next earliest | [4,1,_,_,_] |
| 3 | \(B_5 = 3\) | M2 | job 5 last | [4,1,_,_,5] |
| 4 | \(A_3 = 5\) | M1 | job 3 next earliest | [4,1,3,_,5] |
| 5 | job 2 remains | — | fill the gap | [4,1,3,2,5] |
Step 2 — the in–out table.
| Job | M1 in | M1 out | M2 in | M2 out |
|---|---|---|---|---|
| 4 | 0 | 2 | 2 | 8 |
| 1 | 2 | 5 | 8 | 16 |
| 3 | 5 | 10 | 16 | 25 |
| 2 | 10 | 22 | 25 | 35 |
| 5 | 22 | 31 | 35 | 38 |
Sample: job 1's M2 start \(= \max(5,\ 8) = 8\) — M2 is still busy with job 4. Job 5's M2 start \(= \max(31,\ 35) = 35\) — M2 still busy with job 2.
Step 3 — idle times.
Step 4 — job waiting times (time between finishing M1 and starting M2).
| Job | M1 out | M2 in | Waiting |
|---|---|---|---|
| 4 | 2 | 2 | 0 |
| 1 | 5 | 8 | 3 |
| 3 | 10 | 16 | 6 |
| 2 | 22 | 25 | 3 |
| 5 | 31 | 35 | 4 |
| Total | 16 hours |
Interpretation. M2 is the bottleneck: it works 36 of the 38 hours (94.7 % utilisation) while M1 works only 31 (81.6 %). Jobs queue for M2 for a total of 16 hours.
Management implication. Since M2 is the constraint, investment should go into M2 capacity, not M1. Adding a second M2 unit, or reducing M2 processing times, would shorten the makespan; speeding up M1 would achieve nothing — it is already idle 7 hours.
Comparing with a naive order. Processing in the given order \(1\to2\to3\to4\to5\):
| Job | M1 out | M2 in | M2 out |
|---|---|---|---|
| 1 | 3 | 3 | 11 |
| 2 | 15 | 15 | 25 |
| 3 | 20 | 25 | 34 |
| 4 | 22 | 34 | 40 |
| 5 | 31 | 40 | 43 |
Five hours saved by re-ordering, at zero cost. This is the most compelling argument for sequencing analysis.
Problem 2 — Ties in Johnson's rule¶
Sequence the following, noting the ties.
| Job | M1 | M2 |
|---|---|---|
| P | 4 | 4 |
| Q | 6 | 2 |
| R | 2 | 8 |
| S | 4 | 6 |
Solution.
Pass 1. Smallest of all eight values: 2, appearing twice — \(A_R = 2\) (M1) and \(B_Q = 2\) (M2).
Break the tie arbitrarily. Take \(A_R = 2\) ⟹ R first.
[R,_,_,_]
Pass 2. Smallest remaining: \(B_Q = 2\) (M2) ⟹ Q last.
[R,_,_,Q]
Pass 3. Remaining P \((4,4)\) and S \((4,6)\). Smallest value: 4, appearing three times (\(A_P\), \(B_P\), \(A_S\)).
Take \(A_S = 4\) (M1) ⟹ S as early as possible: [R,S,_,Q], then P fills the gap.
Alternative tie-break. Take \(B_P = 4\) (M2) ⟹ P as late as possible (before Q):
[R,_,P,Q], then S fills the gap.
Try yet another: take \(A_P = 4\) (M1) ⟹ P as early as possible: [R,P,S,Q].
Compare the makespans.
Sequence I (\(R,S,P,Q\)):
| Job | M1 in | M1 out | M2 in | M2 out |
|---|---|---|---|---|
| R | 0 | 2 | 2 | 10 |
| S | 2 | 6 | 10 | 16 |
| P | 6 | 10 | 16 | 20 |
| Q | 10 | 16 | 20 | 22 |
Makespan = 22.
Sequence III (\(R,P,S,Q\)):
| Job | M1 in | M1 out | M2 in | M2 out |
|---|---|---|---|---|
| R | 0 | 2 | 2 | 10 |
| P | 2 | 6 | 10 | 14 |
| S | 6 | 10 | 14 | 20 |
| Q | 10 | 16 | 20 | 22 |
Makespan = 22. ✓
The theoretical point. Johnson's rule guarantees an optimal makespan, not a unique sequence. Ties produce alternate optima.
The practical point. When ties occur, choose on secondary criteria the model ignores:
- minimise total job waiting time (customer service),
- put high-priority customers earlier,
- group jobs needing the same tooling to reduce setup.
(In this instance, total waiting time is \(0+4+6+4 = 14\) for Sequence I and \(0+4+4+6 = 14\) for Sequence III — also tied. A larger example would generally separate them.)
Problem 3 — Proving a pairwise interchange improves the schedule¶
Two jobs \(i\) and \(j\) are adjacent. Show that \(i\) before \(j\) is at least as good as \(j\) before \(i\) iff \(\min(A_i, B_j) \le \min(A_j, B_i)\). Illustrate with \(i = (2, 8)\) and \(j = (6, 3)\).
Solution.
The general condition. Suppose M1 becomes free at time \(t_1\) and M2 at \(t_2\) before this pair. Processing \(i\) then \(j\), the pair's completion on M2 is
The three terms correspond to: M1 being the constraint throughout; \(i\) delaying \(j\) on M2; and M2 being backed up from before.
The first and third terms are symmetric in \(i\) and \(j\), so the comparison reduces to the middle term:
Rearranging the full condition yields the standard form
Illustration. \(i = (A_i, B_i) = (2, 8)\) and \(j = (A_j, B_j) = (6, 3)\).
Verify by direct computation (starting from an empty system, \(t_1 = t_2 = 0\)):
Order \(i \to j\):
| Job | M1 in | M1 out | M2 in | M2 out |
|---|---|---|---|---|
| \(i\) | 0 | 2 | 2 | 10 |
| \(j\) | 2 | 8 | 10 | 13 |
Makespan = 13.
Order \(j\to i\):
| Job | M1 in | M1 out | M2 in | M2 out |
|---|---|---|---|---|
| \(j\) | 0 | 6 | 6 | 9 |
| \(i\) | 6 | 8 | 9 | 17 |
Makespan = 17.
Consistency with Johnson's rule. The smallest of the four values is \(A_i = 2\), on machine 1, so the rule places \(i\) first ✓ — the same answer.
Why the exchange argument proves optimality. If a sequence contains any adjacent pair violating the condition, swapping them does not increase the makespan. Repeating until no violations remain yields a sequence satisfying the condition everywhere — which is precisely Johnson's ordering. Since the makespan never increased, that sequence is optimal. \(\blacksquare\)
Problem 4 — When Johnson's rule does NOT apply¶
Identify which of these situations Johnson's rule can handle, and what to do otherwise.
(a) 3 machines in series. (b) Jobs may pass each other (different order on M2). (c) Job 3 cannot start before hour 5 (release date). (d) Setup time of 1 hour between consecutive jobs on M1. (e) Minimise total job waiting time instead of makespan.
Solution.
(a) 3 machines — CONDITIONALLY. Johnson's rule extends to 3 machines only if
(where \(B\) is the middle machine). If so, convert to a 2-machine problem with \(G_i = A_i + B_i\) and \(H_i = B_i + C_i\), and apply Johnson (L15). If neither condition holds, the 3-machine problem is NP-hard and needs branch and bound or heuristics.
(b) Passing allowed — NOT DIRECTLY. Johnson assumes a permutation schedule (same order on both machines). For 2 machines this costs nothing: there is always an optimal permutation schedule, so allowing passing does not help. (For 3+ machines, permutation schedules can be strictly worse than the true optimum.)
(c) Release dates — NO. Johnson assumes all jobs are available at \(t=0\). With release dates the problem becomes \(F2|r_j|C_{\max}\), which is NP-hard. Use branch and bound, or a heuristic (e.g. apply Johnson to the available set, re-sequencing as jobs are released).
(d) Sequence-independent setup — YES, with a fix. If the setup is the same between any pair, simply add it to each processing time: \(A_i' = A_i + 1\). Johnson then applies unchanged. If setups are sequence-dependent (\(s_{ij}\) depends on which job precedes which), the problem becomes a travelling-salesman-like problem and is NP-hard.
(e) Different objective — NO. Johnson minimises the makespan specifically. To minimise mean flow time (equivalently, total waiting), the optimal rule on a single machine is SPT (shortest processing time first). On two machines with the flow-time objective the problem is NP-hard.
Summary table.
| Variation | Johnson applies? | If not, use |
|---|---|---|
| 2 machines, makespan | ✓ yes, optimal | — |
| 3 machines, condition holds | ✓ via conversion | — |
| 3 machines, condition fails | ✗ | branch and bound |
| Release dates | ✗ | branch and bound / heuristic |
| Uniform setup times | ✓ (absorb into \(A_i\)) | — |
| Sequence-dependent setups | ✗ | TSP-like methods |
| Flow-time objective | ✗ | SPT (1 machine); NP-hard for 2 |
Problem 5 — A complete production-scheduling study¶
A print shop has a printing press (M1) and a binding machine (M2). Six orders are pending. Advise the manager on the sequence, and quantify the benefit.
| Order | Customer | Printing (h) | Binding (h) | Due (h from now) |
|---|---|---|---|---|
| 1 | Alpha | 6 | 3 | 40 |
| 2 | Beta | 2 | 7 | 20 |
| 3 | Gamma | 10 | 8 | 45 |
| 4 | Delta | 4 | 9 | 30 |
| 5 | Epsilon | 8 | 2 | 50 |
| 6 | Zeta | 3 | 6 | 25 |
Solution.
Step 1 — Johnson's rule.
| Pass | Smallest | Machine | Action | Sequence |
|---|---|---|---|---|
| 1 | \(A_2 = 2\) | M1 | order 2 first | [2,_,_,_,_,_] |
| 2 | \(B_5 = 2\) | M2 | order 5 last | [2,_,_,_,_,5] |
| 3 | \(A_6 = 3\) | M1 | order 6 next earliest | [2,6,_,_,_,5] |
| 4 | \(B_1 = 3\) | M2 | order 1 next latest | [2,6,_,_,1,5] |
| 5 | \(A_4 = 4\) | M1 | order 4 next earliest | [2,6,4,_,1,5] |
| 6 | order 3 remains | — | fill | [2,6,4,3,1,5] |
Step 2 — the in–out table.
| Order | M1 in | M1 out | M2 in | M2 out |
|---|---|---|---|---|
| 2 (Beta) | 0 | 2 | 2 | 9 |
| 6 (Zeta) | 2 | 5 | 9 | 15 |
| 4 (Delta) | 5 | 9 | 15 | 24 |
| 3 (Gamma) | 9 | 19 | 24 | 32 |
| 1 (Alpha) | 19 | 25 | 32 | 35 |
| 5 (Epsilon) | 25 | 33 | 35 | 37 |
Step 3 — utilisation.
Step 4 — the due-date check (the crucial business question).
| Order | Customer | Completion | Due | Lateness |
|---|---|---|---|---|
| 2 | Beta | 9 | 20 | −11 (early) |
| 6 | Zeta | 15 | 25 | −10 (early) |
| 4 | Delta | 24 | 30 | −6 (early) |
| 3 | Gamma | 32 | 45 | −13 (early) |
| 1 | Alpha | 35 | 40 | −5 (early) |
| 5 | Epsilon | 37 | 50 | −13 (early) |
Step 5 — comparison with plausible alternatives.
(a) First-come-first-served (\(1\to2\to3\to4\to5\to6\)):
| Order | M1 out | M2 in | M2 out |
|---|---|---|---|
| 1 | 6 | 6 | 9 |
| 2 | 8 | 9 | 16 |
| 3 | 18 | 18 | 26 |
| 4 | 22 | 26 | 35 |
| 5 | 30 | 35 | 37 |
| 6 | 33 | 37 | 43 |
Makespan = 43 hours. Order 6 (Zeta, due at 25) completes at 43 — 18 hours LATE.
(b) Earliest due date (\(2\to6\to4\to1\to3\to5\)):
| Order | M1 out | M2 in | M2 out |
|---|---|---|---|
| 2 | 2 | 2 | 9 |
| 6 | 5 | 9 | 15 |
| 4 | 9 | 15 | 24 |
| 1 | 15 | 24 | 27 |
| 3 | 25 | 27 | 35 |
| 5 | 33 | 35 | 37 |
Makespan = 37 hours — the same as Johnson, and all orders on time.
Step 6 — the recommendation.
Quantified benefits versus first-come-first-served.
| Metric | FCFS | Johnson | Gain |
|---|---|---|---|
| Makespan | 43 h | 37 h | 6 h (14 %) |
| Late orders | 1 (Zeta, 18 h late) | 0 | eliminated |
| Press utilisation | 76.7 % | 89.2 % | +12.5 pts |
| Binder utilisation | 81.4 % | 94.6 % | +13.2 pts |
Additional advice.
-
Six hours of capacity released per cycle at zero cost — enough to take on another Beta-sized order every batch.
-
The binder is the bottleneck (94.6 % utilised versus the press's 89.2 %). Any capacity investment should go to binding.
-
Two optimal sequences exist (Johnson's and the EDD variant), both with makespan 37. Prefer the EDD variant if due dates might tighten, since it completes urgent jobs sooner — the same makespan with a better safety margin. This is a case where using the tie-break intelligently has real value.
-
Caveat. The model assumes deterministic times. If printing times vary by ±20 %, the 5-hour margin on Alpha could evaporate. Recommend a schedule review whenever a job overruns its estimate by more than 3 hours.
14.7 Practice Problems¶
- Sequence: jobs \((A,B)\) = \((5,4), (2,6), (7,3), (4,8)\). [Ans: \(2\to4\to1\to3\); makespan 23]
- For the §4 example, what is the total job waiting time? [Ans: \(0+3+2+0+0 = 5\) h]
- State the two-machine lower bound on makespan and evaluate it for Problem 1 of §5.
- Why can M1 never be idle between jobs in a Johnson schedule?
- Two jobs have \((3,7)\) and \((5,2)\). Which goes first, and why?
- What happens to Johnson's rule if all \(A_i = A\) (constant)? [Ans: order by decreasing... derive it]
- Give two situations in which Johnson's rule does not apply.
14.8 Summary¶
- The 2-machine sequencing problem minimises makespan under strong assumptions: same technological order, no passing, deterministic times, all jobs available at \(t=0\).
- Johnson's rule: repeatedly take the smallest of all \(2n\) times; if it is on M1 place the job as early as possible, if on M2 place it as late as possible. \(O(n\log n)\) versus \(n!\) enumeration.
- Intuition: fill the pipeline fast at the front, drain it fast at the back. Optimality is proved by an adjacent pairwise interchange argument: \(i\) precedes \(j\) iff \(\min(A_i,B_j)\le\min(A_j,B_i)\).
- In–out table: M1 never waits; \(\text{M2 start} = \max(\text{this job's M1 finish},\ \text{previous job's M2 finish})\).
- Idle time on a machine \(=\) makespan \(-\) its total processing time. Lower bound on makespan: \(\max(\sum A_i,\ \sum B_i)\).
- Ties give alternate optima — exploit them for due dates, priority customers or setup grouping.
- Johnson's rule is a rare exact polynomial scheduling result. Three machines (unless a special condition holds), release dates, sequence-dependent setups and flow-time objectives are all NP-hard.
Next lesson: L15 — \(n\) jobs through 3 machines, and 2 jobs through \(m\) machines.
Practise now: unit2-games-networks-lab.html → Sequencing Lab: enter jobs, watch Johnson's rule
build the sequence pass by pass, and see the Gantt chart with idle time shaded.