Open access peer-reviewed chapter

Performance Evaluation of Timed Petri Nets in Dioid Algebra

By Samir Hamaci, Karim Labadi and A. Moumen Darcherif

Submitted: December 1st 2011Reviewed: April 30th 2012Published: August 29th 2012

DOI: 10.5772/48498

Downloaded: 1381

1. Introduction

The theory of Discrete Event Dynamic Systems focuses on the analysis and conduct systems. This class essentially contains man-made systems that consist of a finite number of resources (processors or memories, communication channels, machines) shared by several users (jobs, packets, manufactured objects) which all contribute to the achievement of some common goal (a parallel computation, the end-to-end transmission of a set of packets, the assembly of a product in an automated manufacturing line).

Discrete Event Dynamic Systems can be defined as systems in which state variables change under the occurrence of events. They are usually not be described, like the classical continuous systems, by differential equations due to the nature of the phenomenon involved, including the synchronization phenomenon or mutual exclusion. These systems are often represented by state-transition models. For such systems, arise, among others, three problems: Performance evaluation (estimate the production rate of a manufacturing system), resource optimization (minimizing the cost of some resources in order to achieve a given rate of production). To deal with such problems, it is necessary to benefit of models able to take into account all dynamic characteristics of these systems. However, the phenomena involved by Discrete Event Dynamic Systems, and responsible for their dynamics, are much and of diverse natures: sequential or simultaneous, delayed tasks or not, synchronized or rival. From this variety of phenomena results the incapacity to describe all Discrete Event Dynamic Systems by a unique model which is faithful at once to the reality and exploitable mathematically.

The study of Discrete Event Dynamic Systems is made through several theories among which we can remind for example the queuing theory, for the evaluation of performances of timed systems, or the theory of the languages and the automatons, for the control of other systems. The work presented here is in line with theory of linear systems on dioids. This theory involves subclass of Timed Discrete Event Dynamic Systems where the evolution of the state is representable by linear recurrence equations on special algebraic structures called diod algebra. The behavior of systems characterized by delays and synchronization can be described by such recurrences [1]. These systems are modeled by Timed Event Graphs (TEG). This latter constitute a subclasses of Timed Petri Nets with each place admits an upstream transition and downstream transition. When the size of model becomes very significant, the techniques of analysis developed for TEG reach their limits. A possible alternative consists in using Timed Event Graphs with Multipliers denoted TEGM. Indeed, the use of multipliers associated with arcs is natural to model a large number of systems, for example, when the achievement of a specific task requires several units of a same resource, or when an assembly operation requires several units of a same part.

This chapter deals with the performance evaluation of TEGM in dioid algebra. Noting that these models do not admit a linear representation in dioid algebra. This nonlinearity is due to the presence of weights on arcs. To mitigate this problem of nonlinearity and to apply the results used to evaluate the performances of linear systems, we use a linearization method of mathematical model reflecting the behavior of a Timed Event Graphs with Multipliers in order to obtain a linear model.

Few works deal with the performance evaluation of TEGM. Moreover, the calculation of cycle time is an open problem for the scientific community. In the case where the system is modeled by a TEGM, in the most of works the proposed solution is to transform the TEGM into an ordinary TEG, which allows the use of well-known methods of performances evaluation. In [12] the initial TEGM is the object of an operation of expansion. Unfortunately, this expansion can lead to a model of significant size, which does not depend only on the initial structure of TEGM, but also on initial marking. With this method, the system transformation proposed under singleserver semantics hypothesis, or in [14] under infiniteserver semantics hypothesis, leads to a TEG with |θ|transitions.

Another linearization method was proposed in [17] when each elementary circuit of graph contains at least one normalizedtransition ( i.e.,a transition for which its corresponding elementary T-invariant component is equal to one). This method increases the number of transitions. Inspired by this work, a linearization method without increasing the number of transition was proposed in [8]. A calculation method of cycle time of a TEGM is proposed in [2] but under restrictive conditions on initial marking. We use a new method of linearization without increasing the number of transition of TEGM [6].

