| 应用团划分方法改进多处理机任务近似调度 |
| |
| 引用本文： | 黄金贵.应用团划分方法改进多处理机任务近似调度[J].计算机工程与应用,2009,45(4):4-8. |
| |
| 作者姓名： | 黄金贵 |
| |
| 作者单位： | 湖南师范大学,计算机教学部,长沙,410083 |
| |
| 基金项目： | 国家自然科学基金，湖南省自然科学基金 |
| |
| 摘 要： | 研究多处理机任务调度模型Pm|fix,pj=1|Cmax,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用,但早已被证明为NP难问题,而且也不存在常数近似算法。基于团划分方法构造了该问题的多项式时间近似算法,通过模拟实验进行了验证,和最大宽度优先(LWF)算法相比,该算法花费时间较长,近似比性能要好。
|
| 关 键 词： | 多处理机任务 调度 近似算法 NP难问题 团划分 |
| 收稿时间： | 2008-10-15 |
| 修稿时间： | 2008-11-20
|
Clique partition based approximation scheduling algorithm on multiprocessor tasks |
| |
| HUANG Jin-gui.Clique partition based approximation scheduling algorithm on multiprocessor tasks[J].Computer Engineering and Applications,2009,45(4):4-8. |
| |
| Authors: | HUANG Jin-gui |
| |
| Affiliation: | HUANG Jin-gui Department of Computer Teaching,Hunan Normal University,Changsha 410083,China |
| |
| Abstract: | This paper studies the problem of scheduling model Pm |fix,pj =1|Cmax,that schedules a set of n independent multipro-cessor jobs with unit process time and prespecified processor allocation on a set of identical processors in order to minimize the makespan.The general problem Pm |fix|Cmax,that has widely been used in various fields such as the network parallel computing,the multi-casting system and the project plan,is proved to be NP-hard and cannot be approximated within a constant factor unless P=NP.This ... |
| |
| Keywords: | multiprocessor job scheduling approximation algorithm NP-hard problem clique partition |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
|
