摘要
1) 一句话总结
本文总结了 SPAA 2025 的一项研究，首次提出了在云环境计算容量随时间波动的条件下，最大化非抢占式任务吞吐量的常数因子近似算法。
2) 关键要点
- 背景与挑战：现代云环境的计算容量会因硬件故障或高优先级任务抢占而动态波动，调度非抢占式（不可暂停恢复）任务面临极高的进度丢失风险。
- 任务模型：任务包含发布时间、截止日期、处理时间和权重四个属性，目标是在不超过当前实时容量的前提下最大化吞吐量（完成任务的总权重）。
- 离线环境（单位利润）：在未来任务和容量变化已知的离线环境下，针对单位利润任务，采用优先调度最早完成任务的“贪心”策略可实现 1/2 的近似比。
- 离线环境（不同利润）：针对具有不同利润权重的任务，利用原始-对偶框架（primal-dual framework）可实现 1/4 的近似比。
- 在线环境（标准模型失效）：在任务实时到达的在线环境中，标准的非抢占式算法因单次错误调度可能阻塞大量后续任务，其竞争比趋近于零。
- 在线环境（带重启的中断）：如果允许中断当前任务且保留任务以便后续重试，贪心变体算法可以实现 1/2 的竞争比。
- 在线环境（不带重启的中断）：如果被中断的任务必须永久丢弃且丢失所有进度，所有常规在线算法的竞争比再次趋近于零。
- 共同截止日期场景算法：针对所有任务共享同一截止日期（如夜间批处理）的不可重启场景，提出了一种基于“添加、替换、中断、丢弃”四种操作的新算法，首次实现了 1/11 的常数竞争比。
3) 风险与缺口
- 理论上限差距：在在线环境中，当前算法实现的 1/11 竞争比与 1/2 的理论上限之间仍存在明显差距，表明可能存在更高效的算法。
- 信息假设局限：当前模型假设容量的变化情况是提前已知的，尚未完全覆盖对未来容量了解不完全的实际场景。
- 任务中断风险：在不带重启的中断模型中，任务一旦因容量下降或新任务抢占而被中断，所有已完成的工作进度将彻底丢失且任务被永久丢弃。
正文
作者：Manish Purohit，Google Research 研究科学家
日期：2026年2月11日
在算法任务调度的世界中，计算资源通常被视为静态的：一台服务器拥有固定数量的 CPU，或者一个集群拥有恒定数量的可用机器。然而，现代大规模云计算的现实却充满了动态变化。由于硬件故障、维护周期或电力限制，资源会不断发生波动。
更重要的是，在分层调度系统中，高优先级任务通常会按需占用资源，留给低优先级批处理任务的“剩余”容量是随时间变化的。想象一家餐厅，不同时段会有桌位被预留给 VIP 客户；如何将普通顾客安排在剩余的桌位上，就成了一个复杂的难题。
当这些低优先级任务是非抢占式（non-preemptive，即不能暂停并留待以后恢复）时，调度的风险极高。如果一个任务因为容量下降而被迫中断，所有的进度都会丢失。调度器必须做出抉择：我们是现在就开始这个耗时较长的任务，并承担未来容量下降的风险？还是等待一个更安全的窗口期，但可能因此错过截止日期？
在 SPAA 2025 大会上发表的论文《时变容量下的非抢占式吞吐量最大化》（Non-preemptive Throughput Maximization under Time-varying Capacity）中，我们首次开启了在可用容量随时间波动的环境下，如何最大化吞吐量（即成功任务的总权重或数量）的研究。我们的研究为该问题的多个变体提供了首个常数因子近似算法（即无论问题规模多大，算法结果与最优解之间的“差距”都能保证是一个固定、稳定的数值），为在波动的云环境中构建更稳健的调度器提供了理论基础。
定义调度问题
我们的工作重点是设计一个能够捕捉多项关键约束的调度模型。我们考虑一台机器（或集群），其容量配置随时间变化。该配置决定了在任何给定时刻可以并行运行的最大任务数。我们面临一系列潜在任务，每个任务具有四个关键属性：
- 发布时间（Release time）：任务可以开始运行的时间。
- 截止日期（Deadline）：任务必须完成的硬性期限。
- 处理时间（Processing time）：机器处理该任务所需的持续时间。
- 权重（Weight）：成功完成该任务后获得的价值。
我们的目标是选择一个任务子集并进行调度，使得每个选定的任务都能在其有效窗口内连续运行。关键的约束在于，任何时候运行的任务总数都不能超过当前的容量。我们的最终目标是最大化吞吐量，即所有已完成任务的总权重。
我们在两种不同的环境中探讨了这个问题：
- 离线环境（Offline）：提前已知未来的任务到达情况和容量变化。
- 在线环境（Online）：任务实时到达，调度器必须在不知道未来到达情况的前提下做出不可撤销的决定。不过，容量的变化情况依然是提前已知的。
离线环境的调度结果
在可以提前规划的离线环境中，我们发现简单的策略表现得惊人地好。由于在这种环境下寻找“最优”调度方案被认为是“NP困难”的（即没有已知的捷径可以找到完美答案），我们将重点放在具有严格近似保证的算法上。
我们分析了一种名为“贪心（Greedy）”的短视策略，它会迭代地调度最早完成的任务。我们证明，当任务具有单位利润时，这种简单的启发式算法能够实现 1/2 的近似比（在这种背景下，这通常是能达到的最好结果）。这意味着，即使在由对手恶意选择任务和容量配置的最坏情况下，我们简单的算法也保证能调度至少一半的最优任务数。这与贪心算法在只能同时处理一个任务的简单单位容量机器上所享有的保证相匹配。当不同任务具有不同的相关利润时，我们利用原始-对偶框架（primal-dual framework）实现了 1/4 的近似比。
在线环境的调度结果
真正的复杂性在于在线环境：任务动态到达，调度器必须立即做出不可撤销的决定，且不知道接下来会到达什么任务。我们通过“竞争比（competitive ratio）”来量化在线算法的性能，即我们的在线算法吞吐量与预先知道所有任务的最优算法吞吐量在最坏情况下的对比。
标准的非抢占式算法在这里完全失效，它们的竞争比趋近于零。这是因为，仅仅调度一个长任务的糟糕决定，就可能毁掉未来调度许多小任务的可能性。在这个例子中，如果假设每个完成的任务无论长短都能带来相等的权重，那么完成许多短任务显然比完成一个长任务要有利可图得多。
为了使在线问题变得可解，并反映现实世界中的灵活性，我们研究了两种允许在出现更好机会时中断活动任务的模型（不过，只有重新启动并随后以非抢占方式完成的任务才算作成功）。
带重启的中断（Interruption with restarts）
在这个模型中，在线算法被允许中断当前正在执行的任务。虽然被中断任务已经完成的部分工作会丢失，但任务本身仍保留在系统中，并且可以重试。
我们发现，允许任务重启所提供的灵活性非常有益。一种迭代调度最早完成任务的贪心变体算法，继续实现了 1/2 的竞争比，这与离线环境中的结果相匹配。
不带重启的中断（Interruption without restarts）
在这个更严格的模型中，被中断任务的所有工作都会丢失，并且该任务会被永久丢弃。不幸的是，我们发现在这个严格模型中，任何在线算法都可能遇到一系列任务，迫使其做出阻碍未来完成更多工作的决定。所有在线算法的竞争比再次趋近于零。
对上述困难情况的分析引导我们将注意力转向一个实际场景：所有任务共享一个共同的截止日期（例如，所有数据处理必须在夜间批处理运行结束前完成）。针对这种共同截止日期的场景，我们设计了新颖的常数竞争算法。我们的算法非常直观，这里以单位容量配置（即任何时候只能调度一个任务）的简单设置来描述该算法。
在这种设置下，我们的算法通过将已经到达的任务分配到不相交的时间区间来维护一个暂定调度（tentative schedule）。当新任务到达时，算法会从以下四个操作中采取第一个适用的操作来修改暂定调度：
- 添加（Add）：将新任务放入一个空闲区间，加入暂定调度。
- 替换（Replace）：如果新任务明显更小，则替换暂定调度中的另一个未来任务。
- 中断（Interrupt）：如果新任务比当前正在执行任务的剩余时间还要小，则中断当前任务。
- 丢弃（Discard）：丢弃新到达的任务。
我们的主要结果表明，将该算法推广到任意容量配置时，首次为该问题提供了常数竞争比。具体而言，我们获得了 1/11 的竞争比。虽然保证调度约 9% 的最优任务数听起来像是一个较弱的保证，但这是一个即使在最具对抗性的情况下也成立的最坏情况保证。
结论与未来方向
随着云基础设施变得越来越动态，调度算法中静态容量的假设已不再成立。本文开启了时变容量下吞吐量最大化的正式研究，弥合了理论调度模型与数据中心波动现实之间的差距。
尽管我们建立了强大的常数因子近似，但仍有发展空间。在线环境中 1/11 的竞争比与 1/2 的理论上限之间存在差距，这表明可能存在更高效的算法。探索随机算法或对未来容量了解不完全的场景，可能会为实际应用带来更好的结果。
致谢
本研究是与 Aniket Murhekar（伊利诺伊大学厄巴纳-香槟分校）、Zoya Svitkina（Google Research）、Erik Vee（Google Research）和 Joshua Wang（Google Research）共同完成的合作成果。