Using Johnson's Rule For 2-machine Scheduling The Sequence Is

Using Johnson’s Rule for 2‑Machine Scheduling: Determining the Optimal Sequence

When manufacturers face the classic problem of processing a set of jobs on two workstations, the goal is to minimize the total time the system is busy, known as the makespan. Johnson’s rule, introduced by S. That's why m. Practically speaking, johnson in 1954, offers a simple yet powerful method to obtain the optimal job order for a two‑machine flow shop. This article walks through the logic behind the rule, the step‑by‑step procedure for constructing the sequence, common pitfalls, and practical tips for implementation in real‑world production environments.

Introduction: Why Two‑Machine Scheduling Matters

In many production lines—metal stamping followed by heat treatment, printing then binding, or assembly then testing—each job must travel through exactly two machines in the same order. Although the problem seems straightforward, the order in which jobs are processed can dramatically affect:

• Makespan – the total elapsed time from the start of the first job to the completion of the last.
• Idle time – periods when a machine is waiting for a job, reducing overall equipment effectiveness (OEE).
• Throughput – the number of jobs completed per unit of time.

Finding the sequence that minimizes makespan is a classic combinatorial optimization problem. Even so, for n jobs, there are *n! * possible permutations, quickly becoming infeasible to evaluate by brute force. Johnson’s rule reduces this complexity to a linear algorithm, guaranteeing the optimal sequence for the two‑machine case Simple, but easy to overlook..

This changes depending on context. Keep that in mind The details matter here..

The Core Idea Behind Johnson’s Rule

Johnson’s rule exploits the fact that, on a two‑machine flow shop, the critical path—the longest chain of dependent operations—always includes either the first or the last operation of a job. By strategically placing jobs with short processing times on the first machine early in the schedule, and jobs with short times on the second machine later, the rule balances the workload and eliminates unnecessary waiting.

Formal Statement

Given n jobs (J_1, J_2, \dots, J_n) with processing times:

• (p_{i1}) – time required on Machine 1 (M1)
• (p_{i2}) – time required on Machine 2 (M2)

Johnson’s rule constructs a sequence S as follows:

1. Create two lists:
   List A – jobs where (p_{i1} \le p_{i2}) (shorter on M1)
   List B – jobs where (p_{i1} > p_{i2}) (shorter on M2)

2. Sort List A in ascending order of (p_{i1}).
   Sort List B in descending order of (p_{i2}).

3. Concatenate List A followed by List B. The resulting order is the optimal sequence.

The rule guarantees the minimum makespan for the two‑machine flow shop, assuming:

• No pre‑emptions (once a job starts on a machine, it runs to completion).
• Each machine can process only one job at a time.
• The job order is the same on both machines (permutation schedule).

Step‑by‑Step Example

Consider five jobs with the following processing times (in minutes):

1. Classify Jobs

Easier said than done, but still worth knowing Worth knowing..

2. Sort Each List

List A (ascending (p_{i1})): J3 (3), J2 (4)
List B (descending (p_{i2})): J1 (5), J5 (4), J4 (2)

3. Concatenate

Optimal sequence S = J3 – J2 – J1 – J5 – J4.

4. Verify Makespan (Optional)

Makespan = 30 minutes. Any other permutation yields a makespan ≥ 30, confirming optimality.

Scientific Explanation: Why the Rule Works

2‑Machine Flow Shop as a Directed Graph

Represent each job as a pair of arcs: an arc from start to M1 with length (p_{i1}), then an arc from M1 to M2 with length (p_{i2}). The overall schedule becomes a path traversing these arcs sequentially. The makespan equals the length of the longest path from the start of the first job on M1 to the finish of the last job on M2.

Dominance Property

If a job has a shorter processing time on M1 than on M2 ((p_{i1} \le p_{i2})), placing it as early as possible reduces the chance that M2 becomes a bottleneck later. Conversely, if a job is faster on M2 ((p_{i1} > p_{i2})), positioning it as late as possible prevents it from blocking M1 early on. This “front‑loading/ back‑loading” principle eliminates idle gaps that would otherwise increase the makespan But it adds up..

Proof Sketch

Consider two adjacent jobs i and j in any schedule. On top of that, swapping them changes the makespan only if the order creates a larger idle time on either machine. So by comparing the four possible processing‑time relationships, one can show that the ordering prescribed by Johnson’s rule never worsens—and often improves—the makespan. Repeating this exchange argument across the entire job list yields a globally optimal sequence.

