Multiprocessor scheduling with rejection
Multiprocessor scheduling with rejection
复制标题
DOI：
10.1137/s0895480196300522
复制
发表时间：
2000-01-01
影响因子：
0.8
通讯作者：
Stougie, L
中科院分区：
文献类型：
--
作者：
Bartal, Y;Leonardi, S;Stougie, L
我们考虑使用特殊功能的多处理器调度版本，该功能可能会以一定的惩罚拒绝作业。该问题的实例由M相同的平行机和一组N作业给出，每个作业都以处理时间和罚款为特征。在在线版本中，工作将一个一个人获得，我们必须在获得有关未来工作的任何信息之前安排或拒绝工作。目的是最大程度地减少接受工作的时间表的制造商，加上被拒绝工作的罚款的总和。主要结果是1 + PHI近似于2.618的竞争性算法，用于在线版本，其中PHI是PHI是黄金比率。匹配的下限表明这是适用于所有m的最佳算法。对于固定m，我们提供了改进的界限；特别是，对于M = 2，我们给出了phi近似于1.618的竞争算法，这是最好的。对于离线问题，我们为固定M和任意M的多项式近似方案提供了完全多项式近似方案。此外，我们提出了一种近似算法，该算法在时间O（n log n）中以任意m的速度运行，并保证2-1/m的近似值。
We consider a version of multiprocessor scheduling with the special feature that jobs may be rejected at a certain penalty. An instance of the problem is given by m identical parallel machines and a set of n jobs, with each job characterized by a processing time and a penalty. In the on-line version the jobs become available one by one and we have to schedule or reject a job before we have any information about future jobs. The objective is to minimize the makespan of the schedule for accepted jobs plus the sum of the penalties of rejected jobs.The main result is a 1 + phi approximate to 2.618 competitive algorithm for the on-line version of the problem, where phi is the golden ratio. A matching lower bound shows that this is the best possible algorithm working for all m. For fixed m we give improved bounds; in particular, for m = 2 we give a phi approximate to 1.618 competitive algorithm, which is best possible.For the off-line problem we present a fully polynomial approximation scheme for fixed m and a polynomial approximation scheme for arbitrary m. Moreover, we present an approximation algorithm which runs in time O(n log n) for arbitrary m and guarantees a 2 - 1/m approximation ratio.