| 带并行工件的平行机排序问题的一个新近似算法 |
| |
| 引用本文： | 沈灏,杨启帆,何勇.带并行工件的平行机排序问题的一个新近似算法[J].浙江大学学报(理学版),2004,31(2):138-142. |
| |
| 作者姓名： | 沈灏 杨启帆 何勇 |
| |
| 作者单位： | 1. 杭州电子工业学院,数学系,浙江,杭州,310037
2. 浙江大学,数学系,浙江,杭州,310027 |
| |
| 摘 要： | 讨论并行工件平行机排序问题,目标为极小化所有工件的总完工时间.这是一个强NP-难的问题.通过对(0,1]区间划分的深入研究,提出了一个多项式时间的近似算法,其渐近性能比的上界为1.6,下界为1.5.该算法比LI(1999)中提出的算法的渐近性能比明显地小.
|
| 关 键 词： | 近似算法 平行机排序 渐近性能比 |
| 文章编号： | 1008-9497(2004)02-138-05 |
| 修稿时间： | 2002年5月10日 |
Better approximation algorithm for scheduling independent parallel tasks |
| |
| SHEN Hao,YANG Qi-fan,HE Yong.Better approximation algorithm for scheduling independent parallel tasks[J].Journal of Zhejiang University(Sciences Edition),2004,31(2):138-142. |
| |
| Authors: | SHEN Hao YANG Qi-fan HE Yong |
| |
| Institution: | SHEN Hao~1,YANG Qi-fan~2,HE Yong~2 |
| |
| 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). |
| |
| Keywords: | approximation algorithm parallel task scheduling worst-case performance ratio |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《浙江大学学报(理学版)》下载免费的PDF全文 |
|
