Speed-robust scheduling: sand, bricks, and rocks
Speed-robust scheduling: sand, bricks, and rocks
复制标题
速度稳健的调度：沙子、砖块和岩石
DOI：
10.1007/s10107-022-01829-0
复制
发表时间：
--
影响因子：
2.7
通讯作者：
B. Simon.
中科院分区：
文献类型：
--
作者：
F. Eberle;R. Hoeksma;N. Megow;L. Nölke;K. Schewior;B. Simon.
速度鲁棒调度问题是一个两阶段问题，给定 m 台机器，作业必须最多分组为 m 包，而机器的处理速度未知。速度显示后，分组的作业必须分配给机器，而不是分开。为了评估算法的性能，我们确定了算法的最坏情况下的完工时间比和给定完整信息的最佳完工时间的上限。我们将该比率称为稳健性因子。我们为最一般的设置提供了一个具有鲁棒性因子的算法，并将其改进为 1.8（对于相同大小的作业）。对于无穷小作业的特殊情况，我们给出了最佳鲁棒性因子等于的算法。 Stein 和zhong 之前研究过所有机器速度为 0 或 1 的特定机器环境（ACM Trans Algorithms 16(1):1-20, 2020。https://doi.org/10.1145/3340320）。对于这种设置，我们提供了一种用于调度无限小作业的算法，其最佳鲁棒性因子为。它为匹配相同大小作业的下限的算法奠定了基础。
The speed-robust scheduling problem is a two-stage problem where, givenmmachines, jobs must be grouped into at mostmbags while the processing speeds of the 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 factorfor 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. The particular machine environment in which all machines have either speed 0 or 1 was studied before by Stein and Zhong (ACM Trans Algorithms 16(1):1-20, 2020. https://doi.org/10.1145/3340320). For this setting, we provide an algorithm for scheduling infinitesimal jobs with an optimal robustness factor of. It lays the foundation for an algorithm matching the lower bound offor equal-size jobs.
登录
查看更多内容
DOI：
10.1287/mnsc.2017.2973
发表时间：
2019-02
期刊：
Manag. Sci.
影响因子：
--
作者：
R. Levi;T. Magnanti;Yaron Shaposhnik
通讯作者：
R. Levi;T. Magnanti;Yaron Shaposhnik
影响因子：
1.1
作者：
C. Durr;T. Erlebach;Nicole Megow;Julie Meißner
通讯作者：
C. Durr;T. Erlebach;Nicole Megow;Julie Meißner
DOI：
10.1137/110844210
发表时间：
2012-05
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Julián Mestre;Nicole Megow
通讯作者：
Julián Mestre;Nicole Megow
影响因子：
4.8
作者：
Lin Chen;Nicole Megow;R. Rischke;L. Stougie;José Verschae
通讯作者：
Lin Chen;Nicole Megow;R. Rischke;L. Stougie;José Verschae
DOI：
10.1145/3340320
发表时间：
2019
期刊：
ACM Transactions on Algorithms (TALG)
影响因子：
--
作者：
C. Stein;Mingxian Zhong
通讯作者：
Mingxian Zhong