# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
## 2 Literature Overview
### Parallel Computing  
A significant number of approaches in the literature have been dedicated to employing parallel computing techniques to help solving scheduling problems. These approaches vary due to different parallel devices (multicore CPUs versus GPGPUs), parallelization levels (fine- versus coarse-grained), solving methods (population-based versus single-trajectory) and dependency on the problem (mathematically proven problem-specific properties versus run-of-the-mill parallelization). Below is an overview of the recent papers dedicated to this topic, meant to present the diversity of approaches and to highlight the results. The calculation of the goal function is often the most costly part of solving methods, constituting over 90% of their running time in many cases, as shown in [45]. Thus, considerable effort went into reducing this time. For example, in the mentioned paper, a CUDA-based algorithm was proposed for FSSP with both makespan and total flowtime criteria. The speedup for the resulting tabu search (TS) method was nearly 90 in some cases. A similar approach of fine-grained parallelization for FSSP, suitable for use with GPGPU devices, was shown in [22]. In another paper [46], a method for reducing the computational complexity of calculating the goal function for FSSP with makespan and total flowtime criterion from \(O(nm)\) to \(O(n+m)\) was proven. Interestingly, MMX/SSE instructions from the CPUs instruction set were used, making this approach very fine-grained. This allowed to obtain considerably speedup, achievable in any modern PC without the need of multicore processors or specialized GPGPU devices. A similar low-level approach was used in [47] to solve bi-criteria FSSP with simulated annealing (SA). Usually, single-trajectory methods such as SA are harder to parallelize. However, on average, SA rejects several random neighbors before accepting one. Thus, it is more efficient to generate several random neighbors in parallel using MMX/SSE instructions. This reduced the running time of the method, allowing it to obtain better multi-criteria solutions (Pareto fronts). In another paper [25], it was shown that it was possible to compute the goal function for non-permutation FSSP with time couplings in time \(O(\log^{2}(nm))\) instead of \(O(nm)\). Unfortunately, the method requires a very large number of processors, even for small problem sizes. Finally, in paper [48], parallel computing was used to solve the cyclic job shop scheduling problem (JSSP) with the goal of minimizing the cycle time. With the use of the Intel Xeon Phi manycore coprocessor, the authors achieved a speedup of up to 35 times that of the sequential algorithm. Aside from goal function calculation, other approaches to parallel computing in scheduling problems exist. For example, in paper [49], a very coarse-grained technique was used to enhance the well-known TSAB algorithm for JSSP. While deterministic, TSAB requires several parameters to be calibrated and those values vary for different problem instances. By running many parallel copies of TSAB with different parameters, significantly better results were obtained compared to a single TSAB run without any changes in the underlying algorithm. In another paper [50], genetic algorithm (GA) and ant colony optimization (ACO) were combined and run in parallel to solve multi-criteria JSSP. The combined GACO algorithm obtained better Pareto fronts than either algorithm could separately. However, the need to synchronize both sub-algorithms and update the Pareto set limited the observed speedup. A different result was obtained in work [21], where parallel computing allowed to obtain superlinear speedup for FSSP with the total flowtime criterion. An interesting example is paper [51], where the main memetic algorithm for the FSP is augmented by a local-search procedure. This procedure is required to finish quickly and is thus executed in parallel on a GPGPU device.