Petri网的符号ZBDD可达树分析技术

Petri网是一种适合于并发系统建模、分析和控制的图形工具.可达树是Petri网分析的典型技术之一,它通过标识向量集合表征系统的状态空间,组合复杂性严重制约了该分析技术可处理系统问题的规模.零压缩决策图(Zero-Suppressed Binary Decision Diagrams,ZBDD)是一种新型的数据结构,是表示和处理稀疏向量集合的一种有效技术.文章基于Petri网町达标识向量的稀疏特征,给出了Petri网分析的符号ZBDD技术,该技术通过对标识向量(状态)的布尔向量表示、可达标识向最(状态)的符号ZBDD生成,实现Petri网可达状态空间的高效符号操作和紧凑符号表示.实验表明,基于ZBDD的符号可达性分析算法能够有效处理较大规模Petri网问题.     

基于人工鱼群算法的混杂FMS优化调度

针对已有的调度方法难以找到混杂柔性制造系统调度全局最优解的问题,根据一阶混杂Petri网模型提出了一种基于人工鱼群算法的混杂柔性制造系统调度方法.利用混杂Petri网不变行为状态序列与时间序列的对应关系把寻找最优解转换成寻找最优时间序列.首先给出了合法时间序列的定义及其基于人工鱼群算法的判定方法;然后给出了最优时间序列求解的人工鱼群算法,同时提出基于最优解视野变异的人工鱼群算法以解决多次优化过程中只会得到某个局部最优解的问题.最后基于这些算法给出混杂柔性制造系统的最优调度求解方法.实验结果表明所提出方法正确有效.     

柔性制造系统中生产调度问题的零压缩二叉决策图算法

针对赋时有界Petri网模型下柔性制造系统的生产调度问题,给出了有界Petri网的零压缩二叉决策图表示方法,进而建立了此类生产调度问题求解的符号零压缩二叉决策图算法.该算法在求解过程中对状态空间及其搜索过程中的相关数据,采用零压缩二叉决策图表示,避免了状态和搜索的显式枚举,实现了隐式高效操作,有效地改善了算法的计算性能.实验结果表明了算法的有效性.     

基于改进蚁群算法的维修拆卸序列规划

维修拆卸序列规划是整个维修性设计的重要内容。为了能够以较高的效率求解出产品中零件的拆卸方案,依据产品的基本信息和零件之间的约束关系,建立拆卸Petri网可达图,将拆卸序列规划问题转化为对Petri网可达图最优路径的搜索和寻优问题。同时利用蚁群优化算法对组合优化具有高强适应性的特征,改进基本蚁群算法,对可达图模型进行路径寻优,得到最优或次优的拆卸序列。最后通过实例验证了该方法的有效性。     

Petri网语言表达式及其求解算法

Petri网语言是描述网系统动作序列的集合.为了给出一个网系统语言的形式描述,基于Petri网的状态转换图,分析了Petri网的行为特征,定义了α闭包表达式和Petri网语言表达式,给出了求解Petri网语言表达式的算法,为Petri网语言的形式化描述和分析提供了一种新方法.     

基于带标记的并发可达标识图的关键路径的求解方法

将AOE 网转换成有色时延Petri网模型,在模型转换过程中同时计算出各位置所对应的事件的最早开始时间,给出了模拟AOE 网的有色时延Petri网模型的带标记的并发可达标识图的构建算法;利用并发可达标识图中的标记序列直接得到关键路径并计算出完成所有活动所需的最短时间。实例与仿真实验结果表明,当AOE网中平均存在3个以上的并发活动时,所提方法执行效率优于传统的求解关键路径的算法,并发活动越多,所提算法效率越高。     

有界Petri网的可达图到网图的转换算法

本文给出了有界Petri网的可达标识图到网图的转换算法,对算法的正确性与复杂性分别进行了证明和估计,结果表明该算法是一个多项式算法,因而是有效的。     

应用Petri网求解事故树最小割集的方法研究

为简化事故树分析过程中最小割集求解算法的步骤,在构建事故树Petri网模型的基础上,探讨了事故树Petri网模型的性质,给出了事故树的逻辑表达式与事故树Petri网模型的可达死标识之间的关系,进而提出了利用Petri网可达图求解事故树最小割集的算法,以及在给定基本事件发生时,中间事件和顶事件发生与否的判断方法。结合实例,借助开源的Petri网工具PIPE实现了事故树最小割集的求解,表明了该算法的有效性和可行性。     

基于赋时Petri网描述的多产品间歇过程调度研究

生产调度是多产品间歇生产过程中的一类重要问题。赋时Perti网技术是求解此类问题的一种有效方法。本文给出了复杂中间存储策略下间歇化工过程生产调度的描述方法,包括：无限存储策略UIS、有限存储策略FIS、无中间存储策略NIS和混合存储策略MIS。同时给出了调度求解的修正分支定界和赋时Petri网执行（MBBTE）算法,并通过实例说明了算法的有效性。     

有界Petri网的最小化化简

给出了Petri网的语言等价性概念和有界Petri网的最小化概念；证明了有限状态自动机、有界Petri网、正规文法的等价性，给出了它们之间等价转换的算法；分析了有界Petri网的化简过程，并给出了有界Petri网最小化化简的算法，为有界Petri网的自动化化简提供了方法。     

基于时延Petri网和人工蜂群算法的航电系统并行测试研究

