论文标题
在随机阶模型中安排
Scheduling in the Random-Order Model
论文作者
论文摘要
在相同的机器上，使PAN最小化是在线计划中的一个基本问题。目标是将一系列作业分配给$ m $相同的并行机器，以最大程度地减少任何作业的最大完成时间。格雷厄姆（Graham）在1960年代已经表明，贪婪为$（2-1/m）$ - 竞争力。目前已知的最佳确定性在线算法的竞争比率为1.9201。没有确定性的在线策略可以获得小于1.88的竞争力。 在本文中，我们在在线研究中的pan在流行的随机阶模型中最小化，在该模型中，给定输入的工作作为随机排列到达。众所周知，在这种情况下，贪婪并未达到渐近因素小于2的竞争因素。我们提供了第一个改进的性能保证。具体而言，我们开发了一种确定性的在线算法，该算法的竞争比率为1.8478。结果依赖于一种新的分析方法。我们确定一组属性，即输入作业的随机排列满足高概率。然后，我们对各个排列类别进行算法的最坏情况分析。分析表明，所陈述的竞争力不仅在预期中而且有可能具有很高的可能性。此外，它提供了数学证据，表明导致较高绩效比率的工作序列极为罕见，病理输入。对于随机阶模型，我们通过下限补充结果。我们表明，没有确定性的在线算法可以实现小于4/3的竞争比率。此外，没有确定性的在线算法可以具有很高的可能性，因此可以获得小于3/2的竞争力。
Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to $m$ identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that Greedy is $(2-1/m)$-competitive. The best deterministic online algorithm currently known achieves a competitive ratio of 1.9201. No deterministic online strategy can obtain a competitiveness smaller than 1.88. In this paper, we study online makespan minimization in the popular random-order model, where the jobs of a given input arrive as a random permutation. It is known that Greedy does not attain a competitive factor asymptotically smaller than 2 in this setting. We present the first improved performance guarantees. Specifically, we develop a deterministic online algorithm that achieves a competitive ratio of 1.8478. The result relies on a new analysis approach. We identify a set of properties that a random permutation of the input jobs satisfies with high probability. Then we conduct a worst-case analysis of our algorithm, for the respective class of permutations. The analysis implies that the stated competitiveness holds not only in expectation but with high probability. Moreover, it provides mathematical evidence that job sequences leading to higher performance ratios are extremely rare, pathological inputs. We complement the results by lower bounds, for the random-order model. We show that no deterministic online algorithm can achieve a competitive ratio smaller than 4/3. Moreover, no deterministic online algorithm can attain a competitiveness smaller than 3/2 with high probability.
