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

作者：朴惠淑,贾春玉,常留贤

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

发文机构：大连海事大学交通运输管理学院 宁波工程学院经济与管理学院 电子科技大学中山学院

关键词：平行机排序最优解下限LPT法截取法parallel machine schedulinglower bound of optimum solutionLPT methodintercept method

分类号： F224.3[经济管理—国民经济]