Hybrid evolutionary strategy algorithm for permutation flow shop scheduling

Evolutionary strategy algorithm is employed to optimize the permutation flow shop scheduling problem and a two-dimension encoding approach based on the job sequence is introduced. A kind of recombination operation based on two-point crossover and interchange is used to generate the offspring individuals, and a kind of mutation operation of some gene in the encoding stochastically generated is designed. The neighbor structure of the permutation flow shop scheduling solution is analyzed and three different local search approaches are presented. Experimental results show that hybrid evolutionary strategy algorithm can effectively optimize the permutation flow shop scheduling problem and has better performance than genetic algorithm and NEH heuristic algorithm. Moreover, in three local search approaches, the local search approach based on the interchange operation can obviously improve the performance of evolutionary strategy algorithm and be better than the other local search approaches.