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

【Abstract】 The problem of scheduling independent parallel tasks in parallel identical machine systems is discussed with the objective of minimizing makespan. The problem is known to be strongly NP-hard. Based on the new division of t, it is proposed that an approximation algorithm of which the worst-case performance ratio have an upper bound 1.6 and lower bound 1.5, much smaller than that of the algorithm in LI(1999).更多还原