王玉芳，葛嘉荣，缪 昇，马铭阳

(1.江苏省大气环境与装备技术协同创新中心， 南京 210044；2.南京信息工程大学 自动化学院， 南京 210044；3.江苏省大数据分析技术重点实验室， 南京 210044)

柔性作业车间调度问题(flexible job shop scheduling problem，FJSP)是一种经典车间调度问题，其作为传统作业车间调度问题(job shop scheduling problem，JSP)的延伸，具有更广泛的使用环境和更复杂的求解空间。超过3台机器的JSP已被证明是NP问题[1]。因此，作为延伸问题的FJSP也具有NP困难。FJSP问题中包含2个子问题：机器选择和工序排序问题。2个决策空间增加了求解难度。

多年来，如禁忌搜索[2]、遗传算法[3]、粒子群算法[4]、人工蜂群算法[5]等的许多智能算法被用于解决车间调度问题。李明等[6]引入殖民同化和革命策略的新型帝国竞争算法在解决多目标FJSP中取得了高质量的解；Zhang等[7]通过加强局部搜索弥补遗传算法“易早熟”的缺陷；Maroua等[8]结合实际生产活动，提出了双步粒子群算法，保持了算法的鲁棒性；顾九春等[9]提出基于记忆池的离散个体更新方法，使多目标算法的适用性更强。但这些算法大多从算法本身或模型入手，未采取启发式规则，难免造成算法性能冗余。另外，如何跳出局部最优解一直都是求解FJSP的重点和难点，还存在很大的改进空间。针对上述问题，提出一种改进遗传算法(new improved genetic algorithm，NIGA)求解FJSP。

1 问题描述

FJSP问题描述：工件集{J1，J2，…，Jn}中的n个工件要在机器集{M1，M2，…，Mm}中的总计m台机器上进行加工，每个工件包含若干道工序，每道工序有若干台机器可以选择，工序的加工时间也因机器的选择不同。

根据实际生产情况，FJSP问题需要满足以下约束条件：