Open access peer-reviewed chapter

Process Petri Nets with Time Stamps and Their Using in Project Management

Written By

Ivo Martiník

Submitted: December 5th, 2017 Reviewed: March 26th, 2018 Published: September 19th, 2018

DOI: 10.5772/intechopen.76769

Chapter metrics overview

813 Chapter Downloads

View Full Metrics

Abstract

Process Petri nets with time stamps (PPNTS) are the newly introduced class of low-level Petri nets, whose definition and the properties are the main topic of this chapter; they generalize the properties of Petri net processes in the area of design, modeling and verification of generally parallel systems with the discrete time. Property-preserving Petri net process algebras (PPPAs) were originally designed for the specification and verification of manufacturing systems. PPPA does not need to verify composition of Petri net processes because all their algebraic operators preserve the specified set of the properties. These original PPPAs are generalized for the class of the PPNTSs in this chapter. The new COMP, SYNC and JOIN algebraic operators are defined for the class of PPNTS and their chosen properties are proved. With the support of these operators, the PPNTSs can be extended also to the areas of project management and the determination of the project critical path with the support of the critical path method (CPM). The new CPNET subclass of PPNTS class is defined in this chapter. It is specially designed for the generalization of the CPM activity charts and their properties. This fact is then demonstrated on the simple project example and its critical path and other property specifications.

Keywords

  • process Petri nets with time stamps
  • property-preserving Petri net process algebras
  • critical path method
  • discrete time
  • property preservation
  • parallel systems modeling

1. Introduction

There are currently a number of formally defined classes of Petri nets[1, 2] available for modeling of generally parallel systems. When studying distributed parallel programming systems, real-time systems, economic systems and many other types of systems, it plays a role modeling of the time variables associated with individual system events, the duration of the studied activities, the time history of the modeled system and many other time characteristics. Special classes of Petri nets were introduced for the modeling of these types of systems with discrete time and their properties were studied in detail. Time Petri netsand timed Petri nets[3, 4] are currently the two most important classes of low-level Petri nets that use the concept of discrete time in their definition. Other classes of low-level Petri nets with discrete time are introduced and discussed for instance in [5, 6, 7]. It can be stated that most of the currently studied classes of Petri nets with discrete time use only the relative time variables usually related to the specific marking of the given Petri net. This fact can then cause difficulties, for example, in modeling complex time-synchronized distributed systems in which an external time source is usually available and individual components of this system must be synchronized with this external time source.

Process Petri nets(PPN) [8] were primarily introduced as a special subclass of classic low-level Petri nets for their using in the area of workflow management. PPN is a continuous Petri net that include within the set of all its places the unique input place, the unique output place and a finite set of so-called resource places which may contain, along with the input place, the tokens in the entry marking of the given PPN. These tokens located in the entry marking of PPN at the resource places usually represent the permanent resources of the modeled system. The given PPN can pass into its exit marking that is reachable from its entry marking by performing the final sequence of the transition firings. The tokens of the PPN’s exit marking may be then located only at its single output place and also at its resource places.

Process Petri nets with time stamps(PPNTS) are the newly introduced class of low-level Petri nets whose definition and the properties are the main topics of this chapter. PPNTS generalize the properties of PPNs in the area of design, modeling and verification of generally parallel systems with the discrete time.

Property-preserving Petri net process algebras(PPPA) [9] were originally designed for the specification and verification of manufacturing systems. PPPA has four types of operators: extensions, compositions, refinements and reductions. All operators can preserve about 20 PPN’s properties (some of them under additional conditions), such as liveness, boundedness, reversibility, RC-property, traps, siphons, proper termination, and so on. PPPA does not need to verify composition of PPNs because all their algebraic operators preserve the specified set of the properties. Hence, if the source PPNs satisfy the desirable properties, each of the composite PPN, including the PPN that models the resulting system itself, also satisfies these properties. These original PPPA are generalized for the class of the PPNTS in this chapter and their properties of proper-formed, well-formed and pure-formed PPNTS are then newly introduced. The new COMP, SYNCand JOINalgebraic operators are defined for the class of PPNTS and their chosen properties are proved.

With the support of these operators, the PPNTS can be extended also to the areas of the project management and the determination of the project critical path with the support of the critical path method (CPM) [10]. The new CPPNET subclass of PPNTS class is then defined in this chapter to represent pure-formed time-dependent processes. It is specially designed for the generalization of the CPM activities charts and their properties. This fact is then demonstrated on the simple project example and its critical path and other properties specification.

This chapter is arranged into the following sections: Section 2 explains the base term of this chapter, that is, process Petri nets with time stamps and introduces the terms of proper-formed, well-formed and pure-formed PPNTS; Section 3 discusses algebraic operators COMPand SYNCdefined over the class of PPNTS and their main properties; Section 4 then introduces the special subclass CPPNET of the PPNTS class and explains its use in the area of the project management to represent pure-formed time-dependent processes with using of PPNTSs and to find critical paths for these processes similarly as in the case of the well-known critical path method (CPM). Finally, Section 5 gives the conclusions of the research to conclude the chapter.

Advertisement

2. Process Petri nets with time stamps and their properties

Let Ndenote the set of all natural numbers, N:= {1, 2, …}; N0 the set of all non-negative integer numbers, N0 := {0, 1, 2, …}; ∅ the empty set; |A| the cardinality of the given set A; P(A) denotes the family of all the subsets of the given set A; f: ABa function on a domain Ato a codomain B; ⌐ the logical negation operator. Let (AN0) ∧ (∃nN: |A| = n) ∧ (A≠ ∅); then max(A) := x, where (xA) ∧ (∀yA: x ≥ y). MultisetMover a nonempty set Sis a function M: SN0. The non-negative number M(a) ∈ N0, where aS, denotes the number of occurrences of the element ain the multiset M.The multiset Mover a nonempty set Swill be represented by the notation M:= [aM(a), bM(b), cM(c), …] = [a, …, a, b, …, b, c, …, c, …], where S:= {a, b, c, …}. Notation SMS then denotes the class of all the multisets over the set S.

Definition 1.Let Abe a nonempty set. By the (nonempty finite) sequenceσover the set Awe understand a function σ: {1, 2, …, n} → A,where nN. Function ε: ∅ → Ais called the empty sequenceon the set A. We usually represent the sequence σ: {1, 2, …, n} → Aby the notation σ = <a1, a2, …, an > of the elements of the set A, where ai = σ(i) for 1 ≤ i ≤ n. Empty sequence ε: ∅ → Aon the set Awe usually represent by the notation ε = <>.We denote the set of all finite (and possible empty) sequences over the set Aby the notation ASQ.

