| 《计算机学报》文章摘要 全文下载 | |
| 文章题目 | P4｜fix｜Cmax问题的最优规则调度算法 |
| 作者 | 黄金贵 李荣珩 |
| 作者单位 | (湖南师范大学计算机教学部 长沙4 10081) |
| 发表年份 | 2009 |
| 发表月份 | 8期(1631—1636) |
| 文章摘要 | 摘要 多处理机任务调度问题Pm｜fix｜Cmax(m≥3)是典型的强NP难问题，由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下，寻求该问题的较为理想的近似算法是极其困难的，通常从较少处理机数的系统着手研究.对于m=4的情形，文中研究了P4｜fix｜Cmax的规则调度算法，通过引入组调度技术，给出了该问题的一个线性时间的4/3-近似算法，并证明了该算法是4-处理机系统中的最优规则调度算法. 关键词：多处理机任务调度；规则调度；近似算法；NP-难问题 中图法分类号：TP393 DOI号: 10.3724/SP.J.1016.2009.01631 |