# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 6 Parallel Makespan Calculation  
In this section, the results of Theorem 1 as well as the parallel prefix sums will be applied to reduce the time required to compute the makespan \(C_{\max}\) for the FSSP-MMI problem, as shown by the following Theorem. **Theorem 2**: _Let \(\pi\) be a solution for the permutation flow shop problem with minimal and maximal idle time. Then, the makespan \(C_{\max}(\pi)\) for \(\pi\) can be determined in time \(O(m\log n)\) on PRAM with \(n\) processors._  
In order to stay consistent with the nomenclature of the paper, \(1,2,\ldots,n\) will be used for indexing, instead of \(0,1,\ldots,n-1\). The actual implementation can use either. It is also assumed that \(p_{i}^{a}\) and \(C_{i}^{a}\) are matrices such that row \(a\) contains processing (or completion) times for machine \(a\). As a reminder, \(C_{i}^{a}\) takes into account the processing order \(\pi\), while \(p_{i}^{a}\) does not. Thus, one must remember to access \(p_{i}^{a}=p_{\pi(i)}^{a}\) instead of \(p_{i}^{a}\). The algorithm is split into \(m\) phases, with phase \(a\) determining all values \(C_{i}^{a}\) on machine \(a\) before moving onto machine \(a+1\). Phase 1 is started by performing an exclusive prefix sum of sequence \((\rho_{1}^{1},\rho_{2}^{1},\ldots,\rho_{n}^{1})\) and using sequence \(C^{1}=(C_{1}^{1},C_{2}^{1},\ldots,C_{n}^{1})\) as output. This can be done in time \(O(\log n)\) with Algorithm 2. After this, \(C_{i}^{1}\) contains the sum of the processing times of all jobs processed on \(a\) before job \(i\). Then, each value \(C_{i}^{1}\) is modified as follows:  
\[C_{i}^{1}\gets C_{i}^{1}+r_{1}(i-1)+\rho_{i}^{1}. \tag{42}\]  
The above can be calculated for each \(i\) independently, so it can be done in time \(O(1)\) with \(n\) processors. The reason it is done this way is that, on the first machine, one does not have to worry about the previous machine or maximal idle time \(d_{1}\). The jobs are \"glued\" together: the first job starts at time \(0\) and the next job starts exactly \(r_{1}\) after the previous job is completed. The starting time of a job is thus the sum of the processing times of all jobs before it (performed by the prefix sum) plus the minimal idle time \(r_{1}\) occurring exactly \(i-1\) times (performed by (42)). However, since a completion time is needed, and not a starting time, \(\rho_{i}^{1}\) is added as well. After this, \(C^{1}\) holds correct completion times for machine \(1\), which was done in time \(O(\log n)\) using \(n\) processors. Let us move onto phases 2 through \(m\). They are more complex compared to phase 1, however, they are identical to each other, so only one of them will be described. Assume it is phase \(a\). The phase is started as essentially identical to phase 1: the exclusive prefix sum of \((\rho_{1}^{a},\rho_{2}^{a},\ldots,\rho_{n}^{a})\) is computed, using \(C^{a}=(C_{1}^{a},C_{2}^{a},\ldots,C_{n}^{a})\) as output and corrected with:  
\[C_{i}^{a}\gets C_{i}^{a}+r_{a}(i-1)+\rho_{i}^{a}. \tag{43}\]  
Essentially being the same as phase 1, the part of phase \(a\) up to this point can be performed in time \(O(\log n)\) using \(n\) processors. The computed values \(C_{i}^{a}\) hold completion times; however, they satisfy only the left side of constraint (5). Those starting times need to be corrected to satisfy the constraint (4). The corrections are started by performing:  
\[C_{i}^{a}\leftarrow\ \max\{C_{i}^{a}-\rho_{i}^{a},C_{i}^{a-1}\}+\rho_{i}^{a}. \tag{44}\]  
This correction is similar to the original line 7 of Algorithm 1. Furthermore, since each value \(C_{i}^{a}\) can be corrected independently, this correction can be performed in time \(O(1)\). However, there is one issue with the correction (44): it is only local. If \(C_{i}^{a}\) is increased by 5, while \(C_{i+1}^{a}\) is not increased at all and the gap between the completion time of \(i\) and starting time of \(i+1\) was less than 5, then the jobs will overlap.