Permutation flow shop scheduling algorithm based on a hybrid particle swarm optimization

摘要

The permutation flow shop scheduling problem is a part of production scheduling, which belongs to the hardest combinatorial optimization problem. A new hybrid algorithm is introduced which we called it HPSO, It combines knowledge evolution algorithm(KEA) and particle swarm optimization(PSO) algorithm for the permutation flow shop scheduling problem. The objective function is to search for a sequence of jobs in order that we can obtain the minimization value of maximum completion time (makespan). By the mechanism of KEA, its global search ability is fully utilized for finding the global solution. By the operating characteristic of PSO, the local search ability is also made full use. The experimental results indicate that the solution quality of the permutation flow shop scheduling problem based on HPSO is better than those based on Genetic algorithm, and than those based on standard PSO.