# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 5 Parallel Job Shift Scan
With Lemma 2, the binary relation:  
\[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]6  
was defined through:  
\[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]7 \[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]8  
Before proceeding, two more properties of the binary operation \(\oplus\), which will be required for the next step, will be proven as short corollaries below. Corollary 1: _The binary operation \((y_{a},z_{a})\oplus(y_{b},z_{b})\) is not commutative._  
Proof: To prove this property, it is sufficient to show a single example for which:  
\[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]9  
Let us consider:  
Figure 2.0  
After applying the formulas from Lemma 2 one obtains \((y_{c},z_{c})=(0,0)\). Now, if the operands are swapped then the result is:  
Figure 2.1  
Corollary 2: _The neutral element of the binary relation \((y_{a},z_{a})\oplus(y_{b},z_{b})\) is \((0,0)\)._  
Proof: This is trivially proven by assuming \(y_{a}=0\) and \(z_{a}=0\) in formulas from Lemma 2 and showing that, as a result, \(y_{c}=y_{b}\) and \(z_{c}=z_{b}\). Since \(\oplus\) is not commutative, it is also done in reverse by assuming \(y_{b}=0\) and \(z_{b}=0\) and showing that \(y_{c}=y_{a}\) and \(z_{c}=z_{a}\). In both cases, the results match the expectation. With Lemmas 1 and 2 as well as Corollaries 1 and 2, it is now possible to propose the parallel algorithm for the job shift scan. **Theorem 1**: _The job shift scan given by the recursive Formulas (24) and (25) for the input sequence \(x=(x_{1},x_{2},\ldots,x_{n})\) of \(n\) elements can be determined in time \(O(\log n)\) on a PRAM machine with \(n\) processors._  
The algorithm is based on Algorithm 2, but with several changes applied. Before the start of the up-sweep phase, an additional array \(z\) with \(n\) elements is created. Since the algorithm works in-place, the array \(x\) will serve as array \(y\). Arrays \(x\) and \(z\) are initialized as per Equations (32) and (33) from Lemma 1. It should be noted that (33) is performed first, as (32) overwrites \(x_{i}\). Since each pair \((x_{i},z_{i})\) can be computed separately, this \(x\) and \(z\) initialization phase can be done in time \(O(1)\) using \(n\) processors. Then, the up-sweep phase of Algorithm 2 is conducted, which is performed the same way as for a regular prefix sum, with one exception: the \(+\) operator in line 3 is replaced with the \(\oplus\) operator from Lemma 2. Because of this, line 3 will turn into two separate assignments. Furthermore, the value \(x[p2^{s}]\) is updated first and then \(z[p2^{s}]\). This is because the new value of \(x[p2^{s}]\) requires the old value of \(z[p2^{s}]\). This way, one avoids using temporary variables. While calculating (37) and (38) takes more time than a simple addition and assignment, it can still be achieved in time \(O(1)\). Thus, the up-sweep phase can be performed in time \(O(\log n)\) using \(n\) processors, just as in the case of the regular prefix sum. Before proceeding to the down-sweep phase, the last element has to be zeroed (red arrow in Figure 2.2 This is done by writing \(0\) to both \(x[n]\) and \(z[n]\) (as per Corollary 2). Then, the down-sweep phase starts. The copying of elements (blue arrows) is simply performed by doing both \(y_{i}\gets y_{j}\) and \(z_{i}\gets z_{j}\) for appropriate \(i\) and \(j\) values. Finally, the \(+\) operations (black arrows) once again need to be replaced with the new \(\oplus\) operations. However, there is one difference compared with the up-sweep phase. Let us go back to Figure 1 and see how \(\Sigma(x_{1}\ldots x_{6})\) is computed during the down-sweep phase (\(s=2\)). This is done by summing \(\Sigma(x_{5}\ldots x_{6})\) with \(\Sigma(x_{1}\ldots x_{4})\). However, \(\Sigma(x_{1}\ldots x_{4})\), which represents earlier jobs, is on the right, while \(\Sigma(x_{5}\ldots x_{6})\), representing later jobs, is on the left. This property is true for the entirety of the down-sweep phase. For the regular prefix sum, it had no consequence as the \(+\) operator is commutative.