# Parallel Makespan Calculation for Flow Shop Scheduling Problem with Minimal and Maximal Idle Time
###### Abstract  
In this paper, a flow shop scheduling problem with minimal and maximal machine idle time with the goal of minimizing makespan is considered. The mathematical model of the problem is presented. A generalization of the prefix sum, called the job shift scan, for computing required shifts for overlapping jobs is proposed. A work-efficient algorithm for computing the job shift scan in parallel for the PRAM model with \(n\) processors is proposed and its time complexity of \(O(\log n)\) is proven. Then, an algorithm for computing the makespan in time \(O(m\log n)\) in parallel using the prefix sum and job shift scan is proposed. Computer experiments on GPU were conducted using the CUDA platform. The results indicate multi-thread GPU vs. single-thread GPU speedups of up to 350 and 1000 for job shift scan and makespan calculation algorithms, respectively. Multi-thread GPU vs. single-thread CPU speedups up to 4.5 and 14.7, respectively, were observed as well. The experiments on the Taillard-based problem instances using a simulated annealing solving method and employing the parallel makespan calculation show that the method is able to perform many more iterations in the given time limit and obtain better results than the non-parallel version. flowshop scheduling: discrete optimization; parallel computing; CUDA; prefix sums; minimal idle time; maximal idle time +
Footnote †: journal: Applied Sciences  
15 July 202131 August 202131 August 202131 September 202131 August 202131 August 202131 September 2021  
computing the goal function, which is often the dominant factor in the running time of the solving method [22]. In this paper, a permutation flow shop scheduling problem with makespan criterion and minimal and maximal machine idle time (FSSP-MMI) is considered. A similar, non-permutation variant was previously considered in [23]. FSSP-MMI is a variant of the well-known permutation flow shop scheduling problem (FSSP) [24]. The problem can be used to model some practical processes, e.g., the concreting process (which was described in [23]). Moreover, this problem is also a generalization of several other variants, including: (a) no-idle; (b) minimal idle time; (c) maximal idle time; and (d) classic FSSP. The aim of the paper was to propose a novel parallel computing technique for the faster computation of the goal function for FSSP-MMI and to develop a solving method that is: (1) capable of solving large-size FSSP-MMI problems in reasonable time; and (2) working fast enough for small- and medium-sized FSSP-MMI problems to be applicable as a local-search subroutine in larger algorithms. A parallel algorithm for FSSP-MMI was previously proposed [25], but it required massive numbers of processors, even for small problems. We aimed to rectify this drawback. It should also be noted that while it is intended for FSSP-MMI, the parallel technique will also be applicable for the variants (a)-(d) mentioned above, and with some modifications, for some other variants (e.g., setup times). As such, the main contributions of this paper can be summarized as follows:  
1. A job shift scan operation, based on prefix sums, for correcting overlapping jobs and applicable to a large class of scheduling problems, is proposed and proven;
2. A work-efficient parallel algorithm for determining the job shift scan in logarithmic time with regard to the number of jobs is proposed;
3. A parallel method for the quick calculation of the goal function (makespan) for FSSP-MMI in time \(O(m\log n)\) instead of \(O(mn)\) is proposed;
4. A simulated annealing metaheuristic solving method, with a parallel makespan calculation for FSSP-MMI, is implemented using the CUDA platform;
5. Computer experiments indicate that the proposed solving method is able to obtain better makespans in the same time as its sequential counterpart for large problems. The rest of the paper is structured as follows. Section 2 contains the literature overview. Section 3 describes the considered scheduling problem.