On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity
On-Line Scheduling Algorithms for a Batch Machine with Finite Capacity
复制标题
DOI：
10.1007/s10878-005-6855-5
复制
发表时间：
2005-03
影响因子：
1
通讯作者：
C. Poon;W. Yu
中科院分区：
文献类型：
--
作者：
C. Poon;W. Yu
我们研究了在有限容量的批量机器上发布日期的在线调度作业问题，目的是最小化完工时间。我们将该问题的几种现有算法推广为一类在线算法，这些算法对于任何任意有限的机器容量都是 2-competitive 的。然后，我们证明其中一个广义算法实际上对机器容量 2 具有 7/4 竞争性。这是第一个针对有限机器容量且竞争比小于 2 的在线算法。
We study the problem of on-line scheduling jobs with release dates on a batch machine of finite capacity with the objective of minimizing the makespan. We generalize several existing algorithms for the problem to a class of on-line algorithms that are 2-competitive for any arbitrary finite machine capacity. Then, we show that one of these generalized algorithms is in fact 7/4-competitive for machine capacity 2. This is the first on-line algorithm for a finite machine capacity with competitive ratio less than 2.