An effective two-stage heuristic for scheduling the distributed assembly flowshops with sequence dependent setup times

This paper studies the Distributed Assembly Permutation Flowshop Scheduling Problem with Sequence Dependent Setup Times (DAPFSP-SDST). The optimization objective is minimization of maximal completion time (makespan), and it is shown that minimizing the sum of Total Setup Times for Assembling Products (TSTAP) and Total Idle Times on Assembly Machine (TITAM) is equivalent to minimizing the makespan. Additionally, minimization of TSTAP and TITAM can be transformed into sequencing problems of products and jobs within critical products, respectively. We also find out that a product sequence essentially explores an area in the solution space, with solutions in the area having the same TSTAP but different TITAMs determined by Critical-JobsSequences (CJSs). Based on the new findings, an effective Two-Stage Heuristic Algorithm (TSHA) is proposed to first obtain promising product sequences and then exploit the corresponding areas for the DAPFSP-SDST. At the first stage of TSHA, high-quality initial product sequences are obtained through a constructive method and two Neighborhood Descent for Product Sequence (NDPS) algorithms are presented for more potential searching areas. At the second stage, a Neighborhood Descent for CJS (NDCJS) is designed to find CJSs with TITAM as small as possible. Evaluations on a benchmark instance set show that TSHA achieves better performance compared to the existing meta-heuristic and hyper-heuristic algorithms on the DAPFSP-SDST. Another impressive advantage of the TSHA is its low computational cost, as it is a heuristic algorithm with some neighborhood search operators.