1 Introduction

Petri Nets (PN) is a well known family of formalisms for the modelling of Discrete Event Systems (DES). As any other formalism for DES, they suffer from the well known state explosion problem. Such a problem appears both during the analysis (e.g., to decide if the system is bounded or not) and the synthesis (e.g., designing a controller) of the system, and it affects both the untimed and the timed model.

Many different time interpretations can be adopted for the timing of PN. Nevertheless, without any doubt, one of the “most basic and classical” interpretation for performance evaluation and control consists of: (1) associating exponential probability distributions to the delay of the atomic firing of transitions; and (2) solving conflicts by a race policy (see, for example, for example, Molloy (1982), Ajmone Marsan et al. (1995), or Balbo and Silva (1998)). In the sequel, we will assume this time interpretation for discrete models. The resulting stochastic nets will be referred as Markovian Petri Nets (MPN).

An interesting technique to overcome the above mentioned state explosion problem is known as fluidization. The fluidization of a transition consists of relaxing its firing amount (and thus the marking of its neighbour places) to the non-negative real quantities. If all transitions are fluidized, the result is a fluid or continuous PN (CPN) (David and Alla 2004; Silva et al. 2011; Silva 2016). By fluidization, more efficient analysis techniques can be developed at the price of losing some fidelity. In particular, the CPN may not preserve some qualitative or quantitative properties of the original discrete one (Silva and Recalde 2002; Silva et al. 2011). In other words, this issue is an instance of the classical trade-off between “accuracy” and “computational complexity”.

Similarly to the linearization of any continuous nonlinear time-driven dynamical system, the fluidization of DES (untimed or timed) requires some conditions to be of reasonable quality; for example, to satisfy the marking homothetic monotonicity property (Fraca et al. 2014b). If such property holds and the marking is large, then the results obtained with fluidization are frequently very good. With respect to timed net models, some functional extensions of the law of large numbers lead to the legitimization of the deterministic continuous PN approximation (see Section 2.3). This last relaxed model can be expressed as a set of Ordinary Differential Equations (ODEs). If the marking is not large, then some functional extensions of the Central Limit Theorem can be helpful, leading to Stochastically Differential Equations (SDEs) (Vázquez and Silva 2012; Beccuti et al. 2014). In the sequel we limit to deterministic relaxations.

Synchronizations in PN can be expressed with two complementary constructions: (1) rendez-vous (or joins); and (2) weights in arcs going from places to transitions. At this point it should be pointed out that if the marking is “very large”, the effect of those weights on arcs is not “seen” (Silva 2016) (intuitively speaking, if the marking of the place at the origin of the k-weighted arc is 1000k –i.e, relatively very big– the enabling is 1000, so the continuous approximation is valid). However, if the marking is not “very large”, the relative errors may be higher (intuitively speaking, rounding the number 1.5 to 1 lead to a relative error three orders of magnitude bigger than rounding 1000.5 to 1000). Thus, appropriate fluidization techniques are required for systems whose marking is “relatively” small (and hence cannot be fluidified properly), yet large enough to make its study a discrete system computationally prohibitive.

This paper deals with techniques to improve the fluidization process, what is specially interesting when the population is “relatively” small, at least in some parts of the system. We do not consider neither very small populations (in which fluidization is frequently not needed) nor very large ones (in which fluidization usually provides a good approximation of the original PN).

Some of the differences between discrete and continuous systems appear because solutions of the fundamental equation which are spurious in the untimed discrete system (i.e., analytical solutions of the fundamental or state-transition equation that are not reachable on the net model) may become reachable by the continuous relaxation. Therefore, some transformations on the discrete PN system are firstly proposed. They improve the fluidization process for untimed PN, thus potentially for any timed interpretation. In particular, the steady state throughput of the MPN will be better approximated by the continuous approximation, i.e., by the timed CPN (TCPN).

These transformations are based on the addition of some places which are implicit in the discrete system (Silva et al. 1998) but they constraint the behaviour of the continuous one. In particular, such cutting implicit places (Silva et al. 1998) remove some spurious solutions. The key issue here is that any continuous (possibly integer) spurious deadlock can be removed (the main differences between the discrete model and the continuous approximation is caused by spurious deadlocks). The elimination of a given spurious deadlock is a computational problem of polynomial time complexity. Unfortunately, the number of spurious deadlocks may be theoretically exponential. Nevertheless, this is not a frequent case in practice. Let us remark that improvements in both timed and untimed models are obtained by these techniques.

With respect to timed models, we focus on a particular situation in which the fluidized system does not approximate certain quantitative properties of the original one. It is the case of PN systems in which the enabling bound of a transition is equal to 1, and hence the probability of firing that transition may be very low in the discrete case but not so “difficult” on the continuous approximation. This problem is denoted as the Bound Reaching Problem (BRP) (Fraca et al. 2014a). The BRP is a challenging problem that may appear in many practical cases. It can arise in systems in which relatively small and large populations are combined in a given model, and also when inhibitor arcs of a bounded system are removed and simulated with regular arcs and places.

Among the different concerns related to the BRP, in general terms, the approximation of the throughput of a discrete Markovian PN (MPN) by a Timed Continuous PN (TCPN) under infinite server semantics (ISS) was considered in Silva et al. (2011). Here we extend such an approximation to join or rendez-vous transitions by means of some representative places which implement the concept of linear enabling functions (Teruel et al. 1993; Briz et al. 1994).

The rest of the paper is organized as follows. Section 2 recalls basic definitions. In Section 3, we concentrate on the addition of cutting implicit places with the goal of improving the untimed continuous approximation. The bound reaching problem is introduced in Section 4. In Section 5, a method derived from ISS, here denoted as ρ−s e m a n t i c s, is proposed for the firing of transitions involved in the BRP. Section 6 deals with the extension of previous results to the most frequent class of synchronizations: rendez-vous. A case study is discussed in Section 7, and Section 8 concludes the paper.

2 Definitions and previous concepts

The main concepts related to discrete and continuous PN are recalled here, both as untimed and timed formalisms. The relationship between the timed interpretations when the system population tends to infinity is also established (see Section 2.3). In the following, it is assumed that the reader is familiar with Petri nets (see DiCesare et al. (1993) or David and Alla (2004) for a gentle introduction).

2.1 Discrete Petri nets

A Petri net is a tuple \({\mathcal {N}}={\langle {P,T,\boldsymbol {Pre},\boldsymbol {Post}} \rangle }\) where P={p 1,p 2,...,p n } and T={t 1,t 2,...,t m } are disjoint and finite sets of places and transitions, and Pre, Post are |P|×|T| sized, natural valued, incidence matrices. The preset and postset of a node \(u \in P \cup T\) are denoted by ∙u and u ∙, respectively. A discrete PN system is a tuple \({\langle {{{\mathcal {N}}},{\boldsymbol {M}}_{0}} \rangle }\) where \({{\mathcal {N}}}\) is the net structure and \({\boldsymbol {M}}_{0} \in \mathbb {N}_{\geq 0}^{|P|}\) is the initial marking (denoted in upper case M for the discrete system).

