用蒙特卡洛树搜索解决复杂工件调度问题，效果优于传统方法。
Investigating the Monte-Carlo Tree Search Approach for the Job Shop Scheduling Problem
- 将工件调度建模为马尔可夫决策过程，适配蒙特卡洛树搜索
- 在大规模含循环实例上求解质量优于约束规划方法
- 基于真实数据构建新基准，更贴近实际制造场景
工件调度问题（JSSP）是制造领域的经典优化难题，目标是在不同机器上确定工件的最优执行顺序以最小化加权完成时间之和。本文研究蒙特卡洛树搜索（MCTS）这一基于启发式的强化学习方法在求解大规模JSSP中的潜力，尤其针对存在循环依赖的复杂情形。我们提出了多种马尔可夫决策过程（MDP）建模方式以适配MCTS算法，并引入一个基于真实制造数据生成的新合成基准，该基准能捕捉实际中常见的大型非矩形实例特征。实验结果表明，MCTS在大规模JSSP实例上能够高效生成高质量解，性能超越我们提出的约束规划方法。
原文摘要 · Abstract (English)
The Job Shop Scheduling Problem (JSSP) is a well-known optimization problem in manufacturing, where the goal is to determine the optimal sequence of jobs across different machines to minimize a given objective. In this work, we focus on minimising the weighted sum of job completion times. We explore the potential of Monte Carlo Tree Search (MCTS), a heuristic-based reinforcement learning technique, to solve large-scale JSSPs, especially those with recirculation. We propose several Markov Decision Process (MDP) formulations to model the JSSP for the MCTS algorithm. In addition, we introduce a new synthetic benchmark derived from real manufacturing data, which captures the complexity of large, non-rectangular instances often encountered in practice. Our experimental results show that MCTS effectively produces good-quality solutions for large-scale JSSP instances, outperforming our constraint programming approach.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。