陈 魁，毕 利

(宁夏大学 信息工程学院，银川 750021)

1 引 言

柔性作业车间调度问题(Flexible job shop scheduling problem，FJSP)是经典车间调度问题(Job shop scheduling problem，JSP)的延伸.已知FJSP是一个NP-hard问题.目前，FJSP的求解方法主要集中在群体智能优化算法，如遗传算法[1]和粒子群算法[2]等.

粒子群算法(Particle Swarm Optimization，PSO)相较于遗传算法具有收敛速度快、容易实现等优点，在求解FJSP中被广泛应用.丁舒阳[2]提出了一种离散粒子群优化算法求解FJSP，将不同的交叉策略引入PSO使其离散化.Shao[3]通过PSO的全局搜索与模拟退火算法的局部搜索相结合求解FJSP的帕累托解，采用拥挤距离来识别粒子的适应度.Song[4]采用多目标粒子群算法中加入变邻域搜索策略提高了PSO的开发能力，通过分配规则和调度规则提高初始粒子的质量.Edilson[5]将PSO和随机重启爬山算法结合求解多目标FJSP.Rim[6]在求解FJSP时，提出了一种两级粒子群优化算法，将FJSP的两个子问题机器选择和操作排序分成两层处理.Huang[7]提出了一种基于教和学的混合遗传粒子群优化算法来解决多目标FJSP.仲于江[8]提出了一种将小生境技术和PSO相结合求解多目标FJSP的优化方法，基于小生境技术计算粒子的删除概率对非支配解的外部存档进行更新.Li[9]提出了一种求解多模态优化的小生境粒子群算法，在该算法中加入平衡因子，使得小生境划分更均匀.

工件移动是柔性制造动态性的最直接体现，考虑工件运输时间的FJSP更贴切实际生产[10].赵宁[11]建立了考虑运输时间的关键链优化方式，将运输时间集成到经典FJSP的析取图模型中，结合邻域搜……