No fluff here — just what actually works.

Practical Implementation Tips

1. Data Collection Accuracy

• Ensure processing times are deterministic or based on reliable averages. Large variability can invalidate the optimality guarantee; consider using reliable scheduling or simulation for stochastic environments.

2. Handling Setup Times

• If setup times depend on the job order (sequence‑dependent setups), Johnson’s rule no longer applies directly. A common workaround is to incorporate average setup times into (p_{i1}) and (p_{i2}) or to use a meta‑heuristic (genetic algorithm, tabu search) after obtaining the Johnson sequence as a starting point.

3. Extending to More Than Two Machines

• For three or more machines, the problem becomes NP‑hard. On the flip side, Johnson’s rule can be adapted by aggregating machines into two “super‑machines” (e.g., combine M1+M2 as a single stage, then M3+M4 as the second). This yields a near‑optimal solution in many practical cases.

4. Software Integration

• Most ERP/MES systems include a Johnson scheduling module. When integrating, map your job data fields to the required input format (Job ID, p₁, p₂). Automate the classification and sorting steps to eliminate manual errors.

5. Periodic Re‑evaluation

• Production environments change—new jobs, altered processing times, machine breakdowns. Re‑run Johnson’s algorithm whenever the job set or processing times change to keep the schedule optimal.

Frequently Asked Questions (FAQ)

Q1: Does Johnson’s rule work if a job can skip one of the machines?
No. The rule assumes every job visits both machines in the same order. If a job bypasses a machine, the problem becomes a mixed‑shop and requires a different approach.

Q2: What if a machine can process more than one job simultaneously (parallel machines)?
Johnson’s rule is designed for single‑capacity machines. Parallelism introduces additional decision variables, turning the problem into a flow shop with parallel machines, which is not covered by the classic rule It's one of those things that adds up..

Q3: Can I use Johnson’s rule when processing times are expressed in different units (e.g., minutes vs. seconds)?
Yes, as long as the units are consistent across both machines. Convert all times to the same unit before applying the algorithm.

Q4: How does Johnson’s rule handle idle time on the first machine?
The rule inherently minimizes idle time on M2, which is usually the bottleneck. Idle time on M1 may still occur, but it never increases the makespan beyond the optimal value.

Q5: Is the sequence produced by Johnson’s rule always unique?
Not necessarily. If two jobs have identical processing times that satisfy the same condition, their relative order can be swapped without affecting the makespan. Any such permutation remains optimal.

Common Mistakes to Avoid

Extending Johnson’s Rule: Hybrid Approaches

While Johnson’s rule is elegant, many modern factories face complexities such as machine breakdowns, varying job priorities, and due‑date constraints. Hybrid methods combine the deterministic backbone of Johnson’s sequencing with flexible heuristics:

1. Priority‑Weighted Johnson – multiply (p_{i1}) and (p_{i2}) by a priority factor before classification, ensuring urgent jobs stay near the front or back as needed.
2. Buffer‑Aware Scheduling – insert limited buffers between machines; adjust the rule to account for buffer capacity, preventing overflow.
3. Iterative Improvement – start with the Johnson sequence, then apply local search (swap adjacent jobs) to reduce makespan under additional constraints.

These extensions preserve the low computational cost of the original method while accommodating real‑world nuances.

Conclusion: Leveraging Johnson’s Rule for Competitive Advantage

In a world where lead time and resource utilization directly impact profitability, mastering Johnson’s rule equips production planners with a fast, mathematically proven tool to minimize makespan on two‑machine flow shops. By systematically classifying jobs, sorting them according to processing‑time dominance, and concatenating the two ordered lists, manufacturers can achieve the optimal job sequence without exhaustive enumeration And it works..

Implement the rule as part of a broader scheduling framework:

• Keep processing‑time data current and accurate.
• Incorporate setup times where possible.
• Re‑run the algorithm whenever the job set changes.
• Combine the base sequence with heuristics for priority, buffers, or stochastic variability.

When applied correctly, Johnson’s rule transforms a potentially chaotic scheduling problem into a predictable, repeatable process, delivering shorter makespans, higher equipment utilization, and ultimately, a stronger competitive edge in the marketplace Not complicated — just consistent..