让调度决策更抗干扰,提升动态工厂排产效率
DyRo-MCTS: A Robust Monte Carlo Tree Search Approach to Dynamic Job Shop Scheduling
- 在MCTS中引入抗扰动评估,指导选择更稳健的调度动作
- 相比传统MCTS,显著提升多种场景下的调度性能
- 适合需要长期稳定运行的工业动态排产系统
动态作业车间调度是多个工业领域中的基础组合优化问题,频繁的新任务到达带来巨大挑战。现有方法通过机器学习离线训练调度策略以快速响应动态事件,但离线策略常不完美,需依赖蒙特卡洛树搜索(MCTS)等规划技术在线优化。然而新任务到达的不确定性使基于不完整信息的决策易受干扰。为此,本文提出动态鲁棒蒙特卡洛树搜索(DyRo-MCTS),将动作鲁棒性估计融入MCTS,引导生产环境走向不仅绩效好且易于应对未来任务到来的状态。大量实验表明,DyRo-MCTS在几乎不增加在线规划时间的前提下,显著提升离线策略性能;且在各种调度场景下均优于原始MCTS。进一步分析显示,其鲁棒决策能力带来了持续稳定的长期性能优势。
原文摘要 · Abstract (English)
Dynamic job shop scheduling, a fundamental combinatorial optimisation problem in various industrial sectors, poses substantial challenges for effective scheduling due to frequent disruptions caused by the arrival of new jobs. State-of-the-art methods employ machine learning to learn scheduling policies offline, enabling rapid responses to dynamic events. However, these offline policies are often imperfect, necessitating the use of planning techniques such as Monte Carlo Tree Search (MCTS) to improve performance at online decision time. The unpredictability of new job arrivals complicates online planning, as decisions based on incomplete problem information are vulnerable to disturbances. To address this issue, we propose the Dynamic Robust MCTS (DyRo-MCTS) approach, which integrates action robustness estimation into MCTS. DyRo-MCTS guides the production environment toward states that not only yield good scheduling outcomes but are also easily adaptable to future job arrivals. Extensive experiments show that DyRo-MCTS significantly improves the performance of offline-learned policies with negligible additional online planning time. Moreover, DyRo-MCTS consistently outperforms vanilla MCTS across various scheduling scenarios. Further analysis reveals that its ability to make robust scheduling decisions leads to long-term, sustainable performance gains under disturbances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。