Treffer: An efficient rollout algorithm for unrelated parallel machine scheduling with random rework.

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. [ABSTRACT FROM AUTHOR]

Copyright of International Journal of Production Research is the property of Taylor & Francis Ltd and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Der Volltext kann Gästen nicht angezeigt werden. Login für vollen Zugriff.