The enabling degree of transition t i at marking M is defined as:

$$ Enab(t_{i}, {\boldsymbol{M}}) = \displaystyle\min_{p_{j}\in{\,\!^{\bullet{t_{i}}}}} \lfloor \frac{{\boldsymbol{M}}[p_{j}]}{\boldsymbol{Pre}[p_{j}, t_{i}]} \rfloor $$
(1)

The firing of t i in a certain natural amount α≤E n a b(t i ,M) leads to a new marking \({\boldsymbol {M}}^{\prime }\), which is denoted as \({\boldsymbol {M}} {{\overset {\alpha t_{i}}{\longrightarrow }}} {\boldsymbol {M}}^{\prime }\), and \({\boldsymbol {M}}^{\prime }={\boldsymbol {M}}+\alpha \cdot \boldsymbol {C}[P,t_{i}]\), where C=Post−Pre is the token flow matrix (incidence matrix if \(\mathcal {N}\) is self-loop free) and C[P,t i ] denotes the i th column in C. Hence, M=M 0+C⋅σ, the state-transition (or fundamental) equation, summarizes the marking evolution; where σ is the firing count vector associated to the fired sequence.

Right and left natural annullers of the token flow matrix are called T- and P-semiflows, respectively. When ∃y>0,y⋅C=0, the net is said to be conservative, and when ∃x>0, C⋅x=0, the net is said to be consistent. A nonempty set of places Θ is a trap if \({{\Theta }^{\bullet }}\subseteq {\,\!^{\bullet {\Theta }}}\), while a nonempty set of places Σ is a siphon if \({\,\!^{\bullet {\Sigma }}}\subseteq {{\Sigma }^{\bullet }}\).

The set of all the reachable markings of \({\langle {{{\mathcal {N}}},{\boldsymbol {M}}_{0}} \rangle }\) is denoted as \(RS_{D}({{\mathcal {N}}}, {\boldsymbol {M}}_{0})\). Its linearised reachability set (LRS) contains the markings which fulfill the fundamental equation (even if they are not reachable) (Silva et al. 1998). In this work, the LRS is defined on the real numbers (\({\boldsymbol {m}} \in \mathbb {R}_{\geq 0}^{|P|}\)):

$$ LRS({{\mathcal{N}}},{\boldsymbol{M}}_{0})\text{=}\{{\boldsymbol{m}} | {\boldsymbol{m}}\text{=}{\boldsymbol{M}}_{0}+\boldsymbol{C}\cdot\boldsymbol{\sigma}, {\boldsymbol{m}} \in \mathbb{R}_{\geq 0}^{|P|}\ , \boldsymbol{\sigma}\in \mathbb{R}_{\geq 0}^{|T|}\} $$
(2)

A marking M is spurious if it is a non reachable solution of the state-transition equation, i.e., \({\boldsymbol {M}} \in LRS({{\mathcal {N}}},{\boldsymbol {M}}_{0})\) but \({\boldsymbol {M}} \not \in RS_{D}({{\mathcal {N}}},{\boldsymbol {M}}_{0})\). The structural bound of a place p j , and the structural enabling bound of a transition t i are integer values defined as:

$$ SB(p_{j}) = \lfloor max \{{\boldsymbol{M}}[p_{j}]\ |\ {\boldsymbol{M}} = {\boldsymbol{M}}_{0} + \boldsymbol{C}\cdot\boldsymbol{\sigma}, {\boldsymbol{M}}, \boldsymbol{\sigma} \geq {{\mathbf{0}}}\} \rfloor $$
(3)
$$ \begin{array}{lll} SEB(t_{i}) &=&SEB(t_{i}) \lfloor max\{e \ | \forall p \in {\,\!^{\bullet{t_{i}}}}, e \leq \frac{{\boldsymbol{M}}[p_{j}]}{\boldsymbol{Pre}[p_{j},t_{i}]},\\ \mathrm{s.t.}~\boldsymbol{M}&=& {\boldsymbol{M}}_{0} + \boldsymbol{C} \cdot \boldsymbol{\sigma}, {\boldsymbol{M}}, \boldsymbol{\sigma} \geq {{\mathbf{0}}} \}\rfloor \end{array} $$
(4)

A Markovian Petri net system (MPN) is a particular time stochastic interpretation (Molloy 1982; Ajmone Marsan et al. 1995; Balbo and Silva 1998), in which the time to fire a transition t i follows an exponentially distributed function with parameter λ i ⋅E n a b(t i ,M), where λ i is the firing rate associated to t i . More formally, a MPN is a tuple \({\langle {{\mathcal {N}}, \boldsymbol {M}_{0}, \boldsymbol {\lambda }} \rangle }\), where \(\boldsymbol {\lambda } \in \mathbb {R}^{|T|}_{>0}\) is the vector of rates associated to the transitions.

Given a bounded and ergodic MPN system, the steady state throughput of a transition t i , denoted as χ M P N (t i ), provides a meaningful measure for its long-term performance. It is defined as the limit of the average number of times t i fires per time unit when time tends to infinity (Campos and Silva 1992):

$$ \chi_{MPN}(t_{i}) = \lim\limits_{\tau\to\infty} \frac{\sigma_{i}(\tau)}{\tau} $$
(5)

where τ is the time variable and σ i (τ) is the firing count of transition t i at time instant τ.

2.2 Continuous Petri nets

The main difference between continuous and discrete PN is in the firing amounts and consequently in the marking, which in discrete PN are restricted to be in the naturals, while in continuous PN are relaxed into the non-negative real numbers. Thus, a continuous PN system (CPN) is understood as a relaxation of a discrete one.

A continuous PN system is a tuple \({\langle {{{\mathcal {N}}},{\boldsymbol {M}}_{0}} \rangle }\) where \({{\mathcal {N}}}\) is the net structure (as defined for discrete PN) and \({\boldsymbol {m}}_{0} \in \mathbb {R}_{\geq 0}^{|P|}\) is the initial marking. The enabling degree of a continuous transition t i at marking m is defined as:

$$ enab(t_{i},{\boldsymbol{m}})=\min_{p_{j}\in{\,\!^{\bullet{t_{i}}}}}\left\{\frac{{\boldsymbol{m}}[p_{j}]}{\boldsymbol{Pre}[p_{j},t_{i}]}\right\} \geq Enab(t_{i},{\boldsymbol{m}}) $$
(6)

