Low-Cost Labels, Reliable Choices: Rollout-Calibrated Hyper-Heuristics for Job Shop Scheduling

技术摘要：低成本标签，可靠选择

问题陈述
本文通过选择超启发式（selection hyper-heuristics）的视角探讨作业车间调度问题（JSSP）。虽然学习辅助的超启发式在固定调度规则与端到端学习构建器之间提供了中间路径，既保持了可行性又具备可解释性，但它们面临两个主要瓶颈：

1. 标签生成成本：监督学习需要通过对候选调度规则从部分调度表“展开”（rolling out）至终端状态来生成标签。在每个决策点对每个候选规则进行完整展开，会产生 $O(|H|T)$ 的计算成本，其中 $|H|$ 是规则数量，$T$ 是剩余决策数。
2. 选择的可靠性：由于噪声或过拟合，学习到的选择器可能会意外预测出比强默认规则略好的改进。盲目遵循最低预测分数可能导致性能相较于稳健的固定规则出现退化。

作者旨在研究生成这些监督标签的成本与所得选择器可靠性之间的权衡，具体关注如何防止学习模型在预测收益不可信时，从强默认规则切换出去。

方法论
所提出的方法称为展开校准超启发式（Rollout-Calibrated Hyper-Heuristics），整合了三个核心组件：

1. 遗憾归一化展开标签：
   作者不使用原始完工时间或下界归一化的完工时间作为目标，而是定义了一个每状态的遗憾标签：
   $$r(s, h) = \frac{m(s, h) - \min_{h' \in H_s} m(s, h')}{\min_{h' \in H_s} m(s, h')}$$
   其中 $m(s, h)$ 是在状态 $s$ 应用规则 $h$ 所产生的完工时间。这将目标转化为局部排序信号，即特定状态下最佳规则的遗憾为 0，从而隔离了该特定上下文中规则的相对性能。

2. 不确定性门控选择：
   系统采用上下文 K 近邻（KNN）回归器来预测每个候选规则的遗憾。为确保可靠性，引入了门控机制。选择器仅在预期改进超过经不确定性调整的边际时，才从固定默认规则（$h_0$，在训练集上选定的最佳固定规则）切换到预测的最佳规则（$h^*$）：
   $$\pi_{gated}(s) = \begin{cases} h^* & \text{if } \hat{r}(s, h_0) - \hat{r}(s, h^*) > \lambda \hat{\sigma}(s, h^*) \\ h_0 & \text{otherwise} \end{cases}$$
   此处，$\hat{\sigma}$ 是 $k$ 个最近邻的标准差（作为不确定性估计），$\lambda$ 是控制切换激进程度的超参数。

3. 展开预算权衡：
   作者明确改变展开广度（$b$，评估的候选规则数量）和展开深度（$\kappa$，候选规则在回退到默认规则之前遵循的步数），以绘制标签生成成本（模拟步数/墙钟时间）与最终测试性能（相对百分比偏差，RPD）之间的帕累托前沿。

主要贡献

• 保守选择框架：本文提出了一种门控机制，将可靠性置于激进优化之上，确保学习到的选择器在没有高置信度的情况下不会放弃强固定规则。
• 基于遗憾的监督：通过使用每状态遗憾而非绝对完工时间，该方法专注于局部规则排序，这对于部分调度表中的决策更为稳健。
• 显式的成本 - 质量分析：与许多将标签生成视为固定预处理步骤的研究不同，本研究系统地改变展开深度和广度，以量化成本 - 质量权衡，为部署预算提供实用指导。
• 仅 CPU 的可复现性：整个流程，包括标签生成、KNN 拟合和推理，均设计为在 CPU 上运行，无需 GPU 加速，这与深度强化学习方法形成对比。

实验结果
实验在规模为 $6\times6$、$10\times10$ 和 $15\times10$ 的合成 JSSP 实例上进行。

• 性能：遗憾门控选择器在所有规模的所有学习到的方法中实现了最低的平均 RPD。它非常接近最佳固定调度规则（在这些合成设置中通常为 FIFO 或 MOPNR），平均 RPD 差距分别为 0.70、0.67 和 0.06。
• 鲁棒性：门控方法将 Random-HH 基线的平均 RPD 降低了不止一个数量级（从约 36–54% 降至约 0.8–2.8%）。
• 消融实验：研究证实，门控比总是切换（argmin 选择）更稳定。最佳结果是在使用遗憾标签且置信度阈值 $\lambda=1.0$ 时获得的。下置信界（LCB）变体表现较差，表明不确定性更适合作为切换测试，而非直接作为分数奖励。
• 成本分析：完整展开（$\kappa=\infty, b=|H|$）产生了最佳质量，但成本最高。浅层展开（$\kappa=1$）导致 RPD 显著升高。中等深度提供了可行的权衡，在保持可接受质量的同时大幅减少了模拟步数。

意义与主张
本文谦逊地声称，为研究学习辅助超启发式中的标签成本和保守切换，提供了一个可复现的、仅 CPU 的选择器和评估协议。

作者将其工作定位为对专用求解器、深度强化学习调度器（如 L2D、ScheduleNet）以及大语言模型驱动的程序搜索（如 FunSearch、ReEvo）的补充。虽然这些系统针对设计空间中的不同点（通常发明新算子或端到端策略），但本研究隔离了在现有可解释规则中进行选择的问题。

其主要意义在于解决实际的部署挑战：应花费多少模拟预算来生成标签，以及如何确保学习到的选择器不会因切换过于频繁而降低性能。作者指出，他们的发现特定于所测试的合成、静态和确定性环境。他们承认，扩展到工业实例或动态环境（如机器故障、在线到达）将需要不同的成本 - 质量权衡，并可能需要不同的标签生成动态。本文并不声称能普遍解决 JSSP，而是提供了关于如何使学习辅助超启发式变得可靠且具成本效益的受控研究。