Abstract:

To improve the searching performance of job-shop scheduling algorithms,the population entropy for eva-luating the orderliness（difference） of the algorithm population is proposed by analyzing the convergent graph of the simulated annealing genetic algorithm.Then,a modified simulated annealing genetic algorithm is proposed based on the population entropy,which adapts itself to the variation of population via the dynamic change of both the crossover probability and the mutation probability with the population entropy. Thus, the population diversity is increased, the premature convergence of the algorithm is overcome, and the searching performance is improved. Simulated results show that the proposed algorithm has great superiority in the searching performance. As compared with the traditional genetic algorithm, in the same initial and convergence conditions for the FT10 problem, the optimal result is improved from 998 to 930 and the deviation reduces from 9.78% to 1.94%, while for the LA36 problem, the optimal result is improved from 1 359 to 1 278 and the deviation reduces from 10. 29% to 2.97%.

Key words: genetic algorithm, simulated annealing algorithm, population entropy, job-shop scheduling, hybrid algorithm