摘要
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+ε+2B∗−1/2),where is an arbitrary positive number in(0,1]and B∗is the number of batches in an optimal solution.The ratio is asymptotically optimal when B∗tends toward infinity and the parameter approaches 0.Empirical validation through numerical simulations confirms that our methodology efficiently produces solutions approaching optimality within practical computation times.
基金
supported in part by Henan Science and Technology Research(Grant Number 222102310547)
Natural Science Foundation of Henan(Grant Number 242300421474)
Collaborative Innovation Major Project of Zhengzhou(Grant Number 20XTZX06013).
