# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 5 Parallel Job Shift Scan  
The concept of prefix sums is based on the addition operator \(+\). However, it was shown before (e.g., by [PERSON] [57]) that the idea can be generalized for a larger class of associative binary operations, for example, the multiplication or maximum. Such a prefix sum generalization is usually called a \"scan\". One such scan operation that pertains to scheduling problems will be proposed in this section. As an example, a schedule for some machine \(a\) in the FSSP with \(n=8\) jobs will be considered. Assume the starting and completion times for jobs on that machine have been set as follows:  
\[S^{a} = (0,1,5,13,14,16,25,28), \tag{22}\] \[C^{a} = (4,6,7,16,19,22,29,31). \tag{23}\]  
Furthermore, assume that the starting times cannot be decreased because they are constrained by completion times on the previous machine, e.g., \(S^{a}_{5}=14\) cannot be decreased, because \(C^{a-1}_{5}=14\). Furthermore, assume that the starting and completion times satisfy constraint (3). However, even under those assumptions, the considered schedule is not feasible. This can clearly be seen in Figure 2. Several jobs are overlapping each other (note that this is still a single machine: vertical differences are for easier visualization only). Indeed, for each pair of adjacent jobs, one can compute \(C^{a}_{i}-S^{a}_{i+1}\), as indicated in the figure by the dimension lines. If the resulting distance is positive, then the jobs \(i\) and \(i+1\) overlap and the job \(i+1\) should be shifted to start later. However, such a shift is not always enough. Consider the second and third jobs from Figure 2 with processing times 5 and 2, respectively. Their required shifts are 3 and 1, respectively. Shifting the third job by 1 would be enough if the second job was not shifted as well. As such, the third job needs to be shifted by 4, which is the sum of shifts values 3 and 1. The required \"true\" shift at job \(i\) is thus related to the sum of shifts up to that job. There is, however, an exception. Consider the fourth job. Its \"local\" shift is \(-6\), while the sum of previous shifts before it is 4. A regular sum of the two would yield \(-2\) and shift the fourth job earlier. However, the assumption was that jobs cannot decrease their starting times. Thus, the fourth job will not be shifted at all and the sum of \(-2\) is changed to 0  
Figure 2: Exemplary schedule on a machine with some overlapping jobs. The required “local” job starting times shifts are shown. instead. As a result, the sequence \(y\) of the \"true\" required shifts for all jobs on machine \(a\) is an inclusive scan function given by a recursive formula:  
\[y_{1} =x_{1}, \tag{24}\] \[y_{i} =\max\{y_{i-1}+x_{i},0\}\quad i>1, \tag{25}\]  
where \(x_{i}\) is the \"local\" shift of job \(i\). It should be noted that value \(x_{1}\) (and consequently \(y_{1}\)) is zero when the entire input is considered. This is because the first job processed on the machine has no preceding job and thus will never have to be shifted in this situation. This type of scan function will be called an \"inclusive job shift scan\". The exclusive variant can be defined similarly as in the case of a regular prefix sum. For the example schedule from Equations (22) and (23), the resulting \"true\" job shifts are thus:  
\[y=(0,3,4,0,2,5,2,3). \tag{26}\]  
After applying these shifts, the corrected feasible schedule on the machine \(a\) is obtained:  
\[S^{a} =(0,4,9,13,16,21,27,31), \tag{27}\] \[C^{a} =(4,9,11,16,21,27,31,34). \tag{28}\]  
In this schedule, no jobs overlap with each other and no job was shifted earlier. Before moving on to the next section, let us discuss the computational complexity of calculating the job shift scan. For the sequential algorithm, one directly applies Formulas (24) and (25), resulting in a running time of \(O(n)\) for \(n\) jobs. As for a parallel algorithm, the first idea was to use Algorithm 2 and adjust it to the job shift scan by replacing the standard summation of \(c=a+b\) with \(c=\max\{a+b,0\}\) as per Formulas (24) and (25).