面向资源受限调度的Petri网启发式搜索

# 基于Petri网诱导启发式搜索的资源约束调度问题
来源：https://arxiv.org/html/2605.15983
###### 摘要

我们将资源约束项目调度问题（RCPSP）建模为在带资源的定时变迁Petri网可达图上的最优搜索，利用相对延迟令牌，使得调度决策对应于诱导状态空间中的变迁激发。我们采用结合关键路径和资源下界的启发式函数指导A*搜索，并证明在该基于令牌的时间语义下启发式函数是一致的。在PSPLIB基准测试上的实验表明，该方法在成功率和求解时间上均优于强精确混合整数线性规划（MIP）基线（SCIP、CBC）。实例分析表明，启发式搜索和MIP在独立维度上性能退化，A*受资源紧张度影响，MIP受模型规模影响，而资源强度则决定了哪种求解器更能从规模中获益。

## 引言

资源约束项目调度问题（RCPSP）要求在前驱约束和有限共享资源下安排活动，以最小化完工时间（Herroelen et al. 1998；Brucker et al. 1999；Hartmann and Briskorn 2022）。作为经典调度问题的强NP-hard推广（Blazewicz et al. 1983），RCPSP是调度、组合搜索和资源受限推理交叉领域的基础问题。它也出现在时间规划、机器人任务协调、航天器任务调度、多处理器调度和项目管理中。RCPSP长期以来一直是精确和近似方法的基准，但没有任何单一方法能在所有实例类别中占据主导地位。

领先的精确求解方法是混合整数线性规划（MIP），通常通过分支切割求解（Dorndorf et al. 2000；Koné et al. 2011；Artigues et al. 2015）。虽然MIP提供最优性保证，但扩展性差，像SCIP（Achterberg 2009）这样强大的求解器往往未能在实际时间限制内求解基准实例。元启发式方法（Pellerin et al. 2020）以最优性为代价提高了可扩展性，而混合方法试图寻求折中，但现有没有方法能可靠地兼顾两者。一种自然精确替代方案是启发式搜索（Hart et al. 1968）。Bell和Park（1990）通过冲突序列将A*应用于RCPSP，但该方法在资源约束强的实例上变得难以处理。Zamani和Shue（1998）引入了活动分派状态空间，并通过SLA*应用A*，改进了性能，但需要多次搜索试验才能达到最优。在这两种情况下，缺乏一致启发式函数阻碍了安全剪枝并导致等效调度状态冗余重扩展——我们在当前工作中解决了这个问题。更广泛地说，最近一项综述（Huang et al. 2023）强调了在可达图上进行启发式搜索在平衡解质量和计算工作量方面的前景。相关的基于Petri网的思想已在项目和制造调度中探索（Mejia et al. 2016；Mejia and Odrey 2005），在模型检查背景下研究了Petri网可达图上的有向启发式搜索（Edelkamp and Jabbar 2006），并且模拟已用于估计RCPSP项目工期（Wu et al. 2009）。然而，据我们所知，先前没有工作将最优启发式搜索应用于RCPSP公式的诱导可达图。

本文开发了一种新的RCPSP公式，将其作为由带资源的定时变迁Petri网（TTPNR）诱导的可达图上的最优搜索，使局部调度决策明确，并通过令牌延迟统一表示时间。这产生了一种具有可采纳启发式函数、安全剪枝和高效处理零代价变迁的精确搜索公式。我们证明了组合关键路径和资源启发式函数是一致的，并且在标准PSPLIB基准测试上表明，所提方法与强精确MIP基线（包括SCIP和CBC）具有竞争力。

## RCPSP问题定义

RCPSP由元组$(\mathbb{A}, E, R, C, U, \tau)$表征：

- $\mathbb{A} = \{0, 1, \dots, n, n+1\}$：活动集合，其中0和$n+1$为虚开始和结束活动。
- $E \subset \mathbb{A} \times \mathbb{A}$：前驱约束，$(i,j) \in E$表示$j$不能在$i$完成后开始。设$\bullet j = \{i \mid (i,j) \in E\}$为$j$的紧前活动集合。
- $R = \{r_1, \dots, r_k\}$：可更新资源类型，容量为$C = \{c_1, \dots, c_k\}$。
- $u_{j,i}$：活动$j$对资源$r_i$的需求量。
- $\tau_j$：活动$j$的工期。

与标准RCPSP公式一样，虚活动工期为零（$\tau_0 = \tau_{n+1} = 0$）且资源需求为零（对所有$r_i \in R$，$u_{0,i} = u_{n+1,i} = 0$）。

