计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (33): 7-9.DOI: 10.3778/j.issn.1002-8331.2008.33.002

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

任意处理时间的多处理机任务调度近似算法

黄金贵   

  1. 湖南师范大学 计算机教学部,长沙 410083
  • 收稿日期:2008-07-28 修回日期:2008-08-21 出版日期:2008-11-21 发布日期:2008-11-21
  • 通讯作者: 黄金贵

Approximation algorithm on multi-processor job scheduling

HUANG Jin-gui   

  1. Department of Computer Teaching,Hunan Normal University,Changsha 410083,China
  • Received:2008-07-28 Revised:2008-08-21 Online:2008-11-21 Published:2008-11-21
  • Contact: HUANG Jin-gui

摘要: 研究多处理机任务调度模型PmfixCmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上,提出了该问题的一个改进的多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为2(2m)-2,优于E.Bampis等人给出的3m-2的结果。

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

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.

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