Skip to content

Lesson 14: Sequencing: n Jobs Through 2 Machines

14.1 Learning Outcomes

By the end of this hour a student will be able to:

  1. State the assumptions of the classical sequencing problem.
  2. Apply Johnson's rule to sequence \(n\) jobs on 2 machines.
  3. Construct the in–out table and compute total elapsed time.
  4. Compute idle time on each machine and job waiting time.
  5. 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}\).

\[ \boxed{\ \textbf{Johnson's rule finds the optimum in } O(n\log n) \textbf{ — a sort, nothing more.}\ } \]

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.
\[ \boxed{\ \textbf{Fill the pipeline fast at the front; drain it fast at the back.}\ } \]

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

\[ \min(A_i,\ B_j) \ \le\ \min(A_j,\ B_i) \]

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:

\[ \text{M1 start} = \text{M1 finish of the previous job} \qquad(\text{M1 never waits}) \]
\[ \boxed{\ \text{M2 start} \ =\ \max\big(\text{M1 finish of THIS job},\ \ \text{M2 finish of the PREVIOUS job}\big)\ } \]

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.

\[ \boxed{\ \text{Optimal sequence: } B \to D \to C \to E \to A\ } \]

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.

\[ \boxed{\ \textbf{Total elapsed time} = 30 \ \text{hours}\ } \]

Idle time analysis

\[ \sum_i A_i = 5+1+9+3+10 = 28, \qquad \sum_i B_i = 2+6+7+8+4 = 27 \]
\[ \text{M1 idle} = 30 - 28 = \mathbf{2\ \text{hours}} \]
\[ \text{M2 idle} = 30 - 27 = \mathbf{3\ \text{hours}} \]

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.

\[ \text{makespan} \ \ge\ \max\left(\sum_i A_i,\ \ \sum_i B_i\right) = \max(28, 27) = 28 \]

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]
\[ \boxed{\ \text{Optimal sequence: } 4 \to 1 \to 3 \to 2 \to 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.

\[ \boxed{\ \textbf{Total elapsed time} = 38 \ \text{hours}\ } \]

Step 3 — idle times.

\[ \sum A_i = 2+3+5+12+9 = 31, \qquad \sum B_i = 6+8+9+10+3 = 36 \]
\[ \text{M1 idle} = 38 - 31 = \mathbf{7\ \text{hours}} \quad(\text{all at the end, after } t=31) \]
\[ \text{M2 idle} = 38 - 36 = \mathbf{2\ \text{hours}} \quad(\text{at the start, } 0\to2) \]

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
\[ \text{Makespan} = 43 \ \text{hours versus } 38 \ \text{— Johnson saves } \mathbf{5\ \text{hours (11.6\%)}}. \]

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.

\[ \text{Sequence I: } R \to S \to P \to Q \]

Alternative tie-break. Take \(B_P = 4\) (M2) ⟹ P as late as possible (before Q): [R,_,P,Q], then S fills the gap.

\[ \text{Sequence II: } R \to S \to P \to Q \qquad \textbf{— the same!} \]

Try yet another: take \(A_P = 4\) (M1) ⟹ P as early as possible: [R,P,S,Q].

\[ \text{Sequence III: } R \to P \to S \to 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. ✓

\[ \boxed{\ \textbf{Both tie-breaks give the SAME optimal makespan of 22 hours.}\ } \]

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.
\[ \boxed{\ \textbf{Ties are free flexibility — use them.}\ } \]

(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

\[ C_{ij} = \max\Big(t_1 + A_i + A_j + B_j,\ \ t_1 + A_i + B_i + B_j,\ \ t_2 + B_i + B_j\Big) \]

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:

\[ C_{ij} \le C_{ji} \iff A_i + B_i \le A_j + B_j \ \text{...} \]

Rearranging the full condition yields the standard form

\[ \boxed{\ \min(A_i,\ B_j) \ \le\ \min(A_j,\ B_i)\ } \]

Illustration. \(i = (A_i, B_i) = (2, 8)\) and \(j = (A_j, B_j) = (6, 3)\).

\[ \min(A_i,\ B_j) = \min(2,\ 3) = \mathbf{2} \]
\[ \min(A_j,\ B_i) = \min(6,\ 8) = \mathbf{6} \]
\[ 2 \le 6 \ \Longrightarrow\ \textbf{$i$ should come BEFORE $j$.} \]

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.

\[ 13 < 17 \ \checkmark \ \textbf{— the condition correctly predicted the better order.} \]

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

\[ \min_i A_i \ \ge\ \max_i B_i \qquad\textbf{or}\qquad \min_i C_i \ \ge\ \max_i B_i \]

(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
\[ \boxed{\ \textbf{Johnson's rule is a rare exact polynomial result. Almost every generalisation is NP-hard.}\ } \]

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]
\[ \boxed{\ \text{Optimal sequence: } 2 \to 6 \to 4 \to 3 \to 1 \to 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
\[ \boxed{\ \textbf{Total elapsed time} = 37\ \text{hours}\ } \]

Step 3 — utilisation.

\[ \sum A_i = 6+2+10+4+8+3 = 33, \qquad \sum B_i = 3+7+8+9+2+6 = 35 \]
\[ \text{M1 (press) idle} = 37-33 = \mathbf{4\ h} \ (89.2\%\ \text{utilised}) \]
\[ \text{M2 (binder) idle} = 37-35 = \mathbf{2\ h} \ (94.6\%\ \text{utilised}) \]

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)
\[ \boxed{\ \textbf{ALL SIX ORDERS ARE DELIVERED EARLY. Maximum lateness} = -5\ \text{hours.}\ } \]

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.

\[ \boxed{\ \text{Sequence } 2 \to 6 \to 4 \to 3 \to 1 \to 5\ \text{ (or the EDD variant)}\ } \]

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.

  1. Six hours of capacity released per cycle at zero cost — enough to take on another Beta-sized order every batch.

  2. The binder is the bottleneck (94.6 % utilised versus the press's 89.2 %). Any capacity investment should go to binding.

  3. 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.

  4. 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

  1. Sequence: jobs \((A,B)\) = \((5,4), (2,6), (7,3), (4,8)\). [Ans: \(2\to4\to1\to3\); makespan 23]
  2. For the §4 example, what is the total job waiting time? [Ans: \(0+3+2+0+0 = 5\) h]
  3. State the two-machine lower bound on makespan and evaluate it for Problem 1 of §5.
  4. Why can M1 never be idle between jobs in a Johnson schedule?
  5. Two jobs have \((3,7)\) and \((5,2)\). Which goes first, and why?
  6. What happens to Johnson's rule if all \(A_i = A\) (constant)? [Ans: order by decreasing... derive it]
  7. 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.