The firing of t i in a certain real amount α≤e n a b(t i ,m) leads to a new marking \({\boldsymbol {M}}^{\prime }\) that satisfies \(\boldsymbol {m}^{\prime }=\boldsymbol {m}+\alpha \cdot \boldsymbol {C}[P,t_{i}]\). Notice that in contrast to discrete PN, a continuous transition can fire if all its input places are positively marked, i.e., e n a b(t i ,m)>0, regardless of the input arc weights. Its set of reachable markings is denoted as \(RS_{{C}}({{\mathcal {N}}},{\boldsymbol {m}}_{0})\) (Silva et al. 2011). And its LRS coincides with the LRS of the discrete system. It holds that:

$$ LRS({{\mathcal{N}}},{\boldsymbol{M}}_{0}) \supseteq RS_{{C}}({{\mathcal{N}}},{\boldsymbol{M}}_{0}) \supseteq RS_{D}({{\mathcal{N}}},{\boldsymbol{M}}_{0}) $$
(7)

As in discrete PN, the equation m=m 0+C⋅σ summarizes the system evolution. The derivative of this equation with respect to time is \(\dot {{\boldsymbol {m}}}=\boldsymbol {C}\cdot \boldsymbol {f}\) where \(\boldsymbol {f} = \dot {\boldsymbol {\sigma }}\) is the vector of instantaneous flows of transitions.

A Timed Continuous Petri Net (TCPN) is a continuous PN together with a vector \(\boldsymbol {\lambda } \in \mathbb {R}^{|T|}_{>0}\) defining the speed associated to transitions, denoted as \({\langle {{{\mathcal {N}}},{\boldsymbol {m}}_{0},\boldsymbol {\lambda }} \rangle }\). One of the most used semantics is infinite server semantics (ISS) (proved to be specially interesting for engineering applications (Mahulea et al. 2009)). Moreover, product semantics may be also considered (Silva and Recalde 2002) for population dynamics or (bio)chemistry, and finite server semantics has been also considered in some works (David and Alla 2004). Alternatively, stochastic time interpretations are proposed in the literature such as Stochastic Continuous PN (Vázquez and Silva 2012).

In the sequel, ISS is considered. According to ISS, the flow through a continuous timed transition t i is defined as follows:

$$ f_{i}=\lambda_{i} \cdot enab(t_{i}, {\boldsymbol{m}}) = \lambda_{i} \cdot \min_{p_{j}\in{\,\!^{\bullet{t_{i}}}}}\left\{\frac{{\boldsymbol{m}}[p_{j}]}{\boldsymbol{Pre}[p_{j},t_{i}]}\right\} $$
(8)

If there exists a steady state in a TCPN system, the throughput of t i , denoted as χ T C P N (t i ), is equal to its steady state flow f i (Silva et al. 2011):

$$ \begin{array}{ll} \chi_{TCPN}(t_{i}) = \lim_{\tau\to\infty} f_{i}(\tau) \end{array} $$
(9)

where f i (τ) is the flow of transition t i at time instant τ.

2.3 Deterministic limit of MPN

The deterministic limit of a system (Jacod and Shiryaev 2002) describes the trajectory towards which the population densities of a discrete Markovian system converge as its size tends to infinity. Let us consider a MPN with initial marking \({\boldsymbol {M}}_{0}=k\cdot \boldsymbol {\mu }_{0}\in \mathbb {N}_{\geq 0}^{|P|}\) where \(\boldsymbol {\mu }_{0}\in \mathbb {R}_{\geq 0}^{|P|}\) represents the initial marking density of the system, and \(k\in \mathbb {R}_{>0}\) represents the relative system size (or volume).

The vector field for place p j is defined as \(F_{j}(\boldsymbol {\mu })={\sum }_{t_{i}\in ({\,\!^{\bullet {p_{j}}}}\cup {{p_{j}}^{\bullet }})} \boldsymbol {C}[p_{j},t_{i}] \cdot f_{i}\), where f i =λ i ⋅e n a b(t i ,μ) (notice that F j is a nonnegative function of real arguments on the system densities). Let F(μ) be a vector composed of the vector field functions F j (μ) of every place p j . The two following conditions can be easily checked:

  1. a)

    F(μ) is Lipschitz continuous, i.e., ∃H≥0 s.t. |F(μ)−F(ν)|≤H⋅|μ−ν|;

  2. b)

    \({\sum }_{t_{i}\in ({\,\!^{\bullet {p_{j}}}}\cup {{p_{j}}^{\bullet }})} |\boldsymbol {C}[p_{j},t_{i}]| \cdot f_{i}(\boldsymbol {\mu })<\infty \).

Then, the deterministic limit behaviour of the marking densities μ of the MPN when k tends to infinity is given by the following set of differential equations (Ethier and Kurtz 1986; Jacod and Shiryaev 2002): \(\dot {\boldsymbol {\mu }}=F(\boldsymbol {\mu })=\boldsymbol {C}\cdot \boldsymbol {f}\).

Thus, the deterministic limit of a MPN matches with the time evolution defined for TCPN. Therefore, a TCPN faithfully captures the behaviour of a MPN with “infinitely” large markings.

3 Transformations on the untimed discrete PN: addition of cutting implicit places

By fluidization, spurious markings of a discrete PN system may become reachable in the continuous one (Silva and Recalde 2002). Some transformations of the net system are proposed here to avoid those markings, thus obtaining a more faithful approximation.

The spurious markings can be either integer or not, and it is specially interesting to avoid them when they are deadlocks. Two techniques have been proposed in the literature to avoid integer spurious markings. The first one, considered in Silva et al. (1998) and Silva et al. (2011), avoids markings in which a trap is emptied by adding a polynomially calculable implicit place. Because a trap cannot be emptied in a discrete PN system, the avoided marking is spurious in the discrete system. The second technique (Fraca et al. 2014b) proposes to avoid a marking that empties a siphon by adding a place. However, it cannot assure that the avoided marking was spurious (otherwise stated, the added place is implicit). Thus, this technique can only be applied if it is previously known to be a spurious solution.

Among non-integer spurious markings which can be removed, those which are vertices of \(LRS({{\mathcal {N}}},{\boldsymbol {m}}_{0})\) are particularly interesting. Some classical works aim to remove the non-integer vertices of a polytope, such as the Gomory-Chvàtal cuts. Given a polytope on the reals, they cut the markings outside the integer hull of the polytope (Balas et al. 1996; Cornuejols 2012). This method could be used to remove undesired non integer spurious markings. Although Gomory cuts are tractable for a given set of equations, finding a good family of cuts in the general case requires further investigation (Cornuejols 2012).