项目*调度*为每个活动$j \in \mathbb{A}$分配开始时间$S_j \geq 0$。可行调度满足两个约束：

1. *前驱约束*：活动必须在其所有前驱完成后才能开始（对所有$(i,j) \in E$，$S_j \geq S_i + \tau_i$）。
2. *资源约束*：在任何时间$t$，分配给进行中活动的每种资源类型$r_i \in R$的总量不能超过其可用容量$c_i \in C$。

目标是找到最小化最大完工时间的调度，即虚结束活动的开始时间：$\min S_{n+1}$。前驱和资源约束之间的相互作用产生了一个高度约束的组合问题，我们随后将分别将其表述为可达图和MIP。我们将在整篇论文中使用以下示例。

###### 示例1。

考虑一个RCPSP实例，活动集$\mathbb{A} = \{0,1,2,3,4,5\}$（记$0 \equiv a$, $1 \equiv b$, $2 \equiv c$, 等等）。$a$和$f$是虚开始和结束活动。前驱集为$E = \{(a,b), (a,d), (b,c), (d,e), (c,f), (e,f)\}$，形成两条平行链$a \rightarrow b \rightarrow c \rightarrow f$和$a \rightarrow d \rightarrow e \rightarrow f$。有一种可更新资源$r$，容量$c_1 = 2$。每个非虚活动需要一个单位，即$u_{b,1} = u_{c,1} = u_{d,1} = u_{e,1} = 1$，且$u_{a,1} = u_{f,1} = 0$。工期为$\tau_a = \tau_f = 0$, $\tau_b = 3$, $\tau_c = 1$, $\tau_d = 3$, $\tau_e = 2$。最优调度最大完工时间为5，其中$S_a = S_b = S_d = 0$, $S_c = S_e = 3$, $S_f = 5$。图1(a)总结了问题实例参数。

## 带资源的定时变迁Petri网

*Petri网*（Petri 1966）是一个二分图，由*库所*（圆圈表示）和*变迁*（矩形表示）组成，由有向弧连接。库所持有*令牌*，其分布定义了*标识*$M$。形式上，Petri网是一个元组$(P, T, F, W, M_0)$，其中$P$和$T$是库所和变迁的有限集，$F \subseteq (P \times T) \cup (T \times P)$是弧集，$W: F \rightarrow \mathbb{Z}^+$是权函数，$M_0$是初始标识。我们将$\bullet t = \{p \in P \mid (p,t) \in F\}$记为变迁$t$的输入库所集。如果每个$p \in \bullet t$至少持有$W(p,t)$个令牌，则变迁$t$*使能*；激发会按规则消耗和产生令牌，从而建模并发和同步。在我们的公式中，每个可达标识对应一个搜索状态，可达标识定义了*可达图*，我们的方法会逐步生成并搜索该图。

为了区分原始RCPSP公式及其Petri网编码，我们使用$j \in \mathbb{A}$表示RCPSP活动，使用$t \in T$表示Petri网变迁。下面，每个变迁对应一个活动。我们将经典Petri网扩展为带时间与资源视角的TTPNR：

$\mathcal{N} = (P, T, F, W, M_0, \lambda, \tau_T, R, C)$，

其中$\lambda: T \to \mathbb{A}$将每个Petri网变迁映射到对应的RCPSP活动，$\tau_T: T \to \mathbb{N}_0$为每个变迁分配工期，$R, C$定义资源类型及其容量。每个变迁继承其关联活动的工期（$\tau_T(t) := \tau_{\lambda(t)}$）。一个专门的资源库所子集$P_R \subset P$强制执行容量约束：$M_0$为每个资源库所分配正好$c_i$个令牌。单一使能规则$M(p) \ge W(p,t)$保证了活动仅在其前驱条件和资源需求都满足时才能开始。这种统一的使能规则是相对于之前RCPSP搜索公式的一个关键优势，之前的公式中前驱和资源约束需要在搜索空间外使用单独的冲突解决机制。

图1(b)展示了示例1中RCPSP实例（图1(a)）的TTPNR公式。这里，$a$和$f$分别表示虚开始和虚结束活动。图中显示了初始标识$M_0$，其中$p_1$中放置一个令牌，资源库所$p_r$中放置两个令牌（为简洁起见省略了资源类型索引）。$M_0$下唯一使能的变迁是$a$；激发它会消耗$p_1$中的令牌，并在$p_2$和$p_3$中产生令牌，使活动$b$和$d$可用于竞争共享资源。

