基于Petri网和模拟退火的装备制造系统无死锁调度方法

摘要

本发明公开了一种基于Petri网和模拟退火的装备制造系统无死锁调度方法，首先建立装备制造系统的受控Petri网模型(N,M

说明书

技术领域

本发明属于装备制造系统，具体涉及一种装备制造系统无死锁调度方法。

背景技术

装备制造系统是一类现代化的生产系统，系统中的各类生产资源，如加工机床、机器人、缓冲区等，通过物料运输系统连接起来，由计算机系统统一控制和调度，实现对各种不同类型工件的自动化生产。装备制造系统面临如何合理配置资源、优化生产流程、缩短制造周期和降低生产成本等问题，由于不同工件对共享和有限资源的竞争，需要寻求一种有效的调度策略来分配这些资源，使得生产约束得到满足，并实现生产代价最小化或生产效率最大化。

在传统的车间调度问题中，如流水车间调度和作业车间调度，人们都假定机器与机器之间有无限容量的缓冲，因此当工件完成加工后可以立即离开加工它的机器，进入下一个机器(当下一个机器空闲时)或缓冲区(当下一个机器忙碌时)，当前机器就可以开始加工其他工件。然而，在实际的装备制造系统中，各类生产资源的容量都是有限的，包括缓冲空间，如果缺乏合适的调度策略，当工件完成加工后可能会由于下一个机器忙碌或缓冲区已满而不能离开加工它的机器，工件需要等待下一个机器或缓冲区空闲下来，一旦系统中有一组工件构成循环等待，就会发生死锁。死锁会引起系统中加工任务的阻塞，若不及时处理，可能导致全部任务的停滞，甚至损坏工件，造成重大的经济损失。无死锁调度需要综合考虑死锁控制和优化调度两个问题，既要处理系统中的死锁问题，又要优化系统性能指标，是一个更加复杂的组合优化问题。

目前处理装备制造系统无死锁调度问题的方法主要有两类。一类属于数学规划算法，此类算法面临难以建立系统数学模型的问题，同时由于算法计算量大、计算时间长，无法适用于实际的中等规模及大规模系统。另一类算法基于A*搜索算法，在搜索过程中需要一个启发函数来指导搜索方向，然而由于死锁的存在，算法经常会陷入死锁状态而不得不采取回退操作，极大地降低了算法的求解效率和质量。

Petri网是描述系统状态迁移的图形化数学建模工具，通过分析Petri网模型，可以揭示被描述系统的结构和行为特征。基于Petri网人们研究了很多方法来处理制造系统中的死锁问题。文献《Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems,Xing KY,Zhou MC,Liu HX,et al.,IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,2009,39(1):188-199.》中公开了一种通过在制造系统Petri网模型中增加死锁控制器来建立制造系统的受控Petri网模型的方法，采用此方法建立的受控Petri网模型可以对受控系统进行分析。基于制造系统的受控Petri网模型，很多研究者提出了死锁避免、预防和检测的方法，但目前还没有快速有效的死锁修复和调度方法。

发明内容

发明目的：针对现有技术中存在的问题，本发明公开了一种基于Petri网和模拟退火的装备制造系统无死锁调度方法，该方法能够避免系统发生死锁，而且能够在较短的时间内给出一个较优的调度序列。

技术方案：本发明公开了一种基于Petri网和模拟退火的装备制造系统无死锁调度方法，包括如下步骤：

步骤1：建立装备制造系统的受控Petri网模型(N,M₀)；

步骤2：设定初始温度T₀和终止温度T_f，令当前温度T＝T₀；

步骤3：根据加工的总工件数和加工操作步骤生成随机初始解编码S，对S进行解码得到变迁序列τ(S)；

步骤4：利用系统的受控Petri网模型(N,M₀)修复τ(S)和S，令S_best＝S、τ_best＝τ(S)，其中S_best和τ_best分别表示到目前为止makespan最小的解编码及其变迁序列；

步骤5：计算τ(S)的目标值Ms(S)，令Ms(S_best)＝Ms(S)、k＝0，其中Ms(S_best)代表到目前为止最小的makespan，k记录内循环中Ms(S_best)连续未更新的次数；

步骤6：在S上随机执行一个邻域操作，生成新的解编码S'；

步骤7：对S'进行解码得到变迁序列τ(S')，利用系统的受控Petri网模型(N,M₀)修复τ(S')和S'，计算τ(S')的目标值Ms(S')；

步骤8：令Δ＝Ms(S')-Ms(S)，如果rand[0,1]<exp(-Δ/T)，更新S＝S'、τ(S)＝τ(S')、Ms(S)＝Ms(S')，其中rand[0,1]为分布在[0,1]之间的均匀随机数；

步骤9：如果Ms(S)<Ms(S_best)，更新S_best＝S、τ_best＝τ(S)、Ms(S_best)＝Ms(S)、k＝0；否则，k＝k+1；

步骤10：如果k≥C，转向下一步，其中C为内循环中Ms(S_best)最大连续未更新次数；否则，返回步骤6；

步骤11：如果T<T_f，转向下一步；否则，令T＝β×T、k＝0，返回步骤6，其中β为降温系数；

步骤12：输出最优解S_best、τ_best和Ms(S_best)。

具体地，步骤1中建立装备制造系统的受控Petri网模型(N,M₀)采用文献《Optimal>

步骤3中随机初始解编码S的构造方式为：通过对所有工件号随机排列而产生，只要其中包含L(i)个工件号i；其中为总工件数；L(i)为工件i的加工路径上的变迁数。

步骤3中将解编码S解码得到变迁序列τ(S)的方法为：

从S中第一个位置上的工件号开始，直到最后一个位置，其中的第j个工件号i可以解码为工件i在其加工路径上的第j个变迁，从而可以将一个解编码解码为一个确定的变迁序列。

步骤4中修复τ(S)和S包括如下步骤：

(41)令当前变迁t为变迁序列τ(S)的第一个变迁，当前标识M为系统的初始标识M₀；

(42)检测当前变迁t在当前标识M下是否使能；如果t是使能的，则引发t到达另一个标识M′，并更新当前标识M＝M′；否则从τ(S)中当前变迁t的后面找到第一个在M下使能的变迁t^*，并将其移动到t的位置；

(43)当前变迁t更新为τ(S)中的下一个变迁，重复步骤(42)，直到τ(S)最后一个变迁为止。

步骤5中计算τ(S)的目标值Ms(S)的方法为：

(51)t_k[i]表示第k个变迁t_k对应工件i，对变迁序列τ(S)中的每一个变迁t_k[i]计算其最早引发时间f(t_k[i])，计算方法如下：

f(t₁[u])＝0，其中u为t₁对应的工件

f(t_k[i])＝max{f(^·(^(p)t_k)[i])+d(^(p)t_k[i]),f(t_k-1[j])}，其中d(^(p)t_k[i])为操作库所^(p)t_k[i]对应的加工时间；

(52)变迁序列τ(S)的makespan为其中v为对应的工件，为τ(S)的最后一个变迁。

步骤6中所述的领域操作包括插入、交换、反转和段插入。

有益效果：与现有技术相比，本发明具有以下优点：1、对进入死锁状态的变迁序列进行修复，能够在保证解的可行性的同时，极大地提高算法的搜索效率，从而可以在较短时间给出一个最优变迁序列；2、采用模拟退火算法优化调度过程，最优解不受随机初始解编码的影响；3、该方法既适用于小规模系统，也适用于中等规模及大规模系统；不仅能够避免系统发生死锁，而且能够在较短的时间内给出一个较优的调度序列，显著缩短装备制造系统的制造周期，从而提高生产效率。

附图说明

图1为本发明的基于Petri网和模拟退火的装备制造系统无死锁调度方法的流程图；

图2为本发明实施例中的装备制造系统示意图；

图3为本发明实施例中的装备制造系统的受控Petri网模型；

图4为本发明实施例中的一个随机初始解编码及其解码的变迁序列；

图5为本发明实施例中修复后的解编码和变迁序列；

图6为本发明实施例中可行变迁序列的目标值计算；

图7为本发明的在解编码上执行的四种邻域操作的示意图。

具体实施方式

下面结合附图和具体实施方式，进一步阐明本发明。

图1为本发明公开的一种基于Petri网和模拟退火的无死锁调度方法的流程图。

图2为本实施例中的装备制造系统示意图，系统中共有3个机器：r₁、r₂和r₃，其中r₁和r₃分别最多同时加工1个工件，r₂最多同时加工2个工件。系统可以生产2种类型的工件：q₁和q₂，其中q₁类工件需要依次通过机器r₁和r₂进行加工，q₂类工件需要依次通过机器r₃、r₂和r₁进行加工。系统中q₁类工件需要加工3个，q₂类工件需要加工2个，故总工件数将q₁类的3个工件依次编号为1、2和3，q₂类的2个工件依次编号为4和5。

首先，按照文献《Optimal Petri-Net-Based Polynomial-Complexity Deadlock-Avoidance Policies for Automated Manufacturing Systems,Xing KY,Zhou MC,Liu HX,et al.,IEEE Transactions on Systems,Man,and Cybernetics-Part A:Systems and Humans,2009,39(1):188-199.》中的方法建立系统的受控Petri网模型，如图3所示。库所由机器、死锁控制器和各类工件加工操作、输入缓存和输出缓存组成，其中库所r₁、r₂和r₃分别代表机器r₁、r₂和r₃，它们的初始标识分别是机器r₁、r₂和r₃能同时加工的最大工件数1、2和1；库所c₁为死锁控制器，其初始标识为2，代表机器r₁和r₂能同时加工的最大工件数为2；路径p_I1t₁₀p₁₁t₁₁p₁₂t₁₂p_U1代表q₁类工件的加工路径，p_I1是q₁类工件的输入缓存，其初始标识是需要加工的q₁类工件数3；p₁₁是q₁类工件的第一步操作，需要用到机器r₁，p₁₂是q₁类工件的第二步操作，需要用到机器r₂，p_U1是q₁类工件的输出缓存，p₁₁、p₁₂和p_U1的初始标识都是0。同样的，路径p_I2t₂₀p₂₁t₂₁p₂₂t₂₂p₂₃t₂₃p_U2代表q₂类工件的加工路径，p_I2是q₂类工件的输入缓存，其初始标识是需要加工的q₂类工件数2；得到如图3所示系统的受控Petri网模型(N,M₀)。

结合图3和图4，本发明步骤3中生成随机初始解编码S的具体方法为：

解编码S描述了所有工件的所有操作的加工顺序，可以用来描述系统的调度，是一个有重复的工件号序列：工件i在其加工路径上的所有操作都用它的工件号i来表示，且i出现的次数为工件i的加工路径上的变迁数L(i)。初始解编码采用随机构造的方式：通过对所有工件号随机排列而产生，只要其中包含L(i)个工件号i，为总共件数。

本发明步骤3中将解编码解码为变迁序列的具体方法为：

借助系统的受控Petri网模型(N,M₀)，从S中第一个位置上的工件号开始，直到最后一个位置，其中的第j个工件号i可以解码为工件i在其加工路径上的第j个变迁，从而可以将一个解编码解码为一个确定的变迁序列。随机初始解编码S解码为变迁序列τ(S)的结果如图4所示。

本发明步骤4中利用系统的受控Petri网模型(N,M₀)修复τ(S)和S的具体方法为：

从变迁序列τ(S)的第一个变迁和系统的初始标识M₀开始，检测当前变迁t在当前标识M下是否使能。如果t是使能的，则引发t到达另一个标识M′，更新标识M＝M′，然后移动到τ(S)中的下一个变迁开始新循环；否则从τ(S)中当前变迁t的后面找到第一个在M下使能的变迁t^*，并将其移动到t的位置；重复上述过程直到最后一个变迁为止。τ(S)的修复结果如图5所示。

如图6，本发明步骤5中计算τ(S)的目标值Ms(S)的具体方法为：

令为一个可行的变迁序列，设第k个变迁t_k对应工件i，则用f(t_k[i])代表变迁t_k[i]的最早引发时间。约定系统开始加工的时刻为0，因此f(t₁[u])＝0，其中u为t₁对应的工件。考虑Petri网模型中各加工路径上的操作顺序约束和各操作的加工时间要求，变迁t_k[i]必须在操作^(p)t_k[i]完成之后才能引发，而变迁·(^(p)t_k)[i]的引发代表操作^(p)t_k[i]的开始，故f(t_k[i])≥f(·(^(p)t_k)[i])+d(^(p)t_k[i])，其中^(p)t_k[i]为变迁t_k[i]在其加工路径上的前一个操作库所，^·(^(p)t_k)[i]为操作库所^(p)t_k[i]在其加工路径上的前一个变迁，d(^(p)t_k[i])为操作库所^(p)t_k[i]对应的加工时间。另一方面，考虑变迁序列τ(S)中的顺序约束，设变迁t_k[i]前面的变迁t_k-1对应工件j，则变迁t_k[i]必须在变迁t_k-1[j]引发之后才能引发，故f(t_k[i])≥f(t_k-1[j])。综上，f(t_k[i])＝max{f(·(^(p)t_k)[i])+d(^(p)t_k[i]),f(t_k-1[j])}。需要注意的是，如果t_k[i]是其所在加工路径上的第一个变迁，则f(·(^(p)t_k)[i])+d(^(p)t_k[i])＝0；如果t_k[i]是τ(S)中的第一个变迁，则f(t_k-1[j])＝0。变迁的引发代表最后一个工件离开系统，因此变迁序列τ(S)的makespan为其中v为对应的工件。

考虑实施实例中的Petri网模型，假设各操作的加工时间分别为d(p₁₁)＝25、d(p₁₂)＝23、d(p₂₁)＝15、d(p₂₂)＝20、d(p₂₃)＝26。变迁序列τ(S)＝(t₂₀[4],t₁₀[2],t₂₁[4],t₂₀[5],t₁₁[2],t₁₀[1],t₁₂[2],t₁₁[1],t₁₀[3],t₁₂[1],t₁₁[3],t₂₂[4],t₂₁[5],t₂₃[4],t₂₂[5],t₂₃[5],t₁₂[3])。首先计算第一个变迁t₂₀[4]的引发时间，它即是加工路径上的第一个变迁又是变迁序列τ(S)中的第一个变迁，所以f(t₂₀[4])＝0。考虑第二个变迁t₁₀[2]，它是加工路径上的第一个变迁，所以f(t₁₀[2])＝max{0,f(t₂₀[4])}＝0。考虑第三个变迁t₂₁[4]，它必须在操作p₂₁[4]完成后才能引发，故f(t₂₁[4])＝max{f(t₂₀[4])+d(p₂₁),f(t₁₀[2])}＝15。如图7所示，重复以上过程即可算出τ(S)中所有变迁的引发时间，可以看出τ(S)的makespan为127。

结合图7，本发明步骤6中可以选择执行的邻域操作有四种，分别是插入(insertion)、交换(swapping)、反转(inversion)和段插入(subsequence insertion)。插入操作随机选择解编码上的一个位置，并将该位置上的元素移动到另一个位置；交换操作随机选择解编码上的两个位置，并交换两个位置上的元素；反转操作随机选择解编码上的两个位置，并将两个位置间的元素反序排列；段插入操作类似于插入操作，它将解编码上的某一段元素整体移动到另一个位置。

本发明公开的基于Petri网和模拟退火的无死锁调度方法优化过程采用模拟退火算法，可以选择合理的冷却进度表调整迭代过程，使算法的执行更为有效，即选择合理的初始温度T₀、终止温度T_f、降温系数β和内循环中Ms(S_best)最大连续未更新次数C的值。经对比试验，上述参数取值范围为：2≤T₀≤10，0.1≤T_f≤0.01，0.85≤β≤0.95，5≤C≤10，采用本发明公开的方法能够在较短时间给出一个最优变迁序列。