A Robust PTAS for Machine Covering and Packing
A Robust PTAS for Machine Covering and Packing
复制标题
用于机器覆盖和包装的稳健 PTAS
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
José Verschae
中科院分区：
文献类型：
--
作者：
M. Skutella;José Verschae
最小化最大完工时间和最大化最小机器负载是两个最重要和最基本的并行机器调度问题。在在线场景中，作业是连续添加和/或删除的，目标是始终保持（接近）最优的作业分配给机器。作业的重新分配会产生与其大小成正比的成本，并且重新分配作业的总成本最好以常数r乘以添加或删除作业的总大小为限。我们的主要结果是，对于任何e b>，对于一些常数重分配因子r(e)，人们总是可以保持一个（1 + e）竞争解。对于最小完工时间问题，这是对1996年由Andrews， Goemans和Zhang发表的(2+e)-竞争算法的第一次改进。
Minimizing the makespan or maximizing the minimum machine load are two of the most important and fundamental parallel machine scheduling problems. In an online scenario, jobs are consecutively added and/or deleted and the goal is to always maintain a (close to) optimal assignment of jobs to machines. The reassignment of a job induces a cost proportional to its size and the total cost for reassigning jobs must preferably be bounded by a constant r times the total size of added or deleted jobs. Our main result is that, for any e > 0, one can always maintain a (1 + e)-competitive solution for some constant reassignment factor r(e). For the minimum makespan problem this is the first improvement of the (2+e)-competitive algorithm with constant reassignment factor published in 1996 by Andrews, Goemans, and Zhang.