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