Optimality of Johnson's Algorithm for F2||Cmax

Hello! Welcome back. In our last lesson, you learned how to apply Johnson's algorithm to efficiently find an optimal schedule for the two-machine flow shop problem. We built an intuition for why it works by focusing on minimizing idle time on the second machine.

For your thesis work, having a rigorous, formal understanding of why foundational algorithms are optimal is crucial. This lesson moves from application to justification, addressing the learning outcome: Prove the optimality of Johnson's algorithm for the F2||Cmax problem.

We will use a classic technique called proof by contradiction combined with an exchange argument. The logic is as follows:

Assume there is an optimal schedule that does not conform to Johnson's rule.
Show that this schedule must contain at least one pair of adjacent jobs that violates the rule.
Demonstrate that swapping this "violating" pair to conform with the rule results in a new schedule that is at least as good (i.e., the makespan does not increase).
By repeating this process, we can transform any optimal schedule into one that follows Johnson's rule without worsening the makespan. This leads to a contradiction, proving that a schedule produced by Johnson's algorithm must be optimal.

Let's begin by formalizing the structure of the proof.

1. Setting Up the Proof by Contradiction

Recall from the previous lesson the "partition-and-sort" description of Johnson's algorithm. We partition all jobs $J$ into two sets:

Set A: All jobs $j \in J$ where $p_{j 1} \leq p_{j 2}$ .
Set B: All jobs $j \in J$ where $p_{j 1} > p_{j 2}$ .

Johnson's rule states that the optimal sequence is formed by scheduling all jobs from Set A first, followed by all jobs from Set B.

Within Set A, jobs are sorted in non-decreasing (ascending) order of their processing time on Machine 1 ( $p_{j 1}$ ).
Within Set B, jobs are sorted in non-increasing (descending) order of their processing time on Machine 2 ( $p_{j 2}$ ).

Therefore, an assumed optimal schedule S would violate Johnson's rule if it contains a pair of adjacent jobs, j followed by k, where at least one of these conditions is true:

Inter-set violation: $j \in B$ and $k \in A$ .
Intra-set violation (Set A): $j, k \in A$ but $p_{j 1} > p_{k 1}$ .
Intra-set violation (Set B): $j, k \in B$ but $p_{j 2} < p_{k 2}$ .

Our goal is to show that in each of these three cases, swapping j and k does not increase the makespan.

2. The Exchange Argument

The core of the proof lies in analyzing what happens when we swap two adjacent jobs. Consider a schedule ...l, j, k, m.... If we swap j and k, we get a new schedule ...l, k, j, m....

The completion times of all jobs up to and including l are unchanged.
The total processing time on Machine 1 for the pair (j, k) is $p_{j 1} + p_{k 1}$ , which is the same as for the pair (k, j). This means the start time of job m on Machine 1 is unaffected by the swap.
Consequently, the only factor that can change the overall makespan is the completion time of the pair on Machine 2.

Let's denote the completion time of job l (the job before our pair) on Machine 1 as $C_{l, 1}$ and on Machine 2 as $C_{l, 2}$ .

