我们研究了具有随机再入的流水车间调度问题，作业需要在整个车间完成多次通过，再入次数服从离散概率分布。目标是寻找在期望下最小化性能指标的调度策略。主要贡献是将该问题等价转化为在相同并行机器上并加入机器到达的随机调度问题。该等价保持目标值，使得可以把辅助问题的结构性结果和性能保证直接迁移到再入流水车间。利用该等价，我们证明在几何分布以及更一般的单调风险率分布下，简单的优先级策略在最小化期望完工时间（makespan）和总完成时间方面是最优的。对于最小化加权总完成时间，我们给出一个近似保证，其依赖于底层分布的平方变异系数。我们的工作提供了首批针对随机再入流水车间的最优性和近似保证，表明已有的调度策略可以自然地通过该等价扩展到此情形。
博主点评: 该研究通过巧妙的等价转换，将复杂的再入流水车间问题映射到更易分析的并行机器模型，既保留了原始目标，又让已有的调度理论直接适用，具有重要的理论与实践价值。