李运霞，杜 娟，孙王路

(太原科技大学 机电学院，太原 030024)

0 引言

路径柔性的车间调度问题作为传统作业车间调度问题(Job-shop Scheduling Problem，JSP)的扩展，具有灵活性、复杂性、约束性、非线性、多极小性等特点。路径柔性车间调度作为工艺柔性的一个分支，在现代制造业中具有重要的应用价值和理论意义，是亟需解决的一类调度问题。

路径柔性的作业车间调度问题减少机器约束，增加工序可选机器的不确定性，是复杂的强NP 难题。目前，国内外对此问题进行了多方面的研究，并取得了一定成果。邵斌彬等［1］提出柔性车间的基于综合分派规则的快速启发式调度算法;贺仁杰等［2］提出用知识型协同演化方法求解柔性车间作业调度问题，优化性能良好;王万良等［3］针对局部收敛问题将粒子群法进行改进，求解柔性车间作业调度问题;Seyed Habib A.Rahmati［4］针对柔性作业车间调度，提出生物地理优化算法(BBO);遗传算法［5-7］在柔性车间调度中也取得了一定成果。针对路径柔性的作业车间调度特点以及上述算法的局限性，本文提出一种多种群遗传算法(Multiple Population Genetic Algorithm，MPGA)，采用整数编码和自适应遗传算子，对各种群间进行协同优化，得到最优解。通过文献实例和实际应用验证算法的有效性。

1 路径柔性车间调度模型

假设有n个工件分配至m台设备上加工，每个工件i(i =1，…，n)有pi道工序{pi1，pi2，…pini}，工序pik的机器选择集为mik(mik⊆m)。pik在mj(mj⊆mjk)上的加工时间为Tikj，Tsikj为工序pik在mj开始时间，Te ikj为工序pik在mj的完工时间。工件i最后一道工序的完成时间Ci。Ci通常指工件的最短完工时间为性能指标，即: