Ageing notions in the analysis of stochastic Petri nets

• Alterungseigenschaften in der Analyse stochastischer Petri-Netze

Alexin, Johann; Kamps, Udo (Thesis advisor)

Aachen : Publikationsserver der RWTH Aachen University (2013)
Dissertation / PhD Thesis

Aachen, Techn. Hochsch., Diss., 2012

Abstract

The present thesis introduces a method for analyzing stochastic Petri nets with arbitrarily distributed firing times. This method refers to aging properties of a stochastic Petri net. Stochastic aging properties are qualitative properties of a distribution function. A Petri net is an extended directed bipartite graph and consists of two sets P and T. The first set P contains places, which model local states of a system. The second set T consists of transitions, which model events in a system. The extension of the bipartite graph is realized by tokens, which are allocated in places. The allocation of places by tokens is denoted as a marking and it represents the global state of a Petri net. The firing of an enabled transition in a marking causes a marking change of a Petri net. The marking of a Petri net, which is given before any transition fires, is called the initial marking. If each marking of a Petri net occurs at most once, then this net is called as acyclic Petri net. In this thesis only acyclic Petri nets are considered. There always exist some reachable markings of an acyclic Petri net, where no transition is enabled. These markings are called absorbing. In all remaining markings at least one transition is enabled. A transition is enabled if each input place of this transition contains at least as many tokens as the number of directed arcs between the input place and the transition. The extension of classical Petri nets with timed transitions which firing times are random, forms Stochastic Petri nets. The random firing delays are modeled by stochastically independent, non-negative random variables and these variables are called firing times. Acyclic stochastic Petri nets containing m source places and n sink places are denoted as (m,n)-nets. A place is called a source place, if it is not an output place of any transition. Similarly, a place is a sink place, if it is not an input place of any transition. Since there exists an absorbing marking of an (m,n)-net, the random time between the initial marking and an absorbing marking can be characterized by a random variable. This random time is called the total time of an (m,n)-net. The total time of an (m,n)-net can be modeled as a function of firing times of all transitions. This function characterizes the structure of an (m,n)-net. Based on the aging properties of the distribution functions of firing times, qualitative analysis refers to aging properties of the distribution function of the total time. The determination of the total time distribution function of a large (m,n)-net can be extremely difficult. Using small (m,n)-nets, analyzable large nets can be constructed in a modular way. For the modular approach some building blocks are defined. Building blocks are minimal (m,n)-nets that model certain activities. The total times of building blocks are determined and the inheritance of the aging properties from the transition level up to the building block level is examined. After investigating the qualitative properties of the building blocks, some connection mechanisms are introduced. These mechanisms allow a formation of larger nets, using the building blocks. To introduce these connection mechanisms systematically, modifications of building blocks are introduced. The structure of these modified building blocks differs slightly from the original one, but this structural difference does not influence the total time. Such modifications of building blocks become possible by allowing immediate transitions. There are two connection mechanisms introduced - the connection by substitution and the connection by expansion. The connection of two building blocks by substitution is defined as a substitution of one timed transition in the first building block by the second building block. The connection of two building blocks by expansion means substituting one place in the first building block by the second building block. For some building blocks, the connection by expansion can be characterized by multiple substitutions. For others it is necessary to introduce auxiliary (m,n)-nets, in order to define this connection consistently. This connection mechanisms also allow for the connection of a building block with a suitable (m,n)-net, such that a step-by-step construction of larger nets becomes possible. Furthermore the inheritance of ageing properties from the building block level to the newly constructed (m,n)-net level is examined. Depending on the structure of the connected building blocks, some aging properties of the whole structure remain the same, and others become weaker or get lost. Finally, by connecting the building blocks, a class of (m,n)-nets originates, whose aging properties can be easily determined. The total time distribution function of an (m,n)-net outside this class requires a more detailed analysis.

Institutions

• Department of Mathematics [110000]
• Chair of Statistics [116410]