工件具有相似加工时长时两台机上LPT算法的性能分析

摘要

本文研究了工件具有相似加工时长时2台同类型平行机上LPT算法的最坏性能比。目标函数是使所有机器的最大完工时间达到最小。若工件序列L={J1,J2,...,Jn}中的工件满足pj∈[1,r](r≥1),证明了LPT算法的最坏性能比为r的分段线性函数,此结论改进了已有的最好结论,并且是不能再改进的最好结论。