欢迎访问《控制理论与应用》期刊网站！

基于时延Petri网与代价函数的柔性制造系统优化调度

doi: 10.7641/CTA.2024.40211

李鑫¹ ，黎良^1,2 ，何舟³

1. 武汉科技大学信息科学与工程学院, 湖北武汉 430081

2. 武汉科技大学冶金自动化与检测技术教育部工程研究中心, 湖北武汉 430081

3. 陕西科技大学电气与控制工程学院, 陕西西安 710021

基金项目: 国家自然科学基金项目(62303359, 62373234)资助.

详细信息

作者简介

李鑫硕士研究生,目前研究方向为柔性制造系统建模与优化调度,E-mail: 2228747277@qq.com;

黎良副教授,硕士生导师,目前研究方向为离散事件系统监督控制、Petri网理论与应用,E-mail: liangli@wust.edu.cn;

何舟教授,博士生导师,目前研究方向为离散事件系统故障诊断及资源优化配置,E-mail: hezhou@sust.edu.cn.

通信作者

黎良,E-mail: liangli@wust.edu.cn;Tel.:+8627-68862516.

Optimal scheduling of flexible manufacturing systems based on timed Petri nets and cost function

LI Xin¹ ， LI Liang^1,2 ， HE Zhou³

1. School of Information Science and Engineering, Wuhan University of Science and Technology,Wuhan Hubei 430081 , China

2. Engineering Research Center for Metallurgical Automation and Measurement Technology of Ministry of Education, Wuhan University of Science and Technology, Wuhan Hubei 430081 , China

3. School of Electrical and Control Engineering, Shaanxi University of Science and Technology, Xi’an Shaanxi 710021 , China

Funds: Supported by the National Natural Science Foundation of China (62303359, 62373234).

摘要

针对柔性制造系统最小完工时间的调度问题, 本文提出一种基于时延Petri网和代价函数的调度算法. 首先, 对现有基于时延Petri网的调度算法进行分析, 引入一种考虑当前标识和后继标识到目标标识的变迁发射向量的代价函数; 其次, 通过遍历部分可达图的标识代价函数值选取下一步发射的变迁, 并利用回溯法避免系统的死锁标识和不满足系统规格的标识; 从而, 获得时延Petri网系统的逻辑变迁序列. 通过将逻辑变迁序列转为时延变迁序列, 找到最小时间的变迁序列; 进而, 获得系统最小完工时间的调度方案; 最后, 利用实例验证本文方法的可行性和有效性.

关键词

离散事件系统 / 调度 / Petri网 / 可达图

Abstract

To solve the problem of scheduling for the minimum completion time of tasks in a flexible manufacturing system, this paper proposes a scheduling algorithm based on timed Petri nets (TdPN) and cost function. Firstly, by analyzing the existing TdPN-based scheduling algorithms, we introduce a novel cost function taking into account the transition firing vectors from the current marking and subsequent markings to the target one. Then, through traversing the cost functions of markings in the partial reachable graph, the firing of next transition is selected. Meanwhile, the employment of backtracking method prevents deadlock markings and those markings that do not meet the system specifications, thereby obtaining logical transition sequences of the TdPN system. By transforming the logical transition sequences into timed ones, the minimum time transition sequences are computed, and then the scheduling scheme for the minimum completion time of the system can be obtained. Finally, the feasibility and effectiveness of the approach presented in this paper are validated through practical instances.

Keywords

discrete event systems / scheduling / Petri nets / reachability graph

1 引言 2 时延Petri网 3 调度问题陈述 3.1 调度问题及相关定义 3.2 基于MPC思想的搜索策略与代价函数设定 4 近似最小时间调度算法优化 4.1 近似最小时间的逻辑变迁序列 4.2 近似最小时间的时延变迁序列 4.3 TdPN系统最小时间调度 4.4 复杂度分析 5 FMS最小时间调度分析与对比 6 结论

1 引言

离散事件系统（discrete event systems，DES）是一类状态空间离散且状态演化由事件驱动的动态系统 ^[1]，例如柔性制造系统（flexible manufacturing system，FMS）和项目管理系统等一系列复杂工业系统都可以抽象为DES来研究. 这些系统需要某些操作的多个作业/阶段来完成给定任务，在作业的每个处理阶段，分配不同资源来执行其操作，如机器、机器人和行进区域. 这就面临一个具有挑战性的资源受限调度问题 ^[2] : 给定系统的初始状态和目标状态，在固定资源条件下，如何合理地将不同资源分配给操作使得系统能在最小时间到达目标状态完成工作，从而获得高效率的调度方案. 然而，这类调度问题通常是（non-deterministic polynomial-time hard，NP）困难的 ^[3] .

Petri网作为一种图形工具，已广泛用于DES建模、调度和控制 ^[4-5] . 与图论、自动机等工具相比，Petri网能很好地刻画系统结构特征，如序列、选择、并发和同步，并分析系统行为特征 ^[6] . 此外，Petri网通常提供底层系统更紧凑的结构表示，特别是对于具有较大状态空间的系统. 更重要的是，Petri网的可达图（reachability graph，RG）有助于可视化可达标识和找到系统从当前状态到目标状态运行轨迹的变迁发射路径 ^[7]，充分揭示底层系统的行为.

在具有时间约束的系统中，调度问题的关键之一是满足任务的时间要求. 因此，国内外学者试图在Petri网模型中引入时间信息来研究这一问题. 根据引入确定时间的对象不同分为库所赋时Petri网、变迁赋时 Petri网和弧赋时Petri 网 ^[8] . 两种主要的变迁赋时Petri 网模型是时间Petri网和时延Petri网. 时延Petri网的变迁与固定发射延时相关联. 在解决调度问题时，相比时间Petri网，时延Petri网提供了对任务执行时间的确定性，使得任务排序和安排更为直观. 因此，时延Petri网被广泛用于解决赋时DES的调度问题 ^[9-10] .

利用时延Petri网解决调度问题已有大量方法，例如: 基因遗传算法 ^[11]、粒子群算法 ^[12]，这类结合人工智能的搜索方法需要进行编码与解码等操作的可达性判断，增加了问题处理的复杂度. Lee等 ^[13] 首次基于时延Petri网的RG提出了一种A^∗搜索算法. 该方法不需要搜索完整RG来获得调度方案. 然而，对于大型的复杂系统，很难在合理时间内找到最优或近优调度策略. 为提高搜索效率，研究人员提出了不同的改进方法. 其中，大多数方法通过修改A^∗算法来加速搜索过程，但都以牺牲解的质量为代价，比如具有动态移动窗口的A^∗搜索 ^[14] 和无死锁动态搜索 ^[15] . 有希望解决该问题的方法是基于RG的A^∗搜索设计更为智能的启发式函数 ^[16]，但是许多启发式函数是从不同方面制定的，往往只适用特定场合. 此外，所考虑的系统可能存在死锁，而大多数基于RG的A^∗搜索算法难以解决系统死锁问题和状态爆炸问题.

