<p>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) (<InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\mathcal {C}_{\max }$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">C</mi> <mo movablelimits="true">max</mo> </msub> </math></EquationSource> </InlineEquation>) and the maximum tardiness (<InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\mathcal {T}_{max}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi mathvariant="script">T</mi> <mrow> <mi mathvariant="italic">max</mi> </mrow> </msub> </math></EquationSource> </InlineEquation>). These criteria are combined into a single weighted objective function (<InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {K}$</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="script">K</mi> </math></EquationSource> </InlineEquation>) 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<InlineEquation ID="IEq4"> <EquationSource Format="TEX">$_{1}$</EquationSource> <EquationSource Format="MATHML"><math> <mmultiscripts> <mrow /> <mn>1</mn> <mrow /> </mmultiscripts> </math></EquationSource> </InlineEquation>) delivering the best performance, even surpassing its GRASP-initialized counterpart (MSIG<InlineEquation ID="IEq5"> <EquationSource Format="TEX">$_2$</EquationSource> <EquationSource Format="MATHML"><math> <mmultiscripts> <mrow /> <mn>2</mn> <mrow /> </mmultiscripts> </math></EquationSource> </InlineEquation>).</p>

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

期刊论文
发表日期：

2025年10月10日

查看全文

Achraf Sayah,
Said Aqil,
Mohamed Lahby

摘要

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}$ ).