独立多处理机任务静态调度问题的近似算法  

Approximation Algorithm for Scheduling Independent Multiprocessor Jobs

作　　者：黄金贵[1] 李荣珩[2] 

机构地区：[1]湖南师范大学计算机教学部,湖南长沙410081 [2]湖南师范大学数学与计算机学院,湖南长沙410081

出　　处：《软件学报》2010年第12期3211-3219,共9页Journal of Software

基　　金：国家自然科学基金Nos.60872039;10771060~~

摘　　要：研究独立多处理机任务静态调度问题Pm|fix|Cmax,即在m个处理机系统中调度n个多处理机任务,每个任务指派到所需一组处理机上不可剥夺地执行.该问题应用广泛但早已证明为NP难问题,而且也不存在常数近似算法.分析了问题Pm|fix|Cmax和其中所有任务都是单位处理机时间的特殊情形Pm|fix,p=1|Cmax的调度,并利用实例划分(split scheduling,简称SS)、首次满足优先(first fit,简称FF)和最大宽度优先(large wide first,简称LWF)等方法,构造了问题Pm|fix,p=1|Cmax的2m+1近似算法和问题Pm|fix|Cmax的2 m近似算法,优于目前已有文献的最好结果.This paper studies the multiprocessor job scheduling problem, and describes the m processors system, and analyze the algorithm for the problem of the offiine version, both Pm｜fix｜Cmax of the scheduling problem with arbitrary process time jobs, and Pm｜fix｜, p=1｜Cmax of the scheduling problem with unit processing time jobs. Severalvery simple and practical polynomial time approximation algorithm are constructed, a （√2m ＋1）-approximation algorithm for the problem Pm｜fix, p=1｜Cmax and a 2√m-approximation algorithm for the problem Pm｜fix｜Cmax, by usingthe Split Scheduling （SS）, the First Fit （FF） and the Large Wide First （LWF） technique The results are better than any seen in the literature at present.

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

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]