论文标题
速度稳定时间表 - 沙子，砖和岩石
Speed-Robust Scheduling -- Sand, Bricks, and Rocks
论文作者
论文摘要
速度稳定调度问题是一个两个阶段的问题，给定的$ M $机器，必须将作业分组为最多$ M $袋，而给定的$ M $机器的处理速度未知。透露速度后，必须将分组的作业分配给机器而不会分开。为了评估算法的性能，我们确定了算法的MakePAN最差比率和最佳Makepan的上限。我们将此比率称为鲁棒性因子。我们为最一般的设置提供了一种鲁棒性因子$ 2-1/m $的算法，并将其提高到$ 1.8 $。对于无限工作的特殊情况，我们提供了一种算法，其最佳鲁棒性因子等于$ e/（e-1）\约1.58 $。 Stein and Zhong之前研究了所有机器的特定机器环境（SODA 2019）。对于此设置，我们提供了一种算法，用于安排无穷小作业的最佳鲁棒性系数（1+ \ sqrt {2}）/2 \大约1.207 $。它为相等大小的作业的$ 4/3 $的下降算法奠定了基础。
The speed-robust scheduling problem is a two-stage problem where given $m$ machines, jobs must be grouped into at most $m$ bags while the processing speeds of the given $m$ machines are unknown. After the speeds are revealed, the grouped jobs must be assigned to the machines without being separated. To evaluate the performance of algorithms, we determine upper bounds on the worst-case ratio of the algorithm's makespan and the optimal makespan given full information. We refer to this ratio as the robustness factor. We give an algorithm with a robustness factor $2-1/m$ for the most general setting and improve this to $1.8$ for equal-size jobs. For the special case of infinitesimal jobs, we give an algorithm with an optimal robustness factor equal to $e/(e-1) \approx 1.58$. The particular machine environment in which all machines have either speed $0$ or $1$ was studied before by Stein and Zhong (SODA 2019). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of $(1+\sqrt{2})/2 \approx 1.207$. It lays the foundation for an algorithm matching the lower bound of $4/3$ for equal-size jobs.
