Boundedness and liveness enforcement for labeled Petri nets using transition priority

This paper deals with the supervisory control problem of discrete event systems modeled by labeled Petri nets. The system is originally unbounded. First, the solvability of the problem is confirmed. A necessary condition is given and proven for the existence of a feasible priority-based controller based on the notions of liveness and transition invariants. Next, a cyclic behavior graph is constructed, which shows the reachable markings that guarantee the maximum liveness of the system within a given bound vector. Finally, an on-line control strategy is proposed to enforce boundedness and liveness to the given system by appending priority relations to transitions. The dynamic priority relation changes flexibly according to the current state of the system and enforces the system evolving in a bounded and live manner. In addition, numerical examples are studied to verify the validity of the proposed approach that remains the structure of the plant net and is efficient for on-line control.

Petri Nets—A Versatile Modeling Structure

Petri Nets (PNs) are an effective structure for modeling and analyzing asynchronous systems with concurrent and parallel activities. A Petri net models the static properties of a discrete event system concentrating on two basic concepts: events and conditions. Most of the theoretical work on Petri nets is a formal definition of Petri nets structures, which consist of a set of places, representing conditions, a set of transitions, representing events, an input function and an output function. For practical purposes, a graphical representation is more useful. Two types of nodes portray places and transitions. A circle is a place and a bar is a transition. There is no inherent measure of time in a classical Petri net. To approach time-based evaluation of system performances, Timed Petri Nets (TPNs) were introduced. Modeling the notion of time is not straightforward. There are several possibilities for introducing time in PNs, among them timed transitions and timed places. This paper reviews several published examples where Petri Nets were used in different circumstances such as estimating expected utilization of processing resources at steady state in open queueing networks, verifying computerized simulations and batch planning in textile industry.

An Improved Approach to Test Diagnosability of Bounded Petri Nets

For bounded Petri nets, Cabasino et al. propose a diagnosability test method that is based on the analysis of a modified basis reachability graph and a basis reachability diagnoser. However, its complexity is exponential in the number of nodes of the basis reachability diagnoser. In order to reduce the complexity of their method, this paper presents a new diagnosability test approach for bounded Petri nets. We present the concept of an extended basis reachability graph and prove that our approach is of polynomial complexity in the number of nodes of extended basis reachability graphs. An example is given to illustrate the application of the presented approach.

TAR~*:an improved process similarity measure based on unfolding of Petri nets

Determining the similarity degree between process models was very important for their management,reuse,and analysis.Current approaches either focused on process model's structural aspect,or had inefficiency or imprecision in behavioral similarity.Aiming at these problems,a novel similarity measure which extended an existing method named Transition Adjacent Relation(TAR) with improved precision and efficiency named TAR * was proposed.The ability of measuring similarity was extended by eliminating the duplicate tasks without impacting the behaviors.For precision,TARs was classified into repeatable and unrepeatable ones to identify whether a TAR was involved in a loop.Two new kinds of TARs were added,one related to the invisible tasks after the source place and before sink place,and the other representing implicit dependencies.For efficiency,all TARs based on unfolding instead of its reach ability graph of a labeled Petri net were calculated to avoid state space explosion.Experiments on artificial and real-world process models showed the effectiveness and efficiency of the proposed method.

Polynomial Approach to Optimal One-wafer Cyclic Scheduling of Treelike Hybrid Multi-Cluster Tools via Petri Nets

A treelike hybrid multi-cluster tool is composed of both single-arm and dual-arm cluster tools with a treelike topology. Scheduling such a tool is challenging. For a hybrid treelike multi-cluster tool whose bottleneck individual tool is process-bound, this work aims at finding its optimal one-wafer cyclic schedule. It is modeled with Petri nets such that a onewafer cyclic schedule is parameterized as its robots' waiting time.Based on the model, this work proves the existence of its onewafer cyclic schedule that features with the ease of industrial implementation. Then, computationally efficient algorithms are proposed to find the minimal cycle time and optimal onewafer cyclic schedule. Multi-cluster tool examples are given to illustrate the proposed approach. The use of the found schedules enables industrial multi-cluster tools to operate with their highest productivity.

Computation of an Emptiable Minimal Siphon in a Subclass of Petri Nets Using Mixed-Integer Programming

Deadlock resolution strategies based on siphon control are widely investigated.Their computational efficiency largely depends on siphon computation.Mixed-integer programming(MIP)can be utilized for the computation of an emptiable siphon in a Petri net(PN).Based on it,deadlock resolution strategies can be designed without requiring complete siphon enumeration that has exponential complexity.Due to this reason,various MIP methods are proposed for various subclasses of PNs.This work proposes an innovative MIP method to compute an emptiable minimal siphon(EMS)for a subclass of PNs named S^(4)PR.In particular,many particular structural characteristics of EMS in S4 PR are formalized as constraints,which greatly reduces the solution space.Experimental results show that the proposed MIP method has higher computational efficiency.Furthermore,the proposed method allows one to determine the liveness of an ordinary S^(4)PR.