This chapter is organized as follows. After recalling in Section 2 some properties of Petri nets, we present in Section 3, modeling the dynamic behavior of TEGM, which are a class of Petri nets, in dioid algebra, precisely in (min,+) algebra. In this section we will show that TEGM are nonlinear in this algebraic structure, unlike to TEG. This nonlinearity prevents us to use the spectral theory developed in [5] for evaluate the performances of TEG in (min,+) algebra. To mitigate this problem of nonlinearity, we will encode the mathematical equations governing the dynamic evolution of TEGM in a dioid of operators developed in [7], inspired by work presented in [3]. The description of this dioid and the new state model based on operators will be the subject of Section 4. To exploit the mathematical model obtained, a linearization method of this model will be presented in Section 5, in order to obtain a linear model in (min,+) algebra and to apply the theory developed for performance evaluation. This latter will be the subject of Section 6. Before concluding, w e give a short example to illustrate this approach for evaluate the performances of TEGM in dioid algebra.


2. Petri Net

2.1. Definitions and notations

Petri Nets (PN) are a graphical and mathematical tool, introduced in 1962 by Carl Adam Petri [15]. They allow the modeling of a large number of Discrete Event Dynamic Systems. They are particularly adapted to the study of complex processes involving properties of synchronization and resource sharing.

The behavior over time of dynamical systems, including evaluation of their performance (cycle time,...), led to introduce the notion of time in models Petri Net. Several models Petri Net incorporating time have been proposed. These models can be grouped into two classes: deterministic models and stochastic models. The former consider the deterministic values for durations of activity, whereas the latter consider probabilistic values.Among the existing Timed Petri Net include: the Temporal Petri Net [11] associating a time interval to each transition and each place, the T-Timed Petri Net [4] associating a positive constant (called firing time of transition) at each transition and P-Timed Petri Net ; [4], [5] associating a positive constant (called holding time in the place) at each place of graph. It has been shown that P-Timed Petri Net can be reduced to T-Timed Petri Net and vice versa [13]. In the next, for consistency with the literature produced on the dioid algebra, we consider that P-Timed Petri Net.

A P-Timed Petri Netis a valued bipartite graph given by a 5-tuple(P,T,M,m,τ).

  1. PT
  2. MP×TT×PpPqT,MpqMqpnqppnq
  3. mP:mpp
  4. τP:τpp

Figure 1.

Example of a P-Timed Petri Net.

More generally, for a Petri Net, we denote W=[Mqp](input incidence matrix), W+=[Mpq](output incidence matrix), W=W+W(incidence matrix) and considering Sa possible firing sequence from a marking mito the markingmk, then a fundamental equation reflecting the dynamic behavior of Petri Net, is obtained:

(1)S_is the characteristic vector of the firing sequenceS. In Figure 1, the firing sequenceS={n2}, the characteristic vector is equal toS_t=(0,1,0,0), and from markingm0t=(0,3,0,0,3,0), is reached the marking m1t=(0,0,0,3,0,0)by firing of the transitionn2, after a stay of 2 time units of tokens in the places P2andP5.

2.2. Invariants of a Petri Net

There are two types of invariants in a Petri Net; Marking Invariants, also called P-invariant and Firing Invariant, also called T-invariant [4].

Definition 1 (P-invariant)

Marking Invariants illustrate the conservation of the number of tokens in a subset of places of a Petri Net.

A vector, denoted Y, which has a dimension equal to the number of places of a Petri Net is a P-invariant, if and only if it satisfies the following equation:


From Equation 1, we deduce that if Yis a P-invariant, then for a given marking, denotedmi, obtained from an initial markingm0, we have:


This equation represents an invariant marking, it means that if Y is a P-invariant of Petri Net then the transpose of the vector Y multiplied by the marking vector miof the Petri Net is an integer constant regardless of the mimarking reachable from the initial markingm0. All the places for which the associated component in the P-invariant is nonzero, is called the conservative component of the Petri Net.

Definition 2 (T-invariant)

A nonzero vector of integers θof dimension |T|×1is a T-invariant of Petri Net if and only if it satisfies the following equation:


From Equation 1, the evolution from a marking mito a sequence whose characteristic vector θback the graph to same markingmk=mi. The set of transitions for which the associated component in the T-invariant is nonzero is called the support of T-invariant. A T-invariant corresponding to a firing sequence is called feasible repetitive component.

