Online Algorithm for Parallel Job Scheduling and Strip Packing
Online Algorithm for Parallel Job Scheduling and Strip Packing
复制标题
DOI：
10.1007/978-3-540-77918-6_6
复制
发表时间：
2007-10
期刊：
影响因子：
--
通讯作者：
J. Hurink;J. J. Paulus-J.
中科院分区：
文献类型：
--
作者：
J. Hurink;J. J. Paulus-J.
考虑平行机上并行作业的在线排序问题，P|Online − List，MJ|Cmax。对于这个问题，我们给出了一个6.6623竞争的算法。这改进了这个问题的最著名的7-竞争算法。所提出的算法也适用于机器在一条线上订购，并且只有相邻的机器才能分配给一个作业的特殊情况，因此也适用于在线正交条排样。由于已有的在线正交条排样算法假定矩形有界，因此该算法是第一个具有恒定竞争比的算法。
We consider the online scheduling problem of parallel jobs on parallel machines,P|online − list,mj|Cmax. For this problem we present a 6.6623-competitive algorithm. This improves the best known 7- competitive algorithm for this problem. The presented algorithm also applies to the special case where machines are ordered on a line and only adjacent machines can be assigned to a job and, therefore, also to online orthogonal strip packing. Since previous results for online orthogonal strip packing assume bounded rectangles, the presented algorithm is the first with a constant competitive ratio.