业务过程的扩展广义随机Petri网模型

为建立能够描述外部环境、业务操作耗时服从一般分布的业务过程性能模型,引入扩展广义随机Petri网.用容纳有无穷多托肯的输入库所描述建模对象外部环境,用闸门变迁控制外部环境对建模对象的输入,为非立即变迁绑定一个任意分布时间延迟随机变量.最后给出一个建模实例.     

Automatic construction of systems of distributed components from nested Petri nets models

Multi-level multi-agent systems (MASs) with dynamic structure are widely used in solving important applied problems in telecommunication, transportation, social, and other systems. Therefore, ensuring correct behavior of such systems is an actual and important task. One of the most error-prone stages of system development in the framework of model-oriented approach is the implementation stage, in the course of which a program code is constructed based on the model developed. This paper presents an algorithm for automated translation of MAS models represented as nested Petri nets into systems of distributed components. Nested Petri nets are the extension of Petri nets in the framework of the nets-within-nets approach, which assumes that tokens in a Petri net may themselves be Petri nets, possess autonomous behavior, and interact with other tokens of the net. This makes it possible to model MASs with dynamic structure in a natural way. The translation presented in this paper preserves distribution level and important behavioral properties (safety, liveness, and conditional liveness) of the original model and ensures fairness of the target system execution. The use of such translation makes it possible to automate construction of distributed MASs by models of nested Petri nets. As a test example, translation of nested Petri nets into systems of distributed components was implemented on the basis of the EJB component technology.     

Net structure and control logic synthesis of controlled Petri nets

Control logic synthesis of discrete-event systems is considered in the setting of controlled Petri nets. The problem is to find a control policy that restricts the behavior of a controlled Petri net so that a collection of forbidden state conditions is satisfied. S-decreases are introduced as a tool for the control synthesis. The S-decreases are weight vectors defined on the places of a net such that the weighted sum of tokens in the net never increases with any transition firing. On the basis of S-decreases, the authors propose an efficient method for the synthesis of the maximally permissive state feedback control polity for a class of controlled Petri nets whose uncontrolled subnets are forward and backward conflict-free nets. This method upgrades all integer linear programming-based methods for which one only requires to solve the much simpler linear programming problems to determine maximally permissive controls     

Generalised Batches Petri Net: Hybrid Model For High Speed Systems With Variable Delays

Recently, the possibilityof associating both discrete events and continuous time behaviourin the same formalism has generated a considerable interest inthe Petri net paradigm. A central issue in this field is theconcept of Hybrid Petri net which consists in continuous transitionsand places holding non negative real number, and discrete transitionsand places holding integer tokens. By adding a new type of nodes,batch transitions and batch places, Batches Petri nets have beendefined. A batch node combines both a discrete event and a linearcontinuous dynamic behaviour in a single structure. Batches Petrinets can then be used in the control design and performance analysisof high-speed systems composed of continuous transfer elementswhich introduce variable delays on continuous flows. In thispaper, the complete formalism of Generalised Batches Petri netsis given through the definition of the model, the enabling andfiring rules, the time analysis methods, and two examples illustratethese notions.     

一种基于Petri网的特定手语词汇识别方法

本文尝试使用Petri网进行简单的手语词汇识别。首先采用模板匹配方法检测到一系列简单的手势,如手掌张开直立、握拳、伸出大小拇指。其中,每个简单手势的发生对应于Petri网中的一个变迁。待识别的手语词汇是由一串特定的手势序列构成的,如手掌张开直立一握争伸出大小拇指。通过Petri网记录手势的动态变化,并在每次新变迁发生时检测目标库所的标志增加情况,从而实现特定手语词汇的识别。     

Automating the Conversion of Colored Petri Nets with Qualitative Tokens Into Colored Petri Nets with Quantitative Tokens

The authors describe an algorithm for conversion of colored Petri nets with qualitative tokens into a colored Petri net with quantitative tokens preserving boundedness, mutual exclusion, and liveness properties. This conversion allows the invariance method to be applied to colored Petri nets, which uses the Truncated Set of Solutions finding algorithm for Petri net state equations expressed through systems of linear homogenous Diophantine equations. To show the algorithm’s efficiency, it is applied to the colored Petri net that models the operation of a grid system. Equivalence of net models is tested by constructing and analyzing equal finite-state machine.     