Definition 3 (Consistent Petri Net)

A Petri Net is said consistentif it has a T-invariant θcovering all transitions of graph. A Petri Net which has this property is said repetitive.

The graph reaches a periodic regime when there is a firing sequence achievable with θas characteristic vector.

Definition 4 (Conservative Petri Net)

A Petri Net is said conservative if all places in the graph form a conservative component.

The Petri Nets considered here are consistent( i.e.,there exists a T-invariant θcovering all transitions:{qT|θ(q)>0}=T) and conservative( i.e.,there exists a P-invariant Ycovering all places:{pP|Y(p)>0}=P). Such graphs verify the next properties [13]:

  • A PNPetri Net allows a live and bounded initial marking miffit is consistent and conservative.

  • A consistent Petri Net is strongly connected iffit is conservative.

  • A consistent Petri Net has a unique elementary T-invariant.

  • The product of multipliers along any circuit of a conservative Petri Net is equal to one.

In the next, we denote by q(resp.q) the set of places upstream (resp. downstream) transition q.Similarly, p(resp.p) denotes the set of transitions upstream (resp. downstream) place p.

3. Dynamic behavior of Timed Petri Nets in dioid algebra

Definition 5 An ordinary Timed Event Graph(TEG) is a Timed Petri Net such that each place has exactly one upstream transition and one downstream transition. Weights of arcs are all unit.

These graphs are well adapted to model synchronization phenomena occurring in Discrete Event Dynamic Systems. They admit a linear representation on a particular algebraic structure called the dioidalgebra [1].

Definition 6 A dioid(D,,) is a semiring in which the addition is idempotent (a,aa=a). Neutral elements of and are denoted εand e respectively.
  • A dioid is commutativewhen is commutative. The symbol is often omitted. Due to idempotency of ,a dioid can be endowed with a natural order relation defined by abb=ab(the least upper bound of {a,b} is equal toab).

  • A dioid Dis completeif every subset Aof Dadmits a least upper bound denotedxAx, and if distributes at left and at right over infinite sums. The greatest element denoted Tof a complete dioid Dis equal toxxD. The greatest lower bound of every subset Xof a complete dioid always exists and is denoted xXx.

Example 1 The set{±}, endowed with (min) as and usual addition as, is a complete dioid denoted ¯minand usually called (min,+) algebra with neutral elements ε=+,e=0andT=. Example 2 The set{±}, endowed with (max) as and usual addition as, is a complete dioid denoted ¯maxand usually called (max,+) algebra with neutral elements ε=,e=0andT=+. Definition 7 A signalis an increasing map from to{±}. Denote S=({±})the set of signals.

This set is endowed with a kind of module structure, called min-plus semimodule, the two associated operations are:

  • pointwise minimum of time functions to add signals:t,(xy)(t)=x(t)y(t)=min(x(t),y(t));

  • addition of a constant to play the role of external product of a signal by a scalar:t,ρ{±},(ρ.x)(t)=ρx(t)=ρ+x(t).

Definition 8 An operator Ψis a mapping defined from {±}to {±}is linear in (min,+) algebra if it preserves the min-plus semimodule structure, i.e., for all signals x, y and constantρ,

To study a TEG in (min,+) algebra, considered state variable is a counter,denotedxq(t). This latter denotes the cumulated number of firings of transition xqup to time t(t). To illustrate the evolution of a counter associated with the transition xqof a TEG, we consider the following elementary graph:

Figure 2.

Elementary TEG


Note that this equation is nonlinear in usual algebra. This nonlinearity is due to the presence of the (min) which models the synchronization phenomena

Synchronization phenomena occurs when multiple arcs converge to the same transition.

in the transitionxq. However, it is linear equation in (min,+) algebra:


In the case where weight of an arc is greater than one, TEG becomes weighted. This type of model is called Timed Event Graph with Multipliers, denoted TEGM.

Figure 3.

Elementary TEGM.

The earliestfunctioning rule of a TEGM is defined as follows. A transition nqfires as soon as all its upstream places {pq}contain enough tokens (Mqp) having spent at least τpunits of time in place p.When transition nqfires, it produces Mpqtokens in each downstream placepq.

