Adaptive time warp simulation of timed Petri nets

Time warp (TW), although generally accepted as a potentially effective parallel and distributed simulation mechanism for timed Petri nets, can reveal deficiencies in certain model domains. Particularly, the unlimited optimism underlying TW can lead to excessive aggressiveness in memory consumption due to saving state histories, and waste of CPU cycles due to over-optimistically progressing simulations that eventually have to be “rolled back”. Furthermore, in TW simulations executing in distributed memory environments, the communication overhead induced by the roll-back mechanism can cause pathological overall simulation performance. In this work, an adaptive optimism control mechanism for TW is developed to overcome these shortcomings. By monitoring and statistically analyzing the arrival processes of synchronization messages, TW simulation progress is probabilistically throttled based on the forecasted time stamp of forthcoming messages. Two classes of arrival process characterizations are studied, reflecting that a natural trade-off exists among the computational and space complexity, and the respective prediction accuracy: While forecasts based on metrics of central tendency are computationally cheap but yield inadequate predictions for correlated arrivals (thus negatively affecting performance), time series based forecast methods give higher prediction accuracy, but at higher computational cost     

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.     

Firing and enabling sequences estimation for timed Petri nets

Petri nets (PNs) are useful tools for the modeling and analysis of discrete event systems. This work deals with the estimation of firing and enabling sequences for timed transition PNs with unknown time delays. The marking and reserved marking of the places are measured online. The estimation problem has exact and approximated solutions that are described. Sufficient conditions are given on the measurement accuracy of the marking and reserved marking vectors, so that the estimation of firing and enabling sequences is an exact one. If the estimation provides several solutions, the PN is extended in order to give a unique solution. Numerical aspects of the estimation are also investigated. As a consequence of this, the proposed method provides interesting tools for the modeling, performance analysis, and above all the monitoring of manufacturing systems and road traffic networks     

Feasibility of piecewise-constant control sequences for timed continuous Petri nets

In this study, the determination of control actions for timed continuous Petri nets is investigated by the characterisation of attractive regions in marking space. In particular, attraction in finite time, which is important for practical issues, is considered. Based on the characterisation of attractive regions, the domain of admissible piecewise constant control actions is computed, and sufficient conditions to verify the feasibility of the control objectives are proposed. As a consequence, an iterative procedure is presented to compute piecewise constant control actions that correspond to local minimum time control for timed continuous Petri nets.     

Observer-based state-feedback control of timed Petri nets with deadlock recovery

This paper discusses the problem of controlling a timed Petri net whose marking cannot be measured but is estimated using an observer. The control objective is that of enforcing a set of generalized mutual exclusion constraints (GMEC) and all transitions are assumed to be controllable. We show that the use of marking estimates may significantly reduce the performance of the closed-loop system and in particular may lead to a deadlock. First, we present a linear algebraic characterization of deadlock markings based on siphon analysis. Second, we show how this characterization may be used to derive a procedure that may be invoked to recover from a controller induced deadlock. Finally, we assume that the timing delays associated to transitions are known and show how this knowledge can be used to improve the marking estimate and to recover the net from partial deadlocks. This procedure is similar to the one used for deadlock recovery and may be invoked whenever a transition has not fired for a time longer than its expected delay.     

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     

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.     

Scheduling analysis of FMS: An unfolding timed Petri nets approach

We are interested in Flexible Manufacturing Systems (FMS) scheduling problem. Different methods have been explored to solve this problem and mainly to master its combinatorial complexity: NP-hard in the general case. This paper presents an analysis of the cyclic scheduling for the determination of the optimal cycle time and the minimization of the Work In Process (WIP). Especially, the product ratio-driven FMS cyclic scheduling problem using timed Petri nets (TPN) unfolding is described. In addition, it has been proved that the Basic Unit of Concurrency (BUC) is a set of the executed control flows based on the behavioral properties of the net. Using our method, one could divide original system into some subnets based on machine's operations using BUC and analyze the feasibility time in each schedule. Herein, our results showed the usefulness of transitive matrix to slice off some subnets from the original net, and explained in an example.     

