Minimizing the Weighted Makespan with Restarts on a Single Machine

基本信息

• 论文ID: 2510.09589
• 标题: Minimizing the Weighted Makespan with Restarts on a Single Machine
• 作者: Aflatoun Amouzandeh, Klaus Jansen, Lis Pirotton, Rob van Stee, Corinna Wambsganz
• 分类: cs.DS (数据结构与算法)
• 发表时间: 2025年10月10日
• 论文链接: https://arxiv.org/abs/2510.09589

摘要

本文研究了单机环境下带重启机制的加权最大完成时间最小化问题。重启机制类似于抢占但更弱：作业可以被中断，但必须从头开始重新运行，而不是从中断点恢复。目标是最小化加权最大完成时间，定义为所有作业的最大加权完成时间。研究建立了确定性在线算法竞争比的下界1.4656，针对所有作业具有相同处理时间的情况，设计并分析了一个确定性在线算法，将竞争比改进至优于1.3098，并证明了该情况下1.2344的下界。

研究背景与动机

问题定义

本文研究的核心问题是单机调度中的加权最大完成时间最小化问题，记为1|rj, online, restart|WCmax。每个作业j具有以下特征：

• 处理时间pj
• 到达时间rj
• 权重wj

目标函数为WCmax = max{wjCj}，其中Cj是作业j的完成时间。

研究重要性

1. 理论意义：最大完成时间最小化是调度理论中的基础问题，具有重要的理论价值
2. 实际应用：在云计算、操作系统任务调度等场景中，作业可能因为更高优先级任务的到达而被中断并重启
3. 模型创新：重启模型比传统的抢占-恢复模型更符合某些实际应用场景

现有方法局限性

• Li 12对单机问题建立了竞争比下界2，并提供了竞争比为3的在线算法
• Chai等人4将单机问题的竞争比改进至2
• 对于相同处理时间的情况，Li提出了最优竞争比为(√5+1)/2的算法
• Liang等人13在单次重启限制下研究了该问题，但与本文的无限重启模型不同

核心贡献

1. 建立了一般情况下的下界：证明了任何确定性在线算法的竞争比至少为R₁ ≈ 1.4656，其中R₁是方程R₁³ - R₁² - 1 = 0的实根
2. 设计了改进的算法：针对单位处理时间情况，提出了Limited Largest Weight (LLW)算法，竞争比优于1.3098
3. 提供了紧致的分析：证明了单位处理时间情况下的下界R₂ ≈ 1.2344，其中R₂是方程4R₂³ - R₂² - 6 = 0的实根
4. 完善了理论框架：为带重启的调度问题提供了系统的分析方法

方法详解

任务定义

输入：一系列在线到达的作业，每个作业j有到达时间rj、处理时间pj和权重wj 输出：一个调度方案，使得加权最大完成时间WCmax = max{wjCj}最小 约束：作业可以被重启（从头开始），但不能从中断点恢复

核心算法：Limited Largest Weight (LLW)

LLW算法的核心思想是在贪心策略（优先处理重作业）和时间效率之间找到平衡。算法规则如下：

1. 初始阶段：第一个到达的作业立即开始处理
2. 决策规则：
   • 如果在时间t ≥ (2-R)/(R-1) ≈ 2.2279开始作业，则运行LW算法且不允许中断
   • 如果在时间t < (2-R)/(R-1)开始作业，则运行LW算法允许中断直到时间t' = (t+2)/R - 1