Detecting Data-flow Errors Based on Petri Nets With Data Operations

In order to guarantee the correctness of business processes, not only control-flow errors but also data-flow errors should be considered. The control-flow errors mainly focus on deadlock, livelock, soundness, and so on. However, there are not too many methods for detecting data-flow errors. This paper defines Petri nets with data operations(PN-DO) that can model the operations on data such as read, write and delete. Based on PN-DO, we define some data-flow errors in this paper. We construct a reachability graph with data operations for each PN-DO, and then propose a method to reduce the reachability graph. Based on the reduced reachability graph, data-flow errors can be detected rapidly. A case study is given to illustrate the effectiveness of our methods.

Hybrid Petri Nets for Modeling and Analysis of Microgrid Systems

Hybrid Petri nets(HPNs) are widely used to describe and analyze various industrial hybrid systems that have both discrete-event and continuous discrete-time behaviors. Recently,many researchers attempt to utilize them to characterize power and energy systems. This work proposes to adopt an HPN to model and analyze a microgrid that consists of green energy sources. A reachability graph for such a model is generated and used to analyze the system properties.

Improved design of online fault diagnoser for partially observed Petri nets with generalized mutual exclusion constraints

This paper investigates the fault detection problem for discrete event systems (DESs) which can be modeled by partially observed Petri nets (POPNs). To overcome the problem of low diagnosability in the POPN online fault diagnoser in current use, an improved online fault diagnosis algorithm that integrates generalized mutual exclusion constraints (GMECs) and integer linear programming (ILP) is proposed. Assume that the POPN structure and its initial markings are known, and the faults are modeled as unobservable transitions. First, the event sequence is observed and recorded. GMEC is used for elementary diagnosis of the system behavior, then the ILP problem of POPN is solved for further diagnosis. Finally, an example of a real DES to test the new fault diagnoser is analyzed. The proposed algorithm increases the diagnosability of the DES remarkably, and the effectiveness of the new algorithm integrating GMEC and ILP is verified.

STOCHASTIC OBJECT-ORIENTED PETRI NETS (SOPNS) AND ITS APPLICATION IN MODELING OF MANUFACTURING SYSTEM RELIABILITY

Object-oriented Petri nets (OPNs) is extended into stochastic object-oriented Petri nets (SOPNs) by associating the OPN of an object with stochastic transitions and introducing stochastic places. The stochastic transition of the SOPNs of a production resources can be used to model its reliability, while the SOPN of a production resource can describe its performance with reliability considered. The SOPN model of a case production system is built to illustrate the relationship between the system's performances and the failures of individual production resources.

RECONFIGURABLE PRODUCTION LINE MODELING AND SCHEDULING USING PETRI NETS AND GENETIC ALGORITHM

In response to the production capacity and functionality variations, a genetic algorithm （GA） embedded with deterministic timed Petri nets（DTPN） for reconfigurable production line（RPL） is proposed to solve its scheduling problem. The basic DTPN modules are presented to model the corresponding variable structures in RPL, and then the scheduling model of the whole RPL is constructed. And in the scheduling algorithm, firing sequences of the Petri nets model are used as chromosomes, thus the selection, crossover, and mutation operator do not deal with the elements in the problem space, but the elements of Petri nets model. Accordingly, all the algorithms for GA operations embedded with Petri nets model are proposed. Moreover, the new weighted single-objective optimization based on reconfiguration cost and E/T is used. The results of a DC motor RPL scheduling suggest that the presented DTPN-GA scheduling algorithm has a significant impact on RPL scheduling, and provide obvious improvements over the conventional scheduling method in practice that meets duedate, minimizes reconfiguration cost, and enhances cost effectivity.

A Reduced Reachability Tree for a Class of Unbounded Petri Nets

As a powerful analysis tool of Petri nets, reachability trees are fundamental for systematically investigating many characteristics such as boundedness, liveness and reversibility.This work proposes a method to generate a reachability tree,called ω RT for short, for a class of unbounded generalized nets called ω-independent nets based on new modified reachability trees(NMRTs). ω RT can effectively decrease the number of nodes by removing duplicate and ω-duplicate nodes in the tree, and verify properties such as reachability, liveness and deadlocks.Two examples are provided to show its superiority over NMRTs in terms of tree size.

Formalization and Verification of Business Process Modeling Based on UML and Petri Nets

