一种融合模拟退火的遗传算法在柔性作业车间调度中的应用

王家海　吕程

摘要：针对理论上属于NP完全问题的车间离散调度问题，在传统的遗传算法搜索中融入模拟退火算法，同时按照一定的规则生成初始种群。采用机器码和工序码相结合的编码方式，以全局选择、局部选择以及随机生成的方式产生初始种群，同时针对遗传算法局部搜索能力较差、易出现早熟现象的缺点，考虑模拟退火算法提高全局优化概率搜索。仿真结果表明融合了模拟退火算法遗传算法性能具有更快的收敛性和寻优效果。

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

中图分类号：TP301 文献标识码：A 文章编号：1007-9416（2019）01-0133-04

1 概述

FJSP问题是作业车间调度问题（JSP）的扩展[1]，其突出特点是同一个加工任务有多台加工设备可供调度选择。FJSP是典型的组合优化问题，更加接近实际的生产调度环境，但同时问题复杂度相对于JSP也更高，对于此类问题，传统的数学优化方法无法在相对有限的时间内求解，因此采用近年来兴起的智能优化算法成为了一个可行的解决方法。作为智能算法之一的遗传算法在此问题上得到了广泛的应用，Ho等[2]采将启发式算法与遗传算法结合，提出一种混合算法， Teekeng等[3]设计了一种模糊轮盘赌的种群选择操作廖珊[4]采用一种改进的GA算法，设计了自适应的选择、变异、交叉算子，李铁克[5]提出文化GA求解FJSP。

遗传算法虽然具有较强的全局搜索能力，但同时也存在着过早收敛、容易陷入局部最优、适应性较差等缺点。模拟退火算法具有较强的局部搜索能力，其不仅接受使目标函数变好的解，还能以一定的概率接受使目标函数变差的解，因此该算法具有跳出局部最优解的能力。……