非相同并行加工系统的启发式调度算法

摘要：

该文讨论以极小化总处理时间(Makespan)为优化目标的并行机组工件调度问题。由于该问题是NP－完全的，目前的研究大都是寻找启发式算法并验证其最优性。该文提出一个新的发式算法FPSF(Fasting Processing Speed First)，并给出该算法的解与最优解之比的上界Sm/S1(4/3-1/3m)。研究表明， 该上界与Graham所提出的对于并行机组排的著名启发式算法LPT(Longest Processing Time)的上界具有可比性。

关键词： 调度 非相同并行机组 启发式算法 最坏情形分析

作者: 杨丹 李东

作者单位: 重庆大学理学院应用数学系

会议类型: 国内会议

会议名称: 中国运筹学会第六届学术交流会

会议地点: 长沙

会议语种:中文

页码: 719～727

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