We propose to implement some polynomial time cuts on the polytope defined by \(LRS({{\mathcal {N}}},{\boldsymbol {m}}_{0})\), considering the PN structure. Those cuts aim to avoid spurious markings, and they are obtained by means of implicit places which force some marking relations. We propose three different kinds of implicit places to avoid such non-integer vertices of the polytope: vertex cutting places avoid those vertices which are non-integer; marking truncation places are a particular case but more efficient to compute; enabling truncation places do not modify the set of reachable markings, but they can modify the firing amounts of the transitions.

A place p is said to be an implicit place if it does not constrain the behaviour of the discrete system.

Definition 1

Given a PN system \({\langle {{{\mathcal {N}}}, {\boldsymbol {m}}_{0}} \rangle }\):

  • A place p is implicit in \(\langle {{\mathcal {N}}}, \boldsymbol {m}_{0} \rangle \) if it is never the unique place that prevents the firing of a transition.

  • A place p is structural implicit in \({{\mathcal {N}}}\) if there exists m 0 for which p is implicit.

A characterization of the structural implicit places is given in Silva et al. (1998):

Proposition 1

Let \({{\mathcal {N}}} = {\langle {P \cup \{p\},T,\boldsymbol {Pre},\boldsymbol {Post}} \rangle }\) . Place p is structurally implicit iff (equivalently):

  1. 1.

    A y≥0 exists such that C[p,T] ≥ y T⋅C[P,T]

  2. 2.

    No x≥0 exists such that C[P,T]⋅x≥0 and C[p,T]⋅x<0

Here, we refer to concurrent implicit places, which preserve not only the firing sequences, but also the steps (Silva et al. 1998; García-Vallés and Colom 1999). The removal of a concurrent implicit place allows the timed performance measures to be preserved.

Proposition 2

Given a net system \({\langle {{{\mathcal {N}}},{\boldsymbol {M}}_{0}} \rangle }\) , and \({\langle {{{\mathcal {N}}}^{\prime },{\boldsymbol {M}}_{0}^{\prime }} \rangle }\) the same net system without place p, then p is a concurrent implicit place (García-Vallés and Colom 1999) if M 0 [p]>γ−1, where γ can be computed as:

$$\begin{array}{@{}rcl@{}} \gamma = & min\{{{\mathbf{y}}}^{T} \cdot {\boldsymbol{m}}_{0}^{\prime} + \mu | & {{\mathbf{y}}}^{T} \cdot \boldsymbol{C}^{\prime} \leq \boldsymbol{C}[p, T]\\ \ \ & \ & \ {{\mathbf{z}}}^{T} \cdot \boldsymbol{Pre}^{\prime}[P^{\prime}, {{p}^{\bullet}}] + \mu \cdot {{\mathbf{1}}}^{T} \geq \boldsymbol{Pre}[p, {{p}^{\bullet}}] \\ \ \ & \ & \ {{\mathbf{y}}} \geq {{\mathbf{z}}} \geq {{\mathbf{0}}}, \mu \leq 0 \} \end{array} $$
(10)

If p is implicit in \({\langle {{{\mathcal {N}}}, {\boldsymbol {m}}_{0}} \rangle }\) as a continuous system, then p is also implicit in \({\langle {{{\mathcal {N}}}, {\boldsymbol {m}}_{0}} \rangle }\) as a discrete system. Assume p k is not implicit in \(\langle \mathcal {N}, \boldsymbol {m}_{0}\rangle \) considered as a discrete system. Then, there exists a marking m reachable with discrete firings at which p k constraints the enabling of an output transition t. Since m is also reachable in the system as continuous, p k is not implicit in the continuous system either.

3.1 Vertex cutting place

The aim of this technique is to cut non-integer vertices of \(LRS({{\mathcal {N}}},{\boldsymbol {m}}_{0})\), that are not reachable on the discrete model. Let us explain the technique through an example, before introducing the method in a formal way.

Consider the example in Fig. 1a without place v. As discrete, it is deadlock-free and it has four reachable markings: M 0=(1,0,1,0,0), M 1=(0,1,0,3,0), M 2=(0,0,1,0,3), and M 3=(0,0,1,1,1). The polytope defined by \(LRS({{\mathcal {N}}},{\boldsymbol {m}}_{0})\) is the convex set defined by those vertices and (0,0,1,1.5,0). As continuous, the deadlock \({\boldsymbol {m}}_{d} = (0,0,1,1.5,0)\in LRS({{\mathcal {N}}},{\boldsymbol {M}}_{0})\) is reachable (by firing t 2 followed by 1.5t 3 from m 0). Thus, the deadlock-freeness property is lost. Marking m d is outside its “integer hull”, so it is not reachable in the discrete PN (in particular, \({\boldsymbol {m}}_{d} \not \in \mathbb {N}^{|P|}\)).

Fig. 1
figure 1

(a) The vertex cutting place v cuts the spurious deadlock m d =(0,0,1,1.5,0). (b) The marking truncation place q 4 does not cut m d

Full size image

Consider the marking m d which is a vertex and it is not reachable. Then, there exists at least two other markings which are vertices and in which at least one of the places which are empty at m d (i.e., p 1, p 2 and p 5) are marked (with a marking equal or greater than 1, in the discrete model), otherwise it would not be a vertex. Hence, we can assure that the following inequality holds for every discrete reachable marking: m[p 1]+m[p 2]+m[p 5]≥1. This inequality can be forced by the addition of a place v which is implicit in the discrete (but not in the continuous) PN: m[p 1]+m[p 2]+m[p 5]−m[v]=1. From this equation, place v is defined as C[v,T]=C[p 1,T]+C[p 2,T]+C[p 5,T], and m 0[v]=m 0[p 1]+m 0[p 2]+m 0[p 5]−1, as depicted in Fig. 1a. Place v, here denoted as vertex cutting place, adds the invariant m[p 1]+2⋅m[p 3]+m[p 4]+m[v]=3 to the net, and m d becomes not reachable in the CPN. In this example, the added place v leads to a continuous system which preserves the deadlock-freeness property of the original discrete one.

Definition 2

Vertex cutting place. Given a non-integer vertex m v , a vertex cutting place v is the place which forces the following relation:

$$\begin{array}{@{}rcl@{}} \sum\limits_{i | {\boldsymbol{m}}_{v}[p_{i}] = 0} {\boldsymbol{m}}[p_{i}] \geq 1. \end{array} $$

The obtained vertex cutting place v is implicit in the discrete PN and it cuts the marking m v in the continuous system.

