PLAN：面向柔性作业车间调度高效表示学习的并行类液体近似网络

# PLAN：并行液体启发近似网络，用于柔性作业车间调度的高效表示学习
来源：https://arxiv.org/html/2608.03041
Dhivya Dharshini Kannan1, Wei Zhang1\\通讯作者, Jieyi Bi2, Yingpeng Du2, Tianjun Wei2, Jie Zhang2, Zuming Liu3, Anupam Trivedi4

###### 摘要

用于柔性作业车间调度（FJSP）的深度强化学习（DRL）方法高度依赖以注意力为中心的架构来实现最先进的性能。然而，随着问题规模扩大，这些模型面临参数数量过多和推理延迟过高的问题。虽然液体神经网络（LNN）为建模自适应状态演化提供了一种参数高效的替代方案，但其固有的顺序动力学限制了计算效率。为了解决这一权衡问题，我们提出了 PLAN（并行液体启发近似网络），一个轻量级表示学习框架，将连续液体状态动力学重新表述为离散化且可并行化的形式。PLAN 在结构上将状态演化与上下文聚合解耦，其中液体启发更新负责主要的演化状态表示，而轻量级上下文聚合模块提供补充的全局上下文。此外，PLAN 作为一个通用、即插即用的骨干网络，可推广到复杂的 FJSP 变体：与紧凑的随机模块配对以处理随机 FJSP，并在多面动态 FJSP 中替代重型异构图变换器。在确定性、随机和多面动态 FJSP 基准上的大量评估表明，与相应的最先进基线相比，PLAN 平均将完工时间分别降低了 1.2%、1.4% 和 2.3%，在某个基准设置中改进幅度达到 10.2%。PLAN 还分别将平均推理延迟降低了 13.2%、31.7% 和 26.9%，在最大实例上最大降低 69.2%，同时仅使用基线参数的 22−47%。

## 引言

作业调度是一个基础性的组合优化问题，在工业、计算和服务系统中具有广泛的应用（Kwan 等人 2026 (https://arxiv.org/html/2608.03041#bib.bib1)）。柔性作业车间调度（FJSP）是其研究最广泛的表述之一，已被应用于汽车装配（Kim 等人 2022 (https://arxiv.org/html/2608.03041#bib.bib6)）、医疗调度（Burdett and Kozan 2018 (https://arxiv.org/html/2608.03041#bib.bib7)）和半导体制造（Ghaedy-Heidary 等人 2024 (https://arxiv.org/html/2608.03041#bib.bib8)）等领域。在 FJSP 中，每个作业的每道工序可以被分配到多个可用机器之一，同时满足先后顺序和资源约束（Wang 等人 2026 (https://arxiv.org/html/2608.03041#bib.bib4)）。由于其 NP 困难性质（Xie 等人 2019 (https://arxiv.org/html/2608.03041#bib.bib9)），随着问题规模的增长，在可接受的计算时间内获得高质量调度变得越来越困难。经典方法，包括禁忌搜索（Brandimarte 1993 (https://arxiv.org/html/2608.03041#bib.bib10)）、遗传算法（Li 等人 2019 (https://arxiv.org/html/2608.03041#bib.bib11)）和分派启发式（Li and Gao 2016 (https://arxiv.org/html/2608.03041#bib.bib12)），通常难以在解质量和计算效率之间取得良好平衡，特别是在大规模或动态调度环境中。

深度强化学习（DRL）的最新进展证明了基于学习的调度器在训练后能够以快速推理生成高质量调度（Kaleta and Śliwiński 2026 (https://arxiv.org/html/2608.03041#bib.bib13); Liu 等人 2025 (https://arxiv.org/html/2608.03041#bib.bib14)）。现有的最先进（SOTA）基于 DRL 的方法，如 HGNN（Song 等人 2023 (https://arxiv.org/html/2608.03041#bib.bib16)）和 DANIEL（Wang 等人 2024 (https://arxiv.org/html/2608.03041#bib.bib15)），通过基于深度注意力的表示学习实现了强大性能。然而，这些架构依赖于多个完整注意力块和调度特定的辅助组件来建模工序与机器之间的交互，增加了参数数量、内存占用和推理延迟。随着工序和机器数量的增长，这些组件必须捕获日益复杂的交互，从而导致大型调度实例的计算开销更高。

调度决策是顺序进行的，每个决策都会立即改变调度状态，包括机器可用性和工序就绪状态。因此，调度状态在整个决策过程中不断演化。基于深度注意力的架构能够有效建模调度实体之间的交互（Song 等人 2023 (https://arxiv.org/html/2608.03041#bib.bib16); Wang 等人 2024 (https://arxiv.org/html/2608.03041#bib.bib15)）。然而，它们并非显式设计用于建模顺序决策过程中调度状态的决策依赖演化。这促使我们探索替代的表示学习器，它们能够在保持紧凑的同时高效传播调度信息。液体神经网络（LNN）最初为连续时间动态系统设计，支持以少量参数进行自适应状态更新（Akpinar 等人 2025 (https://arxiv.org/html/2608.03041#bib.bib17)），使其成为表示演化状态的有前景机制。然而，其固有的顺序状态演化限制了计算效率，并妨碍状态更新被高效并行处理。

受这些观察的启发，我们提出了 PLAN，一种并行液体启发近似网络，作为基于 DRL 的 FJSP 的轻量级表示学习框架。PLAN 将 LNN 的顺序液体状态演化重新表述为离散化且可并行化的表示学习过程。其液体启发状态更新执行主要表示学习，而浅层注意力模块提供补充的全局上下文。这种设计将主要表示学习从深度注意力转移到液体启发状态更新，大幅降低了架构复杂性。在确定性、随机和多面动态 FJSP 设置下的实验表明，PLAN 在降低模型复杂性和推理延迟的同时，提高了调度性能。

主要贡献总结如下。

- •我们提出了 PLAN，一种轻量级表示学习器，将液体启发状态更新与浅层注意力模块相结合，用于高效的 FJSP 调度。
- •我们通过基于欧拉近似将 LNN 的顺序常微分方程（ODE）动力学重新表述为可并行化的液体启发表示学习器，在保留自适应状态更新的同时实现并行计算。
- •我们将 PLAN 扩展到随机 FJSP，使用更小的随机处理模块（SPM），并通过替换原始异构图变换器（HGT）扩展到多面动态 FJSP。在确定性和动态设置下的实验表明，模型规模和推理延迟降低，同时性能得到提升。

## 问题表述与调度设置

FJSP 包括作业集合J=J1,J2,...,JnJ=\{J_{1},J_{2},\ldots,J_{n}\}和机器集合M=M1,M2,...,MmM=\{M_{1},M_{2},\ldots,M_{m}\}，其中每个作业JiJ_{i}由有序工序序列Oi=Oi1,Oi2,...,OiniO_{i}=\{O_{i1},O_{i2},\ldots,O_{in_{i}}\}组成，nin_{i}表示JiJ_{i}中的工序数量。全部工序集合记为O=⋃iOiO=\bigcup_{i}O_{i}。工序OijO_{ij}被分配到其兼容机器集Mij⊆MM_{ij}\subseteq M中的一台机器。当OijO_{ij}在机器Mk∈MijM_{k}\in M_{ij}上加工时，需要加工时间pijk>0p_{ij}^{k}>0，CijC_{ij}表示其完工时间。目标是最小化完工时间CmaxC_{\max}，即最后完成工序的完工时间。

Cmax=maxOij∈O⁡Cij,C_{\max}=\max_{O_{ij}\in O}C_{ij},\(1\)可行调度必须满足每个作业内部的先后顺序约束，为每道工序分配一台兼容机器，并确保每台机器同一时间最多加工一道工序。

由于资源条件、执行延迟和意外扰动等因素，加工时间可能不确定，其确切值在调度前可能无法获得。为了对这种不确定性进行建模，我们考虑具有随机加工时间的随机 FJSP（Smit 等人 2025 (https://arxiv.org/html/2608.03041#bib.bib5)），其中确定性加工时间pijkp_{ij}^{k}被随机变量PijkP_{ij}^{k}替代，使得工序完工时间和最终完工时间成为随机变量。我们进一步按照 (Liu 等人 2026 (https://arxiv.org/html/2608.03041#bib.bib22)) 中建立的基准配置和动态事件协议，在多面动态 FJSP 设置下评估 PLAN。

参见 图 1：所提出的 FJSP PLAN 框架概述。
## 方法论

本节介绍 DRL 表述、PLAN 框架及其关键组件以及学习过程。

### MDP 表述

调度问题被表述为马尔可夫决策过程（MDP），其中工序-机器分配决策按顺序进行，直到所有工序都被分配到机器。在每个决策步骤，DRL 智能体根据当前调度状态选择一个工序-机器对，并获得反映所得调度质量的奖励（Wang 等人 2024 (https://arxiv.org/html/2608.03041#bib.bib15)）。MDP 由状态空间S\mathcal{S}、动作空间A\mathcal{A}、转移函数P\mathcal{P}和奖励函数R\mathcal{R}定义，具体描述如下。

状态。状态sts_{t}表示决策步骤tt时的当前调度状态。对于确定性 FJSP，它由三类实体特征组成，由st={HO,HM,HOM}s_{t}=\{H_{O},H_{M},H_{OM}\}给出，其中HOH_{O}、HMH_{M}和HOMH_{OM}分别表示工序、机器和工序-机器对特征。工序特征描述工序的加工和调度状态，机器特征表征机器利用率和可用性，而工序-机器对特征捕获候选工序与机器之间的兼容性和加工关系。对于随机 FJSP，状态额外包括采样的加工时间场景，表示加工时间不确定性的多种可能实现。对于多面动态设置，它进一步捕获调度环境的变化，例如机器故障和新作业到达。

动作。在每个决策步骤tt，智能体选择一个可行动作at=(Oij,Mk)a_{t}=(O_{ij},M_{k})，将工序OijO_{ij}分配到机器MkM_{k}。动作空间At\mathcal{A}_{t}包含决策步骤tt处所有满足工序先后顺序和机器兼容性约束的可行工序-机器对。在确定性、随机和多面动态设置中使用相同的动作定义。

状态转移。一旦动作ata_{t}被执行，调度环境根据工序先后顺序和机器约束更新工序状态、机器可用性和可行动作空间，从当前状态sts_{t}生成下一个状态st+1s_{t+1}。

奖励。奖励函数设计用于鼓励具有更小完工时间的调度。在状态sts_{t}处，估计完工时间记为C^max(st)\hat{C}_{\max}(s_{t})。在执行动作后，即时奖励被表述为当前状态与下一状态估计完工时间之差，rt=C^max(st)−C^max(st+1)r_{t}=\hat{C}_{\max}(s_{t})-\hat{C}_{\max}(s_{t+1})。正奖励表示改进，而负奖励表示调度质量下降。对于随机 FJSP，估计完工时间在nn个采样的加工时间场景上评估，记为{C^max1(st),C^max2(st),...,C^maxn(st)}\{\hat{C}_{\max}^{1}(s_{t}),\hat{C}_{\max}^{2}(s_{t}),\ldots,\hat{C}_{\max}^{n}(s_{t})\}。我们采用风险价值（VaR）作为风险敏感调度目标，即f(st)=VaRα(C^max(st))f(s_{t})=\mathrm{VaR}_{\alpha}\big(\hat{C}_{\max}(s_{t})\big)，并将即时奖励定义为rt=f(st)−f(st+1)r_{t}=f(s_{t})-f(s_{t+1})。

策略。策略πθ(at|st)\pi_{\theta}(a_{t}|s_{t})将当前调度状态映射到可行动作上的概率分布。策略参数θ\theta通过与调度环境的交互进行学习。

### PLAN 框架

图1 (https://arxiv.org/html/2608.03041#Sx2.F1)展示了 PLAN 的整体架构。首先，液体启发状态动力学使得表示学习能够适应不断演化的调度环境。其次，并行近似使得液体状态更新无需顺序 ODE 积分即可高效进行，使该框架适用于大规模调度。为了实现这些思想，PLAN 聚合全局上下文信息，并执行并行液体状态更新，以学习用于下游调度决策的工序和机器表示。每个组件详述如下。

#### 液体启发状态动力学

FJSP 是一个动态决策问题，其中机器负载、工序状态和可行动作在整个调度过程中不断演化。因此，表示学习模型不仅应捕获调度实体之间的关系，还应捕获调度状态的演化。LNN（Kannan 等人 2026 (https://arxiv.org/html/2608.03041#bib.bib20)）通过自适应状态动力学自然地建模这种演化状态。隐藏状态不是学习静态映射，而是根据当前隐藏状态和调度输入连续演化，使得表示能够随着调度环境的变化而自适应。这一表述促使我们提出 PLAN，它开发了一种用于调度的高效并行近似。对于输入x(t)x(t)和隐藏状态h(t)h(t)，连续液体动力学被表述为：

dhtdt=−htτ+σ(Whht+Wxxt),\frac{\mathrm{d}h_{t}}{\mathrm{d}t}=-\frac{h_{t}}{\tau}+\sigma\left(W_{h}h_{t}+W_{x}x_{t}\right),\(2\)其中τ\tau是可学习时间常数，WhW_{h}和WxW_{x}是可训练权重矩阵，σ(⋅)\sigma(\cdot)表示非线性激活函数。给定初始隐藏状态h0h_{0}，对式 (2 (https://arxiv.org/html/2608.03041#Sx3.E2)) 中的 ODE 在时间区间[0,T][0,T]上积分，以获得演化后的隐藏状态h(T)h(T)，其中TT表示积分区间长度：

h(T)=ODE(dhdt,h0).h(T)=\mathrm{ODE}\left(\frac{\mathrm{d}h}{\mathrm{d}t},h_{0}\right).\(3\)直接数值积分增加了额外计算开销，并且不太适合 FJSP，因为 FJSP 中的决策是在离散调度步骤做出的。因此，我们采用带时间步长Δt\Delta t的一阶欧拉离散化：

ht+1=ht+Δtdhtdt.h_{t+1}=h_{t}+\Delta t\frac{\mathrm{d}h_{t}}{\mathrm{d}t}.\(4\)将式 (2 (https://arxiv.org/html/2