摘要
讨论并行工件平行机排序问题,目标为极小化所有工件的总完工时间.这是一个强NP-难的问题.通过对(0,1]区间划分的深入研究,提出了一个多项式时间的近似算法,其渐近性能比的上界为1.6,下界为1.5.该算法比LI(1999)中提出的算法的渐近性能比明显地小.
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).
出处
《浙江大学学报（理学版）》
CAS
CSCD
2004年第2期138-142,共5页
Journal of Zhejiang University（Science Edition）
基金
国家自然科学基金资助项目(10371028).
关键词
近似算法
平行机排序
渐近性能比
并行工件
approximation algorithm
parallel task scheduling
worst-case performance ratio
