Abstract: To study job-shop scheduling problem, scheduling procedure and scheduling result are analyzed. A processing procedure for minimizing idle time and several processing order rules for different idle time are proposed. The initial population generating operator, recombination operator and mutation operator of an evolution algorithm are designed, according to the processing procedure for minimizing idle time. The generalized Hamming distance is introduced into the selection operator and a population modification procedure is inserted into the algorithm to keep population’s diversity. Experiments on classical benchmark problems show that the minimizing idle time procedure is highly efficient and reliable, and that the evolution algorithm can reduce search space, improves search efficiency and avoid premature convergent phenomenon, and is stable and reliable.

Key words: Evolution algorithm, Job-shop scheduling problem, Minimizing idle time, Production scheduling