Open access

Performance Evaluation of Timed Petri Nets in Dioid Algebra

Written By

Samir Hamaci, Karim Labadi and A. Moumen Darcherif

Submitted: 01 December 2011 Published: 29 August 2012

DOI: 10.5772/48498

From the Edited Volume

Petri Nets - Manufacturing and Computer Science

Edited by Pawel Pawlewski

Chapter metrics overview

1,864 Chapter Downloads

View Full Metrics

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 single server semantics hypothesis, or in [14] under infinite server 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 normalized transition ( 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.

Advertisement

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 Net is 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 S a possible firing sequence from a marking mi to the markingmk, then a fundamental equation reflecting the dynamic behavior of Petri Net, is obtained:

mk=mi+W×S_.E1
(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 P2 andP5.

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:

Yt×W=0,Y0.E2
(2)

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

Yt×mi=Yt×m0=k,k.E3
(3)

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 mi of the Petri Net is an integer constant regardless of the mi marking 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|×1 is a T-invariant of Petri Net if and only if it satisfies the following equation:

W×θ=0.E4
(4)

From Equation 1, the evolution from a marking mi to 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 consistent if 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 Y covering all places:{pP|Y(p)>0}=P). Such graphs verify the next properties [13]:

  • A PNPetri Net allows a live and bounded initial marking m iff it is consistent and conservative.

  • A consistent Petri Net is strongly connected iff it 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.

Advertisement

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 dioid algebra [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 commutative when 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 D is complete if every subset A of D admits a least upper bound denotedxAx, and if distributes at left and at right over infinite sums. The greatest element denoted T of a complete dioid D is equal toxxD. The greatest lower bound of every subset X of 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 ¯min and usually called (min,+) algebra with neutral elements ε=+,e=0 andT=. Example 2 The set{±}, endowed with (max) as and usual addition as, is a complete dioid denoted ¯max and usually called (max,+) algebra with neutral elements ε=,e=0 andT=+. Definition 7 A signal is 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ρ,
Ψ(xy)=Ψ(x)Ψ(y)(additiveproperty),E5
Ψ(ρx)=ρΨ(x)(homogeneityproperty).E6

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 xq up to time t (t). To illustrate the evolution of a counter associated with the transition xq of a TEG, we consider the following elementary graph:

Figure 2.

Elementary TEG

xq(t)=minpq,qp(mp+xq(tτp)).E7
(5)

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:

xq(t)=pq,qp(mpxq(tτp)).E8
(6)

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 earliest functioning rule of a TEGM is defined as follows. A transition nq fires as soon as all its upstream places {pq} contain enough tokens (Mqp) having spent at least τp units of time in place p. When transition nq fires, it produces Mpq tokens in each downstream placepq.

Assertion 1 The counter variable associated with the transition nq of an elementary TEGM (under the earliest firing rule) satisfy the following transition to transition equation:
nq(t)=minpq,qpMqp1(mp+Mpqnq(tτp)).E9
(7)

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

Example 3 Let us consider TEGM depicted in Figure 3.
(n1(t)=4+3n2(t1)2,n2(t)=min(2n1(t1)3,2+2n3(t1)),n3(t)=n2(t1)2.E10

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.

Advertisement

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:
t,nq¯,nq(t)=γνnq(t)=nq(t)+ν.E11
Property 1 Operator γν satisfies the following rules:
(γνγν)nq(t)=γmin(ν,ν)nq(t).E12
(γνγν)nq(t)=γν+νnq(t).E13

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 γν

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

(δτδτ)nq(t)=min(nq(tτ),nq(tτ))=nq(tmax(τ,τ))=δmax(τ,τ)nq(t).E20
(δτδτ)nq(t)=δτnq(tτ)=nq(tττ)=δτ+τnq(t).E21

Figure 6.

Operator δτ

 Operator μr to represent a scaling of factor r (r+). It is defined as follows:
t,nq¯,nq(t)=μrnq(t)=r×nq(t),E23

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

Property 3 Operator μr satisfies the following rules when composed with operators δτ and γν :
(μrδτ)n(t)=(δτμr)n(t),E24
(μrγν)n(t)=(γν×rμr)n(t),forνr1×.E25

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)
    ν×r.E27

Figure 7.

Operator μr(r=ab)

Denote by Dmin the (noncommutative) dioid of finite sums of operators {μr,γν} endowed with pointwise min () and composition () operations, with neutral elements equal to ε=μ+γ+ and e=μ1γ0 respectively. Thus, an element in Dmin is a map p=i=1kμriγνi defined from S to S such 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 Dmin by: H(δ)=τh(τ)δτ.

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

F(δ)H(δ):
(fh)(τ)=f(τ)h(τ)=min(f(τ),h(τ)),E29
F(δ)H(δ):
(fh)(τ)=if(i)h(τi)=infi(f(i)+h(τi)),E30

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 n asN(δ)=τn(τ)δτ, simply due to the fact that it is also equal to ne (by definition of neutral element e ofDmin).

Assertion 2 The counter variables of an elementary TEGM satisfies the following equation in dioidDmin[[δ]]:
Nq(δ)=pq,qpμMqp1γmpδτpμMpqNq(δ)E31
(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,γmp and μMqp1 connected 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

Proof:

  • 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[[δ]]:
(N1N2N3)=(εμ1/2γ4δ1μ3εμ1/3δ1μ2εγ2δ1μ2εμ1/2δ1ε)(N1N2N3)E33
Advertisement

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 0 which 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<0 and 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 E an impulse input, we have : a,βQ+,
μβγaδτE(δ)=γβaδτE(δ).E34
(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 N composed of the counter variable. The counter variables corresponding to impulse input e added with each transitionni:

N(δ)=AN(δ)E(δ).E35
(10)

Knowing that such equation admits the following earliest solution:

N(δ)=A*E(δ),E36
(11)
A*=eAA2E37
.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 e correspond 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)+.

(N1N2N3)=(εμ1/2γ4δ1μ3εμ1/3δ1μ2εγ2δ1μ2εμ1/2δ1ε)(N1N2N3)(EEE).E38

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

A*E(δ)=(eAA2A3...)E(δ)=(E(δ)AE(δ)AAE(δ)A2E(δ)AA2E(δ)A3E(δ)...).A*E(δ)=((γ2δ2)(γ3δ4)*δ1(γ1δ2)*δ4(γ1δ4)*)E(δ),E39

which is the earliest solution of the following equations:

(N1(δ)N2(δ)N3(δ))=(γ3δ4γ1δ2γ1δ4)(N1(δ)N2(δ)N3(δ))(γ2δ2δ1δ4)E(δ).E40

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

(n1(t)=3n1(t4)2e(t2),n2(t)=1n2(t2)e(t1),n3(t)=1n3(t4)e(t4).E41

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).

Advertisement

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:

TCm=θqλmq.E42
(12)θq is the component of T-invariant associated with transitionnq, and λmq is the firing rate associated with transition nq of 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 A is said irreducible if for any pair (i,j), there is an integer m such that(Am)ijε. Theorem 1 [5] Let A be a square matrix with coefficient inmin. The following assertions are equivalent:
  • Matrix A is irreducible,

  • The TEG associated with matrix A is strongly connected.

One calls eigenvalue and eigenvector of a matrix A with coefficients inmin, the scalar λ and the vector υ such as:

Aυ=λυ.E43
Theorem 2 [5] Let A be a square matrix with coefficients inmin. If A is 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:
λ=nj=1(ni=1(Aj)ii)1j.E44
(13)λcorresponds to the firing rate which is identical for each transition. This eigenvalue λ can be directly deduced from the TEG by:
λ=mincCM(c)T(c),E45
(14)
  • 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.

TC=1λ,E46
(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

1.5mmTC1=3×43,TC2=2×21,TC3=1×41.E47

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):

λm1=34,λm2=12,λm3=14.E48

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
Advertisement

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.

References

  1. 1. BaccelliF.CohenG.OlsderG.J.QuadratJ.P.1992Synchronization and Linearity: An Algebra for Discrete Event Systems,Wiley and Sons.
  2. 2. ChaoD.ZhouM.WangD.1993Multiple weighted marked graphs, IFAC 12th Triennial World Congress, Sydney, Australie, 371374
  3. 3. CohenG.GaubertS.QuadratJ.P.1998Timed-event graphs with multipliers and homogenous min-plus systems, IEEE Transaction on Automatic Control 9
  4. 4. DavidR.AllaH.1992Du Grafcet au réseaux de Petri, Editions Hermès, Paris.
  5. 5. GaubertS.1995Resource optimization and (min,+) spectral theory, IEEE Transaction on Automatic Control 401119311934
  6. 6. HamaciS.BenfekirA.BoimondJ.L.2011Dioid approach for performance evaluation of weighted t-systems, 16th IEEE International Conference on Emerging Technologies and Factory Automation (ETFA), Toulouse, France, 18
  7. 7. HamaciS.BoimondJ.L.LahayeS.2006On modeling and control of hybrid timed event graphs with multipiers using (min,+) algebra, Journal of Discrete Event Dynamic Systems 2
  8. 8. HamaciS.BoimondJ.L.LahayeS.MostefaouiM.2004On the linearizability of discrete timed event graphs with multipliers using (min,+) algebra, 7th international Workshop on Discrete Event Systems (WODES), Reims, France, 367372
  9. 9. HillionH.1989Modélisation et analyse des systèmes de production discrets par les réseaux de Petri temporisés, Thèse, Université de Paris IV, France.
  10. 10. LahayeS.2000Contribution à l’étude des systèmes linéaires non stationnaires dans l’algèbre des dioïdes, Thèse, LISA- Université d’Angers.
  11. 11. MerlinP.1979Methodology for the Design and Implementation of Communication Protocole, IEEE Transaction on Communication 6
  12. 12. MunierA.1993Régime asymptotique optimal d’un graphe d’événements temporize généralisé: application à un problème d’assemblage, APII 5
  13. 13. MurataT.1989Petri nets: Properties, analysis and applicationsIEEE Proceedings 4541 EOF580 EOF
  14. 14. NakamuraM.SilvaM.1999Cycle time computation in deterministically timed weighted marked graphs, IEEE-International Conference on Emerging Technologies and Factory Automation (ETFA), Universitat Politècnica de Catalunya, Barcelona, Spain, 10371046
  15. 15. PetriC.1962Kommunikation mit AutomatenPhd thesis, Institut für Instrumentelle Mathematik, Bonn, Germany.
  16. 16. SauerN.2003Marking optimization of weighted marked graphsJournal of Discrete Event Dynamic Systems13245 EOF262 EOF
  17. 17. TrouilletB.BenasserA.GentinaJ.C.2001Sur la modélisation du comportement dynamique des graphes d’événements pondérés, in G. Juanole & R. Valette (eds), Conférence, Modélisation des Systèmes Réactifs (MSR),, Hermès, Toulouse, France, 447462

Notes

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

Written By

Samir Hamaci, Karim Labadi and A. Moumen Darcherif

Submitted: 01 December 2011 Published: 29 August 2012