P4|fix|Cmax问题的最优规则调度算法

• 作者: 李荣珩 黄金贵
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 多处理机任务调度 规则调度 近似算法 NP-难问题
• 年，卷（期）: 2009,（8）
• 所属期刊栏目: 研究论文与技术报告
• 页码范围: 1631-1636
• 页数: 6页
• 分类号: TP393
• 字数: 5538字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2009.01631

摘要

多处理机任务调度问题P4|fix|Cmax(m≥=)是典型的强NP难问题,由于其在并行环境中的实际意义而受到越来越多的关注.但在一般情形下,寻求该问题的较为理想的近似算法是极其困难的,通常从较少处理机数的系统着手研究.对于m=4的情形,文中研究了P4|fix|Cmax的规则调度算法,通过引入组调度技术,给出了该问题的一个线性时间的4/3-近似算法,并证明了该算法是4-处理机系统中的最优规则调度算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	黄金贵	湖南师范大学计算机教学部	14	69	5.0	8.0
2	李荣珩	湖南师范大学计算机教学部	11	25	3.0	4.0