Reachability analysis of real-time systems using time Petri nets

Time Petri nets (TPNs) are a popular Petri net model for specification and verification of real-time systems. A fundamental and most widely applied method for analyzing Petri nets is reachability analysis. The existing technique for reachability analysis of TPNs, however, is not suitable for timing property verification because one cannot derive end-to-end delay in task execution, an important issue for time-critical systems, from the reachability tree constructed using the technique. In this paper, we present a new reachability based analysis technique for TPNs for timing property analysis and verification that effectively addresses the problem. Our technique is based on a concept called clock-stamped state class (CS-class). With the reachability tree generated based on CS-classes, we can directly compute the end-to-end time delay in task execution. Moreover, a CS-class can be uniquely mapped to a traditional state class based on which the conventional reachability tree is constructed. Therefore, our CS-class-based analysis technique is more general than the existing technique. We show how to apply this technique to timing property verification of the TPN model of a command and control (C2) system.     

Compositional schedulability analysis of real-time systems using time Petri nets

This paper presents an approach to the schedulability analysis of real-time systems modeled in time Petri nets by separating timing properties from other behavioral properties. The analysis of behavioral properties is conducted based on the reachability graph of the underlying Petri net, whereas timing constraints are checked in terms of absolute and relative firing domains. If a specific task execution is schedulable, we calculate the time span of the task execution, and pinpoint nonschedulable transitions to help adjust timing constraints. A technique for compositional timing analysis is also proposed to deal with complex task sequences, which not only improves efficiency but also facilitates the discussion of the reachability issue with regard to schedulability. We identified a class of well-structured time Petri nets such that their reachability can be easily analyzed.     

Fuzzy rule base systems verification using high-level Petri nets

In this paper, we propose a Petri nets formalism for the verification of rule-based systems. Typical structural errors in a rule-based system are redundancy, inconsistency, incompleteness, and circularity. Since our verification is based on Petri nets and their incidence matrix, we need to transform rules into a Petri nets first, then derive an incidence matrix from the net. In order to let fuzzy rule-based systems detect above the structural errors, we are presenting a Petri-nets-based mechanism. This mechanism consists of three phases: rule normalization, rules transformation, and rule verification. Rules will be first normalized into Horn clauses, then transform the normalized rules into a high-level Petri net, and finally we verify these normalized rules. In addition, we are presenting our approach to simulate the truth conditions which still hold after a transition firing and negation in Petri nets for rule base modeling. In this paper, we refer to fuzzy rules as the rules with certainty factors, the degree of truth is computed in an algebraic form based on state equation which can be implemented in matrix computation in Petri nets. Therefore, the fuzzy reasoning problems can be transformed as the liner equation problems that can be solved in parallel. We have implemented a Petri nets tool to realize the mechanism presented fuzzy rules in this paper.     

Perturbation analysis of stochastic Petri nets

This paper addresses the sensitivity analysis of stochastic Petri nets (SPNs) using simulations. The goal is to evaluate the derivatives of performance measures with respect to timing parameters. To characterize the underlying stochastic processes of SPNs, we use a generalized semi-Markov process (GSMP) representation and propose a new representation, called GSMP*, which differs from GSMP in the routing mechanism. By using existing results on perturbation analysis of GSMPs and by extending them to GSMP*, unbiased sensitivity estimators are obtained for SPNs simulated under a GSMP or GSMP* framework. Most importantly, we prove that only one simulation run is needed for evaluating both the performance measures and their derivatives for a class of free-choice nets simulated under a GSMP framework and for any free-choice net simulated under a GSMP* framework     

Petri nets with causal time for system verification

We present a new approach to the modelling of time constrained systems. It is based on untimed high-level Petri nets using the concept of causal time. With this concept, the progression of time is modelled in the system by the occurrence of a distinguished event, tick, which serves as a reference to the rest of the system. In order to validate this approach as suitable for automated verification, a case study is provided and the results obtained using a model-checker on high-level Petri nets are compared with those obtained for timed automata using prominent tools. The comparison is encouraging and shows that the causal time approach is intuitive and modular. It also potentially allows for efficient verification.     

Performance evaluation of parallel systems by using unboundedgeneralized stochastic Petri nets

Methods of calculating efficiently the performance measures of parallel systems by using unbounded generalized stochastic Petri nets are presented. An explosion in the number of states to be analyzed occurs when unbounded places appear in the model. The state space of such nets is infinite, but it is possible to take advantage of the natural symmetries of the system to aggregate the states of the net and construct a finite graph of lumped states which can easily be analyzed. With the methods developed, the unbounded places introduce a complexity similar to that of safe places of the net. These methods can be used to evaluate models of open parallel systems in which unbounded places appear; systems which are k-bounded but are complex and have large values of k can also be evaluated in an appropriate way. From the steady-state solution of the model, it is possible to obtain automatically the performance measures of parallel systems represented by this type of net     

Performance analysis of stochastic timed Petri nets using linearprogramming approach

Stochastic timed Petri nets are a useful tool in the performance analysis of concurrent systems such as parallel computers, communication networks and flexible manufacturing systems. In general, performance measures of stochastic timed Petri nets are difficult to obtain for practical problems due to their sizes. In this paper, we provide a method to efficiently compute upper and lower bounds for the throughputs and mean token numbers for a large class of stochastic timed Petri nets. Our approach is based on uniformization technique and linear programming     

