SRPT optimally utilizes faster machines to minimize flow time
SRPT optimally utilizes faster machines to minimize flow time
复制标题
SRPT 充分利用更快的机器来最大限度地缩短流程时间
DOI：
10.1145/1435375.1435376
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
J. McCullough
中科院分区：
文献类型：
--
作者：
E. Torng;J. McCullough
针对m台相同机器上n个带释放时间的工件的调度问题，分析了最短剩余加工时间（SRPT）算法。已知如果m = 1，SRPT是最优的，但是SRPT对于该问题具有最坏情况的近似比Θ（min（log n/m，log Δ）），其中Δ是最长作业的长度除以最短作业的长度的比率。先前已经表明，SRPT能够使用更快的机器来产生与使用较慢机器的最优算法一样好的时间表。我们现在表明，SRPT最佳地使用这些更快的机器相对于最坏情况下的近似比。也就是说，如果SRPT的机器速度是最优算法的s ≥ 2 − 1/m倍，那么SRPT的流动时间至少比最优算法的流动时间小s倍。显然，没有算法可以提供一个更好的最坏情况下的保证，我们表明，现有的算法与SRPT没有资源增加类似的性能保证不最佳地使用额外的资源。
We analyze the shortest remaining processing time (SRPT) algorithm with respect to the problem of scheduling n jobs with release times on m identical machines to minimize total flow time. It is known that SRPT is optimal if m = 1 but that SRPT has a worst-case approximation ratio of Θ(min(log n/m, log Δ)) for this problem, where Δ is the ratio of the length of the longest job divided by the length of the shortest job. It has previously been shown that SRPT is able to use faster machines to produce a schedule as good as an optimal algorithm using slower machines. We now show that SRPT optimally uses these faster machines with respect to the worst-case approximation ratio. That is, if SRPT is given machines that are s ≥ 2 − 1/m times as fast as those used by an optimal algorithm, SRPT's flow time is at least s times smaller than the flow time incurred by the optimal algorithm. Clearly, no algorithm can offer a better worst-case guarantee, and we show that existing algorithms with similar performance guarantees to SRPT without resource augmentation do not optimally use extra resources.