计算机工程与应用 ›› 2009, Vol. 45 ›› Issue (4): 4-8.DOI: 10.3778/j.issn.1002-8331.2009.04.002

• 博士论坛 • 上一篇    下一篇

应用团划分方法改进多处理机任务近似调度

黄金贵   

  1. 湖南师范大学 计算机教学部,长沙 410083
  • 收稿日期:2008-10-15 修回日期:2008-11-20 出版日期:2009-02-01 发布日期:2009-02-01
  • 通讯作者: 黄金贵

Clique partition based approximation scheduling algorithm on multiprocessor tasks

HUANG Jin-gui   

  1. Department of Computer Teaching,Hunan Normal University,Changsha 410083,China
  • Received:2008-10-15 Revised:2008-11-20 Online:2009-02-01 Published:2009-02-01
  • Contact: HUANG Jin-gui

摘要: 研究多处理机任务调度模型Pm|fixpj=1|Cmax,即在m个处理机系统中调度n个时间长度都为1的多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。这类问题在网络并行计算、多播系统及工程规划等领域都有广泛的应用,但早已被证明为NP难问题,而且也不存在常数近似算法。基于团划分方法构造了该问题的多项式时间近似算法,通过模拟实验进行了验证,和最大宽度优先(LWF)算法相比,该算法花费时间较长,近似比性能要好。

关键词: 多处理机任务, 调度, 近似算法, NP难问题, 团划分

Abstract: This paper studies the problem of scheduling model Pm|fixpj=1|Cmax,that schedules a set of n independent multiprocessor 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 paper proposes an approximation algorithm for this problem based on the approximation clique partition method.By the analysis from test data,this algorithm presents more optional ratio preference.

Key words: multiprocessor job, scheduling, approximation algorithm, NP-hard problem, clique partition