Abstract: An improved genetic algorithm is proposed for multi-objective of Permutation Flowshop Scheduling Problem （PFSP） to optimize the makespan and total flow time. In order to keep the diversity of the population, the initial population is generated by combining heuristic algorithm and random algorithm in the proposed algorithm. The procedure of evolution is completed with selection, crossover, mutation operation and update strategy. When population evolutionary stagnated, the re-initialization mechanism is introduced to restore diversity. In addition, a variable neighborhood search algorithm is designed to accelerate population convergence and jump out of local optimum. Compared with several other optimization algorithms through experiment on the benchmarks, the results show that the proposed algorithm in both solution quality and stability is superior to other algorithms.

Key words: multi-objective, permutation flowshop scheduling, genetic algorithm, variable neighborhood search

摘要： 针对多目标置换流水车间调度问题（PFSP）提出了一种改进的遗传算法，用于优化最大完工时间和总完工时间。该算法采用启发式算法和随机算法相结合产生初始种群，以保持种群多样性;通过选择、交叉、变异操作以及群体更新策略完成进化过程;当种群进化停滞时，引入群体重新初始化机制恢复多样性。此外，设计了一种变邻域搜索算法，加速种群收敛并跳出局部最优。通过基准测试问题实验以及与其他几个优化算法比较，结果表明，提出的算法无论在求解质量还是稳定性方面都优于其他算法。

关键词: 多目标, 置换流水车间调度, 遗传算法, 变邻域搜索