受模型预测控制（model predictive control，MPC）思想的启发，Lefebvre ^[17-18] 提出了基于时延Petri网和 MPC的方法对含禁止标识的系统状态空间进行部分搜索来获得逻辑变迁序列，再将该变迁序列转换为时延变迁序列. 这种方法在一定程度上有效避免了系统的状态爆炸问题. 文献 ^[19] 在文献 ^[18] 的基础上提出了一种将逻辑变迁序列转换为时延变迁序列的优化方法，并且证明了该方法的有效性.

众所周知，MPC的基本思想是预测系统状态演化以实现控制目标. 在某些约束条件下，每个步骤的性能标准都被最小化，从而获得一系列控制动作 ^[20] . 文献 ^[17-18] 选择代价函数值最小的标识，获取相应变迁序列. 该策略主要是通过选择变迁序列中第1个使能变迁，由系统新标识的代价函数再次预测，继而计算出最小时间的时延变迁序列. 研究人员已经证明文献 ^[17] 的欧式距离代价函数并不能明确描述两个标识之间的距离关系，使得每次预测不一定准确. 文献 ^[18] 在文献 ^[17] 基础上，将发射向量作为代价函数，无论是准确性还是搜索效率都得到明显提升.

综上，本文在文献^[18]的基础上，通过优化预测后继标识的方法，提出一种最小时间调度算法. 具体而言，本文提出新的代价函数，优化了文献 ^[18] 近似最小时间的调度算法，有效降低计算复杂度并且提高了算法搜索的准确性. 同时，通过文献 ^[19] 将逻辑变迁序列转换为时延变迁序列. 最终，提出一种计算系统所有调度方案的时延变迁序方法，以获得最小时间调度方案.

2 时延Petri网

Petri网为四元组Net = ⟨P，T，W_PR，W_PO⟩ ^[6]，其中: P = { p₁，p₂，· · ·，p_n}表示n个库所的有限集合，T ={t₁，t₂，· · ·，t_q}表示q个变迁的有限集合，

W_{P O} \in N^{n \times q}

和

W_{P R} \in N^{n \times q}

分别是Net的后置关联矩阵和前置关联矩阵，其中

N

代表非负整数集. Petri网的关联矩阵为A = W_PO − W_PR.

Petri网的标识表示为

M \in N^{n} ，

含义是为网中每个库所分配非负整数个 token. 在标识 M 中，库所 p中的token数记为 M（p）. 变迁 tj在M 下的使能度为n_j（M）= min{⌊M（p_k）/W_PR（k，j）⌋ : p_k ∈ °t_j}，其中: °t_j为t_j的前置输入库所集，W_PR（k，j）为矩阵W_PR 的第k行第j列的参数值，⌊ ⌋为向下取整数. 当

M ⩾

