Self-Adaptive Population-Based Iterated Greedy Algorithm for Distributed Permutation Flowshop Scheduling Problem with Part of Jobs Subject to a Common Deadline Constraint

Although the distributed permutation flowshop scheduling problem (DPFSP) has recently received extensive research attention, most studies assume that either all jobs have due date constraints or none of them do. Nevertheless, in practice, it is very common to schedule jobs with due dates alongside jobs without a due date. This paper addresses a DPFSP with part of jobs subject to a common deadline (DPFSP-PJCD). The objective is to minimize the total completion time. We establish a mathematical model and propose a Self-adaptive Population-based Iterated Greedy (SPIG) algorithm that is specifically tailored to the characteristics of the problem. We design a hybrid constructive heuristic to generate a population of potentially high-quality solutions. We introduce an insertion-based acceleration method that combines three distinct accelerations to improve operational efficiency. We propose some effective operators to carry out the selection, destruction, and construction of solutions, as well as a local search mechanism, to balance the exploitation and exploration of the algorithm. Additionally, we employ a self-adaptive method to determine a key algorithmic parameter depending on the search phase and search space. We also utilize a self-adjustment insertion procedure to handle infeasible solutions. Through comprehensive experimental evaluations, we demonstrate that the proposed SPIG outperforms five state-of-the-art metaheuristics from the closely related literature, providing effective solutions for the DPFSP-PJCD considered.