On Controllability of Dependent Siphons for Deadlock Prevention in Generalized Petri Nets

A fair amount of research has shown the importance of siphons in the analysis and control of deadlocks in a variety of resource allocation systems by using a Petri net formalism. In this paper, siphons in a generalized Petri net are classified into elementary and dependent ones, as done for ordinary nets in our previous work. Conditions are derived under which a dependent siphon is controlled by properly supervising its elementary siphons, which indicates that the controllability of dependent siphons in an ordinary Petri net is a special case of that in a generalized one. The application of the controllability of dependent siphons is shown by considering the deadlock prevention problem for a class of resource allocation systems, namely, G-system that allows multiple resource acquisitions and flexible routings in a flexible manufacturing system with machining, assembly, and disassembly operations. We develop a monitor-based deadlock prevention policy that first adds monitors for elementary siphons only to a G-system plant model such that the resultant net system satisfies the maximal controlled-siphon property (maximal cs-property). Then, by linear programming, initial tokens in the additional monitors are decided such that liveness is enforced to the supervised system. Also, a simplified live marking relationship for a G-system between the initial tokens of the source places and those of the resource places is derived. Finally, the proposed deadlock prevention methods are illustrated by using an example.     

基于Petri网的柔性制造系统一种预防死锁方法

基于Petri网的结构特性分析,研究了FMS(柔性制造系统)一种预防死锁方法.提出了 Petri网的一种特殊拓扑结构--基本信标的概念.在Petri网中基本信标的集合是SMS(严格极 小信标)集合的一个真子集.尤其在大型Petri网系统中,基本信标的集合比SMS的集合要小得 多.对于Petri网的一个子类S3PR,只对每一个基本信标添加一个库所使其不被清空,就可实现 预防死锁,也就是说无须控制S3PR的所有SMS而达到无信标被清空的目的.此外,对于S3PR, 还提出了一种求取SMS和基本信标的方法.相对于现在普遍采用的控制所有SMS来预防死锁 的策略,其具三方面优势.1)只需控制少量的SMS即所谓的基本信标.相应地,添加少量的控制 库所和连接弧,就可得到无死锁或活的Petri网.2)不需要先行计算出极小信标的集合.3)明显 地,这种方法更适合大型Petri网系统.我们通过穿插在文中的一个例子来说明这些方法.     

A fuzzy Petri net-based expert system and its application to damageassessment of bridges

In this paper, a fuzzy Petri net approach to modeling fuzzy rule-based reasoning is proposed to bring together the possibilistic entailment and the fuzzy reasoning to handle uncertain and imprecise information. The three key components in our fuzzy rule-based reasoning-fuzzy propositions, truth-qualified fuzzy rules, and truth-qualified fuzzy facts-can be formulated as fuzzy places, uncertain transitions, and uncertain fuzzy tokens, respectively. Four types of uncertain transitions-inference, aggregation, duplication, and aggregation-duplication transitions-are introduced to fulfil the mechanism of fuzzy rule-based reasoning. A framework of integrated expert systems based on our fuzzy Petri net, called fuzzy Petri net-based expert system (FPNES), is implemented in Java. Major features of FPNES include knowledge representation through the use of hierarchical fuzzy Petri nets, a reasoning mechanism based on fuzzy Petri nets, and transformation of modularized fuzzy rule bases into hierarchical fuzzy Petri nets. An application to the damage assessment of the Da-Shi bridge in Taiwan is used as an illustrative example of FPNES.     

Modeling and performance evaluation of supply chains using batch deterministic and stochastic Petri nets

