Advanced Metaheuristics for Bi-criteria Optimization in a Distributed Blocking Flow Shop Problem with Setup Times

In this paper, a bi-criteria Distributed Blocking Flow Shop Scheduling Problem with Sequence-Independent Setup Times (DBFSSP-SIST) is considered. The primary objective is to minimize the maximum completion time (makespan) ( $$\mathcal {C}_{\max }$$ C max ) and the maximum tardiness ( $$\mathcal {T}_{max}$$ T max ). These criteria are combined into a single weighted objective function ( $$\mathcal {K}$$ K ) using linear weights to balance their importance. To address this problem, we propose a Mixed Integer Linear Programming (MILP) model as an exact solution method, alongside a set of advanced metaheuristics. Specifically, three metaheuristics are developed: the Oriented Self-Crossover Genetic Algorithm (OSCGA), the Exchanged Multi-Population Migratory Bird Optimization (EMPMBO), and the Multi-Strategy Iterated Greedy (MSIG) algorithm. Each algorithm is implemented with two initialization strategies: the Nawaz-Enscore-Ham (NEH) and the Greedy Randomized Adaptive Search Procedure (GRASP), resulting in six variations. Computational experiments were conducted on a range of test instances. The results demonstrate that the MSIG algorithm consistently outperforms the other methods, with MSIG using NEH initialization (MSIG $$_{1}$$ 1 ) delivering the best performance, even surpassing its GRASP-initialized counterpart (MSIG $$_2$$ 2 ).