针对工序路径不确定的车间调度问题,提出新方法提升调度稳定性与性能。
Learning to Optimize Job Shop Scheduling Under Structural Uncertainty
- 采用不对称架构,批评者基于事后确定状态学习价值函数。
- 在标准基准上使完工时间(makespan)显著降低,优于现有方法。
- 适合处理路径选择由不可知因素决定的复杂制造调度场景。
作业车间调度问题(JSSP)在多种制造不确定性下受到广泛关注。现有研究多聚焦于参数不确定性(如加工时间可变),通常采用演员-评论家框架。本文探讨一种不同但普遍存在的不确定性:结构不确定性。当某个工件可能走多个路径,且路径选择由无法预先知晓的情境因素(如中间品质量)决定时,即产生结构不确定性。传统方法因错误的信用分配而难以应对:高质量操作若后接耗时路径,会被不公惩罚。为此,我们提出新方法UP-AAC。与常规演员-评论家不同,UP-AAC采用非对称架构:演员接收标准随机状态,而批评者则获得事后重构的确定性状态。该设计使批评者能学习更准确的价值函数,从而为演员提供更低方差的策略梯度,实现更稳定的学习。此外,设计基于注意力的不确定性感知模型(UPM)以增强演员决策。大量实验表明,该方法在基准实例上显著降低了完工时间(makespan),优于现有方法。
原文摘要 · Abstract (English)
The Job-Shop Scheduling Problem (JSSP), under various forms of manufacturing uncertainty, has recently attracted considerable research attention. Most existing studies focus on parameter uncertainty, such as variable processing times, and typically adopt the actor-critic framework. In this paper, we explore a different but prevalent form of uncertainty in JSSP: structural uncertainty. Structural uncertainty arises when a job may follow one of several routing paths, and the selection is determined not by policy, but by situational factors (e.g., the quality of intermediate products) that cannot be known in advance. Existing methods struggle to address this challenge due to incorrect credit assignment: a high-quality action may be unfairly penalized if it is followed by a time-consuming path. To address this problem, we propose a novel method named UP-AAC. In contrast to conventional actor-critic methods, UP-AAC employs an asymmetric architecture. While its actor receives a standard stochastic state, the critic is crucially provided with a deterministic state reconstructed in hindsight. This design allows the critic to learn a more accurate value function, which in turn provides a lower-variance policy gradient to the actor, leading to more stable learning. In addition, we design an attention-based Uncertainty Perception Model (UPM) to enhance the actor's scheduling decisions. Extensive experiments demonstrate that our method outperforms existing approaches in reducing makespan on benchmark instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。