无数据神经网络在资源受限项目调度中的应用-计算机科学-无数据神经网络-组合优化.pdf

无数据神经网络在资源受限项目调度中的应用

APREPRINT

MarcBaraIniesta

marc.bara.iniesta@

ORCID:0009-0005-1480-5760

ABSTRACT

本无数据神经网络代表了将神经架构应用于组合优化问题的一种范式转变，通过直接将问题实

例编码到网络参数中来消除对训练数据集的需求。尽管Alkhouri等人（2022）开创性的工

译作证明了无数据方法对于最大独立集问题的可行性，但我们的综述发现没有已发表的研究将

中这些方法扩展到资源受限项目调度问题(RCPSP)。本文通过提出第一个针对RCPSP的无数

1据神经网络方法来填补这一空白，并提供了一个完整的数学框架，该框架将离散调度约束转

v换为适合基于梯度优化的可微目标。我们的方法利用平滑松弛和自动微分解锁GPU并行化，

2而项目调度传统上是一个序列算法的领域。我们详细介绍了先决条件和可再生资源约束的数

2

3学公式，包括一个内存高效的密集时间网格表示。目前正在进行在PSPLIB基准实例（J30、

5J60和J120）上的实现和综合实验，并将在本文的更新版本中报告实证结果。

0

.

7Keywords无数据神经网络资源约束项目调度RCPSP组合优化GPU加速PSPLIB

0

5

2

:1介绍

v

i

x资源约束项目调度问题（RCPSP）是运筹学和项目管理中最为基础且广泛研究的问题之一。鉴于其NP难的

r

a性质及其在各行业中的实际重要性，RCPSP吸引了从精确方法到元启发式算法的各种解决方案。最近，基于

神经网络的方法作为一种有前景的方向出现，然而所有现有的方法都存在一个关键限制：它们需要大量的训

练数据。

阿尔库里等人[1]提出了一个革命性的替代方案，引入了无数据神经网络用于组合优化。他们的方法完全消

除了对训练数据集的需求，而是直接将问题实例编码到网络参数中，并通过基于梯度的优化来解决它。这种

范式转移解决了基于学习的方法的基本限制，特别是它们在处理与训练数据具有不同结构特征的问题实例时

泛化能力较差的问题。

尽管有这一令人鼓舞的先例和对RCPSP的广泛研究，我们全面的文献回顾揭示了一个显著的空白：没有发

表过将无数据神经网络应用于资源约束项目调度问题的工作。鉴于RCPSP具有结构特性，这些特性似乎非

常适合无数据方法，包括明确定义的约束和已建立的连续松弛，这一缺失尤其值得注意。

本文做出了两个主要贡献。首先，我们进行了一个系统性调查，探讨了这种差距存在的原因，并分析了神经

网络方法在RCPSP领域的当前状态，所有这些方法都依赖于训练数据。其次，也是更重要的是，我们提出了

第一个无数据神经网络方法来处理RCPSP，提供了一个完整的数学框架，展示了如何通过基于梯度的优化和

GPU加速改进项目调度。我们的方法通过精心设计的平滑松弛将离散调度问题转化为连续优化问题，从而能

够使用自动微分和平行计算。

无数据神经网络在资源受限项目调度中的应用APREPRINT

我们详细说明了如何将优先级约束和可再生资源约束以可微形式编码，并采用了一种内存高效的公式，该公

式可以扩展到大型实例同时保持最小的GPU内存占用。来自PSPLIB的标准基准实例，特别是J30、J60和

J120集合，为我们的方法提供了测试平台，当前正在实施中，经验验证将在本文的更新版本中进行。

2背景

2