###
DOI:
Journal of Software:2010.21(12):3211-3219

独立多处理机任务静态调度问题的近似算法
黄金贵,李荣珩
()
Approximation Algorithm for Scheduling Independent Multiprocessor Jobs
HUANG Jin-Gui,LI Rong-Heng
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3546   Download 3268
Received:June 26, 2009    Revised:November 04, 2009
> 中文摘要: 研究独立多处理机任务静态调度问题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 近似算法,优于目前已有文献的最好结果.
Abstract:This paper studies the multiprocessor job scheduling problem, and describes the m processors system, and analyze the algorithm for the problem of the offline 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.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60872039, 10771060 (国家自然科学基金) Supported by the National Natural Science Foundation of China under Grant Nos.60872039, 10771060 (国家自然科学基金)
Foundation items:
Author NameAffiliation
HUANG Jin-Gui  
LI Rong-Heng  
Reference text:

黄金贵,李荣珩.独立多处理机任务静态调度问题的近似算法.软件学报,2010,21(12):3211-3219

HUANG Jin-Gui,LI Rong-Heng.Approximation Algorithm for Scheduling Independent Multiprocessor Jobs.Journal of Software,2010,21(12):3211-3219