用图神经网络和强化学习解决不确定工期的资源调度问题
Learning to Solve Resource-Constrained Project Scheduling Problems with Duration Uncertainty using Graph Neural Networks
- 结合图神经网络与强化学习，设计可复用的调度策略
- 在标准测试集上优于现有方法，且泛化能力强
- 适合工业界需多次重复使用的鲁棒调度场景
资源约束项目调度问题（RCPSP）是具有广泛应用的经典调度问题。然而，实际中任务工期存在不确定性，必须考虑以生成鲁棒性调度方案。本文研究带有不确定工期（以已知概率建模）的RCPSP变体，目标是最小化项目的整体期望工期。旨在生成一个可在工业环境中多次复用的基准调度方案。我们采用图神经网络结合深度强化学习（DRL），构建一种类似优先级派发规则的任务调度策略，并与串行调度生成方案配合使用。在标准基准上的实证评估表明，该方法在性能和泛化能力方面均表现出色。所开发的框架Wheatley已公开上线，以促进后续研究和可复现性。
原文摘要 · Abstract (English)
The Resource-Constrained Project Scheduling Problem (RCPSP) is a classical scheduling problem that has received significant attention due to of its numerous applications in industry. However, in practice, task durations are subject to uncertainty that must be considered in order to propose resilient scheduling. In this paper, we address the RCPSP variant with uncertain tasks duration (modeled using known probabilities) and aim to minimize the overall expected project duration. Our objective is to produce a baseline schedule that can be reused multiple times in an industrial setting regardless of the actual duration scenario. We leverage Graph Neural Networks in conjunction with Deep Reinforcement Learning (DRL) to develop an effective policy for task scheduling. This policy operates similarly to a priority dispatch rule and is paired with a Serial Schedule Generation Scheme to produce a schedule. Our empirical evaluation on standard benchmarks demonstrates the approach's superiority in terms of performance and its ability to generalize. The developed framework, Wheatley, is made publicly available online to facilitate further research and reproducibility.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。