Flow Shop Makespan Calculation

1. From Visual Logic to a Mathematical Formula

The logic we used to build Gantt charts can be captured in a set of equations. This is crucial because a computer algorithm can't "see" a chart; it operates on data and formulas. Let's define our terms:

• Let $n$ be the number of jobs and $m$ be the number of machines.
• Let a job sequence be a permutation $\pi =(\pi (1),\pi (2),\dots ,\pi (n))$, where $\pi (k)$ is the job in the $k$-th position of the sequence.
• Let $p_{j,i}$ be the processing time of job $j$ on machine $i$.
• Let $C_{\pi (k),i}$ be the completion time of the job $\pi (k)$ on machine $i$.

The rule from our last lesson was that an operation starts at $\max (\text{job ready time, machine available time})$.

• The job $\pi (k)$ is ready for machine $i$ when it finishes on machine $i-1$. This time is $C_{\pi (k),i-1}$.
• Machine $i$ is available for job $\pi (k)$ when it finishes the previous job in the sequence, $\pi (k-1)$. This time is $C_{\pi (k-1),i}$.

Therefore, the start time for job $\pi (k)$ on machine $i$ is $\max (C_{\pi (k),i-1},C_{\pi (k-1),i})$. The completion time is this start time plus the processing time. This gives us a powerful recursive formula.

The following research paper provides a concise and formal definition of this calculation. Since your goal is to write a thesis, engaging with this kind of formal academic notation is excellent practice.

The core of the calculation is the formula:
$C_{\pi (k),i}=\max (C_{\pi (k),i-1},C_{\pi (k-1),i})+p_{\pi (k),i}$

This single equation, along with the boundary conditions for the first job and first machine, is all an algorithm needs to determine the makespan for any given sequence.

To reinforce this concept, let's watch a short video that explains this exact logic verbally.

2. A Step-by-Step Worked Example

Now, let's apply this formula to a problem. We will use a tabular method, which is how you would likely implement this in code or a spreadsheet.

Consider the following 4-job, 3-machine problem from the resource "Flow Shop", with the job sequence $\pi =(1,2,3,4)$.

Processing Times ($p_{j,i}$):

We want to calculate the completion time matrix, $C_{j,i}$. We'll build it row by row (job by job) and column by column (machine by machine).

Completion Time Matrix ($C_{j,i}$):

Let's walk through the calculations:

Job 1 (first in sequence):

• $C_{1,1}=p_{1,1}=4$ (Boundary case: no previous job)
• $C_{1,2}=C_{1,1}+p_{1,2}=4+2=6$ (Boundary case: no previous job)
• $C_{1,3}=C_{1,2}+p_{1,3}=6+1=7$ (Boundary case: no previous job)

Job 2 (second in sequence):

• $C_{2,1}=C_{1,1}+p_{2,1}=4+3=7$ (Boundary case: first machine)
• $C_{2,2}=\max (C_{2,1},C_{1,2})+p_{2,2}=\max (7,6)+6=7+6=13$
• $C_{2,3}=\max (C_{2,2},C_{1,3})+p_{2,3}=\max (13,7)+2=13+2=15$

Job 3 (third in sequence):

• $C_{3,1}=C_{2,1}+p_{3,1}=7+7=14$
• $C_{3,2}=\max (C_{3,1},C_{2,2})+p_{3,2}=\max (14,13)+2=14+2=16$
• $C_{3,3}=\max (C_{3,2},C_{2,3})+p_{3,3}=\max (16,15)+3=16+3=19$

Job 4 (last in sequence):

• $C_{4,1}=C_{3,1}+p_{4,1}=14+1=15$
• $C_{4,2}=\max (C_{4,1},C_{3,2})+p_{4,2}=\max (15,16)+5=16+5=21$
• $C_{4,3}=\max (C_{4,2},C_{3,3})+p_{4,3}=\max (21,19)+8=21+8=29$

The makespan, $C_{max}$, is the completion time of the last job on the last machine: $C_{4,3}=29$.

3. Application in Heuristics

The calculation you've just mastered is the core engine for evaluating solutions in almost any makespan-minimization algorithm. For example, when we discuss heuristics like the famous NEH algorithm in a future lesson, you'll see that it works by iteratively building a sequence and calculating the makespan at each step to make its decisions. The video below shows several such calculations for different sequences while demonstrating various heuristics. You don't need to understand the heuristics themselves yet, but notice how frequently the makespan calculation is performed.

Conclusion

In this lesson, we transitioned from a visual understanding of schedules to a formal, mathematical procedure for calculating the makespan. This is a critical step towards building and analyzing sophisticated scheduling algorithms.

Key Takeaways:

• The makespan for any permutation flow shop schedule can be found using the recursive formula: $C_{\pi (k),i}=\max (C_{\pi (k),i-1},C_{\pi (k-1),i})+p_{\pi (k),i}$.
• This calculation can be performed systematically using a tabular approach, which is easily translated into a computer program.
• Calculating the makespan is the fundamental step for evaluating the quality of a schedule and is used extensively by optimization algorithms.

Preview of the Next Lesson:
So far, we have only focused on how to evaluate a given sequence. The real challenge is finding the best sequence. For a small number of machines, there are efficient ways to do this. In our next lesson, we will explore Johnson's algorithm, a classic and elegant method that guarantees the optimal solution for any two-machine flow shop problem ($F2|prmu|C_{max}$). This will be our first step into the world of optimization algorithms for scheduling.