用少量预中断提升调度效率，让预测更准时性能更好
Learning-Augmented Online Scheduling with Parsimonious Preemption
- 引入精准预测减少任务中断次数，兼顾延迟与开销
- 单机和异构机场景下每任务仅需常数次中断，竞争比为O(1)
- 首次实现非同质与可变任务的有限中断理论保障
学习增强算法通过融合可能带有噪声的预测，突破了传统在线调度的最坏情况性能下界。现有方法虽优化了任务延迟，但依赖频繁且无差别的中断，忽视了算法性能与中断复杂度之间的权衡。本文首次系统研究了在限制中断次数的前提下优化延迟的调度方法。理论证明：在预测准确时，单机与无关并行机均可实现每任务仅 $O(1)$ 次中断，且竞争比为 $O(1)$；中断代价随预测误差对数增长。本工作首次为异构机器和可变任务提供了有界中断保证，扩展了学习增强框架在更受约束、更贴近实际场景中的适用性。实验验证了算法有效性。
原文摘要 · Abstract (English)
Learning-augmented algorithms have emerged as a powerful paradigm to surpass traditional worst-case lower bounds by integrating potentially noisy predictions. While this framework has seen success in online scheduling, existing work primarily optimizes job latency while relying on frequent, ``blind'' preemptions. This ignores the fundamental trade-off between algorithmic performance and preemption complexity. We provide the first systematic study of learning-augmented scheduling that curbs preemption while optimizing latency. We establish that the gap between theoretical latency bounds and preemption overhead can be bridged with solid analytical foundations. Our results include $O(1)$-competitive algorithms for single and unrelated parallel machines with only $O(1)$ preemptions per job under accurate predictions, with overhead scaling logarithmically with the prediction error. By providing the first bounded-preemption guarantees for unrelated and malleable machines, we extend the theoretical reach of the learning-augmented framework to more constrained and realistic settings. Finally, our algorithms are validated through experiments.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。