Batch deterministic and stochastic Petri nets are introduced as a tool for modeling and performance evaluation of supply chains. The new model is developed by enhancing deterministic and stochastic Petri nets (DSPNs) with batch places and batch tokens. By incorporating stochastic Petri nets (SPNs) with the batch features, inhibitor arcs, and marking-dependent weights, operational policies of supply chains such as inventory policies can be easily described in the model. Methods for structural and performance analysis of the model are developed by extending existing ones for DSPNs. As applications, an inventory system and an industrial supply chain are modeled and their performances are evaluated analytically and by simulation, respectively, using this BSPN model. The applications demonstrate that our model and associated methods can solve some important supply chain modeling and analysis issues. Note to Practitioners-This paper was motivated by the problem of performance analysis and optimization of supply chains but it also applies to other discrete event systems where materials are processed in finite discrete quantities (batches) and operations are performed in a batch way because of batch inputs and/or in order to take advantages of the economies of scale. Existing Petri net modeling and analysis tools for such systems ignore their batch features, making their modeling complicated. This paper suggests a new model called batch deterministic and stochastic Petri nets (BDSPNs) by enhancing deterministic and stochastic Petri nets with batch places and batch tokens. Methods for structural and performance analysis of the model are developed. We then show how an inventory system and a real-life supply chain can be modeled and their performances can be evaluated analytically and by simulation respectively based on the model. The model and associated analysis methods therefore provide a promising tool for modeling and performance evaluation of supply chains.     

网上证券交易系统的时序Petri网描述及验证

基于时序Petri网对我国现行网上静态和动态证券交易系统进行了模拟、形式描述及功能正确性验证.应用时序逻辑推理规则,从形式上严格证明了证券交易系统需求规范及其时序Petri网模型动态行为的一致性.结果表明,时序Petri网能够清楚而简单地描述事件间的因果关系和时序关系以及并发系统中某些与时间有关的重要性质,如最终性和公平性.因此,时序Petri网可作为并发系统形式化描述和分析的有力工具.     

Complex-valued token Petri nets

This paper presents a new extension to ordinary Petri nets (PNs) that uses complex-valued tokens. By allowing two kinds of tokens, "real" and "imaginary," each place marking contains both quantity and type information. Complex-valued token PNs were designed to integrate seamlessly with other popular Petri net extensions such as timed nets, stochastic nets, and colored nets. This simple and intuitive application of complex numbers and complex arithmetic to PNs provides a unique modeling tool. Some examples show the capabilities of this proposed class of PNs. Note to Practitioners-Discrete-event systems are often man-made systems such as transportation systems, computer communication networks, distributed software, and manufacturing systems. They typically involve the flow of information and physical goods through a network. The flow itself evolves in continuous time but the initiation or completion of the event happens at a discrete point in time. Analyzing the system's performance is key to their successful operation. This paper presents a new approach to performance analysis with application to supply-chain management.     

CPN tools-assisted simulation and verification of nested Petri nets

Nested Petri nets (NP-nets) is an extension of Petri net formalism within the “nets-within-nets” approach, when tokens in a marking are Petri nets wich have autonomous behavior and synchronize with the system net. The formalism of NP-nets allows modeling multi-level multi-agent systems with dynamic structure in a natural way. Currently there is no tool support for NP-nets simulation and analysis. The paper proposes translation of NP-nets into colored Petri nets and using CPN Tools as a virtual machine for NP-nets modeling, simulation and automatic verification.     

POC net,a subclass of Petri nets,and its application to timed Petri nets

Liveness is one of the most important properties of the Petri net analysis. This property is concerned with a capability for firing of transitions. On the other hand, place-liveness is another notion related to liveness, which is concerned with a capability for having tokens in places. Concerning these liveness and place-liveness problems, this paper suggests a new subclass of Petri net, ‘POC nets’, as a superclass of AC nets and DC nets. For this subclass, the equivalence between liveness and place-liveness is shown and a sufficient condition for liveness for this POC net is derived. Then the results are extended to liveness problem of timed Petri nets which have transitions with finite firing durations and the earliest firing rule. Although liveness of a (non-timed) Petri net is neither necessary nor sufficient condition for liveness of a timed Petri net, it is shown that liveness is preserved if the net has POC structure. Furthermore, it is pointed out that if a POC net satisfies some additional condition, Petri net liveness is equivalent to timed Petri net liveness. Finally, it is shown that liveness of timed POC nets with TC structure and the earliest firing rule is decidable with deterministic polynomial time complexity.     

