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

Abstract: A Multi-Objective Local Search (MOLS) algorithm was proposed to solve the permutation flowshop sequencing problem with bi-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

Key words: permutation flowshop, multi-objective optimization, metaheuristic, multi-objective local search