An efficient rollout algorithm for unrelated parallel machine scheduling with random rework
研究了随机返工环境下非相关并行机调度问题，提出两阶段启发式和改进的展开算法，在中等返工强度下比传统启发式提升10%，比元启发式提升15%，且计算时间减半。
This study addresses the unrelated parallel machine scheduling problem with random rework, aiming to minimize the expected total weighted tardiness. The stochastic nature of rework timing and frequency complicates job completion time estimation, posing significant challenges for scheduling decisions. Although stochastic dynamic programming yields optimal policies, its applicability is limited to small-scale problems due to the curse of dimensionality. To address this limitation, we first propose a two-stage heuristic based on an assignment problem. Afterwards, we develop an improved post-rollout algorithm that leverages these heuristics for action generation and evaluation, which further enhanced by incorporating design of experiments and common random numbers techniques. Computational experiments validate the effectiveness of the proposed methods. The results demonstrate that, under moderate rework intensity, the presented heuristics achieve a 10% improvement over traditional heuristics. Moreover, the post-rollout algorithm significantly outperforms both the heuristics and the metaheuristics, with overall gaps of 15% and 6%, respectively. Sensitivity analysis reveals that the advantage of the post-rollout algorithm over metaheuristics becomes more pronounced as rework intensity increases, with the gap widening from 1% to 13%. Furthermore, the post-rollout algorithm achieves high computational efficiency, requiring only half the computational time of metaheuristics for large-scale problems.