| 独立多处理机任务静态调度问题的近似算法 |
| |
| 引用本文： | 黄金贵,李荣珩.独立多处理机任务静态调度问题的近似算法[J].软件学报,2010,21(12):3211-3219. |
| |
| 作者姓名： | 黄金贵 李荣珩 |
| |
| 基金项目： | Supported by the National Natural Science Foundation of China under Grant 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 近似算法,优于目前已有文献的最好结果.
|
| 关 键 词： | 多处理机任务调度 近似算法 近似比 NP难问题 |
| 收稿时间： | 2009/6/26 0:00:00 |
| 修稿时间： | 2009/11/4 0:00:00 |
Approximation Algorithm for Scheduling Independent Multiprocessor Jobs |
| |
| HUANG Jin-Gui and LI Rong-Heng.Approximation Algorithm for Scheduling Independent Multiprocessor Jobs[J].Journal of Software,2010,21(12):3211-3219. |
| |
| Authors: | HUANG Jin-Gui and LI Rong-Heng |
| |
| Abstract: | |
| |
| Keywords: | multiprocessor job scheduling approximation algorithm approximation ratio NP-hard problem |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《软件学报》浏览原始摘要信息 |
|
点击此处可从《软件学报》下载全文 |
|
