Zhejiang Daxue xuebao. Lixue ban (Mar 2004)

Better approximation algorithm for scheduling independent parallel tasks(带并行工件的平行机排序问题的一个新近似算法)

  • SHENHao(沈灏),
  • YANGQi-fan(杨启帆),
  • HEYong(何勇)

DOI
Journal volume & issue
Vol. 31, no. 2
pp. 138 – 142

Abstract

Read online

讨论并行工件平行机排序问题，目标为极小化所有工件的总完工时间.这是一个强NP-难的问题.通过对（0，1]区间划分的深入研究，提出了一个多项式时间的近似算法，其渐近性能比的上界为1.6，下界为1.5.该算法比LI(1999）中提出的算法的渐近性能比明显地小.

Keywords