Two-stage flexible flow shop scheduling in GPU systems
研究了GPU并行处理中的负载调度问题，将其建模为两阶段柔性流水车间模型，针对特殊情形提出了多项式时间近似方案（PTAS），改进了已知最优近似比。
This paper investigates a load scheduling problem essential for optimizing GPU performance in parallel processing environments. We formulate the problem as F2(1,Pm) | sizei | 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 Ji is processed first on the single machine and then simultaneously on a set of sizei machines, with the goal of minimizing the makespan. The variant F2(1,Pm) | linei | Cmax requires that the linei machines at the second stage be consecutive (i.e., contiguous in the given order). Focusing on the special case F2(1,P2) | linei | Cmax, which equals to F2(1,P2) | sizei | 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.