# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 8 Computer Experiment  
In this section, the results of computer experiments to measure the parallel speedup of the proposed solving methods as well as some of its subroutines are described. The problem instances generation, the experiment setting and the measure of quality for comparing different variants of the SA metaheuristic will also be described. Considering the testing environment and software used, all programs were written in C/C++ in Visual Studio 2019 version 16.10.2 and compiled using the Release configuration. All programs were run on a server with the AMD Ryzen Threadripper 3990X CPU (2.9 MHz, 64-cores), 64 GB of RAM and an RTX 2080 Ti GPU (1.35 GHz, 11 GB memory, 4352 CUDA cores) in the Microsoft Windows 10 Pro operating system. In the first experiment, the speedups obtained for several subroutines are shown. At first, for comparison, the results of the implementation of the parallel prefix sum calculation are presented. For each input length \(n\), an array of \(n\) integers of random values were created. The prefix sum calculation was then executed on CPU, the GPU with the single thread and GPU with \(n\) threads, obtaining the running times \(T_{C}\), \(T_{G}\) and \(T_{P}\), respectively. Since the running times were small, the computation was repeated a number of times depending on \(n\) (e.g., 400,000 times for \(n=16\) and 25 times for \(n=262,144\)) and the total running time was measured. After this, the obtained total was divided by the number of repetitions. The measured running times (in milliseconds) and speedups of the parallel version against both sequential versions are shown in Table 2.  
It can be observed that the speedup compared to the sequential GPU was already visible at \(n=32\) elements with the maximal speedup of over 350 at \(n=262,144\). Compared to the CPU, the speedups are much lower both due to the lower GPU core speeds as well as the overhead of the executing CUDA kernels. Nonetheless, speedups against CPU are observed for \(n>32,768\) with a maximal speedup of 4.55. This is similar to the speedup reported by [PERSON] et al. for the same \(n\)[67]. The next experiment concerns the running times and speedups of the job shift scan from Theorem 1 and the goal function calculation from Theorem 2. Similar experiments as with the prefix sums were performed but with a different number of repetitions. For the makespan calculation \(m=10\) was assumed. Such a number of machines allowed to lessen the effect of the constant overhead, while also keeping the computation time reasonable. Reporting the running times of the sequential GPU and CPU versions was omitted, as they can be derived from the speedup. The results are shown in Table 3. \begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(n\) & \(T_{P}\) (ms) & \(T_{G}\) (ms) & \(T_{C}\) (ms) & \(T_{G}\)/\(T_{P}\) & \(T_{C}\)/\(T_{P}\) \\ \hline
16 & 3.188 & 2.797 & 0.006 & 0.8773 & 0.0018 \\
32 & 3.072 & 3.132 & 0.012 & 1.0194 & 0.0038 \\
64 & 3.187 & 4.109 & 0.024 & 1.2893 & 0.0074 \\
128 & 3.326 & 6.179 & 0.053 & 1.8578 & 0.0159 \\
256 & 3.598 & 10.108 & 0.103 & 2.8090 & 0.0285 \\
512 & 3.930 & 18.632 & 0.193 & 4.7412 & 0.0491 \\
1024 & 10.426 & 35.743 & 0.418 & 3.4284 & 0.0401 \\
2048 & 10.287 & 69.497 & 0.791 & 6.7560 & 0.0769 \\
4096 & 10.390 & 136.973 & 1.590 & 13.1836 & 0.1531 \\
8192 & 10.644 & 274.419 & 3.172 & 25.7813 & 0.2980 \\
16,384 & 10.438 & 546.239 & 6.403 & 52.3338 & 0.6135 \\
32,768 & 11.404 & 1090.091 & 12.765 & 95.5884 & 1.1193 \\
65,536 & 11.646 & 2177.404 & 25.574 & 186.9658 & 2.1959 \\
131,072 & 15.742 & 4370.652 & 51.094 & 277.6427 & 3.2457 \\
262,144 & 25.332 & 8901.572 & 115.372 & 351.3963 & 4.5544 \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Running times and speedups for the CPU (C); GPU sequential (G); and GPU parallel (P) prefix sum calculation. The computation times and speedups against the sequential GPU for the job shift scan are comparable to those for the prefix sum from Table 2. Speedups against the CPU are observed for \(n>16\),384 with the top speedup of over 6.8.