Universal Sequencing on a Single Machine
Universal Sequencing on a Single Machine
复制标题
DOI：
10.1007/978-3-642-13036-6_18
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
L. Epstein;Asaf Levin;A. Marchetti-Spaccamela;Nicole Megow;Julián Mestre;M. Skutella;L. Stougie
中科院分区：
文献类型：
--
作者：
L. Epstein;Asaf Levin;A. Marchetti-Spaccamela;Nicole Megow;Julián Mestre;M. Skutella;L. Stougie
我们考虑在一台不可靠的机器上进行调度，该机器可能会经历处理速度的意外变化，甚至会出现完全故障。我们的目标是一种通用的解决方案，在不适应任何可能的机器行为的情况下运行良好。以最小化总加权完工时间为目标，设计了一种多项式时间确定性调度算法，该算法能找到一个解在预先知道中断的最优透视算法解值的4倍以内的普适调度序列。该算法的随机化版本在预期中达到了E。我们还证明了这两个结果在所有通用解中是最可能的。作为结果的直接结果，我们肯定地回答了当机器不可用时间提前已知时，是否存在离线版本的恒定近似算法的问题。当作业有单独的发布日期时，情况发生了巨大的变化。即使所有的权重都相等，也存在这样的情况，即任何通解都是比最优序列更差的Ω(logn/logn)的因子。在这种困难的激励下，我们研究了当每个作业的加工时间与其重量成正比时的特殊情况。我们提出了一种具有较小恒定性能保证的非平凡算法。
We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. We aim for a universal solution that performs well without adaptation for any possible machine behavior. For the objective of minimizing the total weighted completion time, we design a polynomial time deterministic algorithm that finds a universal scheduling sequence with a solution value within 4 times the value of an optimal clairvoyant algorithm that knows the disruptions in advance. A randomized version of this algorithm attains in expectation a ratio ofe. We also show that both results are best possible among all universal solutions. As a direct consequence of our results, we answer affirmatively the question of whether a constant approximation algorithm exists for the offline version of the problem when machine unavailability periods are known in advance.When jobs have individual release dates, the situation changes drastically. Even if all weights are equal, there are instances for which any universal solution is a factor of Ω(logn/ loglogn) worse than an optimal sequence. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a non-trivial algorithm with a small constant performance guarantee.