多目标同顺序流水作业的局部搜索算法  

Local search algorithm for multi-objective permutation flowshop sequencing problem

作　　者：董兴业[1] 黄厚宽[1] 陈萍[1] 

机构地区：[1]北京交通大学计算机与信息技术学院,北京100044

出　　处：《计算机集成制造系统》2008年第3期535-542,共8页Computer Integrated Manufacturing Systems

基　　金：国家973计划资助项目(2006CB705500)~~

摘　　要：针对求解最小化最大完工时间和总流程时间的多目标同顺序流水作业问题,提出了一个多目标局部搜索算法。针对两个目标,用现有的构造性算法生成两个解,作为该算法的初始解,然后从这两个初始解出发,以贪婪的方式求出新的Pareto最优解集,持续改进Pareto前沿。选择新的Pareto解的条件是该解既不被原解支配,也不被产生原解的解所支配,同时对某个目标改进最大。当所有解都陷入局部极小时,扰动已得到的Pareto解集,然后从扰动后的解集出发重新搜索。初始解和选择新的Pareto解的方法对算法性能有显著的影响。在基准问题上,与已有文献中的算法比较,结果表明所提算法的总体性能更优,特别是对较大规模的问题,此差异更具有显著性。A Multi-Objective Local Search （MOLS） algorithm was proposed to solve the permutation flowshop sequencing problem with hi-objectives of makespan and total flowtime. MOLS started from two initial solutions, which were constructed by existing heuristics with respect to both objectives, respectively; then new Pareto optimal solutions were searched in a greedy way until the process was trapped into a local optimum. Conditions of selecting a new Pareto solution were that the solution was not dominated by the original solution and the solution from which the original solution was generated, at the same time, the solution had minimal value with at least one of the two objectives. When all Pareto optimal solutions trapped into local optima, the Pareto optimal solutions were perturbed and restarted the search process. The initial solutions and method of selecting new Pareto optimal solution had significantly effected on the performance of the MOLS. Comparison results with existing algorithms on benchmarks showed that the MOLS performed better especially for relatively large instances with more striking statistical significance.

关 键 词：同顺序流水作业 多目标优化 元启发式算法 多目标局部搜索 

分 类 号：TP278[自动化与计算机技术—检测技术与自动化装置] TP301[自动化与计算机技术—控制科学与工程]