低成本标签，可靠选择：用于作业车间调度的Rollout校准超启发式算法

# 针对作业车间调度的滚动校准超启发式方法
来源: https://arxiv.org/html/2605.23957
## 低成本标签，可靠选择：针对作业车间调度的滚动校准超启发式方法

Yanxiao Li¹  Yifu Zhao¹  Zhenhong Peng³  Baili Lu¹  Dexing Yao¹  Haochen Li¹  Qinbin He¹  Sio-Kei Im⁴  Yapeng Wang¹  & Xu Yang¹  
¹澳门理工大学应用科学学院，澳门，999078，中国  
²琶洲实验室（黄埔），广州，510555，中国  
³仲恺农业工程学院动物科技学院，广州，510225，中国  
⁴澳门理工大学，澳门，999078，中国  
通讯作者: [email protected]

###### 摘要

学习辅助的超启发式方法能够在保持构造性作业车间调度问题（JSSP）启发式方法的可行性和可解释性的同时，在调度规则之间进行选择。其主要计算成本在于标签生成，而非模型拟合，因为每个监督标签通常需要从部分调度出发对候选规则进行滚动展开。我们研究了这一标签成本问题，同时关注一个可靠性问题：除非预测的增益是可信的，否则学习到的选择器不应偏离一个强大的默认规则。所提出的选择器使用遗憾归一化的滚动标签、上下文KNN不确定性估计，以及一个仅在预测改进超过不确定性调整后的边际时才激活的门控机制。我们还通过改变滚动深度和广度来衡量成本-质量权衡。在合成JSSP实例上，门控选择器在学习到的选择器中实现了最低的平均RPD，接近最佳固定调度规则，并将Random-HH的平均RPD降低了一个数量级以上。

## 1 引言

选择超启发式方法在构建调度过程中选择低级规则。对于JSSP，这为固定调度规则和端到端学习的构造器之间提供了一个有用的中间地带：动作空间保持较小，通过构造保持可行性，并且规则选择直接可解释。

该设置属于LEAD主题中关于超启发式方法和算子/算法选择的部分。学习器不设计新的调度规则；它决定在给定的部分调度下，哪个现有规则应该被信任。这种分离将规则选择与发明新搜索算子的独立问题区分开来。

主要瓶颈在于监督。一种常见的标注器从部分调度滚动每个候选规则，并记录最终的完工时间。这提供了直接的监督，但对于一个还有 \( T \) 个剩余决策的状态，完全滚动一次的成本是 \( O(\|H\|T) \) 次模拟。第二个问题出现在推理时：学习到的分数可能因偶然原因略好于默认规则，而总是遵循最低分数可能会输给一个强大的固定规则。

我们的公式将这些问题联系在一起：将滚动结果存储为每个状态的遗憾，而不是原始或下界归一化的完工时间，这样目标反映了规则的本地区排名。然后，选择器使用来自上下文KNN回归器的方差估计，仅当预测的边际大于不确定性惩罚时才偏离默认规则。为了使监督成本明确，我们改变滚动深度和广度，并报告由此产生的成本-质量权衡。

研究范围不同于专门的JSSP求解器、深度RL调度器（如L2D (Zhang等人, 2020)）和程序搜索系统（如FunSearch (Romera-Paredes等人, 2024) 和 ReEvo (Ye等人, 2024)）。本贡献在于提供了一个可复现的、仅使用CPU的选择器和评估协议，用于研究学习辅助超启发式方法中的标签成本和保守切换问题。

因此，实验衡量了遗憾标签的价值、不确定性门控的可靠性优势，以及在选择器失去其优势之前可以移除多少滚动深度或广度。这一评估对应了一个实际部署选择：在使用学习到的选择器之前，应该花费多少模拟预算。

## 2 相关工作

选择超启发式方法与我们设置最接近，因为它们为组合优化问题选择低级启发式方法 (Burke等人, 2013)。在线学习变体使用多臂老虎机 (Fialho等人, 2010) 或强化学习 (Özcan等人, 2010) 在每个决策点控制规则选择。先前关于JSSP调度规则选择的工作包括Ingimundardottir和Runarsson (2018) 的模仿学习选择器以及RANFORS (Jun等人, 2019)，其中规则优先级是从实例特征中学习到的。

基于学习的调度提供了另一条研究线。最近的研究将JSSP视为一个顺序决策过程，如L2D (Zhang等人, 2020) 和 ScheduleNet (Park等人, 2021)，通常使用策略梯度进行训练。相关的神经组合优化方法，如POMO (Kwon等人, 2020)，也说明了学习策略对训练分布的依赖性。相比之下，我们的选择器使用滚动标签、工程化状态特征和一个仅CPU的KNN回归器。