Real time identification of discrete event systems using Petri nets

The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net () model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the can be recursively identified. Some results and examples characterize the identified systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of systems via monitor places is proposed.     

Sensitivity analysis and optimization of stochastic Petri nets

In this paper we define the notion of controlled stochastic Petri net (CSPN), which is a stochastic Petri net with controlled parameters and performance indices. Specifically, transition times and/or conflict resolution rules can depend on controlled parameters and transition times can have arbitrary distribution functions. A method for computing statistical estimates of performance indices and their gradients (sensitivities) with respect to controlled parameters is described. This method, which needs only one simulation of a CSPN, is considerably superior to conventional finite differences both in terms of precision and required amount of simulation and is based on likelihood ratio/score function approach, other possibilities based on extensions of infinitesimal perturbation analysis are outlined. These gradient estimates are used in stochastic optimization algorithms to obtain the optimal value of the aggregated performance function of the CSPN. A combined optimization and simulation tool is developed which includes approaches to the gradient estimation mentioned above. The numerical experiments presented in this paper confirm the efficiency of the proposed techniques.     

广义随机Petri网在生态产业园区性能分析中的应用*

为了对生态产业园区规划方案进行定量描述和评价,利用基于广义随机Petri网的建模分析方法,根据广义随机Petri网模型与马尔可夫链的同构关系,得到生态产业园区的Petri网模型和马尔可夫链模型。并通过马尔可夫链理论与相关数学方法,得到生态产业园区规划方案的吞吐性能、时间性能以及关键资源利用率和重点加工环节运作效率等性能指标,诊断出现有规划中存在的问题,为生态产业园区规划方案的评价和改进提供了一个思路。     

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.     

Markovian timed Petri nets for performance analysis ofsemiconductor manufacturing systems

A subclass of generalized stochastic Petri nets (GSPNs) with priorities, called Markovian timed Petri nets, are proposed to model semiconductor manufacturing systems that consider process priorities, routing priorities, resource re-entrance, and nonpreemptive operations. Uniformization technique is used to establish both lower and upper bounds of the performance of interest. These bounds are computable using linear programming. Numerical experiments have been conducted to evaluate the accuracy of the bounds using models adapted from real-world systems. The experiments show that the upper bounds are very close to the simulation results. Thus, performance measures can be accurately estimated using these bounds.     

装配可靠性的模糊广义随机Petri网建模与分析

针对一般广义随机Petri网模型精度低的问题,将模糊数引入到广义随机Petri网,提出模糊广义随机Petri网的概念.结合模糊数包含信息多的优点,利用模糊广义随机Petri网对装配过程进行建模,通过同构的Markov链对模型进行定量分析.用模糊广义随机Petri网模型计算得到的装配可靠度与一般广义随机Petri网模型的装配可靠度进行分析比较,结果表明了模糊广义随机Petri网模型的精度更高.以数控磨床砂轮架为例,证明了上述方法的有效性.     

一种随机着色Petri网及模型的性能分析

针对随机Petri网（SPN）在系统性能分析时,其状态空间随着系统规模增大而指数性增长,造成求解稳定状态概率的复杂性的不足,提出了一种随机着色Petri网（SCPN）。分析了它的有界性和可达性,证明了它同构于一个一维连续时间的马尔可夫链;同时,也分析了随机着色Petri网用于建模和系统性能定量分析的方法。     

Implementation of real-time distributed control for discrete event robotic systems using Petri nets

This article presents a systematic method of modeling and implementing real-time control for discrete-event robotic systems using Petri nets. Because, in complex robotic systems such as flexible manufacturing systems, the controllers are distributed according to their physical structure, it is desirable to realize real-time distributed control. In this article, the task specification of robotic processes is represented as a system control-level net. Then, based on the hierarchical approach, it is transformed into detailed subnets, which are decomposed and distributed into the local machine controllers. The implementation of real-time distributed control through communication between the system controller and the machine controllers on a microcomputer network is described for a sample robotic system. The proposed implementation method is sufficiently general, and can be used as an effective prototyping tool for consistent modeling, simulation, and real-time control of large and complex robotic systems.     

生化网络的随机Petri网建模与分析

细胞的行为是随机性的,学习细胞中的随机性有助于理解细胞的组织,设计和进化。建立、确认和分析随机的生化网络模型是当前计算系统生物学领域的一个重要研究主题。当前,标准的Petri网模型已经成为生化网络模拟和定性分析的有力工具。尝试使用随机Petri网对生化网络进行建模与分析,简单描述了随机Petri网理论对标准Petri网的扩充,通过对二聚作用和肌动蛋白这两个典型例子的建模与演化模拟,介绍、论证了随机Petri网理论的新应用。     

Performance analysis using Petri nets

The purpose of this paper is to focus on the implementation issues associated with using Petri nets for the performance analysis of discrete event dynamic systems while demonstrating several applications in manufacturing systems. Practical modeling issues will be discussed and several applications will be presented that illustrate the advantages and limitations of this methodology. These issues lead to the definition of several research problems in Petri nets for performance analysis.