运筹学与控制论讨论班——Two-stage flexible flow shop scheduling in GPU systems

报告人：Weitian Tong（Georgia Southern University）

时 间：2025年6月4日（星期三），下午13:30-14:30

地 点：海纳苑2幢102

Abstract: We investigate a load scheduling problem essential for optimizing GPU performance in parallel processing environments, and formulate it as F2(1,Pm) | size_i |Cmax, which integrates elements of flexible flow shop and parallel machine scheduling. In this model, a single machine at the first stage is followed by m parallel machines at the second stage; each job J_i is processed first on the single machine and then simultaneously on a set of size_i machines, with the goal of minimizing the makespan. The variant F2(1,Pm) | line_i | Cmax requires that the line_i machines at the second stage be consecutive (i.e., contiguous in the given order). Focusing on the special case F2(1,P2) | line_i |Cmax, which equals to F2(1,P2) | size_i | Cmax coincidentally, we propose a Polynomial Time Approximation Scheme (PTAS) based on a novel three-parameter scheduling system. This PTAS is expandable to more general cases involving a constant number of machines at the second stage. Our approach improves the best-known approximation ratio and achieves optimal approximability under the strong NP-hardness of the problem.

联系人：谈之奕（tanzy@zju.edu.cn）