3. LW-phase概念：对于在时间t < (2-R)/(R-1)开始的作业，区间(t, t')称为LW-phase
4. 中断更新：如果在时间ti发生中断，则更新t := ti并重新计算t'

技术创新点

1. 时间阈值设计：通过数学分析确定关键时间点(2-R)/(R-1)，在此之前允许中断，之后禁止中断
2. 动态阈值调整：LW-phase的结束时间会根据中断时间动态调整
3. 竞争比分析：通过"good set"的概念系统分析算法的竞争比

理论分析

下界证明方法

一般情况下界（定理1）： 构造对抗实例：

• 时间0：作业1到达，w₁=1, p₁=1
• 时间r₂ = 1/(R₁(R₁-1)) - 1：作业2到达，w₂=1/(R₁-1), p₂=0

通过案例分析证明任何算法的竞争比至少为R₁ ≈ 1.4656。

单位时间情况下界（定理3）： 构造更复杂的对抗实例，涉及4个作业的序列，证明竞争比至少为R₂ ≈ 1.2344。

上界证明方法

定理2的证明采用了反证法和案例分析：

1. 假设存在最小反例
2. 定义"good set"概念
3. 通过5个关键性质逐步排除所有可能的反例情况

关键性质包括：

• Property 1：作业1在时间s₁到达并立即开始
• Property 2：存在被中断的作业，且满足特定时间约束
• Property 3-5：逐步限制可能的调度模式

实验设置

理论验证方法

本文主要是理论工作，采用数学证明而非实验验证：

1. 下界构造：通过构造对抗实例并优化参数
2. 计算机辅助：使用计算机优化对抗实例的参数
3. 精确分析：通过求解方程组得到精确的竞争比界

关键参数

• R₁ ≈ 1.4656：一般情况竞争比下界
• R ≈ 1.3098：单位时间情况LLW算法竞争比
• R₂ ≈ 1.2344：单位时间情况竞争比下界

主要结果

竞争比结果总结

与现有工作比较

• 改进幅度：相比Li的结果，在单位处理时间情况下从(√5+1)/2 ≈ 1.618改进到1.3098
• 理论贡献：首次在重启模型下给出了紧致的分析

算法性能保证

LLW算法保证：

• 竞争比严格小于1.3098
• 该界是紧致的（存在达到该比率的实例）

相关工作

调度理论基础

• Graham等人9建立了调度问题的三域记号系统
• 经典最大完成时间问题已被广泛研究

加权最大完成时间研究

• Feng和Yuan16首次考虑单机加权最大完成时间问题
• Li12建立了在线版本的下界2和上界3
• Chai等人4将竞争比改进至2

重启模型研究

• Shmoys等人17首次引入重启概念
• 重启模型在多种目标函数下被证明能改善在线算法性能1,2,11,18
• Liang等人13研究了限制重启次数的变体

结论与讨论

主要结论

1. 理论界限：确立了带重启的加权最大完成时间问题的竞争比界限
2. 算法设计：LLW算法在单位处理时间情况下实现了显著改进
3. 分析方法：提供了系统的竞争比分析框架

局限性

1. Gap存在：单位处理时间情况下仍存在约0.075的上下界gap
2. 一般情况：对于一般处理时间情况，仅提供了下界，缺少匹配的上界算法
3. 实际应用：理论分析缺少实际应用场景的验证

未来方向

1. 缩小Gap：进一步改进算法或提高下界以缩小理论gap
2. 一般情况算法：为一般处理时间情况设计竞争比接近1.4656的算法
3. 扩展模型：考虑多机、并行批处理等更复杂的调度环境

深度评价

优点

1. 理论严谨性：数学证明完整，逻辑清晰
2. 技术创新：LLW算法的设计巧妙，平衡了贪心策略和效率考虑
3. 分析深度：通过"good set"概念提供了系统的分析框架
4. 实际意义：重启模型更贴近某些实际应用场景

不足

1. 理论导向：缺少实际应用验证和实验评估
2. Gap较大：一般情况下缺少上界算法
3. 复杂性：证明过程较为复杂，可读性有待改善

影响力

1. 理论贡献：为调度理论中的重启模型提供了重要的理论基础
2. 方法论价值：分析方法可推广到其他调度问题
3. 实用潜力：在云计算、实时系统等领域具有应用前景

适用场景

1. 云计算：虚拟机调度中的任务重启
2. 实时系统：高优先级任务的抢占式调度
3. 操作系统：进程调度中的时间片轮转机制

参考文献

本文引用了20篇相关文献，涵盖了调度理论的经典工作和最新进展，为研究提供了坚实的理论基础。关键文献包括Graham等人的调度问题分类体系、Li的在线调度算法以及Shmoys等人的重启模型开创性工作。

总体评价：这是一篇高质量的理论计算机科学论文，在调度理论领域做出了重要贡献。虽然主要关注理论分析，但为实际应用提供了重要的理论指导。论文的数学分析严谨，结果具有重要的学术价值。