# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 5 Parallel Job Shift Scan
However, such an approach does not work as will be shown with another example. Let us consider the input sequence \(x=(0,2,-4,3)\). According to the formulas above, the value of the last element of the job shift scan would be:  
\[y_{4}=\max\{\max\{\max\{0+2,0\}-4,0\}+3,0\}=3. \tag{29}\]  
Now, it is shown that the up-sweep phase of Algorithm 2 ends with the last element of the sequence holding the total sum. For the job shift scan, this element should hold the value 3 computed above. Let us verify this by performing the phase. First, partial sums of elements \(x_{1}\) and \(x_{2}\) as well as \(x_{3}\) and \(x_{4}\) are computed. The results are \(\max\{0+2,0\}=2\) and \(\max\{-4+3,0\}=0\). Then, those partial sums are used to compute the final result \(\max\{2+0,0\}=2\). However, this does not match the results from (29). The above shows that applying the base formula directly does not work for the parallel algorithm. The reason for this is that the input has been divided into two subsequences (or blocks): \((0,2)\) and \((-4,3)\). The value \(-4\) is placed on the left-most side of the block, informing us how large of a shift the block is able to initially \"absorb\" before the actual shift takes place. However, when computing the block \((-4,3)\) on its own, the resulting value is 0 and the information of how much of a shift the block can initially absorb is lost. Even if one were to delay applying the maximum, the result of \(-4+3\) is still \(-1\), while in reality, the block can \"absorb\" the shift of 4. Since the sum of the previous block \((0,2)\) is 2, the resulting total sum remains incorrect. The above issue can be solved as follows. We start by adding a second temporary sequence \(z\) with the same number of elements as \(x\) and \(y\). Thus, each block of elements (jobs) \(i\) will be described by a pair of values \(y_{i}\) and \(z_{i}\). Value \(y_{i}\) indicates the job shift at the end of block \(i\) (at its right-most job). This value will either be positive (shift of size \(y_{i}\) required) or zero (no shift). On the other hand, \(z_{i}\) will indicate the maximal shift from a preceding (\"left\") block that block \(i\) is able to absorb without forcing an additional shift on the following (\"right\") blocks. As such, the \(z_{i}\) value will either be positive (absorption of a shift up to \(z_{i}\) is possible) or zero (no absorption possible). Values \(y_{i}\) and \(z_{i}\) are computed simultaneously. After both sequences were determined, sequence \(z\) is discarded (it is only required through the calculation to keep track of the current absorption), while sequence \(y\) holds the required job shift scan. Thus, the previous operation in the form of:  
\[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]0  
is replaced with a new operation:  
\[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]1  
The remaining questions are: (1) how to define the binary operator \(\oplus\); and (2) how to define the initial values of sequences \(y\) and \(z\) based on \(x\). Question (2) is answered by the following Lemma. Lemma 1: _Let \(x_{i}\) be an element of input sequence \(x\), i.e., \(x_{i}\) is a block of jobs of size 1. Then, the values \(y_{i}\) and \(z_{i}\) describing that block are given by_  
\[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]2 \[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]3  
Proof: Three cases must be considered: when \(x_{i}\) is positive; equal to zero; and negative. When \(x_{i}>0\), then the job overlaps with the previous one and the length of the overlapped part is \(x_{i}\). In this case, \(x_{i}\) is the required \"local\" shift, so \(y_{i}=x_{i}\). Since the job itself will be shifted to the right, then no additional shift from earlier elements can be absorbed and thus the left-most absorption \(z_{i}=0\). These results match the assumed Equations (32) and (33). When \(x_{i}=0\), then the starting time of the job is exactly the same as the completion time of the previous job. In such a case, no shift is necessary, but any shift from the left will propagate, leaving no possibility of absorption.