问题实例：act. succ. dur. r
a b,d 0 0
b c 3 1
c f 1 1
d e 3 1
e f 2 1
f — 0 0

(a)
看图注 (b)
看图注 (c)

图1: (a) RCPSP实例；(b) TTPNR初始标识；(c) 在诱导可达图上的A*搜索。节点显示$(g, h, f)$和令牌延迟$\theta$，绿色节点为已扩展。

## 将RCPSP建模为搜索问题

为了通过启发式求解RCPSP，我们直接从TTPNR诱导出可达图。在此搜索图中，每个节点代表一个系统状态，每条边对应于通过激发Petri网变迁来执行特定项目活动的承诺。

*状态* $s \in \mathbb{S}$ 是一个带有令牌相对延迟的标识。通过将时间编码为令牌延迟$\theta$，我们避免了全局时钟，使得更多状态可被识别为相同并被安全剪枝；启发式一致性则保证了任何状态的首次扩展都是最优的。形式上，

$s = \left[p_1: l_1^{\theta_{l_1}}, \dots, p_n: l_n^{\theta_{l_n}}, \;\; p_{r_1}: r_1^{\theta_{r_1}}, \dots, p_{r_k}: r_k^{\theta_{r_k}}\right]$

其中延迟$\theta > 0$的令牌尚不可用，而$\theta = 0$（按惯例省略）表示立即可用。这里，$l_i^{\theta_{l_i}}$表示库所$p_i$中有$l_i$个令牌，延迟为$\theta_{l_i}$，$r_j^{\theta_{r_j}}$表示资源令牌$r_j$个，延迟为$\theta_{r_j}$（仅显示正令牌计数）。

*起始状态* $s_0$ 在虚开始变迁的输入库所中有一个令牌，所有资源库所处于初始标识；*目标状态* 在虚结束变迁的输出库所中有一个令牌，且资源库所恢复。

我们考虑变迁$t \in T$，如果其输入库所包含足够令牌（不考虑当前相对延迟），则视为*使能*。激发$t$即承诺执行对应的活动$\lambda(t)$，过程如下： (1) *时间跳跃*：消耗所需输入令牌，优先选择具有最小相对延迟的令牌。诱导的时间跳跃为 $\Delta t = \max(\theta_{\mathrm{consumed}})$。(2) *延迟与令牌生成*：所有剩余令牌延迟减少$\Delta t$：$\theta^{\mathrm{new}} = \max(0, \theta - \Delta t)$。新产生的令牌被分配延迟 $\tau_T(t) = \tau_{\lambda(t)}$。此外，每个节点维护路径代价 $g(s') = g(s) + \Delta t$ 供A*使用。

### 启发式函数

我们使用从状态$s$出发的剩余最大完工时间的两个下界：关键路径界$h_{CP}(s)$（松弛资源容量得到）和资源负载界$h_{res}(s)$（松弛前驱约束得到）。两者的组合为 $h_{\max}(s) = \max(h_{CP}(s), h_{res}(s))$。

#### 关键路径启发式

$h_{CP}(s)$ 是从当前状态到虚结束活动$n+1$的最长*剩余*前驱路径的长度，通过按拓扑顺序传播剩余最早完成时间（REF）计算：

$REF_j = \begin{cases} 0 & \text{如果 $j$ 已完成，} \\ \theta_j & \text{如果 $j$ 正在执行，} \\ \displaystyle\max_{i \in \bullet j} REF_i + \tau_j & \text{如果 $j$ 尚未开始，} \end{cases}$

初始化 $REF_0 = 0$，且 $h_{CP}(s) = REF_{n+1}$。

命题 1. $h_{CP}$ 是可采纳且一致的。

###### 证明。

可采纳性。移除资源约束不会延长剩余完成时间，因此 $h_{CP}(s) \leq h^*(s)$。

一致性。考虑$s$的后继$s'$，时间增量为 $\delta(s, s') := g(s') - g(s)$。对于每个活动$j$，其剩余工期最多减少 $\delta(s, s')$：正在执行的活动损失最多 $\delta(s, s')$，未开始的活动不变，新开始的活动$\lambda(t)$ 在$s'$中获得剩余延迟 $\tau_{\lambda(t)}$，与其激发前的值相同。由于前驱约束要求沿任何单一路径顺序执行，在$s$中最长路径$P^*$上最多有一个活动正在执行，因此 $P^*$ 的总剩余长度最多减少 $\delta(s, s')$。由于 $h_{CP}(s')$ 是所有路径的最大值，