# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 9 Conclusions and Future Work  
In this paper, a permutation flow shop scheduling problem with minimal and maximal machine idle times and a makespan criterion was considered. A custom prefix sum-like operation called a job shift scan for correcting the completion times of jobs for scheduling problems was proposed. A binary operator that realizes the job shift scan was proposed and its properties, including commutability, were discussed. A work-efficient parallel algorithm for computing the job shift scan for the PRAM model was proposed and its logarithmic running time with regard to the number of jobs was proven. Prefix sums and job shift scans were then used to propose a parallel algorithm for calculating the makespan  
\begin{table}
\begin{tabular}{c c c c c c} \hline \hline \(n\times m\) & \(\text{PRD}_{\text{G}}\) (\%) & \(\text{PRD}_{\text{C}}\) (\%) & \(\text{it}_{\text{P}}\)/\(\text{it}_{\text{G}}\) & \(\text{it}_{\text{P}}\)/\(\text{it}_{\text{C}}\) & \(\text{it}_{\text{P}}\) \\ \hline \(32\times 5\) & \(-0.628\) & \(-9.804\) & \(0.565\) & \(0.002\) & \(11.0\) \\ \(64\times 10\) & \(-2.235\) & \(-11.911\) & \(0.487\) & \(0.006\) & \(32.8\) \\ \(128\times 10\) & \(-0.181\) & \(-7.191\) & \(0.953\) & \(0.015\) & \(82.7\) \\ \(256\times 30\) & \(2.806\) & \(-9.653\) & \(1.793\) & \(0.037\) & \(196.7\) \\ \(512\times 30\) & \(4.129\) & \(-5.071\) & \(3.435\) & \(0.071\) & \(377.9\) \\ \(1024\times 50\) & \(4.248\) & \(-5.320\) & \(4.020\) & \(0.088\) & \(442.2\) \\ \(2048\times 70\) & \(4.845\) & \(-3.061\) & \(8.201\) & \(0.184\) & \(902.1\) \\ \(4096\times 100\) & \(3.744\) & \(-1.289\) & \(18.317\) & \(0.372\) & \(1813.4\) \\ \(8192\times 150\) & \(3.055\) & \(-0.253\) & \(47.147\) & \(0.746\) & \(3630.3\) \\ \(16\),\(384\times 200\) & \(2.021\) & \(0.294\) & \(130.396\) & \(1.638\) & \(7171.8\) \\ \(32\),\(768\times 250\) & \(1.411\) & \(0.425\) & \(312.465\) & \(3.248\) & \(13,748.5\) \\ \(65\),\(536\times 300\) & \(0.853\) & \(0.363\) & \(665.518\) & \(5.980\) & \(24,892.9\) \\ \hline \hline \end{tabular}
\end{table}
Table 4: Averaged PRD and numbers of iteration elapsed for 120 Taillard-based instances using SAP, SAG and SAC variants.  
in the time \(O(m\log n)\). Based on the above, an implementation of the job shift scan and makespan calculation algorithm for the CUDA platform was proposed.  
The results of the computer experiment indicated large GPU-to-GPU speedups of up to 330 and 1030 times for the job shift scan and the makespan calculation, respectively, as well as significant GPU-to-CPU speedups of up to 7 and 14 times. A simulated annealing metaheuristic algorithm for the considered problem was then proposed. Experiments using Taillard-based instances proved that, for sufficiently large problems, the parallel variant of the algorithm performed more iterations in the given time limit and allowed to obtain shorter makespans. With the proposed algorithm, it is possible to solve large-size problem instances in acceptable time or reduce the running time of the algorithm, allowing it to be used as a local-search procedure in other methods.  
For future work, two research directions were considered. The first was to extend the approach to different scheduling problems. The second was to implement the proposed algorithm purely on manycore CPU instead of GPU, for the possibility of further increasing the speedup and avoiding CPU-GPU copying and kernel launch overhead.  
This research received no external funding.  
Not applicable.  
Data Availability StatementData is contained within the article.  
The author declare no conflict of interest.