Online scheduling on identical machines using SRPT
Online scheduling on identical machines using SRPT
复制标题
使用 SRPT 在同一台机器上进行在线调度
DOI：
10.1137/1.9781611973082.10
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Benjamin Moseley
中科院分区：
文献类型：
--
作者：
K. Fox;Benjamin Moseley
最短剩余处理时间（SRPT）算法由于其在单机上最优性，成为求解多台相同机器上最小化平均流时间问题的最自然的算法。众所周知，SRPT在多台机器上实现了最佳的竞争比，直到一个常数。使用资源增加，已知SRPT在给定速度为2 - 1/m的机器时最多达到最优解的总流动时间。此外，已知SRPT的竞争比随着速度的增加而提高;当s ≥ 2- 1/m时，SRPT是s-速度1/s-竞争的。
然而，在我们对SRPT的理解中仍然存在差距。在这项工作之前，SRPT的性能不知道当SRPT给定（1 + ε）-速度时，当0 < ε < 1- 1/m时，尽管人们已经认为SRPT是（1 + ε）-速度O（1）-竞争超过十年。解决这个问题是在开放问题2.9中提出的，来自Pruhs，Sgall和Torng [PST 04]的调查“在线调度”，我们在本文中回答了这个问题。我们表明，SRPT是可扩展的m相同的机器上。也就是说，我们证明了SRPT是（1 + ε）-速度O（1/ε）-竞争的ε > 0。我们通过证明SRPT对于最小化m台相同机器上的流时间的lk范数的目标是（1 + ε）-速度O（1/ε2）-竞争来补充这一点。我们的结果都依赖于新的潜在功能，捕捉SRPT的结构。我们的研究结果，结合以前的工作，表明SRPT是最好的在线算法，基本上在每个方面时，迁移是允许的。
Due to its optimality on a single machine for the problem of minimizing average flow time, Shortest-Remaining-Processing-Time (SRPT) appears to be the most natural algorithm to consider for the problem of minimizing average flow time on multiple identical machines. It is known that SRPT achieves the best possible competitive ratio on multiple machines up to a constant factor. Using resource augmentation, SRPT is known to achieve total flow time at most that of the optimal solution when given machines of speed 2 − 1/m. Further, it is known that SRPT's competitive ratio improves as the speed increases; SRPT is s-speed 1/s-competitive when s ≥ 2--1/m.
However, a gap has persisted in our understanding of SRPT. Before this work, the performance of SRPT was not known when SRPT is given (1 + ε)-speed when 0 < ε < 1--1/m, even though it has been thought that SRPT is (1 + ε)-speed O(1)-competitive for over a decade. Resolving this question was suggested in Open Problem 2.9 from the survey "Online Scheduling" by Pruhs, Sgall, and Torng [PST04], and we answer the question in this paper. We show that SRPT is scalable on m identical machines. That is, we show SRPT is (1 + ε)-speed O(1/ε)-competitive for ε > 0. We complement this by showing that SRPT is (1 + ε)-speed O(1/ε2)-competitive for the objective of minimizing the lk-norms of flow time on m identical machines. Both of our results rely on new potential functions that capture the structure of SRPT. Our results, combined with previous work, show that SRPT is the best possible online algorithm in essentially every aspect when migration is permissible.