关键词: 嫁接共生遗传算法, 车间作业调度问题, 早熟

Abstract: Standard genetic algorithm requires a high computing time and has a low success rate due to premature convergence. Aiming at these limitations, an improved algorithm called Grafting-Symbiosis Genetic Algorithm (GSGA) is developed for job-shop scheduling problem. The introduction of grafting population and the strategy of cross operation over two populations can speed up the evolution process; the employment of double crossover operators and the evolution during the stage of symbiosis can enhance the ability of the improved algorithm to find new solutions, hence the high resolution of the solution. Meanwhile, all the measures proposed above can fight premature convergence. Finally, the superiority is demonstrated by the comparison with the genetic algorithms available, hence its importance in application is proved.

Key words: grafting-symbiosis genetic algorithm, job-shop scheduling problem, premature convergence