无需训练数据,用神经网络直接求解资源受限项目调度问题
Dataless Neural Networks for Resource-Constrained Project Scheduling
- 将调度约束转化为可微目标,通过梯度优化求解
- 在PSPLIB的J30/J60/J120数据集上实现GPU并行调度
- 适合需要快速求解且无历史数据的工程场景
数据无关神经网络为组合优化带来新范式,无需训练数据即可将问题实例直接编码至网络参数中。尽管已有研究证明其在最大独立集问题上的可行性,但尚未有工作将其扩展至资源受限项目调度问题(RCPSP)。本文首次提出针对RCPSP的数据无关神经网络方法,构建完整数学框架,将离散调度约束转化为适用于梯度优化的可微目标。通过平滑松弛与自动微分,实现项目调度的GPU并行化,突破传统串行算法局限。文中详述了前序依赖与可再生资源约束的数学表达,并采用内存高效的密集时间网格表示。当前正在PSPLIB基准数据集(J30、J60、J120)上进行实现与实验,实证结果将在后续版本中报告。
原文摘要 · Abstract (English)
Dataless neural networks represent a paradigm shift in applying neural architectures to combinatorial optimization problems, eliminating the need for training datasets by encoding problem instances directly into network parameters. Despite the pioneering work of Alkhouri et al. (2022) demonstrating the viability of dataless approaches for the Maximum Independent Set problem, our comprehensive literature review reveals that no published work has extended these methods to the Resource-Constrained Project Scheduling Problem (RCPSP). This paper addresses this gap by presenting the first dataless neural network approach for RCPSP, providing a complete mathematical framework that transforms discrete scheduling constraints into differentiable objectives suitable for gradient-based optimization. Our approach leverages smooth relaxations and automatic differentiation to unlock GPU parallelization for project scheduling, traditionally a domain of sequential algorithms. We detail the mathematical formulation for both precedence and renewable resource constraints, including a memory-efficient dense time-grid representation. Implementation and comprehensive experiments on PSPLIB benchmark instances (J30, J60, and J120) are currently underway, with empirical results to be reported in an updated version of this paper.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。