并行任务调度的近似算法

摘要：

并行任务调度不论是从理论上还是应用上近年来都倍受关注.但是目前出现的大量算法很难应用于实际,基于此,本文探讨了典型的调度问题P3|fix|Cmax,这类问题是强NP-难的.本文在Goemans的研究基础上,给出了一个很简单的线性算法,构造出调度性能为9/8的半规则调度,改进了Goemans的7/6的结果.

关键词： 并行任务调度 近似算法 线性算法

作者: 黄金贵 康宝生

作者单位: 湖南师范大学计算机系,长沙,410081 西北大学数学系,西安,710069

会议类型: 国内会议

会议名称: 第一届全国几何设计与计算学术会议

会议地点: 山东青岛

会议语种:中文

页码: 184-190

在线出版日期: 2002-06-01（万方平台首次上网日期，不代表论文的发表时间）