On‐line scheduling revisited
On‐line scheduling revisited
复制标题
DOI：
10.1002/1099-1425(200011/12)3:6
复制
发表时间：
2000-11
影响因子：
2
通讯作者：
R. Fleischer;Michael G. Wahl
中科院分区：
文献类型：
--
作者：
R. Fleischer;Michael G. Wahl
我们提出了一个新的在线算法，MR，在m台相同的机器上的已知加工时间的工件的非抢占式调度击败了最好的以前的算法为m × 64。对于m∞，其竞争比接近1+\sqrt{（1+1{\rm n} 2）/2}<1.9201。版权所有2000 ©约翰威利父子有限公司。
We present a new on-line algorithm, MR, for non-preemptive scheduling of jobs with known processing times on m identical machines which beats the best previous algorithm for m⩾64. For m∞ its competitive ratio approaches 1+\sqrt{(1+1{\rm n} 2)/2}<1.9201. Copyright 2000 © John Wiley & Sons, Ltd.