More formally, given a PN system 〈P,T,Pre,Post;m 0〉 and a marking m v , the system \({\langle {P^{\prime },T^{\prime },\boldsymbol {Pre}^{\prime },\boldsymbol {Post}^{\prime }; {\boldsymbol {m}}_{0}^{\prime }} \rangle }\) resulting of adding vertex v can be obtained by Algorithm 1.

figure d

Checking if a given solution m v is a vertex of a polytope can be done in polynomial time (as explained in Appendix A). However, enumerating all the vertices of the polytope is computationally costly (Avis and Fukuda 1992).

Let us consider a spurious deadlock m d (the continuous enabling degree of all transitions at m d is 0; i.e., m d is a deadlock in the continuous PN). If m d is a vertex of \(LRS({{\mathcal {N}}}, {\boldsymbol {M}}_{0})\), it can be removed with the technique presented in this section. If m d is not a vertex of \(LRS({{\mathcal {N}}}, {\boldsymbol {M}}_{0})\), it must be a convex combination of two or more vertices of the \(LRS({{\mathcal {N}}}, {\boldsymbol {M}}_{0})\). Notice that the null components of m d are also null in such vertices, and that at least one of such vertices is not reachable (if every vertex is reachable, then every linear combination, and in particular m d , is also reachable (Silva and Recalde 2002)). Therefore, at least one of such vertices is a spurious deadlock that can be removed with the presented technique.

The repeated execution of this procedure, i.e., the removal of spurious deadlock vertices, reduces the size of \(LRS({{\mathcal {N}}}, {\boldsymbol {M}}_{0})\) and, therefore, produces a better approximation of the discrete PN.

3.2 Marking truncation places

This subsection introduces a particular class of vertex cutting places, which is called marking truncation places, that can be computed and added very efficiently. Because a marking of a discrete PN system belongs to \(\mathbb {N}^{|P|}\), a place p j will never have more tokens than its structural enabling bound S B(p j ). However, this bound can be overlooked by the continuous system.

The addition of an implicit place q j is proposed, which is a complementary place of p j which truncates the marking of p j to the highest possible integer, and consequently, it limits the firing of the transitions in ∙p j and \({{p_{j}}^{\bullet }}\) (in the continuous system) and avoids undesired markings.

Definition 3

Given a place p j , its marking truncation place q j is obtained as: Pre[q j ,T]=Post[p j ,T] and Post[q j ,T]=Pre[p j ,T]. Its initial marking is obtained as: m 0[q j ]=S B(p j )−m 0[p j ].

Given a PN system 〈P,T,Pre,Post;m 0〉, their marking truncation places can be added by Algorithm 2.

figure e

For example, consider the PN in Fig. 2a, which is also deadlock-free as discrete but not as continuous. The marking truncation place q 3 is added, which is complementary to p 3, whose initial marking is M 0[q 3]=⌊1.5⌋−0=1. It is implicit in the discrete system, but it modifies the \(LRS({{\mathcal {N}}},{\boldsymbol {m}}_{0})\). It avoids having more than 1 token in p 3, hence it avoids the spurious deadlock m d =(0,1,1.5,0), in which m d [p 3]=1.5 is higher than S B(p 3)=1. The resulting system is deadlock-free as continuous. Moreover, the addition of q 3, with m 0[q 3]=1, makes the timed approximation of the original system as MPN more accurate. The improvement is not significant when λ 1 =λ 2 (see first column of Table 1), but it is specially relevant when λ 1>λ 2 (see the second column of the table), because the steady state of the TCPN is near to m d .

Fig. 2
figure 2

(a) The marking truncation place q 3 removes the undesired spurious marking m d =(0,1,1.5,0). (b) With k<q<2⋅k, the enabling truncation place t p 1 improves the throughput approximation, but does not change \(RS_{{C}}({{\mathcal {N}}},{\boldsymbol {m}}_{0})\). If q=k, then t 1 suffers the BRP (see Section 4)

Full size image
Table 1 χ(t 1) of the PN in Fig. 2a, with different λ
Full size table

The addition of every marking truncation place to the system can be done in polynomial time (because computing S B(p) is polynomial). However, this technique does not always obtain the “integer hull” of the polytope. For example, consider again the PN system in Fig. 1b. The marking truncation place q 4 is added to limit the structural bound of p 4, denoted S B(p 4). However, m d is still reachable by the continuous PN by firing t 2,1.5t 3 from m 0 (the rest of places q j would not avoid it either), and the addition of the vertex cutting place is needed.

3.3 Enabling truncation places

Finally, the enabling truncation places do not modify the \(LRS({{\mathcal {N}}},{\boldsymbol {m}}_{0})\), but they limit the flow at a given marking if time is considered. They can have an effect on the throughput, even if all the S B(p) are integer (the marking truncation place would have no effect).

Analogously to the marking of a place, a transition t i will never be fired in an amount higher than its structural enabling bound S E B(t i ). The addition of an implicit place t p i is proposed. It would truncate the maximal possible firing of the transition to the highest possible integer.

Definition 4

Enabling truncation place. Given a transition t i , its enabling truncation place t p i is a self-loop place of transition t i whose initial marking is m 0[t p i ]=S E B(t i ).

Given a PN system 〈P,T,Pre,Post;m 0〉, their enabling truncation places can be added by Algorithm 3.

figure f

Consider the PN in Fig. 2b with k=5, q=8 and λ=(1,5). The structural enabling bound of t 1 is S E B(t 1)=⌊1.6⌋=1. Hence, an enabling truncation place t p 1 with initial marking equal to 1 is added (see place t p 1, drawn in grey colour). The throughput of t 1 in the discrete PN is χ M P N (t 1)=0.90. The concurrent implicit place t p 1 forces the continuous system to be more faithful to the original discrete system and produces the throughput χ T C P N+i m p l (t 1)=1.00, which is a better approximation than the throughput of the original continuous net system χ T C P N (t 1)=1.33. Only t p 1 has been added because place t p 2 would not affect to the behaviour of the continuous PN.

4 The bound reaching problem (BRP)

TCPN under ISS approximate reasonably well the behaviour of MPN when the population is relatively large, as pointed out in Section 2.3. However, the Bound Reaching Problem (BRP) identifies a particular but important situation in which the quality of the approximation may be significantly worse (Fraca et al. 2014a).

Definition 5

A transition t i in \({\langle {{{\mathcal {N}}},{\boldsymbol {M}}_{0}} \rangle }\) is said to suffer from the BRP if S E B(t i )=1. The set of transitions suffering from the BRP in a PN system \({\langle {{{\mathcal {N}}},{\boldsymbol {M}}_{0}} \rangle }\) is denoted as Bound Reaching Transition Set: B R T S={t i | S E B(t i )=1}.