For the original sequence ...l, j, k..., the completion time of job k on Machine 2 is:
$C_{k, 2} = max (max (C_{l, 2}, C_{l, 1} + p_{j 1}) + p_{j 2}, C_{l, 1} + p_{j 1} + p_{k 1}) + p_{k 2}$
For the new sequence ...l, k, j..., the completion time of job j on Machine 2 is:
$C_{j, 2}^{'} = max (max (C_{l, 2}, C_{l, 1} + p_{k 1}) + p_{k 2}, C_{l, 1} + p_{k 1} + p_{j 1}) + p_{j 2}$

To prove our point, we need to show that $C_{j, 2}^{'} \leq C_{k, 2}$ for each of the three violating cases. While the formulas above are precise, they are cumbersome. A more intuitive approach focuses on the idle time created between the two jobs. The time that Machine 2 must wait after finishing job j until it can start job k is $max (0, C_{k, 1} - C_{j, 2})$ . Minimizing this idle time across the schedule is the key.

Let's examine the proof's structure in a more formal context.

Johnson's rule

To formalize our understanding, let's study a structured explanation of the proof. The following text breaks it down into logical steps using the exchange argument we've just discussed.

Please read the section 'Proof of Optimality'. This section formalizes our three cases into two key lemmas. Focus on understanding the logic of why swapping an incorrectly ordered pair of jobs leads to an equal or better schedule.

3. Deconstructing the Proof

As the reading shows, the proof rests on showing that any schedule violating Johnson's rule can be improved (or at least not worsened) by a local swap. Let's walk through each case.

Case 1: Inter-set Violation ( $j \in B, k \in A$ )

Suppose our schedule has job j from Set B immediately followed by job k from Set A.

This means $p_{j 1} > p_{j 2}$ (from Set B) and $p_{k 1} \leq p_{k 2}$ (from Set A).

The question is: is the sequence (j, k) better than (k, j)? Let's compare the total idle time on Machine 2 during the execution of this pair.

Let's assume for simplicity the pair starts at time 0 on M1. The makespan of the pair is determined by the completion time of the second job on M2.

For sequence (j, k): Completion time is $max (p_{j 1} + p_{j 2}, p_{j 1} + p_{k 1}) + p_{k 2}$ .
For sequence (k, j): Completion time is $max (p_{k 1} + p_{k 2}, p_{k 1} + p_{j 1}) + p_{j 2}$ .

Let's compare them. We want to show that swapping to (k, j) is better, i.e.,
$max (p_{k 1} + p_{k 2}, p_{k 1} + p_{j 1}) + p_{j 2} \leq max (p_{j 1} + p_{j 2}, p_{j 1} + p_{k 1}) + p_{k 2}$ .

This expression is not immediately obvious. A simpler way is to compare $max (p_{j 1}, p_{k 2})$ with $max (p_{k 1}, p_{j 2})$ . It can be shown that swapping is advantageous if $min (p_{j 1}, p_{k 2}) < min (p_{k 1}, p_{j 2})$ .
Since $j \in B$ and $k \in A$ , we have $p_{j 1} > p_{j 2}$ and $p_{k 1} \leq p_{k 2}$ .

$min (p_{j 1}, p_{k 2})$
$min (p_{k 1}, p_{j 2})$

Since $p_{j 2} < p_{j 1}$ and $p_{k 1} \leq p_{k 2}$ , it is plausible that $min (p_{k 1}, p_{j 2})$ is smaller. The formal proof in the resource LINK demonstrates this inequality holds, confirming that having a Set B job before a Set A job is suboptimal.

Conclusion for Case 1: An optimal schedule must schedule all jobs from Set A before all jobs from Set B.

Case 2: Intra-set Violation in Set A ( $j, k \in A$ , $p_{j 1} > p_{k 1}$ )

Here, both jobs belong to Set A, so $p_{j 1} \leq p_{j 2}$ and $p_{k 1} \leq p_{k 2}$ . However, they are in the "wrong" order according to Johnson's rule, because the job with the larger M1 time (j) comes first.

We need to show that swapping to the (k, j) sequence is better. We compare the makespans of the pairs again. Using the same logic as Case 1, it can be proven that the makespan does not increase. Intuitively, placing the job with the shorter M1 time first (k) allows M2 to start sooner on the pair, and since both jobs have relatively long M2 times (being in Set A), it's more critical to get M1 free for the next job in the overall sequence.

Conclusion for Case 2: Within Set A, jobs must be sorted in non-decreasing order of $p_{j 1}$ .

Case 3: Intra-set Violation in Set B ( $j, k \in B$ , $p_{j 2} < p_{k 2}$ )

Here, both jobs belong to Set B, so $p_{j 1} > p_{j 2}$ and $p_{k 1} > p_{k 2}$ . They are in the wrong order because the job with the smaller M2 time (j) comes first.

This case can be proven using a clever trick: the reversibility property. An F2|prmu|Cmax problem is symmetrical. If you reverse the schedule (run jobs in reverse order) and swap the machines (M1 becomes M2, M2 becomes M1), the makespan is identical.

If we apply this to our (j, k) pair in Set B:

Original problem: $j, k \in B$ , with $p_{j 2} < p_{k 2}$ .
Reversed problem: The sequence is (k, j). Machine 1 times are now $p_{k 2}, p_{j 2}$ and Machine 2 times are now $p_{k 1}, p_{j 1}$ .
In this reversed problem, the "new" Machine 1 times are $p_{k 1}^{'} = p_{k 2}$ and $p_{j 1}^{'} = p_{j 2}$ . Since $p_{j 2} < p_{k 2}$ , we have $p_{j 1}^{'} < p_{k 1}^{'}$ .
The "new" Machine 2 times are $p_{k 2}^{'} = p_{k 1}$ and $p_{j 2}^{'} = p_{j 1}$ .
Since $j, k \in B$ , we know $p_{j 1} > p_{j 2}$ and $p_{k 1} > p_{k 2}$ . This means in the reversed problem, these jobs would belong to Set A ( $p_{1}^{'} < p_{2}^{'}$ ).
The sequence (k, j) with $p_{j 1}^{'} < p_{k 1}^{'}$ violates the sorting rule for Set A (Case 2). We already proved that for Set A, the job with the smaller M1 time should come first. In the reversed problem, job j has the smaller M1 time ( $p_{j 1}^{'}$ ), so j should come before k.
Therefore, the optimal order in the reversed problem is (j, k). Reversing this back gives the optimal order (k, j) for the original problem.

Conclusion for Case 3: Within Set B, jobs must be sorted in non-increasing order of $p_{j 2}$ .

Test your understanding!

Imagine you have two jobs, Job X and Job Y, both belonging to Set B.

Job X: $p_{X 1} = 10, p_{X 2} = 4$
Job Y: $p_{Y 1} = 8, p_{Y 2} = 7$

According to Johnson's rule, what is the correct order for this pair? Use the logic from Case 3 to justify your answer without fully calculating the makespan for both sequences.

Show answer

According to Johnson's rule for Set B, jobs should be sorted in descending order of their M2 processing times.

Job Y has $p_{Y 2} = 7$ .
Job X has $p_{X 2} = 4$ .

Since $7 > 4$ , the correct order is Y followed by X.

Justification using the exchange argument:
The sequence (X, Y) violates the rule because $p_{X 2} < p_{Y 2}$ . This is an instance of Case 3. Based on our proof, swapping this pair to (Y, X) should result in a makespan that is less than or equal to the original. Therefore, (Y, X) is the optimal sequence for this pair.

Conclusion

In this lesson, we have rigorously established the optimality of Johnson's algorithm. This is a significant step in building the theoretical foundation required for your research.

Key Takeaways:

The optimality of Johnson's algorithm is proven by contradiction using an exchange argument.
Any schedule that is not a Johnson's schedule can be shown to contain an adjacent pair of jobs that violates one of three conditions (inter-set order, intra-set order for A, or intra-set order for B).
Swapping any such violating pair is guaranteed to not increase the makespan, thus systematically transforming any schedule into a Johnson's schedule without performance degradation.
This confirms that the structure defined by Johnson's rule—Set A (sorted by $p_{j 1}$ ascending) followed by Set B (sorted by $p_{j 2}$ descending)—is indeed optimal for the $F 2∣∣ Cmax$ problem.

Preview of the Next Lesson:
We've now fully analyzed the two-machine flow shop problem, for which an efficient, optimal algorithm exists. This makes it a "polynomial-time" solvable problem. What happens when we add just one more machine? In the next lesson, we will begin our exploration of more complex, computationally hard problems by examining why the three-machine flow shop problem ( $F 3∣∣ Cmax$ ) is NP-hard, a crucial concept that motivates the need for heuristics and metaheuristics.

Recommended resources