Universal Sequencing on an Unreliable Machine
Universal Sequencing on an Unreliable Machine
复制标题
DOI：
10.1137/110844210
复制
发表时间：
2012-05
期刊：
影响因子：
--
通讯作者：
Julián Mestre;Nicole Megow
中科院分区：
文献类型：
--
作者：
Julián Mestre;Nicole Megow
我们考虑在不可靠的机器上进行调度，该机器可能会经历处理速度的意外变化，甚至完全崩溃。我们的目标是最小化 wjf (Cj )f 或任何非递减、非负、可微的成本函数 f (Cj )。我们的目标是提供一种通用的解决方案，该解决方案无需适应任何可能的机器行为的所有成本函数，即可表现良好。我们设计了一种确定性算法，可以找到一个通用调度序列，其解值在预先了解机器行为的最佳洞察算法值的 4 倍之内。该算法的随机版本预期达到 e 的比率。We 还表明，对于任何无界成本函数，这两种性能保证都是最好的。我们的算法可以适应在多项式时间内运行，但成本略有增加。当职位有单独的发布日期时，情况就会发生巨大变化。即使所有权重相等，在某些情况下，任何通用解决方案都比任何无界成本函数的最佳序列差 Ω(log n/ log log n) 倍。受这种硬度的启发，我们研究了每个作业的处理时间与其重量成正比的特殊情况。我们提出了一种具有较小的恒定性能保证的重要算法。
We consider scheduling on an unreliable machine that may experience unexpected changes in processing speed or even full breakdowns. Our objective is to minimize wjf (Cj )f or any nondecreasing, nonnegative, differentiable cost function f (Cj ). We aim for a universal solution that performs well without adaptation for all cost functions for any possible machine behavior. We design a 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 machine behavior in advance. A randomized version of this algorithm attains in expectation a ratio of e .W e also show that both performance guarantees are best possible for any unbounded cost function. Our algorithms can be adapted to run in polynomial time with slightly increased cost. 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 Ω(log n/ log log n) worse than an optimal sequence for any unbounded cost function. Motivated by this hardness, we study the special case when the processing time of each job is proportional to its weight. We present a nontrivial algorithm with a small constant performance guarantee.