陈自豪，陈松航，陈 豪

(1.福建省复杂动态系统智能辨识与控制实验室 泉州装备制造研究所，福建 泉州 362200；2.中北大学 电气与控制工程学院，山西 太原 030051)

0 引 言

柔性作业车间调度问题(flexible job-shop scheduling problem,FJSP)可以被描述为每个工件的每道工序只能在一台机器上加工，并且只能加工一次，每道工序可以对机器进行选择，且加工时间确定。FJSP本质上是一种对资源进行优化配置的策略，是一类NP-hard问题。

遗传算法(genetic algorithm,GA)由于其简单通用、鲁棒性强、适于并行处理问题等特点被广泛应用于求解FJSP。张国辉等人[1]改进了种群初始化的方法，应用全局搜索、局部搜索与随机搜索相结合的策略，提升了算法的收敛速度。Pezzella F[2]在遗传算法框架中整合多种选择和和交叉策略，改进种群初始化方法验证了遗传算法求解FJSP的有效性。陈辅斌等人[3]通过引入免疫平衡原理改进了NSGA-Ⅱ算法的选择策略与精英保留策略解决了算法收敛性能不足的缺陷。Wan M[4]在遗传算法中整合多种选择策略并使用并行机制处理基因序列对个体进行编码改善了算法性能。FJSP中传统基准实例规模一般都不超过20×50，基准实例已不能满足对实际生产过程的算法模拟。

本文针对FJSP基准实例的特点与规则编写脚本生成大规模测试集来模拟大规模FJSP问题，提出了一种多种群NSGA-Ⅱ改进算法来求解，并通过大规模基准实例验证了该算法的可行性和有效性。

1 问题描述与建模

1.1 问题描述

本文研究的是FJSP中代表性的偏柔性作业车间调度问题(partial flexible job-shop scheduling problem，PFJSP)，部分工序可以选择工厂中的任意一台机器进行加工，剩余部分的工序就只能选择在一些特定机器上进行加工[5]。……