# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 5 Parallel Job Shift Scan
Thus, \(y_{i}=z_{i}=0\), matching the expected values from (32) and (33). Finally, when \(x_{i}<0\), then there is a gap from the previous job of length \(x_{i}\). As a result, the job is not shifted, so \(y_{i}=0\). Furthermore, due to the gap, we can absorb the shift from the left up to the size of the gap, so \(z_{i}=x_{i}\). Once again, this matches the expected Equations (32) and (33). The above Lemma described how to initialize sequences \(y\) and \(z\). Now, the other question is that of how to combine two adjacent blocks, i.e., how to define the operation \(\oplus\) from (31). This was performed by the following Lemma. Lemma 2: _Let \(a=(x_{i},x_{i+1},\ldots,x_{j-i},x_{i})\) and \(b=(x_{j+1},x_{j+2},\ldots,x_{k-1},x_{k})\) where \(k\geq j+1\) and \(j\geq i\) be two blocks of jobs. Let these blocks be described by pairs \((y_{a},z_{a})\) and \((y_{b},z_{b})\), respectively. Then, block \(c=(x_{i},x_{i+1},\ldots,x_{j-i},x_{j},x_{j+1},x_{j+2},\ldots,x_{k-1},x_{k})\) is described by pair \((y_{c},z_{c})\) which is given by_  
\[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]4 \[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]5  
Proof: Let us first notice that blocks \(a\) and \(b\) are continuous, i.e., block \(a\) contains all jobs from the one being processed on the considered machine as \(i\)-th to the one being processed as \(j\)-th and block \(b\) contains all jobs from the \(j+1\)-th to \(k\)-th. Secondly, the blocks are adjacent with block \(a\) appearing earlier, i.e., the next job being processed on the machine after processing all jobs of block \(a\) is the first job of block \(b\). First consider the value \(z_{c}\). This value should be the largest shift coming from the left that the combined block \(c\) can absorb. It is known that the left-most side of \(c\) is also the left-most side of \(a\), so \(c\) will be able to absorb at least as big of a shift as \(a\) would, hence \(z_{c}\geq z_{a}\). If the shift exceeds \(z_{a}\), then \(a\) will absorb the \(z_{a}\) of it and the rest will propagate into block \(b\). Block \(b\) would normally be able to absorb the shift of \(z_{b}\), but one also needs to take into account the shift \(y_{a}\) of block \(a\) that will be propagated into \(b\). Three cases are possible. If \(y_{a}=0\), then \(b\) can absorb \(z_{b}\) and the total possible absorption of \(c\) is simply \(z_{a}+z_{b}\). If \(y_{a}>0\) but \(y_{a}<z_{b}\), then \(b\) will absorb \(y_{a}\) from \(a\) and will still be able to absorb up to \(z_{b}-y_{a}\), which was not absorbed from \(z_{a}\). The total possible absorption will then be \(z_{b}-y_{a}+z_{a}\). Finally, if \(y_{a}\geq z_{b}\), then \(b\) will use all of \(z_{b}\) to absorb the shift from \(a\), meaning that it will not be able to absorb any additional shift from the block preceding \(a\), so the total absorption of \(c\) will just be \(z_{a}\). All three cases match the expected result (35). Now, consider the value \(y_{c}\) in a similar manner. This value should be the total shift that will be propagated into the next block to the \"right\" of \(c\). The right-most part of \(c\) is \(b\) so this shift will be at least as big as \(y_{b}\). Now, one also needs to add the possible shift from block \(a\). Normally, this would be \(y_{a}\), but block \(b\) can itself absorb up to \(z_{b}\). Once again, three subcases are possible. If \(z_{b}=0\), then \(b\) cannot absorb anything and the entire shift \(y_{a}\) propagates to the end of \(b\). As a result, \(y_{c}=y_{a}+y_{b}\). If \(z_{b}>0\) but \(z_{b}<y_{a}\), then \(b\) will absorb the shift of \(z_{b}\) and the remainder of \(y_{a}-z_{b}\) will be propagated and thus \(y_{c}=y_{a}-z_{b}+y_{b}\). Finally, if \(z_{b}\geq y_{a}\), then \(b\) will absorb all of \(y_{a}\) and nothing will propagate into \(b\), leaving \(y_{c}=y_{b}\). All of these cases match the expected result (34).