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

摘要：

研究独立多处理机任务静态调度问题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近似算法,优于目前已有文献的最好结果.

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

所属期刊栏目：21

分类号：TP316(计算技术、计算机技术)

资助基金：the National Natural Science Foundation of China under Grant Nos.60872039, 10771060

在线出版日期：2011-03-23（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：3211-3219