The cascaded flowshop joint scheduling problem: A mathematical model and population-based iterated greedy algorithm to minimize total tardiness

This paper focuses on a cascaded flowshop joint scheduling problem (CFJSP) based on an investigation of the printed circuit board manufacturing industry, aiming at total tardiness minimization. Unlike single flowshop scheduling problems, the CFJSP can be regarded as a scheduling problem consisting of two sub-problems, i.e., distributed permutation flowshop scheduling problem (DPFSP) and hybrid flowshop scheduling problem (HFSP). The optimization process between DPFSP and HFSP becomes the key to solving this problem. We first formulate its working principle and establish a mixed-integer linear programming model. Second, we propose a population-based iterated greedy (PBIG) algorithm, whose search space alternates sequentially from phase 1 to phase 2 to explore near-optimal solutions. Meanwhile, we present an NEH-based heuristic to generate a high-quality initial solution, and a finite skip boundary reconstruction operator to explore more promising search space and reduce computational effort. The parameters and operators of the PBIG algorithms are calibrated and analyzed using the experiment design and evaluation method. We generate an applicable benchmark instance set to evaluate the PBIG algorithm against five state-of-the-art metaheuristics. Statistically sound results demonstrate the effectiveness of the proposed PBIG algorithm for solving the CFJSP with the total tardiness objective.