基于Petri网与GA—PSO算法的FMS优化调度

董立国

摘要：针对柔性制造系统调度难题，提出了一种基于Petri网与改进遗传-粒子群算法相结合的优化调度方法。利用Petri网对柔性制造系统进行建模，在分析传统调度算法的基础上提出了一种改进遗传-粒子群混合算法对建立的模型进行调度。通过调度验证表明，该算法能有效地解决多品种、小批量的柔性制造系统仿真时的调度问题。

关键词：柔性制造系统；调度；Petri网；遗传算法；粒子群算法

中图分类号：TP311 文献标识码：A 文章编号：1009-3044（2018）03-0046-02

1 概述

柔性制造系统（Flexible Manufacturing System，FMS）的典型特点是系统中时刻存在着异步推进的不同工艺流。在提高系统生产灵活性的同时，也对系统管理提出了很多新的挑战[1]。在一定的约束条件下，如何统筹安排系统的制造行为，以获得最优（或近似最优）的系统运行效率，这就是所谓的FMS优化调度问题[2]。针对上述FMS调度编码和收敛速率问题，本文设计了一种改进的GA-PSO算法求解FMS调度问题。

2 改进的GA-PSO的调度算法

2.1 染色体编码

因为PSO与GA的操作对象及进化策略并不相同，需拷贝两份初始染色体编码以用于后续的进化计算，更新粒子当前的适应度值。GA中染色体的编码采用整数的双层编码[3]。

2.2 适应度函数

本文设计的适应度函数为，其中为所有工序加工时间之和，为进化过程中每次迭代所得的加工完工时间[4]。

2.3 PSO迭代

按照公式（1）、（2）更新粒子的速度、位置，惯性因子执行公式（3）的线性递减策略，其中，、分别表示w取值上限及下限，通常取值为：，，t表示当前迭代步数。如果新粒子对应的适应度比局部历史最优可行解或者全局历史最优可行解更高，那么执行替换[5]。

2.4 GA选择算子设计

设种群中的个体的总数为N，种群个体其适应度函数值为f（t），则种群中该个体被选中的概率为公式（4）所示。

2.5 GA交叉算子设计

交叉概率用于控制交叉操作发生的频率，由于交叉概率过大时，种群中个体的更新过快，会使高适应度的个体很快被破坏掉；而当概率过小时，交叉操作发生的频率过低，使搜索停滞不前，因此本文采用线性递减的单点交叉策略。线性递减的方法如公式（5）所示[6]。

2.6 GA变异算子设计

GA变异算子如公式（6）所示同样采用线性递减策略。

3 FMS调度实例

为验证本文算法的有效性和通用性，下面通过具体实例进行验证，我们利用Matlab2013仿真软件实现算法。首先对一个简单FMS系统例子进行调度并与理论最优解进行验证。

3.1 FJSP调度实例

利用本文算法进行调度都得到了如图4所示的调度干特图，将其与实际加工计划对照，调度出的结果为实际可行解，这说明了本文算法求解FJSP的可行性。

3.2 JSP调度实例

JSP是FJSP的一种，与FJSP主要区别是：JSP的每道工序的加工路径（加工机器）是确定，而FJSP的加工路径是未知的。在作业车间调度中，JSP具有重要的代表性。为测试本文算法的有效性和通用性，下面将该算法应用到FT（也称为MT）和LA两类基准问题中[7， 8]，其中FT类选取了FT06、FT10两个不同规模子问题，LA选取了LA01、LA16两个不同规模子问题进行测试对比。

可见，本文算法对于求解小规模的JSP（FT06和LA01）在保证最优解的前提下有着极高的效率和稳定性。而对大规模系统（FT10和LA16）测试中，LA16问题得到了最优解，尽管FT10问题在这10次仿真没有收敛最优解，但也得到了较优解，说明本文算在大规模系统调度也具有较强的寻优能力和可行性。

4 结论

本文提出一种改进的基于遗传算法与粒子群优化算法相结合的调度算法，算法融合了遗传算法和粒子群算法各自的优点。最后以实例论证了本文算法的可行性和优点。

参考文献：

[1] 苏国军， 汪晋， 田立国. 基于Petri网模型的柔性制造系统优化调度[J]. 系统工程理论与实践， 2014， 34（10）：2716-2721.

[2] 曹阳. 基于赋时有色Petri网离散制造过程控制系统建模与仿真研究[D]. 长春工业大学， 2015.

[3] 蒋元凯， 韩兵， JiangYuankai，等. 启发式搜索在时间Petri网的共享资源调度中的应用[J]. 微型电脑应用， 2000， 16（12）：37-39.

[4] 韋志强. FMS生产调度建模、优化与仿真研究[D]. 西安电子科技大学， 2008.

[5] 郭海东. 遗传算法及其在生产调度中的应用研究[D]，2004.

[6] 马丽丽. 基于改进粒子群算法的车间作业调度问题研究[D]. 哈尔滨理工大学， 2010.

[7] Thompson H F G. Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules[J]. 1963.

[8] Lawrence S. Resource constraint project scheduling： An experimental investigation of heuristic scheduling techniques [J]. 1984.