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

Heuristic Algorithm for Single Job Parallel Machine Scheduling Based on Lower Bound of Optimum Solution

作　　者：朴惠淑[1] 贾春玉[2] 常留贤[3] 

机构地区：[1]大连海事大学交通运输管理学院,辽宁大连116026 [2]宁波工程学院经济与管理学院,浙江宁波315211 [3]电子科技大学中山学院,广东中山528402

出　　处：《工业工程与管理》2015年第2期62-67,共6页Industrial Engineering and Management

基　　金：国家自然科学基金资助项目(71271035)

摘　　要：针对单工序平行机排序LPT方法计算步骤多等问题,提出了一种适用于中小企业现场排序的最优解下限截取启发式算法。传统平行机排序最优解下限表达式存在因偏离最优解过大而难以引导排序走向最优的缺陷,改进后的下限表达式更加接近于最优解。从计算步骤多少和偏离最优解下限的最大偏差率两个角度,比较分析了最优解下限截取法与LPT法的特点。经实验数据验证,得出零件数与平行机数之比非整除且满足一定条件时,简单易行的截取法更优于LPT法的结论。For the problem of single job parallel machine scheduling LPT method cycles, the new heuristic intercept method to be more suitable for minor enterprises scheduling was proposed based on lower bound of optimum solution. The current formula of lower bound of optimum solution was too far from the optimal solution,and the improved formula was close to the optimal solution. From the views of cycles and the maximum deviation rate, the differences of intercept method and LPT method were comparatively analyzed. The test proved that under some conditions of the number of components being divisible not by the number of parallel machine,the optimal degree of the simple intercept method was better than LPT method.

关 键 词：平行机排序 最优解下限 LPT法 截取法 

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