关键词: 置换流水车间调度, 遗传算法, 优先权值, 最大完工时间, 局部收敛

Abstract: In the existing genetic algorithms for permutation flow shop scheduling problem, the crossover and mutation operator is complex because of the processing sequence, the offspring is not similar to parent, and the algorithm easily falls into local optimum. To solve these problems, an improved genetic algorithm with priority-based value coding method and optimum limited operator was proposed. The coding method based on the priority values of the workpieces could avoid illegal coding, and the optimum limited operator could limit the propagation of the best individual to prevent falling into local optimum. The experiments show that this coding method is feasible and it can solve the practical problem when urgent workpieces must be processed firstly. The simulation results on benchmarks demonstrate that the proposed algorithm has superiority of smaller relative error and higher stable solution quality.

Key words: permutation flow shop scheduling, Genetic Algorithm (GA), priority value, makespan, local convergence