Albers Susanne, Janke Maximilian
Lehrstuhl für Algorithmen und Komplexität, Institut für Informatik, Technische Universität München, Boltzmannstr. 3, 85748 Garching, Germany.
Algorithmica. 2021;83(9):2803-2832. doi: 10.1007/s00453-021-00841-8. Epub 2021 Jun 9.
Makespan minimization on identical machines is a fundamental problem in online scheduling. The goal is to assign a sequence of jobs to identical parallel machines so as to minimize the maximum completion time of any job. Already in the 1960s, Graham showed that is -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 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.
在相同机器上最小化完工时间是在线调度中的一个基本问题。目标是将一系列作业分配到相同的并行机器上，以使任何作业的最大完成时间最小化。早在20世纪60年代，格雷厄姆就证明了 是 - 竞争的。目前已知的最佳确定性在线算法实现了1.9201的竞争比。没有确定性在线策略能获得小于1.88的竞争力。在本文中，我们研究流行的随机顺序模型中的在线完工时间最小化问题，在该模型中，给定输入的作业以随机排列的方式到达。已知在这种情况下， 不会渐近地获得小于2的竞争因子。我们给出了首个改进的性能保证。具体而言，我们开发了一种确定性在线算法，其竞争比为1.8478。该结果依赖于一种新的分析方法。我们确定了输入作业的随机排列以高概率满足的一组属性。然后针对相应的排列类别对我们的算法进行最坏情况分析。分析表明，所述的竞争力不仅在期望中成立，而且以高概率成立。此外，它提供了数学证据，表明导致更高性能比的作业序列极其罕见，是病态输入。我们通过随机顺序模型的下界来补充这些结果。我们表明，没有确定性在线算法能实现小于4/3的竞争比。此外，没有确定性在线算法能以高概率获得小于3/2的竞争力。
