DOI: 10.3724/SP.J.1087.2013.03576

Journal of Computer Applications (计算机应用) 2013/33:12 PP.3576-3579

Improved genetic algorithm for solving permutation flow shop scheduling problem

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

ReleaseDate:2014-07-21 16:58:56