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

doi:10.1007/s42514-025-00243-0

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

2025-11-01

0

PRE

AI

DOI：10.1007/s42514-025-00243-0

原文链接

原文求助

摘要

En 中文

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+epsilon+22B & lowast;-1)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(1 + \varepsilon + \frac{2}{2B<^>* - 1})$$\end{document}, where epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon$$\end{document} is an arbitrary positive number in (0, 1] and B & lowast;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B<^>*$$\end{document} is the number of batches in an optimal solution. The ratio is asymptotically optimal when B & lowast;\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$B<^>*$$\end{document} tends toward infinity and the parameter epsilon\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varepsilon$$\end{document} approaches 0. Empirical validation through numerical simulations confirms that our methodology efficiently produces solutions approaching optimality within practical computation times.

Keyword:

Flow shop

Batch and transporter

Approximation algorithms

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

摘要

期刊

机构

引用论文