If σ = <a1, a2, …, an > and τ = <b1, b2, …, bm > are the finite sequences, where σASQ, τASQ, nN, mN, then by the concatenation of the sequencesσand τ, denoted by σ++τ, we understand the finite sequence σ++τ:= < a1, a2, …, an, b1, b2, …, bm>. The following functions are defined:

  1. length: ASQN0, so that: length(σ) := n, length(ε) := 0,

  2. elements: ASQP(A), so that: elements(σ) := {a| ∃i, 1 ≤ i ≤ n: a = σ(i)}, elements(ε) := ∅,

  3. prefix: ASQ × N0ASQ, so that:

    prefix(<a1, a2, …, an>, m) := < a1, a2, …, am>, if m ≤ n,

    prefix(<a1, a2, …, an>, m) := < a1, a2, …, an>, if m > n,

    prefix(ε, m) := ε,

  4. suffix: ASQ × N0ASQ, so that:

    suffix(<a1, a2, …, an>, m) := < am + 1, am + 2, …, an>, if m < n,

    suffix(<a1, a2, …, an>, m) := ε, if m ≥ n,

    suffix(ε, m) := ε,

  5. create: N× AASQ, so that: create(n, a) := < a, a, …, a>, where length(<a, a, …, a>) = n,

  6. sort: (N0)SQ → (N0)SQ, so that: sort(σ) := ρ,

where (ρ = <b1, b2, …, bn>) ∧ (b1 ≤ b2 ≤ … ≤ bn) ∧ ([a1, a2, …, an] = [b1, b2, …, bn]).

We use the following subsets of the set (N0)SQ:

  • N#:= {σ∈ (N0)SQ | (σ = ε) ∨ ((σ = <a1, a2, …, an>) ∧ (a1 ≤ a2 ≤ … ≤ an)), nN},

  • N0 := {σ∈ (N0)SQ | (σ = ε) ∨ ((σ = <0, 0, …, 0>) ∧ (length(σ) = n)), nN}.

Thus, the elements of the set N#constitute the empty sequence ε and all the finite ascending ordered sequences σ consisting of non-negative integer numbers. Similarly, the elements of the set N0 then form an empty sequence ε and all the sequences in the form <0, 0, …, 0 > of any finite length.

Definition 2.NetNETis an ordered triple NET:=(P, T, A), where Pis finite nonempty set of places, Tis finite set of transitions, PT= ∅, and Ais finite set of arcs, A⊆ (P× T) ∪ (T× P). □

The given net NETis then described with a bipartite graph containing a finite nonempty set Pof places used for expressing of the conditions of a modeled process (we usually use circles for their representation), a finite set Tof transitions describing the changes in the modeled process (we usually draw them in the form of rectangles) and a finite set Aof arcs being principally oriented while connecting the place with the transition or the transition with the place and we usually draw them as lines with arrows.

Some commonly used notations for the nets are •y = {x| (x, y) ∈ A} for the presetand y• = {x| (y, x) ∈ A} for the postsetof a net node y(i.e., place or transition). A pathof a net NET:=(P, T, A) is a nonempty sequence <x1, …, xk> of net nodes, where kN, which satisfies (x1, x2), (x2, x3), …, (xk-1, xk) ∈ A. A path of the net NET:=(P, T, A) leading from its node xto its node yis a circuitif (y, x) ∈ A. We denote the set of all the circuits of the net NETby CIRCUITSNET. Net NET’:=(P′, T’, A’) is a subnetof the net NET:=(P, T, A) if (P′P) ∧ (T’T) ∧ (A’ = A∩ ((P′× T’) ∪ (T’× P′))). Net NETis connectedif and only if it is not composed of two or more disjoint and nonempty subnets.

Definition 3.Process net with time stamps(PNTS) PNTSis an ordered tuple PNTS:=(P, T, A, AF, TP, TI, IP, OP, RP), where

  1. (P, T, A) is the connected net, ∀tT: (•t≠ ∅) ∧ (t• ≠ ∅),

  2. AF: (P× T) ∪ (T× P) → N0 is the arc function,

    AFxy>0xyA,AFxy=0xyA,wherex,yPT,

  3. TPis the transition priority function, TP: TN,

  4. TI: (T× P) → N0 is the time interval function,

  5. IPis the input place, (IPP) ∧ (•IP= ∅) ∧ (∀p∈ (P\ ({IP} ∪ RP)): •p≠ ∅),

  6. OPis the output place, (OPP) ∧ (OP• = ∅) ∧ (∀p∈ (P\ ({OP} ∪ RP)): p• ≠ ∅),

  7. RPis the set of resource places, (RP⊆ (P\ {IP, OP})) ∧ (∀tT: ⌐(•tRP)).

The class of all the PNTS will be denoted by PNTS. □

The given PNTS PNTS:=(P, T, A, AF, TP, TI, IP, OP, RP) is represented by the connected net(P, T, A) with nonempty preset and postset of each of its transitions t; the arc functionAFassigning each arc with a natural number (such number has the default value of 1, if not explicitly indicated in the PNTS diagram) expressing the number of removed or added tokens from or to the place associated with that arc when firing a particular transition; transition priority functionTPassigns with each transition the natural number value expressing its priority (with the default value of 1); the time interval functionTIassigns to each arc of the type (transition, place) a non-negative integer dexpressing the minimum time interval during which the token has to remain in the placeinstead of being able to participate in the next firing of some transition and it thus determines the so-called time markingof the given PNTS (the value dassociated with the respective arc is given in the format +din the PNTS diagram); the input placeIPis the only one nonresource place of PNTS PNTSwith no input arc(s); the output placeOPis the only one nonresource place of PNTS PNTSwith no output arc(s); the finite set RPof resource placesis used for expressing conditions of a modeled process containing some initial resources and we use circles with the double line for their representation.

