一种基于GA－SA－TS算法的车间调度方法的研究

刘红军 赵 帅 赵 雷

(①沈阳理工大学机械工程学院，辽宁沈阳 110159;②北京城建设计研究总院有限责任公司，北京 100037)

随着科学技术的不断发展，社会节奏的不断加快，将科学的管理调度技术与车间生产调度紧密结合起来，在现代加工车间中已得到了普遍的应用。而如何将科学技术与车间生产调度更好地融合到一起，成为了当今科学领域普遍重视的问题。车间调度问题实质上就是研究在已有的资源条件和一定的约束条件下，对加工任务进行加工时间、机器、顺序等的合理分配，从而使生产加工达到最优化的状态。

本文针对遗传算法的局部搜索能力差，易限于局部最优等缺点，提出了一种适用于车间调度研究中的混合遗传算法(GA－SA－TS)，即将模拟退火算法、禁忌搜索算法与遗传算法混合使用。该算法的核心在于:在遗传算法的交叉机制中引入模拟退火算法的思想，形成模拟退火－交叉机制，从而避免了遗传算法本身易早熟的缺陷。在变异机制中使用禁忌搜索算法的思想，形成禁忌搜索－变异机制，以此解决遗传算法变异压力问题。通过这些方面的改进，提高了遗传算法的优化效率。

1 车间调度问题的描述

车间调度问题就是研究N(N1，N2，…，NN)个工件在M(M1，M2，…，MM)台机器上进行加工，每个工件具有一定数量的工序J(J1，J2，…，JJ)，每道工序可以在若干台机器上加工，加工的过程按照工件的工艺顺序完成。工件在加工的过程中要遵循以下约束:

(1)每台机器在每个时刻只能加工……