Assertion 1 The counter variable associated with the transition nqof an elementary TEGM (under the earliest firing rule) satisfy the following transition to transitionequation:

The inferior integer part is used to preserve the integrity of Equation 7. In general, a transition nqmay have several upstream transitions {nqq}which implies that the associated counter variable is given by the minof transition to transitionequations obtained for each upstream transition.

Example 3 Let us consider TEGM depicted in Figure 3.

Figure 4.

Timed Event Graph with Multipliers.

The mathematical model representing the behavior of this TEGM does not admit a linear representation in (min,+) algebra. This nonlinearity is due to the presence of the integer parts generated by the presence of the weights on the arcs. Consequently, it is difficult to use (min,+) algebra to tackle, for example, problems of control and the analysis of performances. As alternative, we propose another model based on operators which will be linearized in order to obtain a (min,+) linear model.

4. Operatorial representation of TEGM

We now introduce three operators, defined from {±}to{±}, which are used for the modeling of TEGM.

 Operator γνto represent a shift of νunits in counting (ν{±}). It is defined as follows:
Property 1 Operator γνsatisfies the following rules:

Indeed, we have

  • (γνγν)nq(t)=min(nq(t)+ν,nq(t)+ν)=nq(t)+min(ν,ν)=γmin(ν,ν)nq(t)E14
  • (γνγν)nq(t)=γν(nq(t)+ν)=nq(t)+ν+ν=γν+νnq(t)E15

Figure 5.


 Operator δτto represent a shift of τunits in dating (τ{±}). It is defined as follows:
Property 2 Operator δτsatisfies the following rules:
  • Knowing that the signal nq(t)is non decreasing, we have :


Figure 6.


 Operator μrto represent a scaling of factor r(r+). It is defined as follows:

with r+(ris equal to a ratio of elements in).

Property 3 Operator μrsatisfies the following rules when composed with operators δτand γν:

Indeed, we have:

  • (μrδτ)n(t)=r×n(tτ)=(δτμr)n(t).E26
  • νr1×,(μrγν)n(t)=r×ν+r×n(t)=r×ν+r×n(t)=(γν×rμr)n(t)

Figure 7.


Denote by Dminthe (noncommutative) dioid of finite sums of operators {μr,γν}endowed with pointwise min()and composition ()operations, with neutral elements equal to ε=μ+γ+and e=μ1γ0respectively. Thus, an element in Dminis a map p=i=1kμriγνidefined from Sto Ssuch that t,p(n(t))=min1ik(ri(νi+n(t))).

Let a maph:Dmin, τh(τ)in which h(τ)=kτi=1μriτγνiτ.We define the power series H(δ)in the indeterminate δwith coefficients in Dminby: H(δ)=τh(τ)δτ.

The set of these formal power series endowed with the two following operations:


is a dioid denotedDmin[[δ]], with neutral elements ε=μ+γ+δande=μ1γ0δ0.

Elements of Dmin[[δ]]allow modeling the transfer between two transitions of a TEGM. A formal series of Dmin[[δ]]can also represent a signal nasN(δ)=τn(τ)δτ, simply due to the fact that it is also equal to ne(by definition of neutral element eofDmin).

Assertion 2 The counter variables of an elementary TEGM satisfies the following equation in dioidDmin[[δ]]:
(8)Nq(δ)is the counter nq(t)associated with the transitionnq, encoded inDmin[[δ]]. It is equal to the counter Nq(δ)shifted by the composition of operators μMpq,δτp,γmpand μMqp1connected in series. Let us express some properties of operators γ,δ,μin dioidDmin[[δ]].Proposition 1 Let a,b,we have:
  1. γaδb=δbγaμaδb=δbμa
  2. μa1μb=μ(a1b)E32
  3. N(δ)t,n(t)aμa1γbN(δ)=γa1bμa1N(δ)
  4. γbμa=μaγa1bμaγb=γabμa


  • Point 1 is obvious.

  • Point 2: μa1μbN(δ)corresponds to a1bn(t)=a1bn(t)which leads toμ(a1b)N(δ).

  • Point 3: μa1γbN(δ)correspond to a1(b+n(t))=a1b+a1n(t)since n(t){±}is a multiple of a, which leads toγa1bμa1N(δ).

  • Point 4: γbμaN(δ)corresponds to b+an(t)=a(a1b+n(t))which leads to μaγa1bN(δ).