In order to provide a quantitative analysis and verification method for activity diagrams based business process modeling, a formal definition of activity diagrams is introduced. And the basic requirements for activity diagrams based business process models are proposed. Furthermore, the standardized transformation technique between business process models and basic Petri nets is presented and the analysis method for the soundness and well-structured properties of business processes is introduced.

Modeling and Simulation of Textile Supply Chain through Colored Petri Nets

The purpose of this paper is to describe the business process modeling and simulation of a textile supply chain using Colored Petri nets. Our model takes into account both the source process and delivery logistics that exist between any two members of supply chain;moreover, we model other activities performed by the company such as manufacturing clothing. The model has been built to acquire a better understanding about the behavior of a textile company in the fulfillment of requests from costumers. The model has been built using CPN Tools. This model was built with modules for activities of the supply chain textile, e.g. receiving orders of customers, determination of production plan, procurement raw material, transportation of raw material, production and delivering products to customers. This modularized model offers some advantages to represent complex supply chains according to their structure and requirements. Thus, we can add modules easily depending on the necessary activities.

Hierarchical Colored Timed Petri Nets for Maintenance Process Modeling of Civil Aircraft

Civil aircraft maintenance process simulation model is an effective method for analyzing the maintainability of a civil aircraft. First, we present the Hierarchical Colored Timed Petri Nets for maintenance process modeling of civil aircraft. Then, we expound a general method of civil aircraft maintenance activities, determine the maintenance level for decomposition, and propose the methods of describing logic of relations between the maintenance activities based on Petri Net. Finally, a time Colored Petri multi-level network modeling and simulation procedures and steps are given with the maintenance example of the landing gear burst tire of a certain type of aircraft. The feasibility of the method is proved by the example.

Serial Failure Diagnosis of a Transmission Line Protection Relaying System by Petri Nets

With the development of large-scale complicated modern power systems, the requirement for the associated protection scheme tends to be more stringent and its combination more complex. However, it is very difficult to figure out the factors of failure of such systems. This paper proposes a Petri net model of a transmission line protection relaying system, including three types of relays as well as an automatic reclosing device, and shows how to diagnose serial failure of the system by analyzing invariant sets of the model. Furthermore, it gives four basic types of failure sequences and its execution is much more intuitive and effective than the traditional method.

Process of Petri Nets Extension

To describe the dynamic semantics for the network computing, the concept on process is presented Based on the semantic model with variable, resource and relation. Accordingly, the formal definition of process and the mapping rules from the specification of Petri nets extension to process are discussed in detail respectively. Based on the collective concepts of process, the specification of dynamic semantics also is constructed as a net system. Finally, to illustrate process intuitively, an example is specified completely.

Method of Dynamic Knowledge Representation and Learning Based on Fuzzy Petri Nets

A method of knowledge representation and learning based on fuzzy Petri nets was designed. In this way the parameters of weights, threshold value and certainty factor in knowledge model can be adjusted dynamically. The advantages of knowledge representation based on production rules and neural networks were integrated into this method. Just as production knowledge representation, this method has clear structure and specific parameters meaning. In addition, it has learning and parallel reasoning ability as neural networks knowledge representation does. The result of simulation shows that the learning algorithm can converge, and the parameters of weights, threshold value and certainty factor can reach the ideal level after training.

Mobile businessprocess modelingusinghigh level Petri nets

This paper aims at providing an effective modeling methods for more and more mobile business applications. First a high level Petri nets method-Xml nets is introduced, which combines the advantage of Petri nets and XML. Petri nets have strict mathematics and intuitionistic diagram ex- pression way, rich system describing means and system behavior analytical technology, and the re- lated powerful supporting tools. XML, as an extensible markup language, is already a information description de facto standard. XML nets could be utilized to model both the controlling flow and the data flow of mobile business process effectively, which consequently enables the analysis and optimi- zation of the mobile business processes and could be utilized to simulate the execution of the mobile business process with the Petri nets tools to improve the system execution efficiency. In this paper, to demonstrate the modeling of the controlling flow and data flow of mobile business process, an in- strument repair business case is modeled with XML nets.

Intuitionistic Fuzzy Petri Nets Model Based on Back Propagation Algorithm for Information Services

Intuitionistic fuzzy Petri net is an important class of Petri nets,which can be used to model the knowledge base system based on intuitionistic fuzzy production rules.In order to solve the problem of poor self-learning ability of intuitionistic fuzzy systems,a new Petri net modeling method is proposed by introducing BP(Error Back Propagation)algorithm in neural networks.By judging whether the transition is ignited by continuous function,the intuitionistic fuzziness of classical BP algorithm is extended to the parameter learning and training,which makes Petri network have stronger generalization ability and adaptive function,and the reasoning result is more accurate and credible,which is useful for information services.Finally,a typical example is given to verify the effectiveness and superiority of the parameter optimization method.