Gantt Charts for Flow Shop Scheduling

1. What is a Gantt Chart?

A Gantt chart is the most common and intuitive tool for visualizing a schedule. In the context of shop scheduling, it plots machine activity against a timeline. Given your background in industrial engineering, you have likely encountered Gantt charts in project management; their application here is very similar.

A schedule's Gantt chart typically has:

• A horizontal axis representing elapsed time.
• A vertical axis listing the machines in the shop.
• Bars or blocks on the chart, where each bar represents a specific operation (job $j$ on machine $i$) and its length corresponds to the processing time.

The following document provides a concise introduction.

As the reading states, a Gantt chart isn't an optimization tool itself, but a way to display and evaluate the results of a scheduling decision. By looking at a Gantt chart, we can immediately see the flow of jobs, periods where machines are idle, and when the very last operation finishes, which defines the makespan.

Below is a typical Gantt chart for a permutation flow shop problem with 5 jobs and 4 machines.

2. How to Construct a Gantt Chart

Now, let's move to the main task: how do we get from a problem definition (jobs, machines, processing times) and a given sequence to the chart itself? The process follows a set of logical rules derived directly from the PFSP assumptions we learned in the last lesson.

The key is to determine the start time for each operation. An operation $O_{ij}$ (job $i$ on machine $j$) can only begin when two conditions are met:

1. Job Readiness: The job itself must be ready. This means it must have completed its processing on the previous machine, $j-1$.
2. Machine Availability: The machine must be free. This means it must have finished processing the previous job in the sequence.

Therefore, the start time of an operation is the maximum of these two events.

The following video provides an excellent walkthrough of this logic. It verbally describes the step-by-step placement of each job's operations on a Gantt chart.

Let's solidify this with our own small example.
Consider a 3-job, 2-machine problem with the following processing times ($p_{ij}$):

Let's construct the Gantt chart for the sequence J1-J2-J3.

Step 1: Schedule Job 1 (first in sequence)

• J1 on M1: Starts at $t=0$. Finishes at $t=4$.
• J1 on M2: Ready at $t=4$. M2 is free. Starts at $t=4$. Finishes at $t=4+5=9$.

Step 2: Schedule Job 2 (second in sequence)

• J2 on M1: Can start when M1 is free. M1 finishes J1 at $t=4$. Starts at $t=4$. Finishes at $t=4+2=6$.
• J2 on M2: Ready at $t=6$ (finished on M1). M2 is free at $t=9$ (finished J1). The start time is $\max (6,9)=9$. Starts at $t=9$. Finishes at $t=9+3=12$. Notice the 3 units of idle time for J2 between M1 and M2, waiting for M2 to become free.

Step 3: Schedule Job 3 (third in sequence)

• J3 on M1: Can start when M1 is free. M1 finishes J2 at $t=6$. Starts at $t=6$. Finishes at $t=6+6=12$.
• J3 on M2: Ready at $t=12$ (finished on M1). M2 is free at $t=12$ (finished J2). The start time is $\max (12,12)=12$. Starts at $t=12$. Finishes at $t=12+2=14$.

The makespan is the completion time of the last operation (J3 on M2), which is 14.

3. Comparing Schedules with Gantt Charts

The primary goal of solving a PFSP is to find the sequence with the best makespan. Gantt charts are the perfect tool for comparing different candidate sequences. By drawing the chart for each, you can visually confirm which one finishes earliest.

The following resource provides several examples of Gantt charts for the same problem but with different sequences, clearly showing how the makespan changes.

As you can see from the figures, the sequence has a profound impact.

• The sequence in Figure 2.4 results in a makespan of 78. You can see significant gaps (idle time) on the later machines.
• The sequence in Figure 2.5, however, creates a much more compact schedule, with less idle time and a makespan of only 56.

This visual feedback is invaluable. It helps build intuition about what makes a "good" schedule—typically, one that avoids starving later machines for work and minimizes overall idle time.

Conclusion

In this lesson, we have translated the abstract definition of a permutation flow shop schedule into a tangible, graphical representation. This is a foundational skill for the rest of the course and for your future research.

Key Takeaways:

• Gantt charts are the standard method for visualizing schedules, showing machine activity over time.
• The construction of a Gantt chart for a PFSP is governed by a simple but powerful rule: an operation can only start when both the job is ready (finished on the previous machine) and the machine is available (finished the previous job).
• Gantt charts allow for the direct identification of the makespan, as well as other important features like machine idle time and job waiting time.
• By comparing Gantt charts for different sequences, we can visually and quantitatively assess which schedule is better.

Preview of the Next Lesson:
While drawing a Gantt chart is excellent for understanding, it can be slow and cumbersome. For an algorithm to evaluate thousands of sequences, it needs a faster method. In the next lesson, we will formalize the construction logic you learned today into a set of recursive equations. This will allow us to calculate the makespan for any given sequence purely mathematically, without needing to draw a chart every time.