Qm‖Cmax的一种启发式算法的性能分析

摘要

本文讨论具有m台机器加工n个工件的Q‖Cmax问题,目标是最小化makespan(即处理完所有工件需要的最短时间).由于该问题是NP-完全问题,大多数研究是在寻求启发式算法并进行最坏情形分析.为此应用改进的LPT算法(即FPSF算法)对工件进行排序,证明该算法对于较少工件情况是最优的,得到在最坏情形下该算法比同类算法较紧的上界。