求解车间作业调度问题的混合遗传模拟退火算法  

Mixed Genetic Algorithm and Simulated Annealing Algorithm for Solving Job Shop Scheduling Problem

作　　者：周鑫 马跃[2] 胡毅[2] 

机构地区：[1]中国科学院大学,北京100039 [2]中国科学院沈阳计算技术研究所,沈阳110168

出　　处：《小型微型计算机系统》2015年第2期370-374,共5页Journal of Chinese Computer Systems

基　　金：面向离散制造业的分布式数控系统(DNC)研发及应用示范资助

摘　　要：为了克服传统遗传算法解决车间作业调度问题的局限性,结合遗传算法(GA)和模拟退火算法(SA)的优点,提出一种混合遗传模拟退火算法(GASA),以便高效地解决车间作业调度问题.该算法既发挥了遗传算法收敛速度快、模拟退火算法搜索面广的优点,又克服了前者收敛容易早熟而后者收敛速度较慢的问题.在算法的操作细节上,加入自适应调整的遗传操作及最优个体保留策略,以及增加记忆功能的模拟退火操作与收敛准则.从而既防止了算法会陷入局部最优解的问题,又提高了算法的收敛速度及搜索效率.将提出的混合遗传模拟退火算法(GASA)应用于Muth和Thompson基准问题的实验运行,证明了该算法的高效性和有效性.In order to overcome the limitations of traditional genetic algorithm for solving job shop scheduling problem, combining the advantages of genetic algorithm and simulated annealing algorithm, a hybridgenetic simulated annealing algorithm is presented tosolve the job shop scheduling problemefficiently. The algorithm put to the best use the genetic algorithm which converges rapidly and the simulated annealing algorithm which explores the full model space, as well as overcoming the problems of the premature of the former and the latterwhich works at low convergence speed. The genetic operation of adaptive adjustmentand the strategy of protecting elitists, and the operation of convergence norms and simulated annealing with memorizing function are applied intothe details of algorithm, so as to prevent the algorithm from local optimum and to raise the convergencespeed as well as the search efficiency. Appling thehybrid- genetic simulated annealing algorithm toMuth and Thompson＇ s benchmark problem, proved the feasibility and effectiveness of the pro- posed algorithm.

关 键 词：车间作业调度 模拟退火算法 遗传算法 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]