用佩特里网建模资源调度，启发式搜索比传统方法更快更准。
Petri Net Induced Heuristic Search for Resource Constrained Scheduling
- 将调度问题转化为带资源的时序佩特里网上的最优搜索。
- 在PSPLIB上比SCIP、CBC等精确求解器成功率更高，求解更快。
- 适合资源约束紧或规模大的任务调度场景，互补性强。
我们将资源受限项目调度问题（RCPSP）建模为带有资源的时序变迁佩特里网的可达图上的最优搜索问题，利用相对延迟令牌使调度决策对应于状态空间中的变迁激发。采用受关键路径与资源下界结合启发式引导的A*算法求解，并证明在基于令牌的时间语义下该启发式具有一致性。在PSPLIB基准测试中，该方法在成功率和求解时间上均优于强健的精确混合整数线性规划（MIP）基线（SCIP、CBC）。实例级分析表明，启发式搜索与MIP在不同维度上性能下降：A*受资源紧度影响，MIP受模型规模影响，资源强度决定了哪种求解器在规模增大时更具优势。
原文摘要 · Abstract (English)
We formulate the Resource-Constrained Project Scheduling Problem (RCPSP) as optimal search over the reachability graph of a Timed Transition Petri Net with Resources, using relative-delay tokens so that scheduling decisions correspond to transition firings in the induced state space. We solve the resulting problem with $A^*$ guided by a heuristic that combines Critical Path and resource-based lower bounds, and prove that it is consistent under our token-based time semantics. Experiments on the PSPLIB benchmarks show that the approach outperforms strong exact Mixed-Integer Linear Programming (MIP) baselines (SCIP, CBC) in both success rate and solve time. Per-instance analysis shows that heuristic search and MIP degrade along independent axes, resource tightness for $A^*$ and formulation size for MIP, with resource strength mediating which solver benefits from scale.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。