Optimizing Two-Machine Flow Shops with Johnson's Algorithm

1. The Core Idea: Minimizing Idle Time on Machine 2

Before learning the steps of the algorithm, let's build some intuition. The total time spent on Machine 1 is fixed, regardless of the sequence—it's simply the sum of all processing times on M1. Therefore, to minimize the total makespan, our real goal is to minimize the idle time on Machine 2.

To understand how to do this, let's consider the flow of jobs.

As the reading highlights, we have two competing objectives to minimize idle time on Machine 2:

1. Start Machine 2 as early as possible: The first job in the sequence determines when Machine 2 can start. To get it running quickly, we should choose a job with a very short processing time on Machine 1.
2. Avoid gaps in Machine 2's schedule: Once Machine 2 finishes a job, we want the next job to be ready and waiting for it. A job with a very long processing time on Machine 2 is beneficial to schedule early because it gives Machine 1 a large time window to process subsequent jobs, reducing the chance that Machine 2 will have to wait later on.

These insights seem to conflict. Should we prioritize jobs with short M1 times or long M2 times? Johnson's genius was in finding a rule that elegantly satisfies both principles. The solution is to:

• Place jobs with the shortest M1 times at the beginning of the sequence.
• Place jobs with the shortest M2 times at the end of the sequence.

By scheduling jobs with short M2 times at the end, you are implicitly prioritizing jobs with long M2 times towards the beginning. This simple, powerful idea forms the basis of the algorithm.

2. Johnson's Algorithm: The Procedure

There are two common ways to describe Johnson's algorithm. Both yield the exact same optimal sequence.

Method 1: The Iterative Approach

This method builds the sequence from the outside in. It's very intuitive and easy to apply by hand.

1. List the processing times for all jobs on both machines.
2. Find the shortest processing time among all jobs not yet scheduled.
3. If the shortest time is on Machine 1, place the corresponding job in the first available position in the sequence.
4. If the shortest time is on Machine 2, place the corresponding job in the last available position in the sequence.
5. If there is a tie (e.g., the same shortest time for two different jobs, or for both machines on the same job), you can break the tie arbitrarily. The makespan will be the same.
6. Remove the scheduled job from consideration and repeat from Step 2 until all jobs are scheduled.

Method 2: The Partition-and-Sort Approach

This method is more formal and is often how the algorithm is described in academic texts and implemented in code. It achieves the same result in a non-iterative way.

To summarize the partition-and-sort method:

1. Partition: Create two sets of jobs.
   • Set A: All jobs where processing time on M1 is less than or equal to the time on M2 ($p_{j,1}\le p_{j,2}$).
   • Set B: All jobs where processing time on M1 is greater than the time on M2 ($p_{j,1}>p_{j,2}$).
2. Sort:
   • Sort the jobs in Set A in non-decreasing (ascending) order of their M1 processing times.
   • Sort the jobs in Set B in non-increasing (descending) order of their M2 processing times.
3. Combine: The final optimal sequence is the sorted list of jobs from Set A followed by the sorted list of jobs from Set B.

The computational complexity of this algorithm is dominated by the sorting step, making it very efficient at $O(n\log n)$.

3. A Worked Example

Now let's see the algorithm in action. We'll use the iterative method, as it is visually straightforward.

Let's recap the steps from the video with the initial data:

Processing Times (in hours):

Sequence Construction (6 slots): [__, __, __, __, __, __]

1. Min time: 1 hour (Job 1 on M1). Place Job 1 first.
   • Sequence: [1, __, __, __, __, __]
2. Min time (remaining): 2 hours (Job 4 on M2 and Job 5 on M2). This is a tie. The video breaks it by a secondary rule, but let's choose arbitrarily. Let's pick Job 5. It's on M2, so place it last.
   • Sequence: [1, __, __, __, __, 5]
3. Min time (remaining): 2 hours (Job 4 on M2). Place Job 4 in the last available slot.
   • Sequence: [1, __, __, __, 4, 5]
4. Min time (remaining): 3 hours (Job 2 on M1, Job 6 on M1, Job 3 on M2). Let's pick Job 3. It's on M2, so place it in the last available slot.
   • Sequence: [1, __, __, 3, 4, 5]