Interacting behavioral Petri nets analysis for distributed causal model-based diagnosis

This paper deals with the problem of spatially distributed causal model-based diagnosis on interacting behavioral petri nets (BPNs). The system to be diagnosed comprises different interacting subsystems (each modeled as a BPN) and the diagnostic system is defined as a multi-agent system where each agent is designed to diagnose a particular subsystem on the basis of its local model, the local received observation and the information exchanged with the neighboring agents. The interactions between subsystems are captured by tokens that may pass from one net model to another via bordered places. The diagnostic reasoning scheme is accomplished locally within each agent by exploiting classical analysis techniques of Petri nets like reachability graph and invariant analysis. Once local diagnoses are obtained, agents begin to communicate to ensure that such diagnoses are consistent and recover completely the results that would be obtained by a centralized agent having a global view about the whole system. The paper concludes with an empirical comparison, in terms of the running time, of two implementations of Petri net analysis techniques used as a distributed diagnostic reasoning schemes.     

基于CPN Tools的抑制弧改进方法研究

在Petri网模型中,抑制弧用于表示除输入库所条件外,仅当指定库所为空时变迁才可以触发的情况,可以应用于各类Petri网中。在广泛使用的Petri网模型工具CPN Tools中没有直接提供抑制弧,仅给出了两种等价处理方法。通过对抑制弧的问题进行分析,提出在CPN Tools使用List解决抑制弧问题的改进方法。此方法具有良好的通用性和易用性,并且仅通过修改DropOneInList函数的内容就可以实现随机、栈方式、队列方式、优先级等各种令牌提取方法。     

Suboptimal time management of discrete event systems with uncontrollable events modeled by Petri nets

Preventing systems from entering to forbidden states is a crucial issue in discrete event systems control. Adding supervisors to the system is a common method to avoid entering to forbidden states. In discrete event systems modeled by Petri net adding a supervisor could be done by means of control places. Since, the time is not considered in designing this supervisor, in presence of uncontrollable transitions adding control places can lead to increase the operation time of the system modeled by timed Petri net. Because, the firing of some transitions is prevented when it is not necessary. So, to design a more efficient controller, we will be required to use time information of the system component. Therefore, in this paper, a method for optimizing the time behavior of a supervised timed Petri net will be proposed. To obtain an efficient operation, some timed places as timer will be added to the net. The time of this timer places is calculated to permit firing of some controllable transitions in order to enter into some weakly forbidden states while entering to forbidden states is prevented. This concept leads to increase the speed of system as well as obtain an acceptable operation. This method can be applied for all systems modeled by Petri nets. The efficiency of proposed approach will be discussed and validated with a case study.     

基于有限容量库所的离散事件系统的Petri网控制器综合——第1部分

针对由Petri网建模的离散事件系统, 提出了一种新的控制器设计方法. 控制器是基于有限容量库所的概念构造而成的, 并使被控对象在给定的一组线性不等式约束下运行, 而给定的线性不等式约束是定义在库所标识上的. 控制器的综合利用了有限容量库所Petri网转换为 (普通 )无限容量库所Petri网的技术. 针对约束的不同情况, 给出了相应的Petri网的控制器的设计方法.     

Preserving Languages and Properties in Stepwise Refinement-Based Synthesis of Petri Nets

The current stepwise refinement operation of Petri nets mainly concentrates on property preservation, which is an effective way to analyze and verify complex systems. Further steps into this field are needed from the perspective of system synthesis and language preservation. First, the refinement of Petri nets is introduced based on a k-well-behaved Petri net, in which k tokens can be processed. Then, according to the different compositions of subsystems, well-, under- and overmatched refined Petri nets are proposed. In addition, the language and property relationships among sub-, original, and refined nets are studied to demonstrate behavior characteristics and property preservation in a system synthesis process. A manufacturing system is given as an example to illustrate the effectiveness of the proposed approach in synthesizing and analyzing the Petri nets of complex systems.