柔性制造系统时延Petri网模型排产优化研究

洪 良，王艺翔，南恺恺，田海霖

（西安工程大学电子信息学院，陕西 西安 710048）

1 引言

柔性制造系统[1（]Flexible Manufacturing Systems，FMS）在工业系统中的生产效率问题受到越来越广泛的关注。当生产目标发生变化时，若FMS不能及时调整生产计划，容易产生资源闲置、系统停滞等问题，从而降低生产效率。因此，如何在多项约束条件下提高FMS的排产效率，是制造产业中需要重视的问题。

排产优化问题是一个NP−hard问题，文献[2]提出了一种基于整数线性规划的算法，在系统参数变化后调整生产计划，但在复杂的实际生产中随着计算对象的增多会产生状态空间爆炸问题。文献[3]提出一种启发式算法解决并行多机组工件加工最短时间问题，但对大规模调度问题不能建立相应的模型，从而降低问题处理的效率。因此，为复杂FMS建立适合的模型十分必要。文献[4]可以描述系统的动态行为，可简单准确地表示系统中的并发、资源共享、冲突、相互抑制等特征，图像界面直观清晰，这些特点都表明Petri网FMS建模方面的优越性。目前，Petri网理论已经在车间生产调度问题中得到广泛应用。文献[5]提出应用可达分析技术，在可达图中选择最优路径来提高效率的方法，但是该方法面对大规模复杂系统时，同样存在状态爆炸计算中止的问题。可见，普通Petri网在解决FMS排产优化问题时存在一定的局限性。时延Petri网对FMS建模时可以准确描述系统的时间和路径等约束信息，因此更适合于排产优化研究。

文献[6]提出时延Petri网启发式派遣规则法解决FMS的排产优化问题，但启发函数和实际应用联系过于紧密，其针对性的模型导致通用性不强。遗传算法在全局范围内快速有效地寻优，文献[7]将时延Petri网与遗传算法结合，既可以通过网模型准确地描述系统的动态过程，也可以在短时间内寻找到最优或次优解，具有通用性，但是仅依靠遗传算法寻优存在早熟现象容易陷入局部最优的现象。因此，应用时延Petri网为FMS建模，在遗传算法的并行搜索的基础上，结合模拟退火算法引入随机元素跳出局部最优的能力，提出一种融合遗传算法和模拟退火算法的混合算法，解决FMS的排产优化问题，提高生产效率。

2 时延Petri网

（1）Petri网（Petri Nets，PN）定义为一个五元组，可表示为N=（P，T，F，W，MO），P和T分别称为库所和变迁的集合，其中P≠ø，T≠ø，P∩T=ø。F⊆（P×T）∪（T×P）称为有向弧集，W：（P×T）∪（T×P）➝N+为有向弧的权函数，M0：P➝N+是一个列向量，称为N的初始标识，库所中黑点被称作托肯，M0表示初始状态下所有库所中的托肯数。Petri网是有向图，库所和变迁都称为Petri网的节点。库所p∈P表示系统对象的某种状态，变迁t∈T表示改变状态的事件。

（2）设x∈P∪T是Petri网N的节点。x的前置集·x定义为·x={y∈P∪T｜（y，x）∈F}，后置集·x定义为·x={y∈P∪T｜（x，y）∈F}。

