<p>This paper investigates a two-stage flow shop scheduling model incorporating transportation after the job is complete. The system configuration comprises dual processing machines and a single automated transporter with unit capacity. Each job in the production sequence is defined by distinct physical size, and the transporter can load multiple jobs in a batch at the same time. All jobs follow identical processing order across both machines before they are transported to the destination. The goal of this problem is to determine a schedule and the batch scheme for transport, such that the makespan is minimum, where the makespan represents the minimum completion time required for full job processing and delivery operations. We present a novel approximation algorithm achieving a performance ratio of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$(1 + \varepsilon + \frac{2}{2B^* - 1})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mo stretchy="false">(</mo> <mn>1</mn> <mo>+</mo> <mi>ε</mi> <mo>+</mo> <mfrac> <mn>2</mn> <mrow> <mn>2</mn> <msup> <mi>B</mi> <mo>∗</mo> </msup> <mo>-</mo> <mn>1</mn> </mrow> </mfrac> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>, where <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\varepsilon$</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation> is an arbitrary positive number in (0, 1] and <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$B^$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>B</mi> <mo>∗</mo> </msup> </math></EquationSource> </InlineEquation> is the number of batches in an optimal solution. The ratio is asymptotically optimal when <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$B^$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mi>B</mi> <mo>∗</mo> </msup> </math></EquationSource> </InlineEquation> tends toward infinity and the parameter <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\varepsilon$</EquationSource> <EquationSource Format="MATHML"><math> <mi>ε</mi> </math></EquationSource> </InlineEquation> approaches 0. Empirical validation through numerical simulations confirms that our methodology efficiently produces solutions approaching optimality within practical computation times.</p>

A new approximation algorithm for two-machine flow shop scheduling with transporter coordinate

期刊论文
发表日期：

2025年11月5日

查看全文

Yinling Wang,
Yuping Ge,
Yubai Zhang,
Hui Tian

摘要

This paper investigates a two-stage flow shop scheduling model incorporating transportation after the job is complete. The system configuration comprises dual processing machines and a single automated transporter with unit capacity. Each job in the production sequence is defined by distinct physical size, and the transporter can load multiple jobs in a batch at the same time. All jobs follow identical processing order across both machines before they are transported to the destination. The goal of this problem is to determine a schedule and the batch scheme for transport, such that the makespan is minimum, where the makespan represents the minimum completion time required for full job processing and delivery operations. We present a novel approximation algorithm achieving a performance ratio of $(1 + \varepsilon + \frac{2}{2B^* - 1})$ $(1 + ε + \frac{2}{2 B^{*} - 1})$ , where $\varepsilon$ $ε$ is an arbitrary positive number in (0, 1] and $B^*$ $B^{*}$ is the number of batches in an optimal solution. The ratio is asymptotically optimal when $B^*$ $B^{*}$ tends toward infinity and the parameter $\varepsilon$ $ε$ approaches 0. Empirical validation through numerical simulations confirms that our methodology efficiently produces solutions approaching optimality within practical computation times.