基于最优解下限的单工序平行机排序启发式算法

摘要

针对单工序平行机排序LPT方法计算步骤多等问题,提出了一种适用于中小企业现场排序的最优解下限截取启发式算法。传统平行机排序最优解下限表达式存在因偏离最优解过大而难以引导排序走向最优的缺陷,改进后的下限表达式更加接近于最优解。从计算步骤多少和偏离最优解下限的最大偏差率两个角度,比较分析了最优解下限截取法与LPT法的特点。经实验数据验证,得出零件数与平行机数之比非整除且满足一定条件时,简单易行的截取法更优于LPT法的结论。