• CN:11-2187/TH
  • ISSN:0577-6686

›› 2005, Vol. 41 ›› Issue (6): 224-227.

• 论文 • 上一篇    下一篇

基于进化算法和模拟退火算法的混合调度算法

潘全科;朱剑英   

  1. 聊城大学计算机学院;南京航空航天大学机电学院
  • 发布日期:2005-06-15

EFFECTIVE HYBRID PROCEDURES BASED ON EVOLUTIONARY ALGORITHMS AND SIMULATED ANNEALING ALGORITHMS FOR JOB SHOP SCHEDULING PROBLEMS

Pan Quanke;Zhu Jianying   

  1. College of Computer Science, Liaocheng University College of Mechanical & Electrical Engineering, Nanjing University of Aeronautics and Astronautics
  • Published:2005-06-15

摘要: 将进化算法与模拟退火算法相结合,提出四种有效的混合调度算法,即遗传退火算法、改进遗传算法、改进进化规划和并行模拟退火算法。两种算法搜索机制的互补增强了全局探索能力,基于关键路径的邻域函数运用提高了算法的效率。仿真结果表明:混合算法在求解质量和求解效率方面均有优势,优于国外同类研究成果;基于模拟退火的变异算子的搜索能力优于交叉算子;改进进化规划优于其他混合算法。

关键词: 进化规划, 进化算法, 模拟退火算法, 遗传算法, 作业调度

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. Nu-merical 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 litera-ture. 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: Evolutionary algorithms, Evolutionary programming, Genetic algorithms, Job shop scheduling, Simulated annealing algorithms

中图分类号: