# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 6 Parallel Makespan Calculation
However, this is exactly the same issue which was discussed in Section 5 and Figure 2 that led to the definition of the job shift scan. Thus, this scan can be used to compute the \"true\" required shift and finish the correction as shown below. First, the needed \"local\" jobs shifts are computed in array \(x\) of \(n\) elements as follows:  
\[x_{1} =0, \tag{45}\] \[x_{i} =C_{i-1}^{a}-(C_{i}^{a}-\rho_{i}^{a})-r_{a}\quad i>1. \tag{46}\]  
The first job on the machine has no preceding jobs, hence \(x_{1}=0\). For subsequent jobs, one computes the difference between the completion time of job \(i-1\) (value \(C_{i-1}^{a}\)) and the starting time of job \(i\) (value \(C_{i}^{a}-\rho_{i}^{a}\)). If there is no need for a job shift, then the difference should be equal to the minimal idle time, hence the last term \(r_{a}\). Since each element \(x_{i}\) is computed independently, the entire array can be calculated in time \(O(1)\) on \(n\) processors. Then, the job shift scan is calculated in parallel in time \(O(\log n)\) with input in array \(x_{i}\) as shown by Theorem 1. The additional arrays \(y\) and \(z\) of \(n\) elements are used, as required by this algorithm. As a result, array \(y\) now holds the \"true\" shifts required for each job. The only problem is that the algorithm yields the exclusive job shift scan, while an inclusive one is required. Thus, the result of the job shift scan is applied to correct the completion times \(C_{i}^{a}\), while also applying Formulas (18) and (19) to obtain the inclusive scan:  
\[C_{i}^{a} \gets C_{i}^{a}+y_{i+1},\quad i<n \tag{47}\] \[C_{n}^{a} \gets C_{n}^{a}+y_{L}, \tag{48}\]  
Terms \(y_{i+1}\) and \(y_{L}\) change the exclusive job shift scan into an inclusive one, where \(y_{L}\) is obtained through:  
\[(y_{L},z_{L})=(y_{n},z_{n})\oplus(\max\{x_{n},0\},\max\{-x_{n},0\}). \tag{49}\]  
The corrections (47)-(49) can also be done in time \(O(1)\). The phase \(a\) up to this point can be performed in time \(O(\log n)\). The resulting completion times \(C_{i}^{a}\) satisfy all of the constraints (3)-(5) with one exception: the right side of the constraint (5), which pertains to the maximal idle time \(d_{a}\). In other words, the phases so far give the same result as lines 1-7 from the sequential Algorithm 1. In other words, a parallel equivalent of the remaining lines 8-9 of that algorithm needs to be performed as well. Fortunately, this last issue can be corrected in similar fashion; however, instead of preventing jobs overlapping, excessively large gaps between jobs are prevented. Specifically, one can compute the difference between the starting time of job \(i+1\) and the completion time of job \(i\). If the difference is more than \(d_{a}\), then there is a \"local\" required shift for job \(i\). Otherwise, there is no shift required, but there might be a possibility of absorption. The difference is that, previously, one block was pushed, which could result in the block to its right being pushed as well. This time, a block is being \"pulled\" to the next block (because there was more of a gap between them than is allowed), which might in turn force the block to its left to be \"pulled\" as well. Despite this \"practical\" difference, it is mathematically the same process. Thus, the array \(x_{i}\) is once again prepared in time \(O(1)\) as follows:  
\[x_{n} =0, \tag{50}\] \[x_{n-i+1} =C_{i+1}^{a}-\rho_{i+1}^{a}-C_{i}^{a}-d_{a}\quad i>1. \tag{51}\]  
As one can see, this time the array is prepared a little differently. This is because previously the first job always had a 0 shift and then shifts propagated from left to right. This time, the last job \(n\) has no required shift and \"pulls\" propagate from right to left. Thus, the direction has to be changed. The simplest way to do this is to prepare the input \(x\) from the other end, which allows using the same parallel job shift scan as previously, which will be completed in time \(O(\log n)\).