| 任意处理时间的多处理机任务调度近似算法 |
| |
| 引用本文： | 黄金贵.任意处理时间的多处理机任务调度近似算法[J].计算机工程与应用,2008,44(33):7-9. |
| |
| 作者姓名： | 黄金贵 |
| |
| 作者单位： | 湖南师范大学,计算机教学部,长沙,410083 |
| |
| 摘 要： | 研究多处理机任务调度模型Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上,提出了该问题的一个改进的多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为(2m)~(1/2),优于E.Bampis等人给出的3m~(1/2)的结果。
|
| 关 键 词： | 多处理机任务调度 近似算法 NP难问题 |
| 收稿时间： | 2008-7-28 |
| 修稿时间： | 2008-8-21
|
Approximation algorithm on multi-processor job scheduling |
| |
| HUANG Jin-gui.Approximation algorithm on multi-processor job scheduling[J].Computer Engineering and Applications,2008,44(33):7-9. |
| |
| Authors: | HUANG Jin-gui |
| |
| Affiliation: | Department of Computer Teaching，Hunan Normal University，Changsha 410083，China |
| |
| Abstract: | This paper studies the problem of scheduling a set of n independent multiprocessor jobs with prespecified processor allocation on a set of identical processors in order to minimize the makespan.The problem PmfixCmax is proved to be NP-hard and cannot be approximated within a constant factor unless P=NP.Recently，E.Bampis et al. have given a 3m-2-approximation algorithm for this problem by using the split-round technique.This paper proposes a 2(2m)-2-approximation algorithm for this problem based on the improvement of the split-round algorithm. |
| |
| Keywords: | multiprocessor job scheduling approximation algorithm NP-hard problem |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
