Flow shop scheduling: Johnson's rule

Why it matters

In many shops every job visits the same machines in the same order – turning then grinding, printing then binding, machining then painting. The order in which jobs enter such a flow shop changes how long the second machine sits idle and therefore when the last job is finished. Johnson's rule gives the best sequence for two machines in a few minutes by hand, and it extends to some three-machine cases.

Key ideas

Flow shop. n jobs, m machines, every job follows the same machine order M1 → M2 → … → Mm. Here we consider permutation schedules: the same job sequence on every machine. For two machines (and for three machines under Johnson's condition) the best permutation schedule is optimal among all schedules.

Objective: makespan. The makespan C_max is the time from the start of the first job on M1 to the finish of the last job on the last machine. Minimising it maximises machine utilisation and minimises total idle time on the last machine.

Assumptions. All jobs are available at time zero; processing times are known and include set-up (set-ups independent of sequence); a machine handles one job at a time and a job is on one machine at a time; no preemption; unlimited buffer between machines; transfer time negligible.

Johnson's rule (n jobs, 2 machines).

1. List the times aᵢ on M1 and bᵢ on M2.
2. Find the smallest time among all remaining aᵢ and bᵢ.
3. If it is on M1 (aᵢ), place job i at the earliest free position in the sequence; if it is on M2 (bᵢ), place it at the latest free position.
4. Remove the job and repeat until all are placed.
5. Ties: if a job's aᵢ = bᵢ, put it in either end; if two jobs tie on M1, take either first; if they tie on M2, take either last. Different tie choices give the same makespan. Equivalent form: put jobs with aᵢ ≤ bᵢ first, in increasing aᵢ; then jobs with aᵢ > bᵢ, in decreasing bᵢ.

Why it works. The first job should be quick on M1 so M2 starts early; the last job should be quick on M2 so little work is left after M1 finishes. The total idle time on M2 is what the sequence controls.

Three machines. If min(aᵢ) ≥ max(bᵢ) or min(cᵢ) ≥ max(bᵢ) (M2 is dominated by M1 or M3), form two fictitious machines with times gᵢ = aᵢ + bᵢ and hᵢ = bᵢ + cᵢ and apply Johnson's rule to them; the resulting sequence is optimal for the three machines. If neither condition holds, the method is only a heuristic.

More than three machines. No simple optimal rule exists; heuristics such as Campbell–Dudek–Smith (CDS, which applies Johnson's rule to m − 1 grouped two-machine problems), Palmer's slope index and NEH are used, or branch and bound for small problems.

Gantt chart check. Always draw (or tabulate) start and finish times: on M1 jobs follow back to back; on M2 a job starts at the later of (its M1 finish, the previous job's M2 finish).

Formulas

Finish on M1: C₁(k) = C₁(k−1) + a(k) Finish on M2: C₂(k) = max[C₁(k), C₂(k−1)] + b(k)

• k = position in the sequence, a(k), b(k) = processing times of the job in position k on M1 and M2 (h or min); C₁(0) = C₂(0) = 0.

Makespan C_max = C₂(n)

Idle time on M2 = C_max − Σ bᵢ Idle time on M1 (after its last job, until C_max) = C_max − Σ aᵢ

Three-machine reduction: gᵢ = aᵢ + bᵢ, hᵢ = bᵢ + cᵢ

• Valid when min aᵢ ≥ max bᵢ or min cᵢ ≥ max bᵢ; then C_max is found from the three-machine table, not from g and h.

Worked examples

Example 1 (standard) – five jobs, two machines. Times (h): A: M1 5, M2 2; B: 1, 6; C: 9, 7; D: 3, 8; E: 10, 4.

1. Smallest time = 1 (B on M1) → B first.
2. Next smallest = 2 (A on M2) → A last.
3. Next = 3 (D on M1) → D second.
4. Next = 4 (E on M2) → E fourth (latest free position).
5. C fills the middle. Sequence B–D–C–E–A.
6. Timetable (M1 start–finish | M2 start–finish):
   • B: 0–1 | 1–7
   • D: 1–4 | 7–15
   • C: 4–13 | 15–22
   • E: 13–23 | 23–27
   • A: 23–28 | 28–30
7. Makespan = 30 h. Idle time on M2 = 30 − (2 + 6 + 7 + 8 + 4) = 30 − 27 = 3 h (0–1, 22–23 and 27–28). Checking all 120 sequences confirms 30 h is the minimum.

Example 2 (GATE level) – three machines by Johnson's extension. Times (h) on M1, M2, M3: job 1: 8, 3, 4; job 2: 6, 2, 7; job 3: 7, 4, 5; job 4: 11, 5, 3; job 5: 9, 1, 5.

1. Check: min M1 = 6 ≥ max M2 = 5, so the extension is optimal.
2. Fictitious times g = M1 + M2, h = M2 + M3: job 1 (11, 7), job 2 (8, 9), job 3 (11, 9), job 4 (16, 8), job 5 (10, 6).
3. Only job 2 has g ≤ h (8 ≤ 9), so job 2 goes first.
4. Jobs with g > h in decreasing h: job 3 (9), job 4 (8), job 1 (7), job 5 (6). Sequence 2–3–4–1–5.
5. Timetable (finish times on M1, M2, M3):
   • Job 2: 6, 8, 15
   • Job 3: 13, 17, 22
   • Job 4: 24, 29, 32
   • Job 1: 32, 35, 39
   • Job 5: 41, 42, 47
6. Makespan = 47 h. Idle time on M3 = 47 − 24 = 23 h. Enumeration of all 120 sequences gives the same minimum, 47 h.

Common mistakes

• Placing a job whose minimum is on M2 at the front: M2 minimum means "as late as possible".
• In the "aᵢ ≤ bᵢ first" form, ordering the second group by increasing bᵢ instead of decreasing.
• Starting a job on M2 when M1 finishes it, without checking that M2 is free.
• Applying the three-machine extension without checking the dominance condition.
• Reporting the makespan from the fictitious g/h machines instead of the real three-machine times.
• Calling Johnson's rule a heuristic: for two machines it is exactly optimal for makespan.

For GATE PI

Expect four to six jobs on two machines with a request for the optimal sequence, the minimum makespan or the idle time of a machine; sometimes a three-machine problem that satisfies the dominance condition. Practise doing the sequence and the timetable together, and always verify start times on the second machine from the timetable.

Quick check

1. Job P: M1 = 2, M2 = 7; job Q: M1 = 6, M2 = 3. What is the optimal sequence and makespan?
2. Under Johnson's rule, where does a job with the overall smallest time on M2 go?
3. Three-machine times satisfy min M3 = 6 and max M2 = 5. Can Johnson's extension be used?
4. Σ M2 times = 20 h and makespan = 26 h. What is the idle time on M2?

Answers: 1. P–Q; P: M1 0–2, M2 2–9; Q: M1 2–8, M2 9–12; makespan 12. 2. In the last available position. 3. Yes, because min M3 ≥ max M2. 4. 6 h.