An Improved DNA Evolutionary Algorithm for Job Shop Scheduling

An improved evolutionary algorithm, namely DNA evolutionary algorithm was applied to solving job shop scheduling problems well known to be NP-hard. DNA evolutionary algorithm was a novel evolutionary algorithm based on the reproduction of DNA molecules. The scope of the solutions was enlarged by adding an exchange operation into the division operator so as to enhance the searching quality. Aiming at the feature of job shop scheduling model, the generality of the individuals was kept well and converging prematurely at local optimum was avoided using a new mutation operator combining sub-sequence reversing mutation and two operations changing mutation. Simulations were evaluated and contrastively analyzed in details for the famous benchmarks of mt10. Computational experiments indicate that the improved DNA evolutionary algorithm is more easier and effective comparing with GA algorithm and DNA evolutionary algorithm