跳转至

A Switching Framework for Online Interval Scheduling with Predictions

会议: AAAI 2026
arXiv: 2511.16194
代码: 无
领域: 在线算法 / 学习增强算法 / 调度优化
关键词: 在线区间调度, 学习增强算法, 竞争比, 一致性-鲁棒性权衡, 随机化算法

一句话总结

针对不可撤销的在线区间调度问题，提出 SemiTrust-and-Switch 框架和 SmoothMerge 随机算法，通过在信任预测和经典贪心算法之间切换/融合，在预测准确时趋近最优（一致性），预测错误时性能优雅退化（鲁棒性和平滑性），并证明了该框架在特定实例上的紧性。

背景与动机

在线区间调度是一个经典问题：区间按到达顺序出现，算法必须立即不可撤销地接受或拒绝，目标是最大化被接受区间的总长度。经典结果表明，在最坏情况下没有确定性算法能取得常数竞争比（Lipton & Irani 1994），随机算法的下界是 \(O(\log \Delta)\)，其中 \(\Delta\) 是最长与最短区间的长度比。

然而实际场景中，往往可以通过历史数据或机器学习模型获得对未来区间的预测。近年来"学习增强算法"（algorithms with predictions）兴起，核心思路是设计能利用预测改善性能、同时在预测出错时保持鲁棒的算法。

此前的相关工作：(1) 单位权重区间调度+预测（Antoniadis et al., WADS 2023）；(2) 比例权重+可撤销设定（Karavasilis et al., 2025）。但不可撤销+比例权重这一最具实际意义的设定尚无研究，本文正是填补这个空白。

核心问题

在不可撤销的在线区间调度中，如何利用（可能不准确的）机器学习预测来提升算法性能？具体来说，如何设计算法使其： 1. 一致性好：当预测准确时，性能接近离线最优 2. 鲁棒性好：当预测完全错误时，性能不会太差 3. 平滑性好：性能随预测误差优雅退化，而非断崖式下降

这个问题的核心难点在于决策不可撤销——早期接受了错误预测的区间后，可能永久阻断后续高价值区间。

方法详解

整体框架

论文提出三层递进的算法设计： 1. Trust-and-Switch（热身）：先信任预测，发现预测出错后一次性切换到经典算法 2. SemiTrust-and-Switch（主框架）：在信任阶段仅对短区间信任预测，长区间始终贪心接受，再配合同样的切换机制 3. SmoothMerge（随机算法）：将 Trust 策略和 Greedy 策略通过概率融合，实现平滑过渡

输入是在线到达的区间序列，以及二值预测 \(\hat{O} = \{0, 1\}^n\) 表示每个区间是否应接受。输出是最大化总长度的非重叠子集。

关键设计

  1. Trust-and-Switch 框架：算法从 trust phase 开始，盲目跟随预测。每当新区间 \(I_j\) 到达时，计算评估点 \(t_j\)，比较截至 \(t_j\) 时预测解 \(|Trust(\mathcal{I})|\) 和离线最优 \(|Opt(\mathcal{I})|\) 的差距。一旦发现预测解严格差于最优，就不可逆地切换到经典 \(\theta\)-竞争算法。核心保证：1-一致性 + \(|Opt| \leq \theta \cdot |Alg| + 2k\)（\(k\) 为最大区间长度）。

  2. SemiTrust-and-Switch 框架：引入长度阈值 \(\tau\)。在 trust phase 中，长度超过 \(\tau\) 的区间直接贪心接受（不依赖预测），长度低于 \(\tau\) 的区间才依赖预测。这样即使预测不准，也不会错过高价值的长区间。代价是一致性从 1 退化为 \((1 + k/\tau)\)，但鲁棒性显著提升为 \(|Opt| \leq \max(\theta, \Delta+1) \cdot |Alg| + \tau\)。阈值 \(\tau\) 可调，控制一致性和鲁棒性之间的权衡曲线。

  3. SmoothMerge 随机算法：并行模拟 Trust 和 Greedy 两个策略。对每个到达的区间，如果两策略一致（都接受或都拒绝），则按一致决策执行；如果不一致，以概率 \(p_t\)（Trust 概率）或 \(p_g\)（Greedy 概率）随机接受。核心保证： $\(\mathbb{E}[|Alg|] \geq \max\left\{|Opt| \cdot (1-\eta) \cdot p_t \cdot (1-p_g),\quad \frac{p_g - p_t p_g}{1 - p_t p_g} \cdot |Greedy|\right\}\)$ 其中 \(\eta\) 是预测误差。通过调节 \(p_t, p_g\) 可在平滑性和鲁棒性之间连续插值。