航电系统的复杂程度日益提高,传统的人工检测维护手段已经无法满足现代化装备的支持保障要求,自动测试系统(ATS)正逐步成为复杂系统与设备可靠运行的必要保证,而并行测试是下一代自动测试系统(ATS,automatic test system)的关键技术之一。以并行测试技术为基础,在时延Petri网的基础上,对航电系统测试任务进行建模,并采用人工蜂群算法对Petri网的变迁序列寻求最优解,找到测试时间最短的变迁序列。仿真结果表明,该算法能够快速准确地得到最优的测试方案。     

Petri net supervisors for DES with uncontrollable and unobservabletransitions

A supervisor synthesis technique for Petri net plants with uncontrollable and unobservable transitions, that enforces the conjunction of a set of linear inequalities on the reachable markings of the plant, is presented. The approach is based on the concept of Petri net place invariants. Each step of the procedure is illustrated through a running example involving the supervision of a robotic assembly cell. The controller is described by an auxiliary Petri net connected to the plant's transitions, providing a unified Petri net model of the closed-loop system. The synthesis technique is based on the concept of admissible constraints. Procedures are given for identifying all admissible linear constraints for a plant with uncontrollable and unobservable transitions, as well as methods for transforming inadmissible constraints into admissible ones. A technique is described for creating a modified Petri net controller that enforces the union of all of these control laws. The method is practical and computationally inexpensive in terms of size, design time, and implementation complexity     

基于符号零压缩二叉决策图的组合测试用例生成方法

组合测试是系统测试中一种非常有效的方法,能够在保证错误检出率的前提下采用较少的测试用例来测试系统。但是,组合测试用例集构造问题的复杂度是NP完全的。给出了一种基于符号零压缩二叉决策图(Zero-suppressed Binary Decision Diagram,ZBDD)的组合测试用例生成方法。该方法首先利用ZBDD的结构特性,对测试系统进行紧凑的符号表示。然后利用ZBDD的隐式操作,结合贪心算法的思想,不断地覆盖更多的组合并缩小未覆盖组合集合,生成2～4维覆盖强度的较小测试用例集。实验证明,所提方法不仅可行而且节点开销小。     

网格计算资源调度的层次Petri网建模与分析

本文给出了网格计算资源的三层调度方案，并利用层次颜色Petri网对这一调度方案进行了建模与分析。对不同层次的资源调度建立了相应的颜色时延Petri网模型，不同层次的颜色时延Petri网模型可以有不同的行为表现，体现了网格计算资源的异构、自治等特点。给出了层次颜色Petri网的可迭任务图的概念及构造算法，并利用可达任务图，对网格计算资源调度系统的运行状态进行了分析。     

Polynomial-time algorithm for the legal firing sequences problem of a type of synchronous composition Petri nets

As far as we know, the testing problem of legal firing sequence is NP-complete for gener-al Petri net, the related results of this problem on the polynomial-time solvability are limited only to some special net classes, such as persistent Petri nets, conflict-free Petri nets and state machine Petri nets. In this paper, the language properties of synchronous composition net are discussed. Based on these results, the testing algorithm polynomial-time complexity for legal firing sequence is proposed. Therefore, net classification of polynomial-time solvability for testing legal firing sequence is extended.     

SAT-Solving the Coverability Problem for Petri Nets

Net unfoldings have attracted great attention as a powerful technique for combating state space explosion in model checking, and have been applied to verification of finite state systems including 1-safe (finite) Petri nets and synchronous products of finite transition systems. Given that net unfoldings represent the state space in a distributed, implicit manner the verification algorithm is necessarily a two step process: generation of the unfolding and reasoning about it. In his seminal work McMillan (K.L. McMillan, Symbolic Model Checking. Kluwer Academic Publishers, 1993) showed that deadlock detection on unfoldings of 1-safe Petri nets is NP-complete. Since the deadlock problem on Petri nets is PSPACE-hard it is generally accepted that the two step process will yield savings (in time and space) provided the unfoldings are small.In this paper we show how unfoldings can be extended to the context of infinite-state systems. More precisely, we show how unfoldings can be constructed to represent sets of backward reachable states of unbounded Petri nets in a symbolic fashion. Furthermore, based on unfoldings, we show how to solve the coverability problem for unbounded Petri nets using a SAT-solver. Our experiments show that the use of unfoldings, in spite of the two-step process for solving coverability, has better time and space characteristics compared to a traditional reachability based implementation that considers all interleavings for solving the coverability problem.     

具有不可控变迁离散事件系统的Petri网控制器

考虑可用具有不可控变迁的受控Petri网建模的离散事件动态系统.提出了在这类 系统中实现一组不等式约束的控制器的综合方法.所提出的控制器可通过给系统Petri网模 型增加一些Petri网元素来实现,其计算是建立在本文提出的Petrl网的路增益概念基础上 的.方法是系统、简单、计算量小.     

Firing sequences backward algorithm for simple assembly line balancing problem of type 1

The objective of simple assembly line balancing problem type-1 (SALBP-1) is to minimize the number of workstations on an assembly line for a given cycle time. Since SALBP-1 is NP-hard, many iterative backtracking heuristics based on branch and bound procedure, tabu search, and genetic algorithms were developed to solve SALBP-1. In this study, a new heuristic algorithm based on Petri net approach is presented to solve the problem. The presented algorithm makes an order of firing sequence of transitions from Petri net model of precedence diagram. Task is assigned to a workstation using this order and backward procedure. The algorithm is coded in MATLAB, and its efficiency is tested on Talbot’s and Hoffmann’s benchmark datasets according to some performance measures and classifications. Computational study validates its effectiveness on the benchmark problems. Also comparison results show that the algorithm is efficiency to solve SALBP-1.