滚动策略提供了本文使用的标签生成机制。Bertsekas风格的滚动策略 (Bertsekas, 2013) 通过模拟一个基础策略来估计一个动作的价值。我们借鉴这一思想用于标签生成而非在线控制，这使得模拟成本可以在许多决策点之间摊销。基于代理模型的超启发式方法 (Horn and Bischl, 2016; Branke等人, 2016) 同样以模拟成本换取泛化能力。我们的Pareto扫描将滚动成本可视化，而不是将其视为固定的预处理步骤。

大语言模型和代理驱动的算法设计相关但处理的是流程的不同部分。基于大语言模型的系统，如EoH (Liu等人, 2024)、FunSearch (Romera-Paredes等人, 2024) 和 ReEvo (Ye等人, 2024)，可以直接生成或改进启发式代码。我们的方法保持规则池固定，并研究一个紧凑的选择器何时应信任其预测。

这项工作也与元启发式设计和应用相关，在这方面，LEAD研究通常通过设计新的移动模式、更新方程或混合预测流程来改进搜索算法。近期的例子包括用于工程设计的TSWOA (Wei等人, 2025) 和几何WOA (Wei等人, 2026b)、用于数值优化的MRBMO (Lu等人, 2025)，以及元启发式辅助的预测模型如NAWOA-XGBoost (Wei等人, 2026a) 和 ASKSSA-CNN-BiLSTM (Li等人, 2026)。这些研究修改了优化器本身。我们的工作是互补的：低级规则是固定的，学习仅用于在这些规则中进行选择。

## 3 方法

### 3.1 JSSP与选择超启发式方法

一个JSSP实例是一个元组 \((\mathcal{J}, \mathcal{M}, \pi, p)\)，其中每个作业 \(j \in \mathcal{J}\) 在机器 \(\mathcal{M}\) 上有一个有序的操作序列 \(\pi_j\)，并带有加工时间 \(p\)。一个串行调度生成器 (Giffler and Thompson, 1960) 通过反复从就绪作业集合中选择下一个操作来构建一个可行调度。完工时间 \(C_{\max}\) 是最大的作业完成时间。我们使用标准调度规则调查和作业车间基准 (Panwalkar and Iskander, 1977; Holthaus and Rajendran, 1997) 中涵盖的经典优先级调度规则。规则池 \(\mathcal{H}\) 包含 SPT、LPT、MWKR、LWKR、MOPNR、FIFO 和 Random。这些规则分别按最短或最长加工时间、最多或最少剩余工作量、最多剩余操作数、先进先出顺序或均匀随机选择进行选择。一个选择超启发式方法在每个决策点根据当前状态 \(s\) 选择一个 \(h \in \mathcal{H}\)。

### 3.2 遗憾归一化滚动标签

给定一个部分状态 \(s\)，我们通过从 \(s\) 开始使用 \(h\) 进行下一步然后继续滚动来完成调度，从而评估每个候选 \(h\)。设 \(m(s, h)\) 表示由此产生的完工时间。经典的归一化标签是 \(m(s, h) / \mathrm{LB}(I)\)，其中 \(\mathrm{LB}\) 是实例下界。我们转而使用每状态遗憾：

\[
r(s, h) = \frac{m(s, h) - \min_{h' \in \mathcal{H}_s} m(s, h')}{\min_{h' \in \mathcal{H}_s} m(s, h')},
\tag{1}
\]

其中 \(\mathcal{H}_s \subseteq \mathcal{H}\) 是在状态 \(s\) 评估的候选子集。通过构造，\(r(s, h) \geq 0\)，且对于最佳规则 \(r(s, h) = 0\)。因此目标是一个本地的排名信号，而非绝对完工时间尺度。

### 3.3 不确定性门控选择

我们在 \((s, h)\) 对上拟合一个上下文KNN回归器，其特征在3.5节描述。对于测试状态 \(s\)，我们为每个 \(h \in \mathcal{H}\) 计算：

\[
\hat{r}(s, h) = \frac{\sum_{i \in N_k(s, h)} w_i y_i}{\sum_i w_i},
\quad
\hat{\sigma}(s, h) = \mathrm{std}_{i \in N_k(s, h)}(y_i),
\tag{2}
\]

其中 \(N_k\) 是 \(k\) 个最近邻的训练集合，且 \(w_i = 1/(d_i + \epsilon)\)。设 \(h^\star = \arg\min_h \hat{r}(s, h)\)，并设 \(h_0\) 为一个固定的默认规则（在我们的实验中，是训练集上最佳的固定规则）。*门控*策略仅在预期相对于 \(h_0\) 的改进超过一个置信边界时应用 \(h^\star\)：