Modeling and analysis of timed Petri nets using heaps of pieces

The authors show that safe timed Petri nets can be represented by special automata over the (max, +) semiring, which compute the height of heaps of pieces. This extends to the timed case the classical representation a la Mazurkiewicz of the behavior of safe Petri nets by trace monoids and trace languages. For a subclass including all safe free-choice Petri nets, we obtain reduced heap realizations using structural properties of the net (covering by safe state machine components). The authors illustrate the heap-based modeling by the typical case of safe jobshops. For a periodic schedule, the authors obtain a heap-based throughput formula, which is simpler to compute than its traditional timed event graph version, particularly if one is interested in the successive evaluation of a large number of possible schedules     

Optimal stationary behavior for a class of timed continuous Petri nets

In this paper, we consider a deterministic timed continuous Petri net model where conflicts at places are solved by using stationary routing parameters. We show how to compute the stationary firing rate for all transitions via linear programming, so as to determine the optimal routing parameters that maximize user-defined linear functions of the firing rates. Finally, we discuss the relations with discrete Petri nets.     

A concurrency-preserving translation from time Petri nets to networks of timed automata

Several formalisms to model distributed real-time systems coexist in the literature. This naturally induces a need to compare their expressiveness and to translate models from one formalism to another when possible. The first formal comparisons of the expressiveness of these models focused on the preservation of the sequential behavior of the models, using notions like timed language equivalence or timed bisimilarity. They do not consider preservation of concurrency. In this paper we define timed traces as a partial order representation of executions of our models for real-time distributed systems. Timed traces provide an alternative to timed words, and take the distribution of actions into account. We propose a translation between two popular formalisms that describe timed concurrent systems: 1-bounded time Petri nets (TPN) and networks of timed automata (NTA). Our translation preserves the distribution of actions, that is we require that if the TPN represents the product of several components (called processes), then each process should have its counterpart as one timed automaton in the resulting NTA.     

Modeling of reconfigurable manufacturing systems based on colored timed object-oriented Petri nets

To cope with the rapid change in manufacturing market requirements, reconfigurable manufacturing systems (RMSs) with the feature of reconfigurability, have to be developed. A model that describes the reconfiguring process of a manufacturing system is developed by applying colored timed object-oriented Petri nets. Based on the main difference between configurations of RMSs and flexible manufacturing systems (FMSs), a modular hierarchical structure of RMS is developed. By the object-oriented method, all the object classes in the RMS model are identified. A macro-place is used to model the aggregation of many processes and a macro-transition is used to link all the related macro-places. Macro-places and macro-transitions are connected with arcs to form a Petri net named a macro-level Petri net so that the control logic of RMS is represented. The macro-level Petri net is refined by hierarchical steps, each step describing these macro-places by more detailed sub macro-places until all the macro-places cannot be divided. Then the characteristics of material flow and time constraints in RMS are modeled by applying colored tokens and associated time-delay attributes. This model integrates object-oriented methods, stepwise refinement ideas and Petri nets together. The RMS activities can be encapsulated and modularized by the proposed method, so that RMS can be easily constructed and investigated by the system developers.     

Analysis of railway stations by means of interval timed coloured Petri nets

In this paperinterval timed coloured Petri nets ((van der Aalst, 1993)) are used to model and analyse railway stations. We will show that this approach can be used to evaluate both station operating schedules and the infrastructure of a station.An interval timed coloured Petri net (ITCPN) is a coloured Petri net extended with time; time is in tokens and transitions determine a delay for each produced token. This delay is specified by an upper and lower bound, i.e. an interval. The ITCPN model allows for the modelling of the dynamic behaviour of large and complex systems, without loosing the possibility of formal analysis. In addition to the existing analysis techniques for coloured Petri nets, we use a new analysis method to analyse the temporal behaviour of the net. This method constructs a reduced reachability graph and exploits the fact that delays are described by an interval. We will also discuss other (Petri net based) methods that can be used to analyse railway stations.By order of and in co-operation with the Dutch Railway Company (NS), Department of Traffic Development.     

