← 研踪 PaperTrailarXiv: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
摘要
We study two-stage speed-robust scheduling for minimizing total completion time. Jobs must be partitioned into bags before an adversary reveals the speeds of at most 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~, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between and , well below the optimal makespan factor of about . General speeds make the problem strictly harder: no deterministic algorithm is better than -robust, already for infinitesimally small jobs. We give a -robust algorithm for arbitrary processing times and improve the guarantee to 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.
观测到的版本
相邻记录可能跳过中间版本;首次发现 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 bags before an adversary reveals the speeds of at most 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~, both for unit-size jobs and for arbitrary processing times. For infinitesimally small jobs, the factor lies between and , well below the optimal makespan factor of about . General speeds make the problem strictly harder: no deterministic algorithm is better than -robust, already for infinitesimally small jobs. We give a -robust algorithm for arbitrary processing times and improve the guarantee to 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.
查看此版本解读 →查看此版本原文 ↗