FENG Shi kou, BAO Min, ZHANG Wei

 

(Faculty of Mechanical Engineering & Automation, Zhejiang Sci Tech University, Hangzhou 310018, China)

 

 

Abstract: Aiming at the premature convergence of genetic algorithm in solving the job shop schedule problem(JSP), the convergence and searching efficiency and optimal solution of the genetic algorithm were studied, simulated annealing algorithm was introduced and the genetic algorithm was improved leading to the production of the new hybrid genetic algorithm. In the new algorithm, crossover operators and mutation operators based on the job number were redesigned. Adaptive crossover probability and mutation probability were adopted. Metropolis criterions were introduced in each generation of genetic evolution. The good combination of genetic algorithm and adaptive probability and hybrid simulated annealing algorithm could effectively improve the searching ability of the algorithm. FT06 scheduling problem was simulated by means of genetic algorithm and simulated annealing algorithm and hybrid simulated annealing algorithm. The simulated results indicate that the new hybrid genetic algorithm can improve the searching efficiency and the satisfactory scheduling scheme is obtained.

 

Key words: genetic algorithm; simulated annealing; job shop schedule