WPR（:，t_j）时，变迁t_j∈ T在标识M下是使能的，表示为M[t_j⟩，其中: W_PR（:，t_j）表示W_PR对应t_j的列向量. M下所有使能变迁集表示为 Bn（M）= {t_j∈ T|M [t_j ⟩}. 使能变迁t_j ∈ Bn（M）发射后会产生一个新标识（也称M的后继标识）M′ = M + A ·

{\vec{t}}_{j} ，

其中

{\vec{t}}_{j}

是变迁t_j的发射向量，该过程用M[t_j ⟩M′表示.

时延Petri网（timed Petri nets，TdPN）是一类行为受时间约束的Petri网，其每个变迁具有一个确定性的发射延时. 本文用⟨Net， M₀，D⟩表示一个TdPN系统，其中: M₀是系统的初始标识，

D \in {(R^{+})}^{q}

续时间参数的向量（

R^{+}

是非负实数集），则D（t_j）表示变迁t_j使能持续时间. 本文所考虑的TdPN具有无限服务器语义、竞争策略以及使能记忆策略 ^[18] . 因此，每个使能变迁t_j最早在D（t_j）个时间单位之后发射. 用

d (t_{j}) \in R^{+}

表示变迁t_j的剩余使能持续时间，每个变迁t_j在使能

τ ⩾ 0

时间后最早还需d（t_j）时间单位发射，其中d（t_j）= D（t_j）− τ .

TdPN系统的一个时延变迁序列为

σ_{τ} = (t_{j_{1}} ， η_{1}) (t_{j_{2}} ， η_{2}) \dots (t_{j_{h}} ， η_{h}) \in {(T \times R^{+})}^{*} ， |σ_{τ}| = h

表示σ_τ的长度为 h，其中 η₁，· · ·，η_h表示变迁发射时间且满足

0 ⩽ η_{1} ⩽ η_{2} ⩽ \dots ⩽ η_{h} \cdot σ_{τ}

的全局发射时间记为 τ（σ_τ）= η_h. 在忽视变迁发射时间时，用

σ = t_{j_{1}} t_{j_{2}} \dots t_{j_{h}} \in T^{*}

表示σ_τ的逻辑变迁序列（σ = ε表示空序列），并用

\vec{σ}

表示σ的变迁发射向量，则

\vec{σ}

（t_i）表示σ中 t_i出现的次数.

‖ \vec{σ} ‖_{1}

为σ 中所有变迁出现的次数和，其中

‖ \vec{σ} ‖_{1} = [1]_{1 \times q} \cdot \vec{σ}

且[1]_1×_q为全1的行向量. 对于两个序列σ和σ′，σσ′代表其串联.

对于M₀使能的变迁序列σ_τ下的路径可表示为 TR（σ_τ，M₀）= M₀[（t_j₁，η₁）⟩M₁· · · M_h₋₁[（t_j_h，η_h）⟩ M_h，其中M₁，· · ·，M_h₋₁是中间标识，M_h是最终标识. 为方便起见，M ∈ TR（σ_τ，M₀）代表M存在于路径TR（σ_τ， M₀）中，t ∈ TR（σ_τ，M₀）表示变迁t在序列 σ 中至少出现一次. 如果存在满足 M₀[σ⟩M的 σ，则称M从初始标识M₀可达. TdPN系统中所有可从M₀到达的标识构成的集合表示为R（Net， M₀）. 当不存在其他时延变迁序列

σ_{τ}^{'}

到达M_h，或者当存在其他满足

τ (σ_{τ}) ⩽ τ (σ_{τ}^{'})

的时延变迁序列

σ_{τ}^{'}

到达M_h时，σ_τ为最小时间的时延变迁序列.

3 调度问题陈述

3.1 调度问题及相关定义

一般情况下，实际系统的状态并不都符合要求，因此，本文在研究过程中考虑了系统存在一些非法标识. 如果标识M满足以下至少一个条件，则为非法标识: 1）M不满足系统规格; 2）M是死锁标识. 非法标识均为禁止标识.

给定一个TdPN系统⟨Net，M₀，D⟩，为了找到系统从初始状态到目标状态的最小时间调度方案，1）需要寻找从初始标识M₀到目标标识M_tar可行的最小时间的时延变迁序列，其中该时延变迁序列下的路径标识都合法，并且全局发射时间相同的两个时延变迁序列属于同一调度方案; 2）为减少搜索工作量，在系统初始标识下检查是否存在可行变迁序列是必要的.

定义 1 给定一个TdPN系统⟨Net，M₀，D⟩和两个变迁发射向量相同，但变迁发射顺序不同的时延变迁序列 σ_τ 和

σ_{τ}^{'} ，

若其满足

M_{0} [σ_{τ}⟩ M_{t a r} ， M_{0} [σ_{τ}^{'}⟩ M_{t a r}

和

τ (σ_{τ}) = τ (σ_{τ}^{'}) ，

则σ_τ和

σ_{τ}^{'}

为从初始标识M₀到目标标识M_tar同一调度方案的两个时延变迁序列.

定义 2 给定一个TdPN系统⟨Net， M₀，D⟩，若可达标识M下的变迁都不能发射，则M为死锁标识 ^[21] .

定义 3 给定一个TdPN系统⟨Net，M₀，D⟩和目标标识M_tar，则满足M₀[σ⟩M_tar的任意变迁序列σ都存在一个非负整数的 n 维发射向量

\vec{σ} ，

使得M_tar= M₀ + A ·

\vec{σ}

^[22] .

定义 4 给定一个从M₀发射变迁序列σ_τ可达的标识M_tar（即

\vec{σ}

满足

M_{t a r} = M_{0} + A \cdot \vec{σ}

），则满足M ∈ TR（σ_τ，M₀）的标识称为预选标识，否则为禁止标识. 其中: 禁止标识集用Γ（M₀，M_tar）表示，预选标识集合表示为Pre（M₀，M_tar）= {M ∈TR（σ_τ， M₀）|σ_τ : M₀ [σ_τ ⟩M_tar}.

定义 5 给定一个TdPN系统⟨Net，M₀，D⟩和目标标识M_tar，则满足M₀[σ⟩M_tar的逻辑变迁序列集合可表示为E（M₀，M_tar_）={σ ∈ T^∗|M₀[σ⟩M_tar}，满足 M₀[σ_τ ⟩M_tar的时延变迁序列集合为E_τ（M₀，M_tar）= {σ_τ ∈（T × R⁺）^∗|M₀[σ^τ ⟩M_tar}.

定义 6 给定一个TdPN系统⟨Net，M₀，D⟩及其目标标识 M_tar，对于所有满足M₀[σ_τ ⟩M_tar 的时延变迁序列，若

σ_{τ}^{'}

∈E_τ（M₀，M_tar）满足τ （

σ_{τ}^{'}

）≤τ （σ_τ），其中σ_τ ∈ E_τ（M₀，M_tar）\ {

σ_{τ}^{'}

}，则称

σ_{τ}^{'}

为M₀到M_tar的最小时间时延变迁序列.

性质 1 给定一个TdPN系统⟨Net，M₀，D⟩和变迁序列σ，σ ′ . 若M[σ ′ ⟩M′和M′ [σ⟩M_tar成立，则存在一个非负整数的n 维向量

{\vec{σ}}^{''} = {\vec{σ}}^{'} + \vec{σ} ，

使得M[σ ′′⟩ M_tar.

证若M[σ ′ ⟩M′和M′ [σ⟩M_tar成立，由关联矩阵可知M′ = M +A.

{\vec{σ}}^{'}

和M_tar = M′+A·

\vec{σ}

，联立两式可得M_tar = M + A ·

({\vec{σ}}^{'} + \vec{σ})

. 假设使M[σ ′′⟩M_tar成立的一个变迁序列为σ ′′ ，即M_tar = M + A ·

{\vec{σ}}^{''}

. 因此，可证得

{\vec{σ}}^{''} = {\vec{σ}}^{'} + \vec{σ} .

证毕.

3.2 基于MPC思想的搜索策略与代价函数设定

MPC是一种滚动优化的控制方法. 在文献 ^[18] 中，作者将系统可达图标识作为预测模型，并且利用回溯法矫正禁止标识的干扰，其滚动优化策略是将DES中的离散事件发展过程抽象为Petri网可达图的生成过程. 在可达图生成的过程中，计算当前标识变迁发射长度为H内所有可达标识代价函数值，并从中选取代价函数值最小的标识，以获取最优的下一发射变迁. 在多次迭代到达M_tar后获得最优的逻辑变迁序列. 如图1所示，本文基于 MPC 思想的搜索策略是在文献 ^[18] 基础上提出新的代价函数并设定H恒为1. 每次只计算可达图中当前标识的后继标识代价函数值，并基于当前标识以及后继标识的代价函数值选取下一变迁. 与此同时，通过回溯法避免不合法标识.

图1基于MPC思想的搜索策略流程图

Fig.1Flow chart of search strategy based on MPC

在文献 ^[18] 中，作者将变迁发射向量作为代价函数，但仅考虑当前标识到M_tar变迁发射向量的关系. 受文献 ^[18] 的启发，本文提出一种考虑当前标识和后继标识到M_tar 变迁发射向量的代价函数.

由定义3可知，若不存在

{\vec{σ}}_{0}

，则在M₀下没有可行的逻辑变迁序列σ₀，即由M₀下的变迁发射向量可初步判断系统是否存在可行的逻辑变迁序列. 因此，本文将M₀代价函数设为

J (M_{0}) = {\vec{σ}}_{0}^{*}

，且

{\vec{σ}}_{0}^{*}

满足下式:

D \cdot {\vec{σ}}_{0}^{*} = a r g m i n \{D \cdot {\vec{σ}}_{0} ∣ {\vec{σ}}_{0} \in R ({\vec{σ}}_{0})\},

(1)

其中:

R ({\vec{σ}}_{0}) = \{{\vec{σ}}_{0} \in N^{q \times 1} ∣ A \cdot {\vec{σ}}_{0} = M_{t a r} - M_{0}\} ， {\vec{σ}}_{0}

表示M₀到M_tar的变迁发射向量，σ₀为M_tar从M₀可达的变迁序列，

{\vec{σ}}_{0}^{*}

为集合

R ({\vec{σ}}_{0})

中

D \cdot {\vec{σ}}_{0}

值最小的变迁发射向量.

式（1）确定了M₀到M_tar可用的变迁发射向量，从而可以预测M₀到M_tar近似最小时间的逻辑变迁序列. 假设M_i和M_i₋₁为逻辑变迁序列下路径中的中间标识，其中

M_{i - 1} [t_{i - 1}⟩ M_{i} ， M_{i} [σ_{i}^{*}⟩ M_{t a r} 和 M_{i - 1} [σ_{i}^{'}⟩ M_{t a r} ，

由性质1可知，标识M_i到M_tar的发射向量

{\vec{σ}}_{i}^{*}

满足下式:

{\vec{σ}}_{i}^{*} = {\vec{σ}}_{i}^{'} - {\vec{t}}_{i - 1}

(2)

其中:

{\vec{σ}}_{i}^{*} \in \{{\vec{σ}}_{i} \in N^{q \times 1} ∣ A \cdot {\vec{σ}}_{i} = M_{t a r} - M_{i}\} ， i \in N^{+}

（

N^{+}

为正整数集），

{\vec{σ}}_{i}^{'}

表示标识M_i₋₁到M_tar的发射向量;

{\vec{t}}_{i - 1}

为变迁t_i₋₁的发射向量.

由式（2）得到了逻辑变迁序列下路径的中间标识发射向量，使得后继标识的选择更加准确. 因此，本文设定标识Mi到Mtar的代价函数为

J (M_{i}) = {\vec{σ}}_{i}^{*} .

注意发射向量

\vec{σ}

的求解方法如下: 由

M_{t a r} = M + A \cdot \vec{σ} ，

可得非线性齐次方程组

A \cdot \vec{σ} = M_{t a r} - M ，

再由消元法与矩阵初等变换求

\vec{σ}

，其中

\vec{σ}

中的每个值都为非负整数.

由式（1）可知，J（M₀）的确定利用了M₀到M_tar变迁发射向量的关系; 由式（2）可知， J（M_i）的确定利用了当前标识和后继标识两者到M_tar的变迁发射向量之间的关系. 当

J (M_{0}) \neq ε ，

由于系统可能存在死锁标识，通过J（M₀）不能直接确定存在逻辑变迁序列，需要进一步判断，但是当

J (M_{0}) = ε ，

可知不存在逻辑变迁序列; 当

J (M_{i}) = ε ，

则

M_{i} \in Γ (M_{0} ， M_{t a r}) .

只有

J (M_{i}) \neq ε

成立时，才能确定Mi为新标识，并得到逻辑变迁序列中的下一个使能变迁的发射. 具体的搜索算法将在下一节展示.

4 近似最小时间调度算法优化

4.1 近似最小时间的逻辑变迁序列

本文通过算法1（见表1）中的代价函数值确定下一个标识，从而确定下一个变迁 t^∗的发射. t^∗的确定在变迁集

B n （ M ） = \{t_{j} \in T ∣ M [t_{j}⟩\}

中选择. 由于标识 M下可能存在同时使能的变迁t_j₁和t_j₂，且它们都在所选的逻辑变迁序列中，则t_j₁和t_j₂都可作为下一个变迁. 然而，t_j₁和t_j₂在M下的逻辑变迁序列中具有先后顺序，因此，本文通过设置相关集合储存这类变迁和后继标识，以及指定的代价函数值，并确定逻辑变迁序列中下一个变迁. 其中: S（M）为储存后继标识的集合， T ^⋄（t）为储存变迁的集合，Q（M，M_tar， J（M））表示储存代价函数值的集合，其具体表达式如下:

\begin{matrix} S (M) \subseteq P r e (M_{0}, M_{t a r}); \\ T^{⋄} (t) = \\ \{t \in T ∣ M [t ⟩ M^{'}, \{M, M^{'}\} \subseteq P r e (M_{0}, M_{t a r})\}; \\ Q (M, M_{t a r}, J (M)) = \\ \{J (M) \in N^{q \times 1} ∣ M_{t a r} = \\ M + A \cdot J (M), M \in S (M)} . \end{matrix}

为了确定下一个标识及变迁，步骤3–5计算出M′ 和J（M′）. 步骤6–12将满足条件的变迁以及对应标识和代价函数值储存在相应集合中. 当J（M′）= ε，表示标识M′∈/ Pre（M₀，M_tar），因此，令Γ ←Γ ∪{M′}，防止回溯后再次访问该标识. 考虑到J（M_tar）≡ ε，可通过判断式（

‖ J （ M ） ‖_{1} = 1 且 M^{'} = M_{t a r}

）找到M_tar. 值得注意的是，代价函数值不能排除死锁的影响. 若 J（M）存在，但是Bn（M）= ∅，则M为死锁标识，因此，将此标识加入Γ，防止下一次访问. 同时，设置回溯标志位backtracking=1，使得回溯到逻辑变迁序列下路径的上一标识（见步骤15–17）. 当S（M）存在多个标识时，表示存在多条符合条件的逻辑变迁序列. 为了获取其中一条逻辑变迁序列，可选取S（M）中任意标识作为下一标识. 由于算法1每次运算只确定逻辑变迁序列中的一个变迁，为了减少算法计算复杂度，本文选取集合S（M）中储存的第一个标识M^∗作为下一标识. 同理， t^∗为集合T^⋄（t）中储存的第1个变迁，J（M^∗）为集合Q（M，M_tar，J（M））中储存的第1个代价函数（见步骤19–21）.

M [t ⟩ M_{t a r} ，

则当

‖ J （ M ） ‖_{1} = 1

成立时，由M[t⟩M′和 M′ = M_tar可确定σ最后的变迁为t.

表1计算TdPN系统下一个变迁t^∗

Table1Computation of the next transition t^∗ for TdPN systems

证由定义3可知，若

‖ J （ M ） ‖_{1} = 1 ，

则存在一个非负整数的 n 维向量

\vec{t}

满足等式

M^{'} = M + A \cdot \vec{t} ，

即

M_{t a r} = M + A \cdot \vec{t} .

由

M [t ⟩ M_{t a r}

可知变迁t 在标识M 下能发射; 又因为标识M是从M₀发射逻辑变迁序列σ获得，因此，可确定σ最后的变迁为t. 证毕.

算法1每次确定逻辑变迁序列的一个变迁，为了获得逻辑变迁序列，将通过算法2（见表2）对算法1迭代来解决.

在算法2中，若M不满足系统规格（即非法），初始化时可将该标识加入Γ，即将Γ ← ∅ 改为Γ ← {M}. 算法2对算法1每次迭代都会排除Γ中的标识为下一个标识. 若M是死锁标识，通过算法1将返回条件backtracking=1，回溯到σ下路径的上一标识，从而避开死锁标识的选择. 步骤2通过式（1）计算

{\vec{σ}}_{0}^{*} ，

若

{\vec{σ}}_{0}^{*}

存在并且M_tar从M₀可达，则可确定存在σ. 步骤3–5确定 J（M₀）. 步骤9–10当M₀为死锁标识或不满足系统规格，令success= −1，表示不存在满足条件的σ. 在步骤11–16中，若backtracking=0，即可确定下一标识和变迁; 若backtracking=1，表示当前标识是死锁标识，需要回溯到上一标识. 为此，本文利用集合S^∗（M）记录所选σ下路径的标识，通过去除S^∗（M）最后所选标识M_END及σ中最后选择的变迁t_END回溯到上一标识，转而搜索其他符合条件的标识. 步骤18–20中的 M = M_tar 表示搜索到的 σ 中最后一个变迁，可得 success=1.

表2计算TdPN系统的逻辑变迁序列σ

Table2Computation of the logical transition sequence σ for TdPN systems

定理 2 给定一个初始标识为M₀的TdPN系统及其目标标识M_tar ∈ R（Net，M₀），通过算法 2对算法1迭代可避免死锁标识并得到逻辑变迁序列σ ∈ E（M₀，M_tar）.

证假设

σ = t_{j_{1}} t_{j_{1}} \dots t_{j_{h}} ，

由式（1）得

J (M_{0}) = \vec{σ}

且

{‖J (M_{0})‖}_{1} = h .

算法2通过算法1确定下一个发射的变迁. 具体而言，算法1由

M ⩾ W_{P R} (: ， t_{j_{h}})

确定变迁

t_{j_{h}}

可以发射，并通过

J (M_{h + 1}) = J (M_{h}) - {\vec{t}}_{j_{h}}

确定

t_{j_{h}}

为 σ 中的变迁. 当系统不存在死锁标识时，算法2 通过多次迭代后可知

{‖J (M_{0})‖}_{1} = h ， {‖J (M_{1})‖}_{1} = h - 1 ， \dots ， {‖J (M_{h - 1})‖}_{1} = 1

为严格单调递减. 当

{‖J (M_{h - 1})‖}_{1} = 1 ，

由定理1可确定σ最后的变迁. 当 M₀为死锁标识，可得success= −1并返回σ = ε. 若当前标识M_k的后继标识M_k₊₁为死锁标识，则backtraking=1，回溯到M_k∈ S^∗（M）的上一个标识M_k₋₁，然后，继续通过算法1计算标识M_k₋₁下的变迁. 若backtraking=0，则可确定新的变迁

t_{j_{k - 1}}^{'} ，

此时有

σ = σ t_{j_{k - 1}}^{'} .

再通过算法1将

M_{k}^{'} = M_{k - 1} + A \cdot {\vec{t}}_{j_{k - 1}}

作为当前标识，并确定其后继标识

M_{k + 1}^{'}

和变迁

t_{j_{k}}^{'} .

综上，算法2 对算法1迭代可获得σ并且可以避免死锁标识. 证毕.

4.2 近似最小时间的时延变迁序列

给定一个逻辑变迁序列σ，在不改变σ变迁发射顺序下，通过算法3（见表3）可将σ转为时延变迁序列σ_τ . 其核心是利用CAL，CAL表示在当前标识M下处于使能状态的变迁及其剩余使能持续时间的集合，迭代计算σ_τ中变迁的发射时间，并更新M处已发射变迁的剩余使能持续时间 ^[19] . 其中: 对于步骤3–20中通过变迁序列σ得到的每一个标识M，将其对应的使能变迁及剩余使能持续时间由CALnew进行保存，并添加至集合

C A L = \{(t_{j_{k}} ， d (t_{j_{k}})) ∣ t_{j_{k}} \in B n （ M ）\} ，

进而得到变迁

t_{j_{k}}

的全局发射时间（见步骤3–4）; 步骤5–12 找与变迁

t_{j_{k}}

能够同时使能的变迁t ′及其剩余使能持续时间; 步骤14–19找到

t_{j_{k}}

发射后生成的变迁t ′′ 及其剩余使能持续时间，

d (t_{j_{k}}) \leftarrow D (t_{j_{k}})

表示σ中所有的变迁剩余使能持续时间.

d (t_{j_{k}})

初始状态等于

D (t_{j_{k}})

. 其中: 算法3应用变迁最早发射策略，将变迁发射向量相同而变迁发射顺序不同的逻辑变迁序列σ和σ ′转为时延变迁序列后，

τ (σ_{τ}) = τ (σ_{τ}^{'})

为了详细介绍上述算法实现时延变迁序列的计算过程，如图2所示的具有变迁使能持续时间参数向量 D = ^{[1 2 1 3 1 4 2]}的TdPN，下面分两种情况讨论.

1）给定初始标识M₀ = [1 0 0 0 0]^T，目标标识 M_tar = [0 0 0 0 1]^T. 根据算法1–2，该TdPN的逻辑变迁序列搜索如图3所示. 首先，计算出J（M₀）= [1 0 1 0 2 1 2]^T，即存在逻辑变迁序列且

{‖J (M_{0})‖}_{1}

= 7. 继而计算出 M₀ 后继标识M₁，M₂，M₃ 及其代价函数J（M₁），J（M₂），J（M₃）和变迁t₁，t₂，t₅. 其中只有 J（M₁）≠ ε，挑选M₁为下一标识并确定下一变迁为 t₁. 算法 2对算法1迭代6次后，可得

σ = t_{1} t_{3} t_{5} t_{5} t_{6} t_{7} ，

当前标识M = [0 0 0 1 1]^T及其代价函数J（M）= [0 0 0 0 0 0 1]^T. 由此可知

‖ J （ M ） ‖_{1}

= 1，算法2再通过对算法1迭代后得到标识M = M_tar，因此，success←1表示搜索到逻辑变迁序列中最后一个变迁，即得到

σ = t_{1} t_{3} t_{5} t_{5} t_{6} t_{7} t_{7} .

最后，通过算法 3将σ 转为

σ_{τ} = (t_{1} ， 1) (t_{3} ， 2) (t_{5} ， 3) (t_{5} ， 3) (t_{6} ， 7) (t_{7} ， 9) (t_{7} ， 9) .

图3蓝色箭头和变迁为所选逻辑变迁序列下的路径，黑色箭头为不可选路径. 算法2在整个计算过程，共访问18个节点（标识），即平均每次访问2.57个节点. 在求得相同逻辑变迁序列情况下，文献 ^[18] 则需至少访问27个节点，平均每次访问3.38个节点.

表3将σ转换为时延变迁序列σ_τ

Table3Transtormation of σ into σ_τ

2）给定M₀=[0 0 0 3 0]^T和M_tar =[0 0 0 0 1]^T，可得J（M₀）= [0 0 0 0 0 2 3]^T. 如图4所示，算法2 对算法 1第1次迭代可得J（M₁）和J（M₂）都不为空，此时，S（M）= {M₁，M₂}，T ^⋄（t）= {t₆，t₇}，Q（M，M_tar，J（M））= {J（M₁），J（M₂）}，即M₀下的变迁t₆和t₇都可被选为下一变迁. 本文选择S（M）中第1个标识M₁作为下一个标识以及对应T^⋄（t）中第1个变迁 t₆作为下一变迁. 算法 2对算法 1多次迭代后得出

σ = t_{6} t_{6} t_{7} t_{7} t_{7}

. 具体情况如图4所示（图中忽略了部分可达图中不可选标识），其中存在3条逻辑变迁序列:

t_{6} t_{6} t_{7} t_{7} t_{7} ， t_{6} t_{7} t_{6} t_{7} t_{7}

和

t_{7} t_{6} t_{6} t_{7} t_{7} ，

其时延变迁序列分别为

(t_{6} ， 4) (t_{6} ， 4) (t_{7} ， 4) (t_{7} ， 6) (t_{7} ， 6) ， (t_{6} ， 4) (t_{7} ， 4) (t_{6} ， 4） (t_{7} ， 6) (t_{7} ， 6) 和 (t_{7} ， 2) (t_{6} ， 4) (t_{6} ， 4) (t_{7} ， 6) (t_{7} ， 6) .

由定义1可知，通过算法3将变迁发射向量相同而变迁发射顺序不同的σ转为σ_τ后，3条时延变迁序列为同一调度方案. 其中序列

t_{6} t_{6} t_{7} t_{7} t_{7}

是选择S（M）和 T^⋄（t）中第1个值的结果. 若要找到所有符合要求的逻辑变迁序列，则需进一步优化对S（M），T^⋄（t），Q（M，M_tar，J（M））中各个参数的选择. 结合图2和图4可以发现变迁t₆和t₇同时使能使得t₆，t₇都可以被选择，导致出现多条符合条件的逻辑变迁序列.

图2一个TdPN ^[18]

Fig.2A TdPN ^[18]

图3部分搜索的可达图

Fig.3Partial searching reachable graph

4.3 TdPN系统最小时间调度

给定一个TdPN系统，可能会存在多个从M₀到达 M_tar的σ_τ，基于文献^[18]的优化算法只能得到一条近似最小时间的σ_τ . 由定义3可知，当M₀到M_tar的逻辑变迁序列存在时，必然存在一个

{\vec{σ}}_{0} \in R ({\vec{σ}}_{0}) .

通过合理的选取

{\vec{σ}}_{0}

（即J（M₀）），利用算法2可快速算出符合条件的σ₀，再由算法3转为σ_τ . 由于不同J（M₀）对应不同逻辑变迁序列，通过不断标记已经选取的J（M₀），再计算出未被标记J（M₀）对应的逻辑变迁序列并转为时延变迁序列，可将所有调度方案计算出来. 详细流程如图5所示.

图4逻辑变迁序列搜索图

Fig.4Graph for searching logical transition sequences

图5时延变迁序列求解流程图

Fig.5Flow chart for solving timed transition sequences

定理 3 给定一个TdPN系统⟨Net， M₀，D⟩，通过算法2–3可以得到系统所有调度方案的时延变迁序列σ_τ ∈ E_τ（M₀，M_tar），进而得到最小时间时延变迁序列

σ_{τ}^{'}

∈ E_τ（M₀，M_tar）.

证由定理2可知，算法2对算法1迭代可得逻辑变迁序列σ ∈ E（M₀，M_tar）. 算法3将σ转换为时延变迁序列σ_τ，同时，将变迁发射向量相同而变迁发射顺序不同的逻辑变迁序列σ和σ ′转为时延变迁序列后，可得τ（σ_τ）= τ（

σ_{τ}^{'}

）. 通过将已访问的J（M₀）标记，由算法 2–3计算出所有

\vec{σ}

对应的时延变迁序列 σ_τ ∈ E_τ（M₀，M_tar）. 由定义1可知，相同

\vec{σ}

下变迁发射顺序不同的时延变迁序列的τ （σ_τ）相等属于同一调度方案，因此，通过该方法可以计算出系统所有方案的时延变迁序列σ_τ ∈ E_τ（M₀，M_tar）. 由定义6，对于所有满足 M₀[σ_τ ⟩M_tar的时延变迁序列，

σ_{τ}^{'}

∈ E_τ（M₀，M_tar）满足

τ (σ_{τ}^{'}) ⩽ τ (σ_{τ}) ，

从而可得最小时间的时延变迁序列

σ_{τ}^{'}

. 证毕.

4.4 复杂度分析

目前，相关工作都未考虑优化代价函数提高计算效率，而是在文献 ^[18] 代价函数基础上引入其他智能搜索算法，以获取更好的调度方案. 例如文献 ^[19] 将文献 ^[18] 的代价函数与混合滤波波束搜索算法结合，尽管提高了搜索的准确性，但面对复杂系统时，会消耗大量时间求解所需参数，并且由于受代价函数的约束，难以得到系统的最小时间调度方案. 因此，下面结合图2所示例子将本文与文献 ^[18] 中的方法进行对比.

如表4所示，本文算法2在计算逻辑变迁序列在效率上比文献 ^[18] 方法有较大提升. 其中: Q_l为所需的逻辑变迁序列下的路径访问节点（标识），Q_sp为非所选路径访问的节点. 相比文献 ^[18]，本文（J（M））方法只有当访问节点为死锁标识才有几率访问Q_sp，即Q_sp ≈ 0，而文献 ^[18] 由于仅考虑当前标识到目标标识代价函数值，其中访问节点存在大量不可忽略的伪解标识，因此需要大量回溯才能解决这个问题. 实际对比情况如表5所示，其结果是图2所示的TdPN在获得相同逻辑变迁序列下测试多次后的平均访问节点数.

表4σ的算法复杂度对比

Table4Comparison of algorithmic complexity of σ

表5σ访问节点对比

Table5Comparison of access nodes for σ

5 FMS最小时间调度分析与对比

为验证本文方法的有效性，考虑一个可以处理两种类型零件 b₁和b₂ 的FMS，如图6所示. 其中: b₁型零件有两条加工路线:

w_{1} = p_{1} t_{1} p_{2} t_{2} p_{3} t_{3} p_{4} t_{4} p_{5} t_{5} p_{6} ， w_{2} = p_{1} t_{1} p_{2} t_{6} p_{7} t_{7} p_{8} t_{8} p_{5} t_{5} p_{6} ，

而b₂型零件只有1条加工路线

w_{3} = p_{9} t_{9} p_{10} t_{10} p_{11} t_{11} p_{12} t_{12} p_{13} .

目标需求是得到零件b₁和b₂所有调度方案，并从中选择最优调度方案. 库所和变迁的含义见表6.

图6某FMS的TdPN模型

Fig.6The TdPN model of an FMS

表6库所和变迁的含义

Table6Implication of places and transitions

由表6可知D = [2 5 8 1 4 3 6 4 2 6 3 4]（工序时间均设为单位时间），零件1库和零件2库加入2个未加工零件，初始标识以及目标标识如下:

\begin{matrix} M_{0} = {[\begin{matrix} 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 1 & 2 & 1 & 1 & 2 \end{matrix}]}^{T}, \\ M_{t a r} = {[\begin{matrix} 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 2 & 1 & 2 & 1 & 1 \end{matrix}]}^{T} . \end{matrix}

由式（1）可知

R ({\vec{σ}}_{0}) =

{[2 2 2 2 2 0 0 0 2 2 2 2]^T，[2 1 1 1 2 1 1 1 2 2 2 2]^T，[2 0 0 0 2 2 2 2 2 2 2 2]^T}，即系统有3 个调度方案. 其中: 方案1: 2个 b₁型零件选用路线w₁，2个b₂型零件选用路线w₃; 方案2: 2个b₁ 型零件分别选用路线w₁和w₂，2个b₂型零件选用路线w₃; 方案3: 2个b₁型零件选用路线w₂，2 个 b₂型零件选用路线w₃.3个方案中

D \cdot {\vec{σ}}_{0}

值分别为70，69和68. 因此，上述调度方案分别记为: 1）w₁，w₃，70; 2）w₁，w₂，w₃，69; 3）w₂，w₃，68. 由此可知，p₁中b₁型零件可选择路线w₁或w₂加工，b₂型零件则只可选择路线w₃. 当p₉中b₂型零件不为空时，调度方案的数量仅与库所p₁中的资源数量相关. 若b₁型零件有

x \in N

个，则图6所示的TdPN系统必然有x + 1个调度方案.

根据图5，由式（1），首先，选择

D \cdot {\vec{σ}}_{0}

值最小的方案 3并标记J（M₀），通过算2–3计算出该方案的时延变迁序列，即

\begin{matrix} σ_{τ} = \\ (t_{1}, 2) (t_{9}, 2) (t_{6}, 5) (t_{1}, 7) (t_{10}, 8) (t_{6}, 10) (t_{9}, 10) \\ (t_{7}, 11) (t_{11}, 14) (t_{7}, 17) (t_{12}, 18) (t_{10}, 20) (t_{11}, 23) \\ (t_{8}, 24) (t_{12}, 27) (t_{5}, 28) (t_{8}, 32) (t_{5}, 36) . \end{matrix}

再选取计算

R ({\vec{σ}}_{0})

中

D \cdot {\vec{σ}}_{0}

值最小且未被标记的方案2的时延变迁序列，即

\begin{matrix} σ_{τ} = \\ (t_{1}, 2) (t_{9}, 2) (t_{6}, 5) (t_{2}, 7) (t_{1}, 7) (t_{10}, 8) (t_{9}, 10) \\ (t_{7}, 11) (t_{11}, 11) (t_{3}, 15) (t_{12}, 15) (t_{10}, 17) (t_{4}, 18) \\ (t_{11}, 20) (t_{8}, 21) (t_{5}, 22) (t_{12}, 24) (t_{5}, 26), \end{matrix}

最后计算方案1的时延变迁序列，即

\begin{matrix} σ_{τ} = \\ (t_{1}, 2) (t_{9}, 2) (t_{2}, 7) (t_{10}, 8) (t_{11}, 9) (t_{1}, 10) \\ (t_{9}, 11) (t_{2}, 14) (t_{3}, 15) (t_{10}, 16) (t_{4}, 17) (t_{12}, 18) \\ (t_{5}, 21) (t_{11}, 21) (t_{3}, 23) (t_{4}, 24) (t_{12}, 25) (t_{5}, 28) . \end{matrix}

通过本文方法可计算出所有方案的时延变迁序列，其中方案 3“w₂，w₃，68”的

D \cdot {\vec{σ}}_{0}

值最小，与文献 ^[18] 方法计算的方案时间相同，但显然其不是最小时间的调度方案. 表7是通过图6所示TdPN模型与文献 ^[18] 计算的σ_τ调度方案对比结果，其中文献 ^[18] 只能计算出一条近似最小时间的调度方案，而本文计算的方案数等于系统存在的方案数. 结合表7和上述分析可知，本文可以计算出所有的时延变迁序列方案，并最终获得最小时间的调度方案.

6 结论

为获取柔性制造系统最小完工时间的调度方案，在现有基于时延Petri网的近似最小时间时延变迁序列搜索算法的基础上，提出了一种基于时延Petri网与代价函数的优化调度算法. 首先，通过改进的代价函数搜索可行的逻辑变迁序列. 其次，将逻辑变迁序列转为时延变迁序列，并通过初始标识代价函数标记已经找到的时延变迁序列，来计算所有可能的时延变迁序列，最终，找到系统最小完工时间的调度方案. 相比现有近似最小时间的调度算法，本文提出的优化调度算法能有效降低计算复杂度并提高算法搜索的准确性. 然而，当时延Petri网系统存在大量可行时延变迁序列时，找出所有变迁序列的计算量会增大. 下一步工作将通过设置更优的代价函数以快速找到最小时间的时延变迁序列. 此外，在本文方法的基础上研究含不可控或不可观变迁的Petri网系统优化调度也将是一项挑战性的工作.

表7与文献 ^[18] 所得σ_τ方案对比

Table7Scheduling methods compared with σ_τ in ^[18]

注 1 p ^∗ = p₁₄ + 2p₁₅ +p₁₆ +p₁₇ + 2p₁₈，多集形式的初始标识M₀ = 2p₁ + 2p₉ +p₁₄ + 2p₁₅ +p₁₆ +p₁₇ + 2p₁₈等价于M₀ = [2 0 0 0 0 0 0 0 2 0 0 0 0 1 2 1 1 2]^T，其代表零件1库和2库中各有两个待加工的零件. 访问节点数是所计算方案总体节点数的平均值，例如上述案例计算的方案 1，2，3 访问节点数测试结果分别为49，39，50，则该案例访问节点数定为46.

图1基于MPC思想的搜索策略流程图

Fig.1Flow chart of search strategy based on MPC

下载: 全尺寸图片

图2一个TdPN ^[18]

Fig.2A TdPN ^[18]

下载: 全尺寸图片

图3部分搜索的可达图

Fig.3Partial searching reachable graph

下载: 全尺寸图片

图4逻辑变迁序列搜索图

Fig.4Graph for searching logical transition sequences

下载: 全尺寸图片

图5时延变迁序列求解流程图

Fig.5Flow chart for solving timed transition sequences

下载: 全尺寸图片

图6某FMS的TdPN模型

Fig.6The TdPN model of an FMS

下载: 全尺寸图片

表1计算TdPN系统下一个变迁t^∗

Table1Computation of the next transition t^∗ for TdPN systems

下载: 全尺寸图片

表2计算TdPN系统的逻辑变迁序列σ

Table2Computation of the logical transition sequence σ for TdPN systems

下载: 全尺寸图片

表3将σ转换为时延变迁序列σ_τ

Table3Transtormation of σ into σ_τ

下载: 全尺寸图片

表4σ的算法复杂度对比

Table4Comparison of algorithmic complexity of σ

下载: 全尺寸图片

表5σ访问节点对比

Table5Comparison of access nodes for σ

下载: 全尺寸图片

表6库所和变迁的含义

Table6Implication of places and transitions

下载: 全尺寸图片

表7与文献 ^[18] 所得σ_τ方案对比

Table7Scheduling methods compared with σ_τ in ^[18]

下载: 全尺寸图片

图1基于MPC思想的搜索策略流程图

Fig.1Flow chart of search strategy based on MPC

图2一个TdPN ^[18]

Fig.2A TdPN ^[18]

图3部分搜索的可达图

Fig.3Partial searching reachable graph

图4逻辑变迁序列搜索图

Fig.4Graph for searching logical transition sequences

图5时延变迁序列求解流程图

Fig.5Flow chart for solving timed transition sequences

图6某FMS的TdPN模型

Fig.6The TdPN model of an FMS

表1计算TdPN系统下一个变迁t^∗

Table1Computation of the next transition t^∗ for TdPN systems

表2计算TdPN系统的逻辑变迁序列σ

Table2Computation of the logical transition sequence σ for TdPN systems

表3将σ转换为时延变迁序列σ_τ

Table3Transtormation of σ into σ_τ

表4σ的算法复杂度对比

Table4Comparison of algorithmic complexity of σ

表5σ访问节点对比

Table5Comparison of access nodes for σ

表6库所和变迁的含义

Table6Implication of places and transitions

表7与文献 ^[18] 所得σ_τ方案对比

Table7Scheduling methods compared with σ_τ in ^[18]

图(6) / 表(7)

引用本文

李鑫, 黎良, 何舟. 基于时延 Petri网与代价函数的柔性制造系统优化调度. 控制理论与应用, 2026, 43(2): 415 – 424

复制

LI Xin, LI Liang, HE Zhou. Optimal scheduling of flexible manufacturing systems based on timed Petri nets and cost function. Control Theory & Applications, 2026, 43(2): 415 – 424

Copy

计量

图1基于MPC思想的搜索策略流程图

Fig.1Flow chart of search strategy based on MPC

图2一个TdPN ^[18]

Fig.2A TdPN ^[18]

图3部分搜索的可达图

Fig.3Partial searching reachable graph

图4逻辑变迁序列搜索图

Fig.4Graph for searching logical transition sequences

图5时延变迁序列求解流程图

Fig.5Flow chart for solving timed transition sequences

图6某FMS的TdPN模型

Fig.6The TdPN model of an FMS

表1计算TdPN系统下一个变迁t^∗

Table1Computation of the next transition t^∗ for TdPN systems

表2计算TdPN系统的逻辑变迁序列σ

Table2Computation of the logical transition sequence σ for TdPN systems

表3将σ转换为时延变迁序列σ_τ

Table3Transtormation of σ into σ_τ

表4σ的算法复杂度对比

Table4Comparison of algorithmic complexity of σ

表5σ访问节点对比

Table5Comparison of access nodes for σ

表6库所和变迁的含义

Table6Implication of places and transitions

表7与文献 ^[18] 所得σ_τ方案对比

Table7Scheduling methods compared with σ_τ in ^[18]

SILVA M. On the history of discrete event systems. Annual Reviews in Control,2018,45:213-222.

HUANG B, ZHOU M, LU X S,et al. Scheduling of resource allocation systems with timed Petri nets: A survey. ACM Computing Surveys,2023,55(11):1-27.

WU Naiqi, QIAO Yan. A novel production scheduling methodology by using discrete event system control theories. Control Theory & Applications,2021,38(11):1809-1818.(伍乃骐, 乔岩. 应用离散事件系统控制理论求解生产调度的新方法. 控制理论与应用,2021,38(11):1809-1818.)

LI Dacheng, LUO Jiliang, SUN Shasha,et al. The integrated method of scheduling and control for manufacturing systems based on parallel Petri nets. Acta Automatica Sinica,2023,49(4):845-856.(李大成, 罗继亮, 孙莎莎, 等. 基于平行Petri网的制造系统调度与控制一体化方法. 自动化学报,2023,49(4):845-856.)

UZAM M, LI Z W, GELEN G,et al. A divide-and-conquer-method for the synthesis of liveness enforcing supervisors for flexible manufacturing systems. Journal of Intelligent Manufacturing,2016,27:1111-1129.

GIUA A, SILVA M. Petri nets and automatic control: A historical perspective. Annual Reviews in Control,2018,45:223-239.

CASALINO A, ZANCHETTIN A M, PIRODDI L,et al. Optimal scheduling of human-robot collaborative assembly operations with time Petri nets. IEEE Transactions on Automation Science and Engineering,2019,18(1):70-84.

WANG Chen, LI Liang, LIU Bin. Initial resource allocation of realtime systems based on minimum initial states of labeled time Petri nets. Control Theory & Applications,2024,41(11):2103-2111.(王琛, 黎良, 刘斌. 基于标签时间Petri网最小初始状态的实时系统初始资源配置. 控制理论与应用,2024,41(11):2103-2111.)

LI Yong, LI Kuncheng, SUN Baiqing,et al. Multi-robot-multi-task coordination framework based on the integration of intelligent agent and Petri net. Acta Automatica Sinica,2021,47(8):2029-2049.(李勇, 李坤成, 孙柏青, 等. 智能体Petri网融合的多机器人-多任务协调框架. 自动化学报,2021,47(8):2029-2049.)

LI Wenhong, ZHENG Jianzhi. Research on automatic scheduling strategy for downhole dispatching transportation. Control Theory & Applications,2021,38(6):757-765.(李文宏, 郑建志. 井下调度运输的自动调度策略研究. 控制理论与应用,2021,38(6):757-765.)

MEJIA G, PEREIRA J. Multi-objective scheduling algorithm for flexible manufacturing systems with Petri nets. Journal of Manufacturing Systems,2020,54:272-284.

WU Yali, HE Shuting, YANG Yanxi,et al. Scheduling optimization of aluminum extrusion production line based on timed Petri net and BSO algorithm. Journal of System Simulation,2023,35(1):178-189.(吴亚丽, 何淑婷, 杨延西, 等. 基于时延Petri网与BSO的铝挤压线排产调度优化. 系统仿真学报,2023,35(1):178-189.)

LEE D Y, DICESARE F. Scheduling flexible manufacturing systems using Petri nets and heuristic search. IEEE Transactions on Robotics and Automation,1994,10(2):123-132.

LUO J C, XING K Y, ZHOU M C,et al. Deadlock-free scheduling of automated manufacturing systems using Petri nets and hybrid heuristic search. IEEE Transactions on Systems, Man,and Cybernetics: Systems,2014,45(3):530-541.

WANG X, XING K, FENG Y,et al. Scheduling of flexible manufacturing systems subject to no-wait constraints via Petri nets and heuristic search. IEEE Transactions on Systems, Man,and Cybernetics: Systems,2019,51(10):6122-6133.

HUANG B, ZHOU M C. Symbolic scheduling of robotic cellular manufacturing systems with timed Petri nets. IEEE Transactions on Control Systems Technology,2022,30(5):1876-1887.

LEFEBVRE D. Approaching minimal time control sequences for timed Petri nets. IEEE Transactions on Automation Science and Engineering,2015,13(2):1215-1221.

LEFEBVRE D. Near-optimal scheduling for Petri net models with forbidden markings. IEEE Transactions on Automatic Control,2018,63(8):2550-2557.

LEFEBVRE D, BASILE F. An approach based on timed Petri nets and tree encoding to implement search algorithms for a class of scheduling problems. Information Sciences,2021,559:314-335.

CAMACHO E F, BORDONS C, CAMACHO E F,et al. Model Predictive Controllers. Switzorland: Springer,2007.

XING K, WANG F, ZHOU M C,et al. Deadlock characterization and control of flexible assembly systems with Petri nets. Automatica,2018,87:358-364.

DU Y Y, NING Y H, QI L. Reachability analysis of logic Petri nets using incidence matrix. Enterprise Information Systems,2014,8(6):630-647.