Definition 4.Let PNTS:=(P, T, A, AF, TP, TI, IP, OP, RP) be the PNTS. Then:

  1. markingMof the PNTS PNTSis a function M: PN0,

  2. time markingmof the PNTS PNTSis a function m: PN#,

    where ∀pP: |M(p)| = length(m(p)),

  3. variable τN0 is the net timeof the PNTS PNTS,

  4. stateSof the PNTS PNTSis an ordered triple S:= (M, m, τ),

  5. transition tTis enabledin the state S:= (M, m, τ) of the PNTS PNTSthat is denoted by tenS, if ∀p∈ •t: (M(p) ≥ AF(p, t)) ∧ (∀nelements(prefix(m(p), AF(p, t))): n ≤ τ)),

  6. firing of the transitiontTresults in changing the state S:= (M, m, τ) of the PNTS PNTSinto its state S′:= (M’, m’, τ) that is denoted by S[tS′, where ∀pP:

    • M’(p):= M(p) − AF(p, t) + AF(t, p),

    • m’(p):= sort(suffix(m(p), AF(p, t))++create(τ + TI(t, p), AF(t, p))),

  7. elapsing of time intervalδNresults in changing the state S:= (M, m, τ) of PNTS PNTSinto its state S′:= (M, m, τ + δ), where ∀tT: ⌐(ten(M, m, τ)), that is denoted by S[δS′, so that:

    tTnN1n<δ:tenMmτ+ntT:tenMmτ+δ,

  8. if the transitions t1, t2, …, tnTare enabled in the state S:= (M, m, τ) of PNTS PNTS(i.e., (t1 enS) ∧ (t2 enS) ∧ … ∧ (tnenS)) we say that these transitions are enabled in parallelin the state Sthat is denoted by {t1, t2, …, tn} enS,

  9. finite nonempty sequence σ := t1 t2 tnof the transitions t1, t2, …, tnTfor which the following is valid in the state S1 := (M1, m1, τ1) of PNTS PNTS:

    • (M1, m1, τ1) [t1⟩ (M2, m2, τ1) [t2⟩ … [tn⟩ (Mn + 1, mn + 1, τ1),

    • tT: ⌐(ten(Mn + 1, mn + 1, τ1)),

    is called stepσin the given state S1 of PNTS PNTSand it is denoted by.

    M1m1τ1σMn+1mn+1τ1,

  10. finite nonempty sequence ρof steps and time intervals elapsing that represents the following finite sequence

    M1m1τ1σ1M2m2τ1δ1Mn+1mn+1τnδnMn+1mn+1τn+1

    of the state changes of PNTS PNTSis the sequence ρ := σ1 δ1 σ2 δ2 σn δnof steps σ1, σ2, , σnand time intervals elapsing δ1, δ2, , δn,

  11. we say the state S′of PNTS PNTSis reachable from its state Sif there exists the finite sequence ρ := σ1 δ1 σ2 δ2 σn δnof steps σ1, σ2, , σnand time intervals elapsing δ1, δ2, , δnsuch that S[σ1 δ1 σ2 δ2 σn δnS′; the set of all the reachable states of PNTS PNTSfrom its state Sis denoted by [S⟩; the set of all the finite sequences ρ := σ1 δ1 σ2 δ2 σn δnassociated with all the reachable states S′∈ [S⟩ is denoted by [S⟩⟩, that is,

    S{σ1δ1σ2δ2σnδnS[S:S[σ1δ1σ2δ2σnδnS,nN},

  12. the set of all the states S:= (M, m, τ) of PNTS PNTSis denoted by S,

  13. the set of all the markings Massociated with the set Sof all the states of PNTS PNTSis denoted by M, that is, M:= {M| (S = (M, m, τ)) ∧ (SS)},

  14. static stateSs:= (Ms, ms, τs) of PNTS PNTSis every of its states where

    pP\RP:Msp=0msp=<>,

  15. the set of all the static states Ss:= (Ms, ms, τs) of PNTS PNTSis denoted by Ss,

  16. the set of all the static markings Msassociated with the set Ssof all the static states of PNTS PNTSis denoted by Ms, that is, Ms:= {Ms| (Ss:= (Ms, ms, τs)) ∧ (SsSs)},

  17. the function ξ: MMswhich assigns to each marking MMof a given PNTS PNTSthe associated static marking MsMsis defined as follows:

    • pRP: ξ(M(p)) := M(p),

    • pP \ RP: ξ(M(p)) := 0,

  18. entry stateSe:= (Me, me, τe) of PNTS PNTSis every of its states where

    • ∃kN: (Me(IP) = k) ∧ (length(me(IP)) = k),

    • pP \ (RP ∪ {IP}): (Me(p) = 0) ∧ (me(p) = <>),

    • pRP: (Me(p) ≥ 0) ∧ (me(p)N0),

  19. the set of all the entry states Se:= (Me, me, τe) of PNTS PNTSis denoted by Se,

  20. exit stateSx:= (Mx, mx, τx) of PNTS PNTSthat is reachable from its entry state Se:= (Me, me, τe) is every of its states where

    • Sx[Se,

    • Mx(OP) = Me(IP),

    • pP \ (RP ∪ {OP}): (Me(p) = 0) ∧ (me(p) = <>),

  21. the set of all the exit states Sx:= (Me, me, τe) of PNTS PNTSthat are reachable from its entry state Se:= (Me, me, τe) is denoted by [Sex,

  22. the set of all the exit states Sxof PNTS PNTSthat are reachable from all its entry states SeSeis denoted by Sx. □

The above established concepts are demonstrated in a simple example of the PNTS PNTS1 := (P, T, A, AF, TP, TI, IP, OP, RP) that is shown in Figure 1, where P:= {IP, P1, R1, OP}, T:= {T1, T2, T3}, A:= {(IP, T1), (IP, T2), (T1, P1), (T2, P1), (R1, T1), (P1, T3), (T3, R1), (T3, OP)}, AF:= {((IP, T1), 1), ((IP, T2), 1), ((T1, P1), 1), ((T2, P1), 2), ((R1, T1), 1), ((P1, T3), 1), ((T3, R1), 1), ((T3, OP), 1)}, TP:= {(T1, 2), (T2, 1), (T3, 1)}, TI:= {((T1, P1), 3), ((T2, P1), 3), ((T3, R1), 1), ((T3, OP), 4)}, IP:= IP, OP:= OP, RP:= {R1}.

Figure 1.

Firing of transitionT1in PNTSPNTS1.

PNTS PNTS1 is in its entry state Se:= (Me, me, τe), where marking Me:= (Me(IP), Me(P1), Me(R1), Me(OP)) = (2, 0, 2, 0), time marking me:= (me(IP), me(P1), me(R1), me(OP)) = (<0, 2>, <>, <0, 0>, <>) and net time τe = 0 (i.e., τe = τ). Static marking MsMsassociated with the entry marking Me(see (xiv) and (xvii) of Definition 4) has the value Ms:= ξ(Me) = (0, 0, 2, 0).

Time marking mof any PNTS expresses the current time state of the modeled system using the final (or empty) ascending ordered sequences of non-negative integers (i.e., elements of the set N#) associated with each of its places. The individual values of the time marking massociated with the arbitrary place pof the given PNTS in its state S, informally said, represent the values of the net time τat which the respective token can first participate in the firing of selected enabled transition tof the given PNTS.

The transitions T1and T2are enabled in the entry state Sebecause (see (v) of Definition 4):

  • p∈ •T1: (2 = M(IP) ≥ AF(IP, T1) = 1) ∧ (2 = M(R1) ≥ AF(R1, T1) = 1) ∧ (∀nelements(prefix(m(IP), AF(IP, T1))) = elements(prefix(<0, 2>, 1)) = elements(<0>) = {0}: 0 ≤ 0) ∧ (∀nelements(prefix(m(R1), AF(R1, T1))) = elements(prefix(<0, 0>, 1)) = elements(<0>) = {0}: 0 ≤ 0),

  • p∈ •T2: (2 = M(IP) ≥ AF(IP, T1) = 1) ∧ (∀nelements(prefix(m(IP), AF(IP, T2))) = elements(prefix(<0, 2>, 1)) = elements(<0>) = {0}: 0 ≤ 0).

When enabling individual transitions of the given PNTS so-called conflictscan originate in its certain markings (or conflict transitions). At the enabling of the transitions t1 and t2 of the given PNTS in its state Sthe conflict occurs, if both transitions t1 and t2 have at least one input place, each of the transitions t1 and t2 is individually enabled in the state S, but the transitions t1 and t2 are not enabled in parallel in the state S(see (viii) of Definition 4) and enabling of one of them will prevent enabling of the other (i.e., (•t1 ∩ •t2 ≠ ∅) ∧ (t1 enS) ∧ (t2 enS) ∧ ⌐({t1, t2} enS)). The term of conflict transitions can be obviously easily generalized for the case of a finite set t1, t2, …, tn, nNof the transitions of the given PNTS.

The transitions T1and T2in the entry state Seof PNTS PNTS1 are conflict transitions because the time marking me(IP) = <0, 2 > (i.e., only one token of the entry marking Me(IP) may participate in the firing of the transition T1or T2in the net time τe = 0). When solving such transitions conflict we therefore follow the rule which determines, informally said, that from the set of conflict transitions the one will be enabled, whose value of the transition priority function TPis the highest. If such transition from the set of conflict transitions does not exist, the given conflict would have to be solved by other means. The transition T1is then enabled in the entry state Seon the basis of that rule in our studied example (because TP(T1) = 2 and TP(T2) = 1).

Firing of the transition T1changes the entry state Se:= (Me, me, τe) of the PNTS PNTS1 into its state S1 := (M1, m1, τe) (i.e., Se[T1S1—see Figure 1), where (see (vi) of Definition 4):

  • M1(IP) := Me(IP) - AF(IP, T1) = 2 − 1 = 1,

  • m1(IP):= sort(suffix(me(IP), AF(IP, T1))) = sort(suffix(<0, 2>, 1)) = sort(<2>) = <2>,

  • M1(P1) := Me(P1) + AF(T1, P1) = 0 + 1 = 1,

  • m1(P1):= sort(create(τ + TI(T1, P1), AF(T1, P1))) = sort(create(0 + 3, 1)) = sort(create(3, 1)) = sort(<3>) = <3>,

  • M1(R1) := Me(R1) - AF(R1, T1) = 2 − 1 = 1,

  • m1(R1):= sort(suffix(me(R1), AF(R1, T1))) = sort(suffix(<0, 0>, 1)) = sort(<0>) = <0> .

There is no enabled transition in the state S1 := (M1, m1, τ1) and it is necessary to perform the time interval elapsing with the value of δ = 2. This will change the state S1 := (M1, m1, τe) into the state S2 := (M1, m1, τ1), where τ1 := τe + δ = 2 (i.e., S1 [2⟩ S2). It can be easily shown that transition T1in the state S2 is enabled and firing of this transition changes the state S2 := (M1, m1, τ1) of the PNTS PNTS1 into its state S3 := (M2, m2, τ1) (i.e., S2 [T1S3), where M2 := (M2(IP), M2(P1), M2(R1), M2(OP)) = (0, 2, 0, 0) and m2 := (m2(IP), m2(P1), m2(R1), m2(OP)) = (<>, <3, 5>, <>, <>).

It can then be easily verified that S3 [1⟩ S4 [T3S5 [2⟩ S6 [T3Sx, where:

  • S4 = (M2, m2, τ2) = ((0, 2, 0, 0), (<>, <3, 5>, <>, <>), 3),

  • S5 = (M3, m3, τ2) = ((0, 1, 1, 1), (<>, <5>, <4>, <7>), 3),

  • S6 = (M3, m3, τ3) = ((0, 1, 1, 1), (<>, <5>, <4>, <7>), 5),

  • Sx = (M4, m4, τ3) = ((0, 0, 2, 2), (<>, <>, <4, 6>, <7, 9>), 5).

There are no enabled transitions in the exit state Sx:= (M4, m4, τ3) of PNTS PNTS1 that is reachable from the entry state Se:= (Me, me, τe) (see (xx) of Definition 4) and there is also no time interval elapsing value δin this state that enables any of the transitions.

The set AMsMsof all the allowed static markingsof the given PNTS PNTS, informally said, expresses how many tokens may be located in its individual resource places if PNTS PNTSbe in its (now no longer arbitrary) allowed entry state ASeASe, where ASeSe. For instance, the set AMsof the PNTS PNTS1 (see Figure 1) can be defined as AMs:= {(0, 0, k, 0) | kN}, that is, there must be at least one token in the resource place R1(and of course at least one token in the input place IP) in any allowed entry state ASeASe.

Definition 5.Let PNTS :=(P, T, A, AF, TP, TI, IP, OP, RP) be a PNTS, AMsMsbe the set of all of its allowed static markings and ASe:= {ASe| (ASe = (AMe, ame, 0)) ∧ (ξ(AMe) ∈ AMs)} be the set of all of its allowed entry states. Then:

  1. PNTSis k-boundedPNTS if

    ASeASekN0pPSASe,SMmτ:Mpk,

  2. PNTSis proper-formedPNTS if

    ASeASe:(S[ASeSx[ASex:Sx[S)(nN:[ASe=n),

  3. proper-formed PNTSis well-formedPNTS if

    ASeASeSxASex,SxMxmxτx:ξMxAMs,

  4. well-formed PNTSis pure-formedPNTS if

    ASeASeSxASex,SxMxmxτx:ξAMe=ξMx.

PNTSis proper-formedPNTS if for any of its state Sthat is reachable from any allowed entry state ASeASethere exists its output state Sxthat is also reachable from its allowed entry state ASeASesuch that the output state Sxis also reachable from the state S(i.e., ∀S∈ [ASe⟩ ∃Sx∈ [ASex: Sx∈ [S⟩). Furthermore, the cardinality of the set [ASe⟩⟩ of all the sequences ρ := σ1 δ1 σ2 δ2 σn δnassociated with all the reachable states S∈ [ASe⟩⟩ must be finite (i.e., (∃nN: |[ASe⟩⟩| = n).

Proper-formed PNTSis well-formedPNTS if for any of its allowed entry state ASeASeand for any of its exit state Sx∈ [ASex, where Sx:= (Mx, mx, τx), it is true that the exit static marking ξ(Mx) of all its resource places is an elementof the set AMsof all its allowed static markings if PNTS PNTSbe in its allowed entry state ASeASe(i.e., ∀ASeASeSx∈ [ASex, Sx:= (Mx, mx, τx): ξ(Mx) ∈ AMs).

Well-formed PNTSis pure-formedPNTS if for any of its allowed entry state ASeASe, where ASe:= (AMe, ame, τe), and for any of its exit state Sx∈ [ASex, where Sx:= (Mx, mx, τx), it is true that the exit static marking ξ(Mx) of all its resource places is equal tothe entry static marking ξ(AMe) of all its resource places that is associated with the allowed entry state ASe(i.e., ∀ASeASeSx∈ [ASex, Sx:= (Mx, mx, τx): ξ(AMe) = ξ(Mx)).

For instance, if the set AMsof the PNTS PNTS1 (see Figure 1) is defined as:

  1. AMs:= {(0, 0, k, 0) | kN} (i.e., there must be at least one token in the resource place R1in any allowed entry state ASeASe), then it can be shown that PNTS PNTS1 is k-bounded, proper-formed, well-formed and pure-formed PNTS,

  2. AMs:= {(0, 0, 0, 0)} (i.e., there may not be any token in the resource place R1in any allowed entry state ASeASe), then it can be shown that PNTS PNTS1 is k-bounded, proper-formed, but not well-formed or pure-formed PNTS (see for instance the sequence

    1000<0><><><>0T20200<><33><><>03.0200<><33><><>3T3 T30022<><><44><77>3,whereξMx=ξ0022=00200000=AMs).

Lemma 1.If PNTSis proper-formed PTNS then PNTSis k-bounded PNTS.

Proof. Clear. PNTS PNTS:= (P, T, A, AF, TP, TI, IP, OP, RP) is a connected net that contains the finite set Tof the transitions. Then the finite number of tokens will be added to each of the places pPby firing each of the transitions tT. The number of states S∈ [ASe⟩ for any allowed entry state ASeASemust be also finite because PNTSis proper-formed PNTS (i.e., ∃nN: |[ASe⟩⟩| = n). From these facts then immediately follows that in any state S∈ [ASe⟩ the finite number of tokens must be placed in any place pP, where any final number of tokens is placed in the input place IPin the entry state ASe. From these facts then immediately follows that ASeASekN0pPSASe,SMmτ:Mpk.

Definition 6.Process Petri net with time stamps(PPNTS) PPNTSis an ordered couple PPNTS :=(PNTS, Se), where PNTS :=(P, T, A, AF, TP, TI, IP, OP, RP) is the PNTS and SeSeis the entry state of PNTS PNTS. The class of all PPNTSs will be denoted by PPNTS.□

Advertisement

3. Algebraic operators COMP and SYNC and their properties

We study the issue of transforming PNTS through precisely defined binary operator COMPand n-ary operator SYNCover the class PNTSand we also examine the preservation of individual PNTS’s properties when applying each of these operators. Formal enrollment of an application of generally n-ary operator OPwhose operands are the PNTS PNTS1, PNTS2, …, PNTSn(nN) and whose application requires the specification of values of kformal parameters (kN) par1, par2, … park, will be denoted by the expression.

PNTSPNTS1PNTS2PNTSn.OPpar1par2park,

where PNTSis the resulting PNTS.

Definition 7.Let PNTS1 := (P1, T1, A1, AF1, TP1, TI1, IP1, OP1, RP1) and PNTS2 := (P2, T2, A2, AF2, TP2, TI2, IP2, OP2, RP2) be the PNTSs. Let AMs1 := {(AMs1(IP1), AMs1(p11), …, AMs1(p1n), AMs1(r11), …, AMs1(r1m), AMs1(OP1)) | P1 := {p11, …, p1n, r11, …, r1m}, RP1 := {r11, …, r1m}, nN, mN} be the set of all the allowed static markings of PNTS1, AMs2 := {(AMs2(IP2), AMs2(p21), …, AMs2(p2k), AMs2(r21), …, AMs2(r2h), AMs2(OP2)) | P2 := {p21, …, p2k, r21, …, r2h}, RP2 := {r21, …, r2h}, kN, hN} be the set of all the allowed static markings of PNTS2.

Cartesian productAMs1AMs2 is then the following set:

AMs1AMs2AMs1IP1AMs1p11AMs1p1nAMs1r11AMs1r1mAMs1OP1,AMs2IP2AMs2p21AMs2p2kAMs2r21AMs2r2hAMs2OP2.AMs1IP1AMs1p11AMs1p1nAMs1r11AMs1r1mAMs1OP1AMs1.AMs2IP2AMs2p21AMs2p2kAMs2r21AMs2r2hAMs2OP2AMs2.

PNTS PNTS1 and PNTS2 are disjoint and we denote this fact by PNTS1PNTS2 if.

P1P2=T1T2=.

Definition 8.The function COMP: PNTS× PNTSPNTSof nets compositionis defined as follows: if PNTS1 := (P1, T1, A1, AF1, TP1, TI1, IP1, OP1, RP1) and PNTS2 := (P2, T2, A2, AF2, TP2, TI2, IP2, OP2, RP2) be the arbitrary PNTSs, PNTS1PNTS2, tbe an arbitrary transition, where (tT1) ∧ (tT2), tiN0, then PNTS :=[PNTS1, PNTS2].COMP(t, ti), where PNTS PNTS:= (P, T, A, AF, TP, TI, IP, OP, RP) fulfills the following:

  1. P:= P1P2,

  2. T:= T1T2 ∪ {t},

  3. A := A1A2 ∪ {(OP1, t), (t, IP2)},

  4. AF:= AF1AF2 ∪ {((OP1, t), 1), ((t, IP2), 1)},

  5. TP:= TP1TP2 ∪ {(t, 1)},

  6. TI := TI1TI2 ∪ {(t, IP2), ti)},

  7. IP := IP1,

  8. OP := OP2,

  9. RP:= RP1RP2. □

Symbolic representation of PNTS [PNTS1, PNTS2].COMP(t, ti) can be seen in Figure 2.

Figure 2.

Symbolic representation of PNTS [PNTS1,PNTS2].COMP(t,ti).

Lemma 2.Let PNTS1 := (P1, T1, A1, AF1, TP1, TI1, IP1, OP1, RP1) and PNTS2 := (P2, T2, A2, AF2, TP2, TI2, IP2, OP2, RP2) be two arbitrary PNTS, PNTS1PNTS2, tbe an arbitrary transition, (tT1) ∧ (tT2), tiN0, AMs1 and AMs2 be the sets of all the allowed static markings of PNTS1 and PNTS2. Let PNTS:= [PNTS1, PNTS2].COMP(t, ti).

If PNTS1 and PNTS2 are proper-formed, resp. well-formed, resp. pure-formed, PNTS and AMs = AMs1AMs2 be the set of all the allowed static markings of PNTS PNTS, then also resulting PNTSis proper-formed, resp. well-formed, resp. pure-formed, PNTS.

Proof. Clear, it directly follows from Definition 5, Definition 7 and Definition 8. □

Definition 9.The function SYNC: PNTS× PNTS× … × PNTSPNTSof synchronous nets compositionis defined as follows: if PNTS1 := (P1, T1, A1, AF1, TP1, TI1, IP1, OP1, RP1), PNTS2 := (P2, T2, A2, AF2, TP2, TI2, IP2, OP2, RP2), …, PNTSn:= (Pn, Tn, An, AFn, TPn, TIn, IPn, OPn, RPn), be the arbitrary PNTSs, ∀i, 1 ≤ i ≤ n, ∀j, 1 ≤ j ≤ n: i ≠ jPNTSiPNTSj, where nN, piand pobe the arbitrary places, (piP1P2 ∪ … ∪ Pn) ∧ (poP1P2 ∪ … ∪ Pn) ∧ (pipo), tiand tobe the arbitrary transitions, (tiT1T2 ∪ … ∪ Tn) ∧ (toT1T2 ∪ … ∪ Tn) ∧ (tito), af1 ∈ N, af2 ∈ N, …, afnN, ti1 ∈ N0, ti2 ∈ N0, …, tinN0, tioN0, then

PNTSPNTS1PNTS2PNTSn.SYNCpipotitoaf1afnti1tintio,

where PNTS PNTS:= (P, T, A, AF, TP, TI, IP, OP, RP) fulfills the following:

  1. P:= P1P2 ∪ … ∪ Pn ∪ {pi, po},

  2. T:= T1T2 ∪ … ∪ Tn ∪ {ti, to},

  3. A:= A1A2 ∪ … ∪ An ∪ {(pi, ti), (ti, IP1), …, (ti, IPn), (OP1, to), …, (OPn, to), (to, po)},

  4. AF:= AF1AF2 ∪ … ∪ AFn ∪ {((pi, ti), 1), ((ti, IP1), af1), …, ((ti, IPn), afn), ((OP1, to), af1), …, ((OPn, to), afn), ((to, po), 1)},

  5. TP:= TP1TP2 ∪ … ∪ TPn ∪ {(ti, 1), (to, 1)},

  6. TI:= TI1TI2 ∪ … ∪ TIn ∪ {((ti, IP1), ti1), …, ((ti, IPn), tin), ((to, po), tio)},

  7. IP:= pi,

  8. OP:= po,

  9. RP:= RP1RP2 ∪ … ∪ RPn. □

Symbolic representation of PNTS [PNTS1, PNTS2, …, PNTSn].SYNC(pi, po, ti, to, af1, …, afn, ti1, …, tin, tio) can be seen in Figure 3.

Figure 3.

Symbolic representation of PNTS [PNTS1,PNTS2, …,PNTSn].SYNC(pi,po,ti,to,af1, …,afn,ti1, …,tin,tio).

Lemma 3.Let PNTS1 := (P1, T1, A1, AF1, TP1, TI1, IP1, OP1, RP1), PNTS2 := (P2, T2, A2, AF2, TP2, TI2, IP2, OP2, RP2), …, PNTSn:= (Pn, Tn, An, AFn, TPn, TIn, IPn, OPn, RPn) be arbitrary PNTSs, ∀i, 1 ≤ i ≤ n, ∀j, 1 ≤ j ≤ n: i ≠ jPNTSiPNTSj, where nN, piand pobe arbitrary places, (piP1P2 ∪ … ∪ Pn) ∧ (poP1P2 ∪ … ∪ Pn) ∧ (pipo), tiand tobe arbitrary transitions, (tiT1T2 ∪ … ∪ Tn) ∧ (toT1T2 ∪ … ∪ Tn) ∧ (tito), af1 ∈ N, af2 ∈ N, …, afnN, ti1 ∈ N0, ti2 ∈ N0, …, tinN0, tioN0 and AMs1, AMs2, …, AMsnbe the sets of all the allowed static markings of PNTS1, PNTS2, …, PNTSn. Let PNTS:= [PNTS1, PNTS2, …, PNTSn].SYNC(pi, po, ti, to, af1, …, afn, ti1, …, tin, tio).

If PNTS1, PNTS2, …, PNTSnare proper-formed, resp. well-formed, resp. pure-formed, PNTS and AMs = AMs1AMs2 ⊗ … ⊗ AMsnis the set of all the allowed static markings of PNTS PNTS, then also PNTSis proper-formed, resp. well-formed, resp. pure-formed, PNTS.

Proof. Clear, it directly follows from Definition 5, Definition 7 and Definition 9. □

Advertisement

4. Process Petri nets with time stamps and their applications in project management area

Critical Path Method (CPM) is a method used in modeling and project management that was developed at the end of 1950s and that is commonly used for all the types of projects including software development [10]. The CPM is the most widely used method of so-called network analysis, even though it is designed to analyze the time consumption of only deterministic projects, that is, projects where the duration of each of their activities is exactly known, including all their sub-activities.

The basis for using CPM is to create a project model that includes:

  • the list of all activities needed to complete the project,

  • the time duration of each activity that is constant,

  • the dependencies between the project activities,

A critical path is then a designation for a sequence of activities whose time duration directly affects the time duration of the entire project. The activities that make up the critical path are then referred to as critical activities. There may be several critical paths in the project. When managing the project, a sequence of activities within a given network chart describing this project that increases the longest total time duration of a project is called its critical path. The critical path within the network chart can be used to determine the shortest time required to complete the project. The application of the CPM method can therefore determine which activities within the studied project are “critical” (i.e., activities on the longest path in the network chart describing the project) and which activities may be delayed in the execution of the project without increasing its total time.

The special class CPNETPNTSof PNTS is introduced in the following paragraphs to represent network chart used in the CPM method through PNTS. Special unary operator JOINthat is required in the definition of the class CPNETis introduced first.

Definition 10.The function JOIN: PNTSPNTSof net transition joiningis defined as follows: if PNTS1 := (P1, T1, A1, AF1, TP1, TI1, IP1, OP1, RP1) be the arbitrary PNTS, pP1 be the arbitrary place, t1 and t2 be the arbitrary transitions, (t1 ≠ t2) ∧ (t1 ∈ T1) ∧ (t2 ∈ T1), tiN0, then PNTS := PNTS1.JOIN(p, t1, t2, ti), where PNTS PNTS:= (P, T, A, AF, TP, TI, IP, OP, RP) fulfills the following:

  1. P:= P1 ∪ {p},

  2. T:= T1,

  3. A:= A1 ∪ {(t1, p), (p, t2)},

  4. AF:= AF1 ∪ {((t1, p), 1), ((p, t2), 1)},

  5. TP:= TP1 ∪ {(t, 1)},

  6. TI:= TI1 ∪ {(t1, p), ti)},

  7. IP:= IP1,

  8. OP:= OP1,

  9. RP:= RP1. □

Symbolic representation of the unary operator JOINapplication over the PNTS PNTS1 can be seen in Figure 4.

Figure 4.

Symbolic representation of PNTSPNTS := PNTS1.JOIN(p,t1,t2,ti).

Definition 11.Let PNTS1 := (P1, T1, A1, AF1, TP1, TI1, IP1, OP1, RP1), PNTS2 := (P2, T2, A2, AF2, TP2, TI2, IP2, OP2, RP2), …, PNTSn:= (Pn, Tn, An, AFn, TPn, TIn, IPn, OPn, RPn), where nN, be the arbitrary PNTSs, ∀i, 1 ≤ i ≤ n, ∀j, 1 ≤ j ≤ n: i ≠ jPTSNiPTSNj. The class CPNETPNTSthen contains the following PNTSs:

  1. if pbe an arbitrary place, p∉ (P1P2 ∪ … ∪ Pn), then PNTS BASEpCPNET, where BASEp:= ({p}, ∅, ∅, ∅, ∅, ∅, p, p, ∅},

  2. if PNTS1CPNET, PNTS2CPNET, tbe an arbitrary transition, where (tT1) ∧ (tT2), tiN0, then also [PNTS1, PNTS2].COMP(t, ti) ∈ CPNET,

  3. if PNTS1, PNTS2, …, PNTSnCPNET, piand pobe the arbitrary places, (piP1P2 ∪ … ∪ Pn) ∧ (poP1P2 ∪ … ∪ Pn) ∧ (pipo), tiand tobe the arbitrary transitions, (tiT1T2 ∪ … ∪ Tn) ∧ (toT1T2 ∪ … ∪ Tn) ∧ (tito), ti1 ∈ N0, ti2 ∈ N0, …, tinN0, tioN0, then also PNTS PNTSCPNET, where

    PNTSPNTS1PNTS2PNTSn.SYNCpipotito11ti1ti2tintio,

  4. if PNTS1CPNET, pP1 be an arbitrary place, t1 and t2 be the arbitrary transitions, (t1 ≠ t2) ∧ (t1 ∈ T1) ∧ (t2 ∈ T1), tiN0 and afN, then also PNTSCPNET, where PNTS:= (P, T, A, AF, TP, TI, IP, OP, RP), such that:

    • PNTS := PNTS1.JOIN(p, t1, t2, ti),

    • ⌐(x1 x2 … xnCIRCUITSPNTS: (x1 ∈ T) ∧ (xnP) ∧ (nN)). □

Four simple PNTSs BASEP1, CPNET1, CPNET2 and CPNET3 that are the members of the class CPNETcan be seen in Figure 5, where:

  • CPNET1 := [[BASEP2, BASEP3].COMP(T2, 2), BASEP4].COMP(T3, 5),

  • CPNET2 := [[BASEP6, BASEP8].COMP(T6, 2), BASEP7]

    .SYNC(P5, P9, T5, T7, 1, 1, 1, 6, 3),

  • CPNET3 := [ANET2, ANET3, BASEP1].SYNC(IP, OP, T1, T8, 1, 1, 1, 4, 1, 8, 2)

    .JOIN(P10, T3, T5, 4).

    .JOIN(P11, T3, T6, 5).

Figure 5.

PNTSsBASEP1,CPNET1,CPNET2 andCPNET3.

Note also that the PNTS CPNET3 does not contain any circuit as it is required in the (4) of Definition 11.

Lemma 4.Let PNTSCPNETbe an arbitrary PNTS. Then PNTSis pure-formed PNTS.

Proof. Clear, it directly follows from Definition 5, Definition 7, Definition 10 and Definition 11 and from the fact that any PNTSCPNETdoes not contain any resource place (i.e., if the given PNTSis proper-formed PNTS, then it is also immediately well-formed and pure-formed PNTS). Furthermore, it is also clear that if we allow the existence of a circuit within the PNTS PNTS(see (iv) of Definition 11), there is always the danger of a deadlock in such a PNTS and PNTSis in this case neither a proper-formed PTSN. See, for instance, PNTS CPNET4 in its entry state Sein Figure 6, where CPNET4 := CPNET3.JOIN(P12, T7, T2, 6). It is true that CPNET4 ∉ CPNETbecause there exists for instance the circuit.

T2 P3 T3P10T5 P6 T6 P8 T7P12CIRCUITSCPNET4.

Figure 6.

PNTSCPNET4 in its entry stateSe.

It is also clear that after the firing of the transition T1in the entry state Seof the PNTS CPNET4 no one transition will be enabled for any value of the net time τ in this PNTS (i.e., there exists the deadlock marking in this PNTS) and thus the CPNET4 is not even proper-formed PNTS. □

Definition 12.The class CPPNETPPNTScontains all the PPNTSs PPNTS :=(PNTS, Se) where PNTSCPNETand Se:=((1, 0, …, 0), (<0>, <>, …, <>), 0). □

An example of a simple process is presented in the following paragraphs the characteristics of which will be studied with using of the PPNTS from the CPPNET class. The studied process is described in the following table of activities (see Table 1):

ActivityDurationPrevious activities
A2
B3
C4
D2C
E6B, D
F5A
G5C
H3E, F

Table 1.

Table of activities and their dependencies of studied process.

The CPM chart of the abovementioned process comprising the activities listed in Table 1 is shown in Figure 7 where:

  • selected activity of the studied process and its duration is associated with each edge of the CPM chart,

  • each node of the CPM chart is associated with its serial number (indicated in the upper half of the node), the earliest possible activation time of the given node (shown in the lower left quarter of the node) and the possible latest activation time of the given node (shown in the lower right quarter circle of the node),

  • the desired links of the individual activities are expressed through the oriented edges and their associated nodes in the CPM chart,

  • the critical path of the CPM chart passes through its nodes where the earliest possible activation time is equal to the latest possible activation time, that is, through nodes 1, 2, 3, 5 and 6, and it is thus formed by A, D, E and H activities (these activities are represented by dashed line graphs in the CPM chart) with a total duration of 15 time units.

Figure 7.

CPM chart of process activities listed inTable 1.

The pure-formed PPNTS PROCthat represents the process comprising the activities listed in Table 1 can be seen in Figure 8, where

  • PROC:= [PROC1, [BASEC, BASEG].COMP(T5, 5)].SYNC(IP, OP, T1, T7, 1, 1, 0, 4, 0),

  • PROC1 := [[BASEA, BASEF].COMP(T3, 5), [BASEB, BASEE].COMP(T4, 6)]

Figure 8.

PPNTSPROCof process activities listed inTable 1.

.SYNC(P1, H, T2, T6, 1, 1, 2, 3, 3).

Places A, B, C, D, E, F, Gand Hof PNTS PROCrepresent individual activities of the studied process and the appropriate values of the time interval function TIthen express the time durations of relevant activities (i.e., for instance, the time duration of the activity Ais represented by the value of TI(T2, A) = 2, etc.).

In order to find the critical path of the process represented by PPNTS PROC, we first perform the association of each place and transition of the PPNTS PROCwith the value of the critical path function CPthat is introduced in the following Definition 13.

Definition 13.Let PPNTS PPNTS:= (P, T, A, AF, TP, TI, IP, OP, RP, Se), PPNTSCPPNET. The critical path functionCP: (PT) → N0 is defined as follows:

  1. CP(IP) := 0,

  2. p∈ (P\ IP): CP(p) := CP(t) + TI(t, p), where t= •p,

  3. tT: CP(t) := max({CP(p1), CP(p2), …, CP(pn)}), where •t = {p1, p2, …, pn}, nN. □

The PPNTS PROCwhose each place and transition is associated with the value of the critical path function CPcan be seen in Figure 9 (where, for instance, CP(E) = CP(T4) + TI(T4, E) = 6 + 6 = 12, where T4= •E; CP(T4) = max({CP(B), CP(D)}) = max({3, 6}) = 6, where •T4 = {B, D}, etc.).

Figure 9.

PPNTSPROCwith the associated values of critical path functionCP.

It follows directly from the Definition 4 that the value of the critical path function CPassociated with any transition tTof the arbitrary PPNTS :=(P, T, A, AF, TP, TI, IP, OP, RP, Se), where Se:=((1, 0, …, 0), (<0>, <>, …, <>), 0), then represents the net time τ value when the given transition twill be fired. The value of the critical path function CPassociated with the output place OP(i.e., CP(OP)) then immediately indicates the total duration of the process critical path (i.e., the net time τ value when the transition t= •OPwill be fired). The algorithm for finding the set of PPNTS nodes of which the project critical path is formed is then obvious and it is expressed by the following pseudocode in PASCAL (the set of nodes forming the critical path of the project is then contained in the CriticalPathvariable):

Node:= OP; CriticalPath:= {OP};

WHILE (Node<> IP) DO

BEGIN

MaxValue:= max({CP(X1), CP(X2), …, CP(Xn)}), where •Node = {X1, X2, …, Xn}, nN;

Node:= Xi, where (Xi∈ {X1, X2, …, Xn}) ∧ (CP(Xi) = MaxValue);

CriticalPath:= CriticalPath∪ {Node};

END;

The critical path of PPNTS PROCis after applying of the above algorithm represented by the set CriticalPath:= {IP, T1, C, T5, D, T4, E, T6, H, T7, OP} (see Figure 9). It is also clear that the given PPNTS may contain more critical paths with the same total time duration.

Advertisement

5. Conclusions

Further research in the field of PNTSs is mainly focused on the definition of additional unary, binary and n-ary PPPA operators preserving their specified properties, for instance, the binary SUBSToperator that performs the substitution of the given PNTS for the selected place of another PNTS, and so on. In the field of the project management the research is focused on modeling complex processes, which individual activities can additionally share in parallel a selected set of the resources. These resources are then represented in the given PNTS by individual tokens located in the resource places of its selected net marking. Finding the time-optimal critical path of such a process as well as verifying the properties of the given PNTS that models such a process is generally a nontrivial problem and the use of PPPAs plays a crucial role here.

Another class currently being studied is the class of multiprocess Petri nets with time stamps that represents the generalization of the class of PNTS. The given multiprocess Petri net with time stamps then represents the finite set of processes each of which is modeled by a separate PNTS that share a common set of resources modeled by its individual resource places and their tokens. Many of the studied properties of the multiprocess Petri nets with time stamps are similar or identical to those of the PNTS class and they allow for a further generalization of the concept of a critical path formed by a sequence of activities of the process modeled by the given multiprocess Petri nets with time stamps.

Advertisement

Acknowledgments

This chapter was supported by the SGS at the Faculty of Economics, VŠB-TU Ostrava, under Grant Evaluation of comparative applications using cognitive analysis and method of data envelopment analysis, number SP2018/146.

References

  1. 1. David R, Alla H. Discrete, Continuous and Hybrid Petri Nets. 2nd ed. Berlin: Springer-Verlag; 2010. 550 p. ISBN: 978-3642424694
  2. 2. Reisig W. Elements of Distributed Algorithms: Modeling and Analysis with Petri Nets. 1st ed. Berlin: Springer-Verlag; 1998. 302 p. ISBN: 3-540-62752-9
  3. 3. Diaz M. Petri Nets: Fundamental Models, Verification and Applications. 1st ed. London: John Willey & Sons; 2009. 656 p. ISBN: 978-0-470-39430-4
  4. 4. Popova-Zeugmann L. Time and Petri Nets. 1st ed. Heidelberg: Springer-Verlag; 2013. 209 p. ISBN: 978-3662514351
  5. 5. Furia CA, Mandrioli D, Morzenti A, Rossi M. Modeling Time in Computing. 1st ed. Heidelberg: Springer-Verlag; 2012. 424 p. ISBN: 978-3642323317
  6. 6. van Hee K, Sidorova N. The right timing: Reflections on the modeling and analysis of time. In: Application and Theory of Petri Nets and Concurrency 2013, 34th International Conference Proceedings; 24–28 June 2013; Milan. Berlin: Springer-Verlag; 2013. pp. 1-20
  7. 7. Martos-Salgado M, Rosa-Velardo F. Dynamic networks of timed Petri nets. In: Application and Theory of Petri Nets and Concurrency 2014, 35th International Conference Proceedings; 23–27 June 2014; Tunis. Berlin: Springer-Verlag; 2014. pp. 294-313
  8. 8. van der Alst W, van Hee K. Workflow Management: Models, Methods and Systems. 1st ed. Massachusetts: MIT Press; 2004. 384 p. ISBN: 978-0262720465
  9. 9. Huang H, Jiao L, Cheung T, Mak WM. Property-Preserving Petri Net Process Algebra in Software Engineering. 1st ed. Singapore: World Scientific Publishing; 2012. 318 p. ISBN: 978-981-4324-28-1
  10. 10. O’Brien JJ, Plotnick FL. CPM in Construction Management. 8th ed. New York: McGraw-Hill; 2016. 736 p. ISBN: 978-1259587276

Written By

Ivo Martiník

Submitted: December 5th, 2017 Reviewed: March 26th, 2018 Published: September 19th, 2018