Example 4 The TEGM depicted in Figure 3 admits the following representation inDmin[[δ]]:

5. Linearization of TEGM

The presence of integer part modeled by operator μinduces a nonlinearity in Equation 8 used to represent a TEGM. So, as far as possible, we seek to represent a TEGM with linear equations in order to apply standard results of linear system theory developed in the dioid setting, which leads to transform a TEGM into a TEG (represented without operatorμ).

5.1. Principle of linearization

A consistent TEGM has a unique elementary T-invariant in which components are in *.The used method is based on the use of commutation rules of operators and the impulse inputs (Proposition 1 and 2).

In the next, we suppose that all tokens in a TEGM are "frozen" before time 0 and are available at time 0which is a classical assumption in Petri Nets theory. Hence, with each counter variable of a TEGM is added a counter variable corresponding to an impulse input e( i.e.,e(t)=0for t<0and e(t)=+fort0). These initial conditions are weakly compatible. For more details, see [10].

To linearize the expression of counters variables written as Equation 8, one expresses each counter according to an entry impulse. This latter will permit to linearize the mathematical model reflecting the behavior of a TEGM in order to obtain a linear model in (min, +) algebra.

Figure 8.

Impulse (Point of view of counter).

Proposition 2 let Ean impulse input, we have : a,βQ+,
(9)Proof: Thanks to Proposition 1.3, μβγaδτE(δ)corresponds to β×(a+e(tτ))=β×a+e(tτ)since fort0e(t)+, hence e(t)is a multiple ofβ, which leads toγβaδτE(δ).

We now give the state model associated to the dynamic of counters of a TEGM. Consider the vector Ncomposed of the counter variable. The counter variables corresponding to impulse input eadded with each transitionni:


Knowing that such equation admits the following earliest solution:

.Proposition 3 For initial conditions weakly compatible, consistent and conservative TEGM is linearizable without increasing the number of its transitions. Proof: Consider a consistent and conservative TEGM represented by the equationA(δ)=AN(δ)E(δ). Using Equation 11, and then apply the Proposition 2, we obtain a linear equation between transitions of graph (corresponding to a linear TEG). This linearization method may be applied to all transitions of graph, since for any transition, one can involve an impulse input. Example 5 The TEGM depicted in Figure 5 admits the elementary T-invariantθt=(3,2,1).

Figure 9.

TEGM with impulse inputs added to each transition.

The inputs ecorrespond to the impulse inputs. They have not influence on the evolution of the model. Indeed, t0, nqT, min(nq(t),e(t))=nq(t), since e(t)+.


Using Equation 11,N(δ)=A*E(δ). The Proposition 2 allows to calculateA*E(δ):


which is the earliest solution of the following equations:


Let us express these equations in usual counter setting (dioid¯min), we have,t:


These equations are quite (min,+) linear. It turns out that the TEG depicted in Figure 9, composed of three elementary circuits:(n1,n1), (n2,n2), (n3,n3), is a possible representation of the previous equations.

Figure 10.

TEG (Linearized TEGM).


6. Performance evaluation of TEGM

General case: To evaluate the performance of a TEGM returns to calculate the cycle time and firing rate associated with each transition of a graph.Definition 9 [16] The cycle time, TCm, of a TEGM is the average time to fire once the T-invariant under the earliest firing rule (i.e., transitions are fired as soon as possible) from the initial marking.

This cycle time is equivalent to the average time between two successive firing of a transition. It is calculated by the following relation:

(12)θqis the component of T-invariant associated with transitionnq, and λmqis the firing rate associated with transition nqof TEGM corresponding to the average number of firing of one transition per unit time.For an industrial system, the cycle time corresponds to the average manufacturing time of a piece, and the firing rate is the average number of pieces produced per unit of time.Particular case: Elements of performance evaluation for TEG. We recall main results characterizing an ordinary TEG modeled in the dioidmin. Knowing that a TEG is a TEGM with unit weights on the arcs, and their components of T-invariant are all equals 1.Definition 10 A matrix Ais said irreducibleif for any pair (i,j), there is an integer msuch that(Am)ijε. Theorem 1 [5] Let Abe a square matrix with coefficient inmin. The following assertions are equivalent:
  • Matrix Ais irreducible,

  • The TEG associated with matrix Ais strongly connected.

One calls eigenvalueand eigenvectorof a matrix Awith coefficients inmin, the scalar λand the vector υsuch as:

Theorem 2 [5] Let Abe a square matrix with coefficients inmin. If Ais irreducible, or equivalently, if the associated TEG is strongly connected, then there is a single eigenvalue denotedλ. The eigenvalue can be calculated in the following way:
(13)λcorresponds to the firing rate which is identical for each transition. This eigenvalue λcan be directly deduced from the TEG by:
  • C is the set of elementary circuits of the TEG.

  • T(c) is the sum of holding times in circuitc.

  • M(c) is the number of tokens in circuitc.

In the case of Ordinary TEG strongly connected, The inverse of eigenvalue λis equivalent to cycle time, denoted TC.

(15)Example 6 The TEG depicted in Figure 9, which is not strongly connected, is composed of three circuits : (n1,n1), (n2,n2) and (n3,n3). Each circuit admits a T-invariant composed of one component equals 1.

Using the Definition 9 and Equation ??, one deduce that each circuit, which is an elementary TEG strongly connected, admits the following cycle time:

  • Circuit (n1,n1),TC=43.

  • Circuit (n2,n2),TC=21.

  • Circuit (n3,n3),TC=41.

The cycle time of TEGM depicted in Figure 3, corresponds to the time required to fire each transition a number of times equal its corresponding elementary T-invariant component. Hence


Note that the cycle time is identical for all transitions of the graph which is equal to 4 time units. This means that each transition is asymptotically fired once every four time units.

About the firing rate associated with each transition of the graph, using the relation (12):


Confirmation of these results can be deducted directly to the following marking graph of the initial TEGM.

Figure 11.

Marking graph of the initial TEGM.

  • kni/tnik

7. Conclusion

Performance evaluation of TEGM is the subject of this chapter. These graphs, in contrast to ordinary TEG, do not admit a linear representation in (min,+) algebra. This nonlinearity is due to the presence of weights on the arcs. For that, a modeling of these graphs in an algebraic structure, based on operators, is used. The obtained model is linearized, by using of pulse inputs associated with all transitions of graphs, in order to obtain representation in linear (min+)algebra, and apply some results basic spectral theory, usually used to evaluate the performance of ordinary TEG. The work presented in this chapter paves the way for other development related to evaluation of performance of these models. In particular, the calculation of cycle time for any timed event graph with multipliers is, to our knowledge, an open problem to date.


  • Synchronization phenomena occurs when multiple arcs converge to the same transition.

© 2012 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

How to cite and reference

Link to this chapter Copy to clipboard

Cite this chapter Copy to clipboard

Samir Hamaci, Karim Labadi and A. Moumen Darcherif (August 29th 2012). Performance Evaluation of Timed Petri Nets in Dioid Algebra, Petri Nets - Manufacturing and Computer Science, Pawel Pawlewski, IntechOpen, DOI: 10.5772/48498. Available from:

chapter statistics

1381total chapter downloads

More statistics for editors and authors

Login to your personal dashboard for more detailed statistics on your publications.

Access personal reporting

Related Content

This Book

Next chapter

Reachability Criterion with Sufficient Test Space for Ordinary Petri Net

By Gi Bum Lee, Han Zandong and Jin S. Lee

Related Book

First chapter

An Application of GSPN for Modeling and Evaluating Local Area Computer Networks

By Masahiro Tsunoyama and Hiroei Imai

We are IntechOpen, the world's leading publisher of Open Access books. Built by scientists, for scientists. Our readership spans scientists, professors, researchers, librarians, and students, as well as business professionals. We share our knowledge and peer-reveiwed research papers with libraries, scientific and engineering societies, and also work with corporate R&D departments and government entities.

More About Us