# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 8 Computer Experiment
The results for the makespan calculation, however, are more surprising. Even though this procedure relies on the prefix sum and jobs shift scan, the observed speedups are vastly different. The speedup against GPU is lower at first (observable from approximately \(n=140\)), but becomes much higher, with over 1000 for \(n=262\),144. Similarly, against CPU, the speedup is obtained from approximately \(n=9000\) and the highest speedup observed is over 14.7. However, one possible explanation for this result is that most of the CUDA kernels launched during the makespan computation work in time \(O(1)\) instead of \(O(\log n)\)--further increasing the perceived speedup. The speedups obtained for the prefix sum, job shift scan and makespan calculations against the GPU and CPU are shown in Figures 3 and 4. Then, research was conducted to compare the SAC, SAG and SAP variants of the SA metaheuristic. As for problem instances, 12 instances groups were prepared with \(n\times m\) sizes from \(32\times 5\) to 65,536 \(\times\) 300. The reason for choosing such an instance size was both to consider large-scale problems (for cloud scheduling and Big Data applications), as well as to research the limitations of the speedup achievable with this method. For each instance group, 10 instances were prepared (as in the original [PERSON] scheme), yielding 120 instances in total. Each instance was generated using the pseudo-random number generator used by [PERSON] (2018), which is often used, with slight modification, by researchers, in order to stay consistent with [PERSON]'s original instances. The generation procedure is shown in Algorithm 4. The same 120 seed values as in [PERSON]'s were used. ```
Data:\(s\), \(n\), \(m\)
1\(g\leftarrow\) TaillardGenerator(\(s\));
2 for\(i=1,2,\ldots,m\)do
3 for\(j=1,2,\ldots,n\)do
4\(p_{j}^{i}\leftarrow\)g.nextInt(\(I\), 99);
5\(v_{1}=\leftarrow\)g.nextInt(\(0\), 9);
6\(v_{2}=\leftarrow\)g.nextInt(\(0\), 9);
7 if\(v_{1}<v_{2}\)then
8\(r_{i}\gets v_{1}\);
9\(d_{i}\gets v_{2}\);
10
11 else
12\(r_{i}\gets v_{2}\);
13\(d_{i}\gets v_{1}\);
```  
**Algorithm 4**Instance generation procedure  
All three SA variants have a time limit as their stopping conditions, thus, the comparison will be based on the quality of solutions (makespan values) the variants are able to provide in that time limit. In order to compare instances of vastly different sizes, the per  
Figure 4: Measured GPU vs. CPU speedups as a function of the number of jobs for the prefix sum, job shift scan and makespan. Black dashed line indicates a speedup of 1.0.  
centage relative deviation (PRD) was chosen as the quality measure. Assuming that \(\pi\) is a solution provided by the given algorithm for the given instance, then PRD is defined as  
\[100\%\frac{C_{\max}(\pi_{\text{ref}})-C_{\max}(\pi)}{C_{\max}(\pi_{\text{ref}})}, \tag{57}\]  
where \(\pi_{\text{ref}}\) is a reference solution. Ideally, this would be the optimal solution, but it can be also a best-known or arbitrary solution. In this research, the parallel variant (SAP) will be compared with the sequential variants (SAG and SAC), therefore:  
\[\text{PRD}_{\text{G}}=100\%\frac{C_{\max}(\pi_{\text{G}})-C_{\max}(\pi_{\text{ P}})}{C_{\max}(\pi_{\text{G}})}, \tag{58}\]  
\[\text{PRD}_{\text{C}}=100\%\frac{C_{\max}(\pi_{\text{C}})-C_{\max}(\pi_{\text{ P}})}{C_{\max}(\pi_{\text{C}})}, \tag{59}\]  
where \(\pi_{\text{P}}\), \(\pi_{\text{G}}\), \(\pi_{\text{C}}\) are the solutions found by the SAP, SAG and SAC variants, respectively. Furthermore, it, \(\text{it}_{\text{P}}\) and \(\text{it}_{\text{C}}\) denote the number of iterations performed by the SAP, SAG and SAC variants, respectively. Since SA is a probabilistic method, every instance was executed 10 times and the results are shown in Table 4. Each value is an average out of 100 runs (10 instances, 10 repeats for instance). As expected, the SAP variant is able to perform more iterations in the given time limit starting at approximately \(n=140\). At \(n=65\),536, the SAP is able to complete 665 times more iterations than SAG.