预测模型

  • 二值预测 \(\hat{O}\)：对每个区间给出 accept/reject 建议，随区间在线到达
  • 全信息预测 \(\hat{I}\)：预测所有区间的到达时间和截止时间（更强的预测模型）
  • 一个有趣的结论是：更详细的预测或离线预测并不能改善可达的理论保证

损失函数 / 训练策略

本文是理论算法设计工作，不涉及训练。核心性能指标是竞争比的一致性和鲁棒性。

实验关键数据

实验基于真实调度数据（NASA-iPSC-1993 和 CTC-SP2-1996 并行机器调度 benchmark）：

数据集 区间数 最大截止时间
NASA-iPSC-1993-3.1 18,065 62,643
CTC-SP2-1996-3.1 77,205 71,998
  • 通过控制预测中被破坏的区间数量来模拟不同的预测误差 \(\eta\)
  • SmoothMerge 在预测误差较小时性能接近 Opt，误差增大时在 Trust 和 Greedy 之间平滑过渡
  • 当预测误差很大时，SmoothMerge 降级为接近 Greedy 的表现，不会崩溃
  • Trust 策略随预测误差增大性能急剧下降，而 SmoothMerge 退化平缓

消融实验要点

  • \(p_t = 1, p_g = 0\) 时退化为纯 Trust（完美平滑性，无鲁棒性）
  • \(p_t = 0, p_g = 1\) 时退化为纯 Greedy（完全鲁棒，无平滑性）
  • 中间取值（如 \(p_t = 0.6, p_g = 0.4\)）同时获得两个性质，但系数有所折损

亮点

  • 切换时机的精巧设计：Trust-and-Switch 在发现预测出错后只切换一次且不可逆，但通过精心选取评估点 \(t_j\)（考虑预测区间的截止时间），确保在预测准确时永远不会误触发切换——从而保证完美的 1-一致性
  • SemiTrust 中的阈值思想：长区间贪心+短区间信任预测，这个简单分治策略优雅地将鲁棒性从 \(+2k\) 改善到了 \(+\tau\)（\(\tau < k\)），且一致性损失可控
  • 冲突图分析方法：将 Opt 和 Alg 的选择建模为冲突图的连通分量来分析，这一技巧可迁移到其他在线优化问题
  • 紧性证明构造性对手：通过精心设计的对抗实例证明框架在两值实例上的最优性，展示了 consistency-robustness 的根本 tradeoff

局限性 / 可改进方向

  • 两值实例已紧，一般情况有 gap：上下界在两值（short/long）实例上匹配，但一般实例的 gap 尚未封闭
  • 仅考虑区间长度作为权重：没有扩展到任意权重的区间调度，而实际中权重可能与长度无关
  • 预测误差的粒度：当前二值预测模型比较粗糙，更精细的预测信息（如置信度）可能带来更好的保证
  • 实验规模有限：仅在两个 benchmark 上测试，缺乏对不同 \(\Delta\) 值的系统性实验
  • 潜在扩展：可撤销设定、多资源调度、带约束的调度等变体

与相关工作的对比

工作 设定 决策 主要贡献
Antoniadis et al. (WADS 2023) 单位权重 不可撤销 确定性算法紧界
Karavasilis et al. (2025) 比例权重 可撤销 二值预测下的自适应算法
本文 比例权重 不可撤销 统一框架 + 随机平滑算法

本文的核心差异是：(1) 解决了最困难的"不可撤销+比例权重"设定；(2) 提出了通用框架而非特定算法，可插入任何经典算法作为后备；(3) SmoothMerge 是首个在此设定下实现平滑性的算法。

启发与关联

  • 这类"信任-切换"范式可以迁移到其他在线最大化问题（如在线背包、匹配）
  • 冲突图分析方法值得学习，在分析贪心类算法性能时很有用
  • 预测误差 \(\eta\) 的定义方式（基于 Trust 与 Opt 的比值）可作为评估"预测对算法有多大帮助"的通用度量

评分

  • 新颖性: ⭐⭐⭐⭐ 填补了重要设定空白，框架设计有新意，但switching技术本身不算全新
  • 实验充分度: ⭐⭐⭐ 理论工作，实验仅作为补充验证，规模和多样性有限
  • 写作质量: ⭐⭐⭐⭐⭐ 结构清晰，从warm-up逐步推进到主框架和随机化，proof sketch直观
  • 价值: ⭐⭐⭐⭐ 对学习增强在线算法领域有贡献，框架的模块化设计具有通用性