跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2611.20795 · v1

Speed-Robust Scheduling for Total Completion Time

首次提交 2026-11-16 17:42
版本更新 2026-11-16 17:42
雷达观测 2026-11-17 17:11
arXiv ↗PDF ↗

摘要

We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into MM bags before an adversary reveals the speeds of at most MM machines. Each bag is then assigned to one available machine, and the jobs on each machine may be processed in any order independent of the bags. We compare with an optimal schedule that knows the speeds in advance and assigns jobs individually. This model has been studied for makespan minimization. We initiate its study for total completion time, as suggested by Stein and Zhong (TALG 2020). For an unknown number of identical machines, we show that the optimal deterministic robustness factor is exactly~13/1213/12, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between 31/30≈1.033331/30\approx1.0333 and 28/27≈1.037028/27\approx1.0370, well below the optimal makespan factor of about 1.20711.2071. General speeds make the problem strictly harder: no deterministic algorithm is better than 1.26691.2669-robust, already for infinitesimally small jobs. We give a 25/1625/16-robust algorithm for arbitrary processing times and improve the guarantee to 1681/1152≈1.45921681/1152\approx1.4592 for infinitesimally small jobs. Our main tools are a layer decomposition that extends guarantees from unit-size jobs to arbitrary processing times when one assignment satisfies them for every prefix in non-increasing processing-time order, and a threshold analysis of the bag counts produced by greedy assignment rules.

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

目前只收录了一个版本。收录下一版后,可以对照标题、作者、分类和摘要。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v1 · 2026-11-16 17:42 · 最新观测版本

Speed-Robust Scheduling for Total Completion Time

We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into MM bags before an adversary reveals the speeds of at most MM machines. Each bag is then assigned to one available machine, and the jobs on each machine may be processed in any order independent of the bags. We compare with an optimal schedule that knows the speeds in advance and assigns jobs individually. This model has been studied for makespan minimization. We initiate its study for total completion time, as suggested by Stein and Zhong (TALG 2020). For an unknown number of identical machines, we show that the optimal deterministic robustness factor is exactly~13/1213/12, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between 31/30≈1.033331/30\approx1.0333 and 28/27≈1.037028/27\approx1.0370, well below the optimal makespan factor of about 1.20711.2071. General speeds make the problem strictly harder: no deterministic algorithm is better than 1.26691.2669-robust, already for infinitesimally small jobs. We give a 25/1625/16-robust algorithm for arbitrary processing times and improve the guarantee to 1681/1152≈1.45921681/1152\approx1.4592 for infinitesimally small jobs. Our main tools are a layer decomposition that extends guarantees from unit-size jobs to arbitrary processing times when one assignment satisfies them for every prefix in non-increasing processing-time order, and a threshold analysis of the bag counts produced by greedy assignment rules.

查看此版本解读 →查看此版本原文 ↗