Abstract: Standard Genetic Algorithm has limitations of low convergence rate and premature convergence in solving job-shop scheduling problem, and some improved algorithms available only solve one of those limitations. To it, this paper presented a Grafted Genetic Algorithm(GGA) inspried by graftage in botany. The improved algorithm accelerates convergence rate greatly and also increases the ability to fight premature by introducing grafted population and crossover probability matrix. Finally, the algorithm was test-proved, and it shows the superiority in terms of stability, convergence and precision.

Key words: Grafted Genetic algorithm, job-shop scheduling problem, hybrid optimization strategy