（3）时延Petri网（Timed Petri Nets，TdPN）表示为Nt=（N，D），其中N表示普通Petri网，D表示时延dt的集合，dt∈N+是变迁t∈T的延迟，N+为正整数的集合。当且仅当∀p∈·t，M（p）≥W（p，t），变迁t∈T在标识M下使能，记为M[t〉。变迁t发射后，经过dt个单位时间，变迁t发射结束，从·t中转移定量的托肯到t·中。

3 FMS的TdPN模型

FMS的特点表明，单一加工工序可经由不同路径实现。加工工序的路径信息称为该工序的约束信息，工序约束信息表明该工序经由若干机床按照特定顺序完成加工，同时限定解空间内的可选择路径，找到最优或次优解。

引入TdPN为FMS建模，考虑工序的约束信息，在普通Petri网的基础上，建立TdPN模型的具体步骤如下：

（1）设该系统中共有β台机床，共有z个包含约束信息的工序变迁。选择其中任一变迁t（ii∈｛1，2，…，z｝），·ti=｛p｝s，·ti=｛ps+1｝，ps和ps−1分别表示ti的输入库所和输出库所，Si（kk∈｛1，2，…，n｝）表示工序ti对应的n种加工路径之一，若路径Sik中只包含一个机床，用变迁ti表示该机床的工序，若路径Sik中包含多个机床，则用变迁tikx表示这些机床的工序；x∈｛1，2，…，β｝表示机床的编号，资源库所pmx表示机床x的状态；

（2）删除变迁ti；

（3）case1（该路径仅包含一个机床）：添加资源库所pmx与变迁tik，构成可达路径EP（pmx，tik）=pmxtik，其中pmx•=·pmx=｛ti｝k，tik•=｛pmx，ps｜1｝，·tik=｛pmx，p｝s，此时M（opmx）=1；

case2（该路径包含α（1<α≤β）个机床）：根据约束信息添加α个资源库所pmx与数量相等的变迁tikx，构成可达路径EP（pmx，tikx′）=pmxtikx…pmx’tikx′，pmx（’x ′∈｛1，2，…，β｝）表示资源库所，与最后一个变迁tikx′对应，其中pmx•=·pmx=｛tikx｝，tikx′•=｛pmx′，ps+1｝，·tikx=｛pmx，p｝s，此时M（opmx）=1；

（4）已建立的独立网模型末尾库所与下一组网模型的首部库所为同一库所，通过该库所将独立的网模型连接，建立完整的TdPN。

为使网模型更加简洁，网模型中名称相同的资源库所pmx重复出现在网模型的不同位置但实际表示同一库所。一套简单加工进程的普通Petri网模型，如图1所示。其中各库所和变迁表示的含义，如表1所示。该进程中的所有工序均由四台机床m1、m2、m3、m4完成，每台机床同时只能加工一个工件。单一工序可选择约束信息内的任意生产路径完成加工，如工序t1可由S11、S12、S13中的任一路径完成，S11表示由m2和m3顺序加工完成工序t1的工作。描述了该简单加工进程中各变迁的生产路径和时间约束信息，如表2所示。

表1 Petri网各节点与实际加工过程映射关系Tab.1 Mapping Relations Between Nodes of Petri Nets and Machining Processes

图1 简单加工进程的Petri网模型Fig.1 The Petri Net of A Simple Machining Process

表2 工序生产路径约束和工作耗时（分钟）Tab.2 Production Path Constraints and Worktime（min）

在图1普通Petri网模型中增加时间参数与加工路径信息，得到时延Petri网模型，如图2所示。图2（a）中的与构成路径S11，表示机床m2和m3顺序参与加工，分别耗时3min和9min。同理，t12构成路径S12、t13构成路径S13。图2（b）、图2（c）表示对t2、t3发生时的不同加工路径，最终，将三个独立部分通过共享库所p3、p4连接复合，建立完整的TdPN模型，如图2（d）所示。

图2 TdPN建模步骤Fig.2 Modeling Steps of TdPN

4 算法

已建立的TdPN模型显示，FMS生产具有加工路径多样性。引入TdPN 为FMS 建模，更加清晰地描述了某项工序的多种路径，但同时网模型中也产生了资源冲突问题。为解决模型中的资源冲突，实现FMS的高效生产，设计遗传算法和模拟退火算法的混合算法。

遗传算法的特点是高度并行和自适应性，同时比较多个解，在搜索效率上有较高的优越性。对目标函数G（x）求解时，设置初始变量，最大遗传代数imax，种群数量Size，交叉概率Pc和变异概率Pm，种群可表示为S=[S1，S2，…，Sr，…，Ssize]T，其中，当染色体长度为l时整个种群S是Size×l的矩阵。算法根据适应度判断是否接受新解，适应度函数为：

模拟退火算法在解空间的搜索中引入随机元素，以Metrolo‐lis准则判定当前解是否被接受并有概率跳出局部最优解。初始化时给定初始温度To，目标函数G（x），模型扰动产生新解x′及对应的目标函数值G（x′），函数差值△f=（fx′）−（fx），若△f≤0则接受新解为当前解，若△f>0，则以概率p接受新解。

式中：降温系数q∈（0，1），当前温度T=To·qk，k—常数，表示当前迭代次数。

为保证算法的通用性，又使得算法易于实现，采用变迁发生序列作为染色体编码，对现有网模型中的变迁发生序列寻优，通过计算时间找到最优或次优变迁发生序列。因此，本算法优化的目标函数为：

式中：di—染色体S（rr∈[1，size]）对应的变迁ti发生的时延；

l—FMS总工序数，变量与建模步骤中的变量保持一致。

算法的约束条件：

（1）TdPN模型运行规则

当且仅当∀p∈·t，M（p）≥W（p，t），变迁t在标识M下使能，变迁t在满足工件加工规则时，经过dt个单位时间，从·t中转移一个托肯到t·中。

（2）工件加工规则

工件按照工序顺序进行加工，但每道工序可通过满足工序约束信息的任意路径完成，路径对应变迁t的发射顺序是固定的。

（3）设备资源竞争

当多个变迁t同时使能，且满足工件加工规则时，依据混合算法产生的变迁发生序列，确定加工路径。

基于遗传算法与模拟退火算法的混合算法步骤如下：

输入：TdPN网模型与工序约束矩阵，最大遗传代数imax，种群数量Size，交叉概率Pc和变异概率Pm，初始温度T0，降温系数q；

输出：当前种群最短加工时间及其对应的染色体序列。

（1）根据TdPN中变迁个数确定染色体长度l，产生初始种群其中每个基因位的选择由各工序的生产路径约束信息决定，令i：=0，i表示当前遗传代数；

（2）若i

（3）计算适应度函数（fS）r=

（4）轮盘赌选取个体进入下一代，个体Sr被选择的概率P（S）r

（5）以交叉概率Pc运算，将交叉算子插入种群；

（6）在约束信息范围内以变异概率Pm运算，将变异算子插入种群；

（7）模拟退火操作随机生成扰动解Sr′，计算△f=（fSr′）−（fS）r，若△f≥0，或者△f≤0且符合Metropolis准则，Sr：=Sr′，更新种群；否则，不再更新种群；

（8）降温T：=To·qi，i：=i+1，返回（2）。

采用图2已建立的TdPN对上述算法进行验证，该网模型中共有3个变迁，故染色体共包含3个基因位，其约束信息，如表1所示，因此共有12种加工方案。经算法多次实验，可以得到最优加工路径为S13S22S32，与其对应的最短加工时间为12分钟。

5 算例

柔性车间中4台机床m1、m2、m3、m4组成的FMS，如图3所示。

图3 FMS图示Fig.3 Presentation of FMS

每台机床同时只能执行一项操作，各机床分别承担车削、装配等操作，该系统完整加工工件流程共需要8道工序，每道工序由特定的路径完成，4台设备通过机械臂来调度，设备之间相互配合，按已设定的程序工作。根据系统加工顺序建立的Petri网模型，如图4所示。各项加工工序的约束信息，如表3所示。

表3 FMS中机床路径约束信息和工作耗时（分钟）Tab.3 Production Path Constraints of FMS and Worktime（min）

图4 FMS Petri网模型Fig.4 Petri Nets of FMS

建模过程中，所有表示待执行工序的库所中均保留至少一个托肯，保证任意变迁都是使能的。应用提出的混合算法，实验中的算法各参数设置为：最大遗传代数imax=100，种群数量Size=50，交叉概率Pc=0.8，变异概率Pm=0.2，初始温度T0=1000，冷却系数q=0.2，任务可选择方案共1944 个。

在同等条件下，该算法与文献[7]仅使用遗传算法的性能比较，如表4所示。可见提出的算法在搜寻最优变迁发生序列时，50次实验中有32次得到最短的生产时间为25min，10次得到较短的加工时间，其中8次得到加工时间超过了30min。

表4 分别利用该算法和文献[7]提出算法优化结果对比Tab.4 Contrasts of Optimization Results of the Algorithms Proposed in this Paper and in Paper[7]

故而混合算法在得到最短时间的概率上和和跳出陷阱的能力上都更加高效。

经该算法计算可得到多种最优或次优的变迁发生序列所对应生产时间都为25min，其中一条染色体序列为：S13S22S33S41S21S62S73S81，仿真实验适应度随遗传代数变化曲线，如图5所示。可见随着遗传代数的增加，适应度趋于稳定。

图5 仿真实验结果适应度曲线Fig.5 The Fitness Curve of Simulation Experiment

改变FMS中的生产约束信息，即仅改变网模型的变迁数及其对应的加工时间，其他条件保持不变的情况下进行50次实验，实验结果，如表5所示。可见随着生产路径的多样化，可选择加工方案数的增多，计算得到最优解或次优解的准确率越高，说明算法在一定程度上解决了大型生产系统加工优化问题。

表5 所提出算法对不同模型计算最优或次优实验结果Tab.5 The Results of the Experiments of Algorithm Proposed in this Paper for Calculating Optimal or Suboptimal Solutions of Different Models

6 结语

通过引入TdPN对FMS建模，结合遗传算法的并行搜索能力和模拟退火算法更易跳出陷阱的优势，设计混合算法，快速搜索到最优或次优变发生序列，优化FMS生产路径。引入TdPN模型在一定程度上解决了加工系统建模精准度与通用性的问题，设计遗传算法结合模拟退火算法的混合算法，提升了加工路径优化中计算准确性与跳出局部最优方面的能力。算例仿真验证了算法的高效性，同时表明了该算法在解决大规模生产加工优化问题方面具有一定的应用价值。