一种基于改进遗传算法的车间调度问题研究  

Study on job shop scheduling based on modified genetic algorithm

作　　者：曾益[1,2] 

机构地区：[1]中南大学交通运输工程学院,长沙410083 [2]华东交通大学机电学院,南昌330013

出　　处：《机械设计与制造》2011年第7期180-182,共3页Machinery Design & Manufacture

基　　金：国家自然科学基金项目(70962002);江西省教育厅科学研究规划项目(GJJ09127);载运工具与装备省部共建教育部重点实验室开放基金资助

摘　　要：作业车间调度是一类求解较困难的组合优化问题,在考虑遗传算法早熟收敛问题结合模拟退火算法局部最优时能概率性跳出的特性,该特性最终使算法能够趋于全局最优。在此基础上,将遗传算法和模拟退火算法相结合,提出了一种基于遗传和模拟退火的混合算法,该算法将模拟退火算法赋予搜索过程一种时变性融入其中,具有明显的概率跳跃性。同时。通过选取Brandimarte基准问题和经典的Benchmarks基准问题进行分析,并应用实例对该算法进行了仿真研究。该结果表明,通过模拟退火算法与遗产算法相集合,可以使计算的收敛精度明显提高,是行之有效的,与传统的算法相比较,有较明显的优越性。As you know job shop scheduling problem is one of the NP-complete combinatorial optimal problems.In this case GA premature convergence is consedered in it combining the jump probability of simulated annealing algorithm（SA）,which is tending to be global optimal.Anda new hybrid algorithm based on genetic algorithm（GA）and simulated annealing algorithm（SA）is proposed,in which the algorithm of simulated annealing algorithm is given witha time-varying characteristical to integrate insearching process,which show the algorithm with a marked probability jump.meanwhile,by analyzing Brandimated and typical Benchmarks problems,the algorith is studied through simulation,which test shows that the method is feasible and effective compared with traditional one with obvious convergence precision improvment.

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

分 类 号：TH16[机械工程—机械制造及自动化] TP312[自动化与计算机技术—计算机软件与理论]