5. Min time (remaining): 3 hours (Job 2 on M1 and Job 6 on M1). Let's pick Job 6. It's on M1, so place it in the first available slot.
   • Sequence: [1, 6, __, 3, 4, 5]
6. Final job: Only Job 2 remains. Place it in the last open slot.
   • Final Optimal Sequence: [1, 6, 2, 3, 4, 5]

Note: The video gets a slightly different sequence (1-6-2-3-5-4) because of its specific tie-breaking rule. Both sequences, however, will result in the same optimal makespan. Let's stick with the video's sequence for consistency.

Once the sequence (1, 6, 2, 3, 5, 4) is determined, you would calculate the makespan just as we learned in the previous lesson. The rest of the video (from 05:26 onwards) does exactly this, finding a makespan of 29 hours.

Test your understanding!

Now it's your turn. Use the data from the image below to find the optimal sequence and the corresponding makespan.

Processing Times:

Job	Machine 1	Machine 2
A	5	9
B	11	6
C	9	7
D	7	3
E	4	8
F	3	11

1. Apply Johnson's algorithm (either method) to determine the optimal job sequence.
2. Calculate the makespan for this optimal sequence.

Show answer

1. Finding the Optimal Sequence (Iterative Method):

• Initial Slots: [__, __, __, __, __, __]
• Step 1: The shortest time is 3 (Job D on M2). Place D last: [__, __, __, __, __, D]
• Step 2: The next shortest time is 3 (Job F on M1). Place F first: [F, __, __, __, __, D]
• Step 3: The next shortest time is 4 (Job E on M1). Place E in the first available slot: [F, E, __, __, __, D]
• Step 4: The next shortest time is 5 (Job A on M1). Place A in the first available slot: [F, E, A, __, __, D]
• Step 5: The next shortest time is 6 (Job B on M2). Place B in the last available slot: [F, E, A, __, B, D]
• Step 6: The only remaining job is C. Place it in the open slot: [F, E, A, C, B, D]

The optimal sequence is F-E-A-C-B-D.

2. Calculating the Makespan:

We'll use the tabular method from the previous lesson.

• Sequence: (F, E, A, C, B, D)
• Processing Times (M1): (3, 4, 5, 9, 11, 7)
• Processing Times (M2): (11, 8, 9, 7, 6, 3)

Completion Time Matrix:

Job	C(k,1)	C(k,2)
F	3	14
E	7	22
A	12	31
C	21	38
B	32	44
D	39	47

Calculations:

• Job F: $C_{F,1}=3$; $C_{F,2}=3+11=14$
• Job E: $C_{E,1}=3+4=7$; $C_{E,2}=\max (7,14)+8=14+8=22$
• Job A: $C_{A,1}=7+5=12$; $C_{A,2}=\max (12,22)+9=22+9=31$
• Job C: $C_{C,1}=12+9=21$; $C_{C,2}=\max (21,31)+7=31+7=38$
• Job B: $C_{B,1}=21+11=32$; $C_{B,2}=\max (32,38)+6=38+6=44$
• Job D: $C_{D,1}=32+7=39$; $C_{D,2}=\max (39,44)+3=44+3=47$

The optimal makespan is 47.

Conclusion

Today you've learned a foundational algorithm in scheduling theory. While it applies to a specific case (two machines), its elegance and optimality are a benchmark against which more complex problems and heuristic solutions are often compared.

Key Takeaways:

• Johnson's algorithm provides an optimal sequence to minimize makespan for the two-machine flow shop problem (F2||prmu|C_max).
• The core principle is to minimize idle time on the second machine by scheduling jobs with short M1 times early and jobs with short M2 times late.
• The algorithm can be applied iteratively or through a partition-and-sort method, both yielding the same result efficiently in $O(n\log n)$ time.

Preview of the Next Lesson:
We have seen how to apply Johnson's algorithm and developed an intuition for why it works. In the next lesson, we will formalize this intuition by diving into the proof of optimality for Johnson's algorithm. This will involve using an "exchange argument," a common proof technique in optimization that is essential for a rigorous understanding of scheduling algorithms—a key skill for your thesis work.