\[
\pi_{\mathrm{gated}}(s) = 
\begin{cases} 
h^\star & \text{如果 } \hat{r}(s, h_0) - \hat{r}(s, h^\star) > \lambda \, \hat{\sigma}(s, h^\star), \\
h_0 & \text{否则}.
\end{cases}
\tag{3}
\]

超参数 \(\lambda\) 权衡了激进性与可靠性：\(\lambda = 0\) 恢复为 \(\arg\min_h \hat{r}\)，而大的 \(\lambda\) 则收敛到默认规则。我们还报告了一个LCB风格的变体 \(h_{\mathrm{lcb}} = \arg\min_h \hat{r}(s, h) - \lambda \hat{\sigma}(s, h)\)。

### 3.4 滚动预算权衡

标签生成的成本由滚动广度 \(b = |\mathcal{H}_s|\) 和滚动深度 \(\kappa\) 决定。广度决定了每个状态评估多少个候选规则；深度决定了在完成调度并恢复默认规则 \(h_0\) 之前，候选规则被跟随多长时间。完全滚动设置中，\(\kappa = \infty\) 且 \(b = |\mathcal{H}|\) 是最昂贵的情况。通过在一个小网格上变化 \((\kappa, b)\)，我们绘制出一条帕累托曲线，将标签生成成本（以滚动步数或挂钟秒数衡量）与学习到的选择器的测试RPD联系起来。

### 3.5 状态特征

状态表示包含35个实例级和状态级特征，涵盖实例大小、加工时间统计量、机器负载不平衡度、调度进度、就绪集加工时间、剩余工作量以及机器和作业就绪时刻，以及一个7维的候选启发式独热编码。所有特征在训练时进行 \(z\)-归一化，并在推理时重复使用相同的归一化。

### 3.6 训练流程

对于每个训练实例，我们通过遵循均匀随机调度规则来采样部分调度。在每个采样状态下，标注器评估候选规则的一个子集，将每个候选应用于下一个决策，并根据滚动深度设置完成剩余调度。完全深度意味着候选规则被跟随至终止完成；有限深度意味着在 \(\kappa\) 个候选引导步骤后，滚动返回默认规则。记录的完工时间被转换为归一化目标或公式(1)中的遗憾目标。

默认规则 \(h_0\) 在训练集上被选为使平均完工时间最低的固定规则。这使得门控测试变得保守：学习到的选择器必须证明偏离一个在部署分布上已经具有竞争力的规则是合理的。在推理过程中，KNN模型在每个决策点为每个候选规则打分，门控（公式(3)）决定是否偏离 \(h_0\)。

## 4 实验

### 4.1 设置

我们在三种规模的合成JSSP实例上进行评估：\(6 \times 6\)、\(10 \times 10\) 和 \(15 \times 10\)（作业 \(\times\) 机器）。每个实例为每个作业绘制一个独立的随机机器排列，加工时间在 \([1, 99]\) 上均匀分布。对于每种规模，我们使用150个训练实例和40个留出测试实例。

选择器是一个基于CPU的上下文KNN回归器，\(k = 7\)。其拟合步骤对滚动特征向量进行归一化并存储其目标；推理时使用NumPy在CPU上计算最近邻距离。滚动标签从每个训练实例的25个采样状态和每个实例在均匀随机规则混合下的三个探索轨迹中收集。默认训练设置在每个采样状态下评估所有七个候选规则，并将每个候选滚动至终止完成，广度 \(b=7\) 且深度 \(\kappa = \infty\)，除非4.5节明确变化滚动预算。门控默认 \(h_0\) 自动选为训练集上最佳的固定规则，在我们的规模上通常是FIFO或MOPNR。

学习到的配置包括：*Norm-Argmin*（使用下界归一化滚动标签，采用 \(\arg\min\) 选择）、*Regret-Argmin* 和 *Regret-Gated*（\(\lambda=1\)）。我们将它们与相同的调度规则基线进行比较：SPT、LPT、MWKR、LWKR、MOPNR 和 FIFO (Panwalkar and Iskander, 1977; Holthaus and Rajendran, 1997)；一个*Random-HH*基线（在每个决策点均匀随机选择规则，取五个种子平均）；以及*Oracle-Fixed*参考（事后为每个实例选择最佳固定规则）。我们报告相对于这个事后参考的平均相对百分比偏差（RPD）、中位数RPD以及每种方法在测试实例上取得最佳结果的次数。Oracle-Fixed仅用于归一化性能，并非可部署的调度策略。实验在Ubuntu 20.04上进行，配备Intel Xeon E5-2698 v4 CPU（40个逻辑核心）、251 GiB RAM和Python 3.13；标签生成未使用GPU。