Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart
Online scheduling of equal length jobs on a bounded parallel batch machine with restart or limited restart
复制标题
DOI：
10.1016/j.tcs.2014.05.021
复制
发表时间：
2014-07
期刊：
影响因子：
--
通讯作者：
Hailing Liu;Jinjiang Yuan
中科院分区：
文献类型：
--
作者：
Hailing Liu;Jinjiang Yuan
本文研究了容量为B的有界批处理机上等长工件的在线（随时间）排序问题，目标是最小化重新启动或有限重新启动的完工时间。设α = 0.29，β = 0.47，γ = 0.38，φ = 0.40为文中定义的四个参数。当B= 2时，在重新启动或有限重新启动的假设下，给出了竞争比为1+ α的最佳可能在线算法HL（B= 2）.在有限重启动且B≥ 3的假设下，给出了一个竞争比为1+ β的最佳可能在线算法HL（B≥ 3）.在重新启动的假设下，当B= 3时，给出了竞争比为1+ γ的最佳可能在线算法H（B= 3）;当B≥ 4时，给出了竞争比为1+ φ的最佳可能在线算法H（B≥ 4）.在我们的在线算法的假设下，重新启动，每个作业最多中断两次。因此，我们的结果涵盖了所有k≥ 1的k限制重新启动的设置。
We consider the online (over time) scheduling of equal length jobs on a bounded parallel batch machine with a capacity b to minimize makespan with restart or limited restart. Let α≈ 0.29, β≈ 0.47, γ≈ 0.38, and φ≈ 0.40 be four parameters defined in the text. When b= 2, we present a best possible online algorithm H L (b= 2) with a competitive ratio of 1+ α under the assumption of restart or limited restart. Under the assumption of limited restart with b≥ 3, we present a best possible online algorithm H L (b≥ 3) with a competitive ratio of 1+ β. Under the assumption of restart, when b= 3, we present a best possible online algorithm H (b= 3) with a competitive ratio of 1+ γ, and when b≥ 4, we present a best possible online algorithm H (b≥ 4) with a competitive ratio of 1+ φ. In our online algorithms under the assumption of restart, each job is interrupted at most two times. Consequently, our results cover the setting of k-limited restart for all k≥ 1.