Efficient Algorithms for Average Completion Time Scheduling
Efficient Algorithms for Average Completion Time Scheduling
复制标题
DOI：
10.1007/978-3-642-13036-6_31
复制
发表时间：
2010-06
期刊：
影响因子：
--
通讯作者：
René Sitters
中科院分区：
文献类型：
--
作者：
René Sitters
本文分析了在相同并行机上求最小化（加权）平均完工时间的算法的竞争比，证明了著名的最短剩余处理时间算法（SRPT）是5/4-竞争w.r.t.平均完成时间目标。对于加权完工时间，我们给出了一个竞争比为1.791 +o（m）的确定性算法.这个比例适用于抢占式和非抢占式调度。
We analyze the competitive ratio of algorithms for minimizing (weighted) average completion time on identical parallel machines and prove that the well-known shortest remaining processing time algorithm (SRPT) is 5/4-competitive w.r.t. the average completion time objective. For weighted completion times we give a deterministic algorithm with competitive ratio 1.791 +o(m). This ratio holds for preemptive and non-preemptive scheduling.