|
Abstract: Four effective hybrid procedures are proposed for the job
shop scheduling problems by combining evolutionary algorithms (EA) with
simulated annealing algorithms (SA). These are genetic-simulated
annealing algorithms (GSA), enhanced genetic algorithms (EGA), enhanced
evolutionary programming (EEP) and parallel simulated annealing
algorithms (PSA). The cooperation of EA and SA intensify the
neighborhood search and to avoid premature convergence. The neighborhood
search template that employs a critical path is adopted to decrease the
search area and improve the efficiency of the exploration. Numerical
simulation demonstrates that within the framework of the newly designed
hybrid algorithms, the NP-hard classic job-shop scheduling problem can
be efficiently solved with higher quality, and that the optimization
performances of hybrid procedures are superior to the algorithm reported
in the literature. The simulation also indicates that the search ability
of mutations based on SA is stronger than crossover operation and that
the optimization power of EEP is better than other hybrid procedures.
Key words: Job shop scheduling Evolutionary algorithms Simulated
annealing algorithms Genetic algorithms Evolutionary programming
CLC No: F406
国家自然科学基金(50275078)和山东省自然科学基金(2004ZX14)资助项目.
Received 20040630, received in revised form 20041203
|