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

Approximation algorithm on multi-processor job scheduling

作　　者：黄金贵[1] 

机构地区：[1]湖南师范大学计算机教学部,长沙410083

出　　处：《计算机工程与应用》2008年第33期7-9,共3页Computer Engineering and Applications

基　　金：湖南省自然科学基金No.06JJ50105~~

摘　　要：研究多处理机任务调度模型Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行。该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法。在E.Bampis等人提出的Split-Round技术基础上,提出了该问题的一个改进的多项式时间近似算法,并从理论上证明了该算法在最坏情况下的近似比为(2m)^(1/2),优于E.Bampis等人给出的3m^(1/2)的结果。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 Pm｜fix｜ Cmax 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 3√m -approximation algorithm for this problem by using the split-round technique.This paper proposes a2√m-approximation algorithm for this problem based on the improvement of the split-round algorithm.

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

分 类 号：TP393[自动化与计算机技术—计算机应用技术]