# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 7 Solving Method
### SA Variants and CUDA Implementation  
The last missing part of the solving method is the implementation of the subroutine that computes the goal function. In fact, three variants of the SA metaheuristic were developed--two sequential and one parallel:  
1. SAC: in this variant, the entire algorithm is executed on CPU using a single thread;
2. SAG: in this variant, the goal function is computed on GPU using a single thread. The rest of the algorithm is run on CPU using a single thread;
3. SAP: in this variant, the goal function is computed on GPU in parallel using \(n\) threads. The rest of the algorithm is run on CPU using a single thread. The implementation of the goal function computation for SAC is straightforward, directly employing Algorithm 1. Since no accelerator for quickly computing the goal function of the neighbor \(\pi^{\prime}\) is known, the makespan has to be recomputed from scratch in time \(O(nm)\). The rest of the algorithm follows the outline of Algorithm 3. No GPU resources are used and thus no CPU-GPU transfers occur. All memory is allocated on the host and most of it is dynamic allocation. The implementation of the SAG variant is similar. The same sequential Algorithm 1 is used, except the computation is performed by running a CUDA kernel with one thread. Data such as matrices \(p_{i}^{a}\) and \(C_{i}^{a}\) are copied into the GPU memory only once at the start of the algorithm. The data are not copied from the GPU back to the CPU, except for obtaining the value of \(C_{\max}\) (by copying \(C_{n}^{m}\)) and for assigning an improved \(\pi\) to \(\pi^{*}\). The generation of \(\pi^{\prime}\) is performed by swapping two elements in \(\pi\) on GPU (in time \(O(1)\)) with the CPU code providing which elements to swap. If \(\pi^{\prime}\) is not accepted, then the elements are simply swapped back to restore \(\pi\). This variant uses a global GPU memory plus some local variables. As a result, the goal function calculation is done in time \(O(nm)\) as for the SAC variant. The implementation of the SAP variant is the most complex. The makespan \(C_{\max}\) is generally computed by implementing Theorem 2. Specific parts of it (prefix sums, job shift scan, input preparation, corrections) are performed by running CUDA kernels with a number of blocks. A single block runs 256 threads and each thread handles two elements, yielding 512 elements handled per block. Most of the operations required to compute the makespan, such as (42)-(44), can be performed in time \(O(1)\) through simple kernel functions that run a necessary number of blocks. This is because the computation for each element are independent. However, the computation of prefix sums and job shift scans is more complex, as results from one block impact the sum/scan further on in subsequent blocks. To solve this issue, the parallel prefix sum was implemented following the implementation shown by [PERSON] et al. [67]. First, the prefix sum computation for a single block is implemented, following Algorithm 2.The problem instance is first allocated on CPU and then allocated and copied to the GPU global memory. It is important to note that this happens only once at the beginning of the entire SAP solving method. The CUDA kernels that run in time \(O(1)\) use this global memory (plus some local variables). However, kernels used for computing the prefix sum and job shift scan use the GPU shared memory, which is faster. Data are copied from the appropriate parts of the global memory into the shared memory (which is only visible to the given thread block). The kernel then works on that shared memory (plus local variables) and the results are copied into appropriate global memory locations (possibly different from the input location) before the kernel terminates. Furthermore, to increase performance and prevent memory access conflicts from bottlenecking the kernel, memory coalescing is used, avoiding memory bank conflicts. This is performed in a manner presented in [67].