The differences between discrete and continuous behaviour are due to the fact that synchronizations (arc weights and therefore joins) are strongly relaxed when the net system is fluidified. Consider transition t 1 in Fig. 2b with q=k (and without t p 1). Thus, S E B(t 1)=1. Seen as discrete, t 1 is only enabled when M[p 1]=k. However, as continuous, t 1 is enabled for any positive amount of tokens 0<m[p 1]≤k, regardless of the arc weight k.

Considering the net system as a MPN, the firing time distribution of t 1 from m follows an exponential probability function with parameter \(\lambda _{1} \cdot \lfloor \frac {{\boldsymbol {m}}[p_{1}]}{k} \rfloor \). After the first firing of t 1, only t 2 can be fired, and it keeps on firing until the k tokens are again at p 1. Then, t 1 becomes enabled again. If k increases, the probability of having k tokens in p 1 decreases, and also its steady state throughput. Its average cycletime is obtained from order statistics as \({\Theta } = \frac {1}{\lambda _{1}} + \frac {1}{\lambda _{2}} \cdot {\sum }_{i=1}^{k} \frac {1}{i}\), and its mean throughput is \(\frac {1}{\Theta }\), i.e., \( \chi _{MPN}(t_{1}) = \lambda _{2} / ({\sum }_{i=1}^{k}\frac {1}{i} + \frac {\lambda _{2}}{\lambda _{1}}) \).

Notice that χ M P N (t 1) is the product of a dimensionless coefficient depending on k and \(\frac {\lambda _{2}}{\lambda _{1}}\), multiplied by λ 2 that defines a time scale (time homothecy (Silva and Recalde 2002)). Thus, we can normalize λ 2=1, and the normalized χ M P N (t 1) depends on k and λ 1. The steady state throughput of t 1 for different values of k is shown in Table 2 for λ=(10,1).

Table 2 Throughput of t 1 in Fig. 2b, with k=q, and λ=(10,1)
Full size table

Considered as a TCPN, t 1 is enabled for any marking m[p 1]>0. Moreover, the firing of t 1, and hence the behaviour of the system, is not modified by k. The throughput of t 1 as a TCPN is time homothetic (i.e., its steady state flow is proportional to λ), and it is equal to: \(\chi _{TCPN}(t_{1}) = \lambda _{2} / (1 + \frac {\lambda _{2}}{\lambda _{1}})\).

Considering λ=(10,1), χ T C P N (t 1)=0.909 for any value of k. The continuous throughput coincides with the discrete one for k=1, but it provides a bad approximation for k>1 (see Table 2), which gets worse when k grows.

In order to overcome this lack of accuracy due to the BRP, different techniques can be investigated. They can range from fully continuous (Fig. 3a) to hybrid (Fig. 3b). A first possibility is to modify the flow of the continuous transition. For example, an “ad hoc” continuous flow estimation is explained inFraca et al. (2014a) as an alternative to ISS. However, it has some disadvantages such as no time homothecy.

Fig. 3
figure 3

Enabling degree of t 1 in Fig. 2b with q=k. (a) TCPN under ISS (continuous and differentiable flow); (b) Hybrid PN (see Fig.4a), t 1 discrete and approximately scaled arcs; (c) ρ-semantics (piecewise function, based on ISS)

Full size image

5 A new semantics to approach the bound reaching problem

The aim of this section is to propose an alternative fluidization technique to tackle the BRP. The resulting method will be a deterministic approach based on ISS.

Consider again the PN in Fig. 2b, with q=k. A key difference between the behaviour of the MPN and the TCPN under ISS is that in the MPN, t 1 can fire only when the k tokens are in p 1; while in the continuous case, it is not needed to “wait until the k tokens” are in p 1 to fire t 1.

In a TCPN, waiting until p 1 has k tokens would take infinite time. Hence, it makes sense to wait until some other smaller value, such as k−ρ (where ρ comes from “the rest”). This behaviour can be obtained by transforming p 1- t 1 (see Fig. 2b) to a subnet composed of \(p_{1}^{\prime }\), \(t_{1}^{\prime }\), p a , p b , t i m m (see Fig. 4b), such that \(t_{1}^{\prime }\) is not enabled for “the first” k−ρ tokens, and it is enabled for higher amounts.

Fig. 4
figure 4

(a) Hybrid PN system in which \(t_{1}^{\prime }\) is discrete (black transition) and t 2 is continuous, arc weights are modified to \(k^{\prime }\), (b)Transformation of the PN in Fig. 2b, with q=k. Transitions t 1 and t 2 are continuous under ISS, and t i m m is immediate (thin black transition)

Full size image

Immediate transitions are difficult to handle in TCPN (Recalde et al. 2006). A first approximation can be to consider immediate transitions as timed ones which are several orders of magnitude faster than the other transitions (for example, λ i m m =10000 if λ=(10,1)). However, this has some disadvantages: If λ i m m is relatively not very high, then the steady state might not be the desired one; while for very high relative values of λ i m m , stiffness problems would appear.

In this particular construction, we can abstract the structure given by \(p_{1}^{\prime }\), \(t_{1}^{\prime }\), p a , p b , t i m m by a unique transition which compacts the desired behaviour, resulting in the denoted ρ−s e m a n t i c s, based on ISS (seeFraca et al. (2014a) and Fig. 3c for more details). Its flow is given by:

$$ f_{1}{=} \lambda_{1} \cdot \left\{ \begin{array}{ll} 0 & \text{ if \small{\({\boldsymbol{m}}[p_{1}] \leq \boldsymbol{Pre}[p_{1},t_{1}]\)-\(\rho\)}} \\ \frac{{\boldsymbol{m}}[p_{1}]\text{-}(\boldsymbol{Pre}[p_{1},t_{1}]\text{-}\rho)}{\rho} & \text{ otherwise} \end{array} \right. $$
(11)

The transient flow of t 1 is still a continuous function but piecewise defined, which introduces certain “hybridization” in the behaviour of the transition (see Fig. 3c). If ρ tends to 0, the flow tends to a step function of values from 0 to λ 1, while if ρ tends to Pre[p 1,t 1], the flow tends to ISS. The computation done by this approach is local to transition t 1 (the transition in BRTS), and it is simple and fast to calculate. It inherits some basic properties of ISS, such as homothetic monotonicity w.r.t. the firing rates.

With the proposed ρ-semantics, the throughput of the system can be “tuned” from 0 (when ρ∼ 0) to the throughput of the TCPN (when ρ is “equal” to Pre[p 1,t 1]). The challenge is how to select ρ to approximate the steady state throughput of the MPN.

Let us first compute ρ for the PN in Fig. 2b with q=k, and then apply that heuristics on any PN system with a similar structure. The throughput of t 1 at the steady stated can be symbolically computed, considering ρ-semantics for the flow of t 1 (i.e., Eq. 11, with ρ as a parameter), and ISS for t 2 (i.e., Eq. 8). Because of its p-semiflow, it holds m[p 1]+m[p 2]=k. At the steady state, the equality C⋅f s s =0 must be satisfied, and hence χ ρ (t 2)=k⋅χ ρ (t 1). From these equalities, the value of χ ρ (t 1) for the PN in Fig. 2b with q=k is:

$$ \chi_{\rho}(t_{1}) = \lambda_{2} \cdot \frac{\rho}{k + \rho \cdot \frac{\lambda_{2}}{\lambda_{1}}} $$
(12)

Forcing χ M P N (t 1)=χ ρ (t 1), an analytical formula for the value of ρ is obtained, that fortunately depends only on k (not on λ):

$$ \rho = \frac{k}{{\sum}_{i=1}^{k}\frac{1}{i}} $$
(13)

The PN model in Fig. 2b can be seen as a simplification of any net system with analogous structure. Hence, it will be possible to use the heuristic formula (13) in other transitions suffering from the BRP such that | ∙t|=1.

6 Generalization of the ρ-semantics to join transitions

As introduced in Section 5, the ρ-semantics has been designed for transitions with a unique input arc. The aim of this section is to generalize it to transitions with more than one input place (rendez-vous or join transitions).

First, linear enabling functions for join transitions are presented. Then, the addition of the representative places is introduced. Finally, the application of the ρ-semantics to join transitions is proposed.

6.1 Linear enabling functions

Linear Enabling Functions (LEF) were introduced for discrete PN in Teruel et al. (1993) and Briz et al. (1994) to characterize the enabling of a transition by a single linear expression.

The enabling of a transition t i can be represented with a single LEF if every p∈ ∙t i except at most one (denoted as π), satisfies the equality S B(p)=Pre[p,t i ], i.e,

$$ \exists \pi\in {\,\!^{\bullet{t_{i}}}} \text{ s.t. } \forall p \in \{{\,\!^{\bullet{t_{i}}}}\setminus\pi\}, SB(p) = \boldsymbol{Pre}[p,t_{i}] $$
(14)

A particular case appears if every place p∈ ∙t i satisfies S B(p)=Pre[p,t i ]. If S B(p)>Pre[p,t i ] holds for more than one of its input places p, its enabling cannot be directly represented by a single LEF, and some previous transformations of the PN should be done (see (Teruel et al. 1993)).

Given a transition t i which holds Eq. 14 it will be enabled when:

$$ {\boldsymbol{M}}[\pi] + SB(\pi) \cdot \underset{p\in \{{\,\!^{\bullet{t_{i}}}}\setminus\pi\}}{\sum} {\boldsymbol{M}}[p] \geq \boldsymbol{Pre}[\pi,t_{i}] + SB(\pi) \cdot \underset{p\in \{{\,\!^{\bullet{t_{i}}}}\setminus\pi\}}{\sum} \boldsymbol{Pre}[p,t_{i}] $$
(15)

Consider the PN in Fig. 5a (without the grey place, r 1). Transition t 1 holds Eq. 14 with π=p 6 (because S B(p 6)=5>Pre[p 6,t 1]=2, { ∙t 1∖π}={p 4}, and S B(p 4)=Pre[p 4,t 1]=2). The enabling of t 1 (in the discrete system) is given by: M[p 6]+S B(p 6)⋅M[p 4] ≥ Pre[p 6,t 1]+S B(p 6)⋅Pre[p 4,t 1].

Fig. 5
figure 5

(a)The grey place r 1 is the representative place of transition t 1. The ρ-semantics is applied to transition t 1. (b) Steady state throughput of t 1, with λ=(10,1,1,1,1)

Full size image

6.2 Representative places for join transitions

The LEF of a discrete transition can be represented in the PN system with an implicit place which is representative of its enabling (Briz et al. 1994).

Given a PN system \({\langle {{{\mathcal {N}}},{\boldsymbol {M}}_{0}} \rangle }\) which satisfies (14), a representative place r i can be added to the system, which is computed as a linear non-negative combination of the places in ∙t i . Place r i is built as:

$$ \boldsymbol{C}[r_{i},T] = \boldsymbol{C}[\pi,T] + SB(\pi) \cdot \underset{p\in\{{\,\!^{\bullet{t_{i}}}}\setminus\pi\}}{\sum} \boldsymbol{C}[p,T] $$
(16)

And its initial marking is computed as:

$$ {\boldsymbol{M}}_{0}[r_{i}] = {\boldsymbol{M}}_{0}[\pi] + SB(\pi) \cdot \underset{p\in\{{\,\!^{\bullet{t_{i}}}}\setminus\pi\}}{\sum} {\boldsymbol{M}}_{0}[p] $$
(17)

Consider again t 1 in Fig. 5a. The representative place r 1 is added, computed as C[r 1,T]=C[p 6,T]+S B(p 6)⋅C[p 4,T], where S B(p 6)=5 (see the grey place r 1 in Fig.5a). Its initial marking is computed as M 0[r 1]=M 0[p 6]+S B(p 6)⋅M 0[p 4]=0. In general, the added place r i (the marking of r i ) is a non-negative linear combination of the places in ∙t i (their markings). Hence, r i will never be the unique place constraining the enabling degree of t i , and it is implicit in the discrete and the continuous systems.

The original places in ∙t i become implicit in the discrete PN system when r i is added. However, they do not become implicit in the continuous one. For example, once the implicit place r 1 has been added in Fig. 5a, p 4 and p 6 become implicit in the discrete net system. However, \({\boldsymbol {m}}_{1}^{\prime } = (3,0,0,0,1,1,0)\) is reachable in \({\langle {{{\mathcal {N}}},{\boldsymbol {M}}_{0}} \rangle }\), and the enabling degree of t 1 is restricted by p 4 at \({\boldsymbol {m}}_{1}^{\prime }\) (and not by r 1). Analogously, place p 6 does not constrain the enabling degree of t 1 in the reachable marking \({\boldsymbol {m}}_{2}^{\prime } = (2,0,0,1,3,0,5)\). Hence, p 4 is not implicit in the continuous system and p 4, p 6 cannot be removed.

6.3 Generalization of the ρ-semantics

The flow of the join transition t i is defined by using the ρ-semantics for place r i , and ISS for the rest of the places in ∙t i .

The value of ρ i is computed from ρ as defined in Eq. 13. If place r i was obtained as a linear combination of those in ∙t i , then ρ i is obtained with the same linear combination of ρ(Pre[p i ,t j ]) for the places p j ∈ ∙t i , where ρ(Pre[p i ,t j ]) is computed from Eq. 13, with k=Pre[p i ,t j ].

Given a representative place r i which has been obtained as \(\boldsymbol {C}[r_{i},T] = \boldsymbol {C}[\pi ,T] + SB(\pi ) \cdot {\sum }_{p\in \{{\,\!^{\bullet {t_{i}}}}\setminus \pi \}} [p,T]\), then ρ i is obtained as follows:

$$\begin{array}{@{}rcl@{}} \rho_{i} = \rho(\text{\small{\(\boldsymbol{Pre}[\pi,t_{i}]\)}}) + SB(\pi) \cdot {\sum}_{p\in\{{\,\!^{\bullet{t_{i}}}}\setminus\pi\}} \rho(\text{\small{\(\boldsymbol{Pre}[p,t_{i}]\)}}) = \\ \frac{\boldsymbol{Pre}[\pi,t_{i}]}{{\sum}_{n=1}^{\boldsymbol{Pre}[\pi,t_{i}]} \frac{1}{n}} + SB(\pi) \cdot \vspace{-12pt} {\sum}_{p\in\{{\,\!^{\bullet{t_{i}}}}\setminus\pi\}} \vspace{-12pt} \frac{\boldsymbol{Pre}[p,t_{i}]}{{\sum}_{n=1}^{\boldsymbol{Pre}[p,t_{i}]} \frac{1}{n}} \vspace{16pt} . \end{array} $$
(18)

The flow of the transition (defined in Eq. 11) is generalized below to join transitions, in which an analogous term is used for the representative place, and ISS is used for the rest of the places in ∙t i :

$$ f_{i}{=} \lambda_{i} \cdot \left\{ \begin{array}{ll} 0 & \text{ if \small{\({\boldsymbol{m}}[r_{i}] \leq \boldsymbol{Pre}[r_{i},t_{i}]\)-\(\rho_{i}\)}} \\ min \{\frac{{\boldsymbol{m}}[r_{i}]\text{-}(\boldsymbol{Pre}[r_{i},t_{i}]\text{-}\rho_{i})}{\rho_{i}}, \underset{p\in {\,\!^{\bullet{t_{i}}}}}{min} \{\frac{{\boldsymbol{m}}[p]}{\boldsymbol{Pre}[p,t_{i}]} \} \} & \text{ otherwise} \end{array} \right. $$
(19)

For example, consider transition t 1 in the PN in Fig. 5a. In this case, ∙t 1={p 1,p 2}, so | ∙t 1|>1 and the ρ-semantics cannot be directly applied. The first step is to add the representative place r 1 (see Section 6.2). Then, the value of ρ 1 can be obtained from Eq. 18. Finally, the ρ-semantics proposed in Eq. 19 can be applied to t 1. Considering λ=(10,1,1,1,1), the ρ-semantics (χ ρ (t 1)=0.41, see the Table in Fig. 5b) gives a better approximation than the TCPN (χ T C P N (t 1)=0.484) to the original MPN (χ M P N (t 1)=0.396).

The ρ-semantics has been presented here for join transitions, eventually with weights in the arcs. However, the behaviour of those transitions in which joins and choices are combined requires further investigation.

7 Case study

The aim of this section is to apply the techniques presented in this paper to an example from the literature. The Petri net example shown in Fig. 6 is obtained from Bordbar et al. (2000). It represents a supervisory control system for a distributed manufacturing process.

Fig. 6
figure 6

Case study. Petri net which models a supervisory control system (obtained from Bordbar et al. (2000))

Full size image

In Bordbar et al. (2000), the system is modelled with UML, and then a discrete PN system is derived. The system represents a production line process, in which two components interact. The left part of the Petri net (with places and transitions labelled by B) represents a belt, while the right part represents some film. Both parts are mutually synchronized.

In this work, we modify the production line, allowing the system to produce k jobs at the same time. In order to obtain that, we allow the belt to hold k jobs, so we modify the initial marking of B o u t to k. These jobs will be synchronized in transition B n e w , so also the weight of the arcs around this transition are modified to k. Moreover, k jobs will be wrapped by using the film (right part of the figure) at the same time. The k tokens in F o u t are synchronized in transition F n e w .

Let us consider the computation of the steady state throughput of transition B n e w . It can be efficiently done for low values of k for the discrete PN, however, the state explosion problem raises for bigger values of k. For example, the Markov chain obtained for k=1 has 16 states, for k=3 it has 673 states, and for k=5 it grows to 7322 states. It grows exponentially for bigger values of k. Hence, the fluidization of the system is interesting in this case.

Consider a small value of k such as k=3, and λ=(1,1,1,1,10,1,1,1,1,10). In this case, χ S P N (B n e w ) = 0.356 for the MPN. This value is not well approximated by the continuous PN, χ I S S (B n e w ) = 0.714, but it is well approximated by applying the ρ-semantics to transitions B n e w , in which the obtained throughput is χ ρ (B n e w )= 0.398. A relative error (computed as |χ S P N −χ ρ |/χ S P N ) of 11.8% is obtained. This result was obtained in 3.32 seconds.

Moreover, it is not only a good approximation of small populations, but also when the parameter k grows, dealing to ’relatively small’ populations. Consider for example k=100, in which χ S P N (B n e w )=6.010. The approximation given by the ρ-semantics (χ ρ (B n e w )=4.774) is much better than the value obtained by the continuous PN under ISS (χ I S S (B n e w )=23.810). See Table 3 for an overview of results for the case study.

Table 3 Steady state throughput of transition F n e w in the PN in Fig. 6
Full size table

8 Conclusions

Fluidization aims to reduce the analysis complexity of discrete PN models. Unfortunately, some logical and performance properties of the discrete PN may be lost by fluidization, specially when the system population is “relatively” small. In this paper, two sorts of techniques have been proposed to improve the fluid approximation of the discrete model.

The relaxation of the formalism entails the reachability of some spurious markings (i.e., non reachable in the discrete PN) in the continuous model. The removal of spurious markings, and in particular the removal of spurious deadlocks, in the fluidified model has been proposed. The technique is based on the addition of cutting places which are implicit in the discrete PN (they do not modify the behaviour of the original discrete system) but not in the continuous one. This yields a more faithful approximation to the original discrete system, for both the untimed and timed interpretations.

Moreover, we have studied the Bound Reaching Problem (BRP), which may appear in timed systems, and that causes the throughput of the original discrete PN system and the continuous approximation to be particularly different. A new method based on ISS, which is denoted ρ-semantics, has been proposed to tackle the BRP. Such novel semantics inherits basic properties from ISS such as time homothecy, but not marking homothecy. It is specially accurate when it is applied to transitions with a single input place. Moreover, the technique has been generalized to join transitions by means of representative places.