Giving semantics to SA/RT by means of high-level timed Petri nets

In the IPTES project a dual language approach is proposed for overcoming both the problems derived from the use of a user-friendly, high-level, but not-formally-defined language and from a lower-level, formal, but difficult-to-use language. The approach uses a user-friendly, high-level language as user interface and a lower-level, formal language asmachine language. In this way the users can both access the IPTES environment through a nice interface and can profit from non-ambiguity-checks and proofs algorithms based on the formal kernel machine language. The correspondence between the two languages is built-in in the IPTES environment that provides a transparent mapping mechanism that relates the users specifications expressed by means of the high-level interface-language with the formal definitions expressed in the formal machine language.This paper presents the mapping mechanism that relates the current IPTES user interface (SA/RT (Ward and Mellor 1985)) with the IPTES machine language (high-level timed Petri nets (Ghezzi, Mandrioli, Morasca and Pezzé 1991)). As a side effect, it also presents the formal semantics of SA/RT defined by means of high-level timed Petri nets.This material is based upon work supported by the CEC under the ESPRIT program project no. EP5570 IPTES, by the Piano Finalizzato Sistemi Informatici e Calcolo Parallelo (CNR) and by The Technical Development Centre of Finland (TEKES).     

Mapping timed cause-effect structures into timed petri nets

Conclusion The problem of inverse mapping of Petri nets into CES remains an interesting open question. Raczunas [5] claims that it is not for every PN that a strictly equivalent CES exists. He accordingly proposes weak equivalence of this mapping. Kotov [6] defines a topologically structured subclass of PN—regular PN. The subclass of regular PN has the same cardinality as the class of all PN in the sense of behavioral equivalence. It is therefore relevant to compare the class of regular PN with CES. The study was partially financed by the Russian Foundation for Basic Research, grant No. 93-012-986. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 44–54, March–April, 1997.     

Statechartable Petri nets

Petri nets and statecharts can model concurrent systems in a succinct way. While translations from statecharts to Petri nets exist, a well-defined translation from Petri nets to statecharts is lacking. Such a translation should map an input net to a corresponding statechart, having a structure and behaviour similar to that of the input net. Since statecharts can only model a restricted form of concurrency, not every Petri net has a corresponding statechart. We identify a class of Petri nets, called statechartable nets, that can be translated to corresponding statecharts. Statechartable Petri nets are structurally defined using the novel notion of an area. We also define a structural translation that maps each statechartable Petri net to a corresponding statechart. The translation is proven sound and complete for statechartable Petri nets.     

Error-correcting Petri nets

The paper introduces error-correcting Petri nets, an algebraic methodology for designing synthetic biologic systems with monitoring capabilities. Linear error-correcting codes are used to extend the net’s structure in a way that allows for the algebraic detection and correction of non-reachable net markings. The presented methodology is based on modulo-p Hamming codes—which are optimal for the modulo-p correction of single errors—but also works with any other linear error-correcting code.     

Possibilistic Petri nets

This paper presents the possibilistic Petri net model which combines possibility logic with Petri nets with objects. The main feature of this model is to allow one to reason about the aspects of uncertainty and change in dynamic discrete event systems. The paper presents relevant concepts of Petri nets with objects and possibility logic and how imprecision and vagueness are introduced in the marking of a Petri net with objects. The marking of a net is imprecise, or in a more general way, fuzzy, in order to represent an ill-known knowledge about a system state. A new marking updating according to the fuzzy marking such defined is also discussed. An example of shop door monitoring is presented that illustrates our approach.     

Normal Petri nets

A class of Petri nets, called normal Petri nets, is introduced, and it is shown that, for each initial marking, the reachability set of a normal marked Petri net is an effectively computable semilinear set. More generally, we show that the reachability set of a marked Petri net is an effectively computable semilinear set unless the total number of tokens in a minimal circuit is decreased to 0. We also show that a Petri net is normal if and only if it is weakly persistent for each initial marking without token-free circuits.