Basic Server Semantics and Performance Monotonicity of Continuous Petri Nets

Abstract

Continuous Petri nets were introduced as an approximation to deal with the state explosion problem which can appear in discrete event models. When time is introduced, the flow through a fluidified transition can be defined in many ways. The most used in literature are constant and variable speed (David and Alla, Discrete, continuous and hybrid Petri nets, Springer-Verlag, 2005), which can be seen as some kind of finite and infinite server interpretations of the transitions behavior, and derived from stochastic (discrete) Petri nets (Silva and Recalde, Annu Rev Control 28(2):253–266, 2004). In this paper we will compare the results obtained with both relaxations for the broad class of mono-T-semiflow reducible nets, and prove that, under some frequently true conditions, infinite server semantics offers a throughput which is closer to the throughput of the discrete system in steady state. In the second part, it will be proved that the throughput of mono-T-semiflow reducible net systems is monotone with respect to the speed of the transitions and the initial marking of the net.

1 Introduction

Petri nets (PNs) are a well-known formalism to deal with discrete event systems (DiCesare et al. 1993). The state explosion problem appears frequently in such systems, making the enumerative analysis methods inapplicable in many practical cases. Fluidification is a classical approximation technique that relaxes the description of the system by removing the integrality constraints. Applying this idea to discrete PNs, the firing of transitions is not limited to natural numbers but to positive real numbers leading to continuous Petri nets (contPNs) (David and Alla 2005; Silva and Recalde 2002).

In the last years, contPNs have been used in many applications in which the number of clients is relatively big. The main application has been in manufacturing systems (Lefebvre 1999; Amrah et al. 1998; Allam and Alla 1998) but have been used also in traffic systems (Julvez and Boel 2005) or supply chains (Dotoli et al. 2008), for example. Fluid models may be studied by means of net based structural analysis techniques (Júlvez et al. 2005; Balduzzi et al. 2000).

As in the discrete case, contPNs can be autonomous (untimed) or can have time associated with the transitions or places, namely timed contPNs. In the literature, in the continuous case, timing is mainly associated to transitions and two basically different ways of defining their firing are often used: finite server semantics (or constant speed) and infinite server semantics (or variable speed) (David and Alla 2005; Silva and Recalde 2002, 2004).

For discrete PNs infinite server semantics is more general, since it can simulate finite server semantics (Ajmone et al. 1995). However, the continuous approximation of this model under infinite server semantics is not equivalent to using finite server semantics in the original fluidified model. In the continuous case the two semantics are in fact related to conceptually and technically different relaxations of the model. Since these two semantics are different, the immediate question is, given a net system, which one is better? Up to now, the first reference to this problem we were able to find in the literature is a remark in Alla and David (1998), where the authors mention having observed that in several cases infinite server semantics provides a very accurate approximation of discrete PNs.

One of the goals of this paper is to provide some results about the use of these semantics. In general, is shown that it is not possible to say that one of them is always better than the other. Hence, we will concentrate on a subclass of nets, hopefully with a very significant modeling power from a practical point of view. The subclass is called mono-T-semiflow reducible (Júlvez et al. 2005, 2006). Focusing on live and bounded systems, this class includes mono-T-semiflow nets (Júlvez et al. 2005) and equal conflict nets (Teruel and Silva 1996) (thus free-choice and choice-free (Teruel et al. 1997)). We will prove that for mono-T-semiflow reducible nets infinite server semantics provides a throughput which is closer to the throughput of the discrete system in steady state, under quite conditions in practice.

Another good indicator of the practical interest of a class of net models is the kind of properties it verifies. In the last part of the paper monotonicity of the throughput w.r.t. the firing speed of transitions and the initial marking is studied. It is proved that under a quite general condition the class of mono-T-semiflow reducible nets enjoys these monotonicity properties. This means, for example, that if a machine is replaced by a faster one or more resources are available, the production rate will never decrease.

A purely structural property that will be necessary to check is whether the places that restrict the firing of transitions in the steady state contain the support of a P-semiflow. Two algorithms are presented for this.

The paper is organized as follows: in Section 2 basic definitions of timed contPN are given. In particular, the procedures to compute the evolution of continuous net systems under finite and infinite server semantics are recalled. Section 3 is devoted to the comparison and a more in depth study of the two semantics, concentrating on the class of mono-T-semiflow reducible nets. Sufficient conditions that guarantee steady state performance monotonicity w.r.t. the speed of transitions and w.r.t. the initial marking are proved in Section 4. Two algorithms to check structural properties sufficient for monotonicity are shown in Section 5. A manufacturing system is taken as case study in Section 6 and it is shown how the previous results can be used for its analysis. Some conclusions are given in Section 7.

2 Preliminaries

2.1 Untimed contPNs

Definition 1

A contPN system is a pair $\langle\mathcal{N} ,\boldsymbol{m_0}\rangle$, where: $\mathcal{N} = \langle P,T,\boldsymbol{Pre},\boldsymbol{Post}\rangle$ is a net structure (with set of places P, set of transitions T, the pre and post incidence matrices $\boldsymbol{Pre}, \boldsymbol{Post} : P \times T \to \mathbb{N}$) and $\boldsymbol{m_0}$ is the initial marking.

The token load of the place p _i at marking $\boldsymbol{m}$ is denoted by m _i and preset and postset of a node X ∈ P ∪ T are denoted by ^∙ X and X ^∙, respectively.

A transition t _j  ∈ T is enabled at $\boldsymbol{m}$ iff $\forall p_i \in \,\!^\bullet{t_j}$, m _i  > 0 and its enabling degree is $enab(t_j,\boldsymbol{m}) = \min \limits_{p_i \in \,\!^\bullet{t_j}} \left\{ \frac{m_i}{\boldsymbol{Pre}(p_i,t_j)} \right\}$. An enabled transition t can fire in any real amount $0 < \alpha < enab(t,\boldsymbol{m})$ leading to a new marking $\boldsymbol{m'} = \boldsymbol{m} + \alpha \boldsymbol{C}(\cdot,t)$, where $\boldsymbol{C} = \boldsymbol{Post} - \boldsymbol{Pre}$ is the token-flow matrix. If $\boldsymbol{m}$ is reachable from $\boldsymbol{m_0}$ through a finite sequence σ, a state (or fundamental) equation can be written: $\boldsymbol{m} =\boldsymbol{m_0} +\boldsymbol{C}\cdot\boldsymbol{\sigma}$, where $\boldsymbol{\sigma}\in\mathbb{N}^{|\mathit{T}|}$ is the firing count vector.

A contPN is bounded when every place is bounded ($\forall p \in P,\exists b{\!\!_{p}} \in \mathbb{R}_{\geq 0}$ with m(p) ≤ b _p at every reachable marking $\boldsymbol{m}$). It is live when every transition is live (it can ultimately occur from every reachable marking).

Right and left non negative annullers of the token flow matrix $\boldsymbol{C}$ are called T- and P-semiflows, respectively. If non negativity is not required, the annullers are called T- and P-flows. When $\boldsymbol{y} \cdot \boldsymbol{C}=0$, $\boldsymbol{y}>0$ the net is said to be conservative, and when $\boldsymbol{C}\cdot\boldsymbol{x}=0$, $\boldsymbol{x}>0$ the net is said to be consistent.

Two transitions t ₁ and t ₂ are said to be in conflict relation if $\,\!^\bullet{t_1} \cap \,\!^\bullet{t_2}\neq \emptyset$. Two transitions t ₁ and t ₂ are in continuous equal conflict (CEQ) relation when there exists k > 0 such that $\boldsymbol{Pre}[P, t_1] = k \cdot \boldsymbol{Pre}[P, t_2] \neq 0$.

2.2 Timed contPNs

Under any timed interpretation of the net model, the fundamental equation depends on time: $\boldsymbol{m}(\tau) = \boldsymbol{m_0} + \boldsymbol{C} \cdot \boldsymbol{\sigma}(\tau)$. Differentiating with respect to it, the following equation is obtained: $\dot{\boldsymbol{m}}(\tau) = \boldsymbol{C} \cdot \dot{\boldsymbol{\sigma}}(\tau)$. The derivative of the firing sequence will be called the (firing) flow of the timed model: $\boldsymbol{f}(\tau)=\dot{\boldsymbol{\sigma}}(\tau)$.

Different definitions of the flow of continuous timed transitions have been given, the two most important being finite server (or constant speed) and infinite server (or variable speed) (Alla and David 1998; Silva and Recalde 2002).

2.2.1 Preliminaries for the server semantics

In general, transitions are interpreted as stations (in QN terminology), where servers and clients meet. Thus, the more appropriate firing relaxation depends on the relative number of servers and clients in the discrete model we want to approximate. Assuming, qualitatively speaking, that there may be “many” or “few” of each one of them, fluidification can be considered for clients, for servers or for both. Table 1 represents the four theoretically possible cases. If the number of clients is “small” (Few-Few and Few-Many in Table 1), the system is not really loaded, the transitions “should” remain discrete and the fluidification may be unsuitable. If there are many clients and a few servers (Many-Few) the relaxation is only at the level of clients, and finite server semantics can provide a good approximation. On the other hand, in the case of many clients and many servers (Many-Many), a continuous model with infinite server semantics seems reasonable, since there are so many servers that there is no need to make them explicit.

Table 1 On the fluidification of a transition (Silva and Recalde 2004)

It is important to notice that finite server semantics corresponds at conceptual level to a hybrid behavior: fluidification is applied only to clients, while servers are kept as discrete, counted as a finite number (used to define the bound of firing speed of the transition). On the other hand, infinite server semantics really relaxes clients and servers, being the firing speed driven by the enabling degree of the transition, like for stochastic-markovian (discrete) PNs.

2.2.2 Finite server semantics

Under finite server (constant speed), each transition t _j has associated a real positive number, λ _j , called maximal firing speed. If the markings of the input places of the transition are strictly greater than zero (strongly enabled), its flow will be constant, equal with this value (all servers working at full speed). Otherwise (weakly enabled), the flow will be the minimum between its maximal firing speed and the total input flow to the places with zero marking. With this definition, λ _j represents the product of the number of servers in the transition and their speed. The instantaneous flow of a transition t _j is given by:

$$\label{eq-flowfin} f_j=\left\{\begin{array}{l} \lambda_j, \text{ if } \not\exists p_i \in \,\!^\bullet{t} \text{ with } m_i=0 \\ \min \left\{ \min \limits_{p_i \in \,\!^\bullet{t}|m_i=0} \left\{ \displaystyle\sum\limits_{t' \in \,\!^\bullet{p_i}} \frac{f[t'] \cdot Post[t',p_i]}{Pre[p_i,t_j]} \right\}, \lambda_j\right\} \text{ otherwise} \end{array} \right. $$

(1)

Observe that Eq. 1 is not defining completely the flow of a contPN under finite server semantics. In the case of conflict, a resolution policy should be specified, otherwise many solutions of the flows are possible (Balduzzi et al. 2000). Therefore, this semantics is non-deterministic as defined in Eq. 1.

2.2.3 Infinite server semantics

Under infinite server (variable speed) the flow of a transition t _j is:

$$\label{eq-flowinf} f_j=\lambda_j \cdot enab(t_j,\boldsymbol{m}) = \lambda_j \cdot \min \limits_{p_i \in \,\!^\bullet{t_j}} \left\{ \frac{m_i}{\boldsymbol{Pre}[p_i,t_j]} \right\} $$

(2)

The enabling degree of the transition t _j represents the number of active servers for that transition at $\boldsymbol{m}$. The flow will be the number of active servers times the work each one does per time unit (λ _j ). Notice that the number of active servers in a transition (station) depends only on the marking of its input places.

Definition 2

(Mahulea et al. 2008) A configuration $\mathcal{C}_i$ of $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ at $\boldsymbol{m}$ is a set of (p,t) arcs, one per transition, such that p ∈ ^∙ t and

$$ \boldsymbol{f}[t]=\boldsymbol{\lambda}[t]\cdot \frac{\boldsymbol{m}[p]}{\boldsymbol{Pre}[p,t]}. $$

The number of configurations is upper bounded by: $\prod \limits_{t \in T} |\,\!^\bullet{t}|$. In general, we are interested in the set of places that limit the enabling degree. So, associated to a configuration $\mathcal{C}_i$, we define the corresponding P-configuration, the set of places from which there exist at least one output arc belonging to $\mathcal{C}_i$. Formally, the P-configuration of $\mathcal{C}_i$, is:

$$ P-\mathcal{C}_i=\{ p{\!_{j}} | \exists (p{\!_{j}},t_k) \in \mathcal{C}_i\}.$$

A contPN system evolves and may reach a steady state (i.e. a marking such that $\dot{\boldsymbol{m}}(\tau)=0$). The (P-)configuration of the steady state marking will be called the steady state (P-)configuration. This steady state marking, if it exists, has to fulfill certain conditions: the flow it defines has to be a T-semiflow (because $\dot{\boldsymbol{m}}=\boldsymbol{C}\cdot \boldsymbol{f}=\boldsymbol{0}$), and has to verify the equations defined by the P-flows (see Mahulea et al. (2008) for more details). The solutions of these equations represent all the possible ways of distributing the tokens of the P-flows so that the system remains on that marking. However, it may happen that several markings fulfill these conditions. We will refer to all these possible steady states markings as possible equilibrium markings. All their (P-)configurations will be called possible equilibrium (P-)configurations.

Through this paper we will assume that the net system will reach a steady state after some time, and try to derive some results about this steady state. However, it may happen that the system does not approach to steady state, even being a mono-T-semiflow net system.

We want to stress that under both semantics, the timed system is defined by the untimed net system and a positive vector, $\boldsymbol{\lambda}$ (i.e. here it is assumed that there are no immediate transitions), although $\boldsymbol{\lambda}$ has a different meaning under each semantics: it is the firing rate of a transition in the case of infinite server semantics, and it is a maximal firing speed in the case of finite server semantics (the product of the number of servers and the firing rate of one server).

2.3 Mono-T-semiflow reducible nets

As in queueing network theory, the visit ratio of transition t _j with respect to t _i , $\boldsymbol{v}^{(i)}[t_j]$, is the average number of times t _j is visited (fired) for each visit to (firing of) the reference transition t _i in steady-state. Mono-T-semiflow reducible nets is a class for which the visit ratio vector depends only on the net and the firing rate vector, but not on $\boldsymbol{m_0}$, i.e., $\boldsymbol{v}^{(i)}=\boldsymbol{v}^{(i)}(\mathcal{N},\boldsymbol{\lambda})$ (Júlvez et al. 2005).

Definition 3

 (Júlvez et al. 2005) $\langle\mathcal{N} ,\boldsymbol{\lambda} \rangle$ is a mono-T-semiflow reducible net if it is consistent, conservative and the following system has a unique solution (its visit ratio):

$$ \left\{ \begin{array}{ll} \boldsymbol{C} \cdot \boldsymbol{v}^{(1)}=\boldsymbol{0} \\ \displaystyle\frac{\boldsymbol{v}^{(1)}[t_i]}{\boldsymbol{Pre}[p,t_i]\cdot \lambda[t_i]} = \displaystyle\frac{\boldsymbol{v}^{(1)}[t_j]}{\boldsymbol{Pre}[p,t_j]\cdot \lambda[t_j]} & \forall t_i,t_j \text{ in CEQ relation,} \ \forall p \in \,\!^\bullet{t_i} \\\noalign{} \boldsymbol{v}^{(1)}[t_1]=1 \end{array}\right. $$

(3)

Based on the above definition, an immediate result is:

Proposition 1

Let $\langle \mathcal{N}, \boldsymbol{\lambda}_1, \boldsymbol{m}_0 \rangle$ be a mono-T-semiflow reducible net system, and $\boldsymbol{\lambda}_2$ a rates vector such that $\boldsymbol{\lambda}_1$ and $\boldsymbol{\lambda}_2$ keep the same proportion in continuous equal conflicts, i.e., for every pair t _i ,t _j in CEQ relation $\boldsymbol{\lambda}_1[t_i]/\boldsymbol{\lambda}_1[t_j]= \boldsymbol{\lambda}_2[t_i]/\boldsymbol{\lambda}_2[t_j]$ . The timed contPN systems $\langle \mathcal{N}, \boldsymbol{\lambda}_1, \boldsymbol{m_0} \rangle$ and $\langle \mathcal{N}, \boldsymbol{\lambda}_2, \boldsymbol{m_0} \rangle$ have the same visit ratio vector: $\boldsymbol{v}^{(i)}(\mathcal{N},\boldsymbol{\lambda}_1) = \boldsymbol{v}^{(i)}(\mathcal{N},\boldsymbol{\lambda}_2)$.

Through this paper, if $\boldsymbol{\lambda}_1$, $\boldsymbol{\lambda}_2$ satisfy the above condition, we will say that they are visit ratio preserving. This can be extended to sets of rates.

Example 1

The mono-T-semiflow reducible net in Fig. 1 represents a queuing network, adapted from Cassandras (1993). It has four minimal T-semiflows: $\boldsymbol{x_1}=t_1+t_2+t_3$, $\boldsymbol{x_2}=t_1+t_2+t_4+t_6+t_8+t_{11}$, $\boldsymbol{x_3}=t_6+t_8+t_{10}$ and $\boldsymbol{x_4}=t_1+t_2+t_5+t_7+t_9+t_{12}$. The values of λ ₃, λ ₄ and λ ₅ will determine the splitting of the flow entering in p ₃ (because t ₃, t ₄ and t ₅ are in free-choice) while λ ₁₀ and λ ₁₁ will define the splitting of the flow entering in p ₁₁. For example, for the particular value of $\boldsymbol{\lambda}=\boldsymbol{1}$, the visit ratio vector normalized for t ₃ is $\boldsymbol{v}^{(3)} = [3,3,1,1,1,2,1,2,1,1,1,1]^T$ (the addition of the minimal T-semiflows).

Fig. 1

Continuous mono-T-semiflow reducible net system, adapted from a queuing network in Cassandras (1993). In fact, it is an EQ net; {t ₃,t ₄,t ₅} and {t ₁₀,t ₁₁} are equal conflicts

3 Finite server semantics vs. infinite server semantics

3.1 Motivation example

Let us consider the contPN system in Fig. 2, modeling a shared resource (place p ₆) among two processes and let us see its evolution with both continuous approximations: finite and infinite server semantics. Let $\boldsymbol{\lambda}=[1,2,1,1,0.5]$. Observe that in this case the behavior of the discrete PN is the same for finite and infinite server semantics because the (single) servers are implicit in the model. On the contrary, continuous finite and infinite server semantics do not lead to the same values.

Fig. 2

ContPN system used in Section 3.1

Infinite server semantics

First, observe that p ₂ is implicit (i.e. it is never the only place to constrain the firing of t ₄ (DiCesare et al. 1993)) and its marking verifies: m ₂(τ) = m ₄(τ) + m ₆(τ). Hence, f ₄ =  min {m ₂,m ₆} = m ₆, and so only two configurations can govern the system evolution. At τ = 0, m ₃ < m ₆, therefore the evolution is governed by the configuration $\mathcal{C}_1=\{(p_1,t_1), (p_3,t_2), (p_4,t_3),$ (p ₆,t ₄), (p ₅,t ₅)}. The linear system in $\mathcal{C}_i$ will be called Σ _i .

The evolution of the contPN system is sketched in Fig. 3. It evolves according to Σ₁ until τ ≃ 1.14 t.u. when m ₃(τ) = m ₆(τ). At that point, a switch occurs and the new governing configuration is: $\mathcal{C}_2=\{(p_1,t_1),$ (p ₆,t ₂), (p ₄,t ₃), (p ₆,t ₄), (p ₅,t ₅)}. The system evolves according to Σ₂ and reaches the steady state marking [0.4,0.6,0.2,0.4,0.4,0.2] with the corresponding flow: [0.4,0.4,0.4,0.2,0.2].

Fig. 3

Evolution of contPN in Fig. 2 with $\boldsymbol{\lambda}=[1,2,1,1,0.5]^T$ under infinite server semantics

Finite server semantics

The evolution of the system under finite server semantics is presented in Fig. 4. At $\boldsymbol{m_0}$, the input places of t ₁ and t ₄ are marked, therefore t ₁ and t ₄ are strongly enabled and f ₁ = f ₄ = 1. The other transitions are weakly enabled and their flow depends on the input flows to the empty input places. For t ₂, the input flow to p ₃ (the only empty input place) is 1, hence f ₂ =  min {λ ₂,1} = 1. Transition t ₃ will work at the maximum speed because the input flow in p ₄ is f ₂ = 1, equal to λ ₁, its maximal firing speed. For t ₅, the input flow to p ₅ is 1, then its flow is limited by its maximal firing speed that is 0.5. According with these flow equations, the evolution of the system will be governed by a linear system, Σ₃, until τ = 2, when m ₆ and m ₂ become empty. At this time, the marking is [1,0,0,0,1,0]. Now, t ₁ and t ₅ are strongly enabled, therefore f ₁ = 1 and f ₅ = 0.5. The weakly enabled transitions t ₂ and t ₄ are in conflict and a resolution policy should be specified. Assume, for example, that the flow of t ₂ is equal to the flow of t ₄. Moreover, the output flows of all the empty places are upper bounded by the input flows. The solution is f ₂ = f ₃ = f ₄ = 0.5. So, the system of equations that defines the evolution after τ = 2 is a new linear system Σ₄.

Fig. 4

Evolution of contPN in Fig. 2 with $\boldsymbol{\lambda}=[1,2,1,1,0.5]^T$ under finite server semantics

At τ = 4, p ₄ is emptied and a new flow computation has to be done. The current marking is [0,0,1,0,1,0]. The only strongly enabled transition is t ₅, hence f ₅ = 1. Solving the flows, f ₁ = f ₂ = f ₃ = f ₄ = 0.5 is obtained. These values correspond to a steady state marking ($\dot{\boldsymbol{m}}(\tau)=0$).

Clearly, the evolution of a contPN system is quite different under both semantics: different transitory regimes and steady-state markings are obtained.

3.2 Comparison of server semantics for mono-T-semiflow reducible nets

In this subsection we study both continuous semantics to see which one approximates better the steady state throughput of the discrete net. In Júlvez et al. (2005) a branch and bound algorithm is used to compute upper bounds of the steady state throughput for continuous systems under infinite server semantics, each node corresponding to a LPP. In the case of mono-T-semiflow reducible nets, the bounds can be computed solving only one simple LPP. The linear programming problem is the “continuous version” of the bounds obtained in Campos and Silva (1992) for discrete nets.¹

Let $\langle \mathcal{N}, \boldsymbol{\lambda}, \boldsymbol{m}_0 \rangle$ be a mono-T-semiflow reducible net and γ _i the solution of the linear programming problem:

$$\label{eq-LPPbound} \gamma_i= \max \left\{ \boldsymbol{y} \cdot \boldsymbol{PD}_i | \boldsymbol{y} \cdot \boldsymbol{C} =0, \boldsymbol{y} \cdot \boldsymbol{m_0}=1, \boldsymbol{y} \geq 0 \right\} $$

(4)

where $\boldsymbol{PD}(p)=\max \limits_{t \in {p}^\bullet} \frac{\boldsymbol{Pre}(p,t) \cdot \boldsymbol{v}^{(i)}(t)}{\boldsymbol{\lambda}(t)}$ and $\boldsymbol{v}^{(i)}$ is the visit ratio vector normalized for transition t _i .

According to Júlvez et al. (2005) the flow of the continuous system under infinite server semantics, $\boldsymbol{f}$, verifies $\boldsymbol{f} \leq \frac{1}{\gamma_i}\boldsymbol{v}^{(i)}$. Moreover, this bound is reached (i.e. $\boldsymbol{f} = \frac{1}{\gamma_i}\boldsymbol{v}^{(i)}$) iff the steady state P-configuration contains the support of a P-semiflow (Júlvez et al. 2005).

On the other hand, in Campos and Silva (1992) it is given an upper bound of the throughput in steady state of the stochastic (discrete) PN: $\chi \leq \frac{1}{\gamma_i} \cdot \boldsymbol{v}^{(i)}$, where γ _i and $\boldsymbol{v}^{(i)}$ are the same as in continuous case. This bound is valid for arbitrary probability distribution functions of service (including deterministic). Hence, if the steady state P-configuration contains the support of a P-semiflow, the throughput of the continuous net under infinite server semantics is an upper bound of the throughput of the discrete net system.

We will now prove that the throughput of continuous net systems under finite server semantics is greater than or equal to the throughput under infinite server semantics when the servers are made explicit, by adding the corresponding place self-loops (otherwise the comparison is inappropriate). Also, we assume that the conflict resolution in the case of finite server semantics is done according to the same visit ratio vector, as in discrete and infinite server semantics.

The comparison is done under the liveness hypothesis of the untimed contPN system. Liveness is used to ensure that at any time instant the continuous system under finite server semantics has at least one strongly-enabled transition. Otherwise, according to the flow definition Eq. 1 every transition has one empty input place and the net is not live as untimed. Liveness analysis of autonomous and timed mono-T-semiflow reducible nets is studied in Júlvez et al. (2006). It is proved that deadlock freeness is equivalent to liveness for this subclass of models. Also a necessary condition for the existence of a marking that makes the system lim-live is given, which can be checked in polynomial time: every transition has at least one place that is not input of any other transition.

Proposition 2

Let $\langle\mathcal{N} ,\boldsymbol{m_0}\rangle$ be a live mono-T-semiflow reducible contPN system. For any $\boldsymbol{\lambda}$ , the flow in steady state under finite server semantics is greater than or equal to the flow under infinite server semantics.

Proof

The net is mono-T-semiflow reducible so the throughput in steady state will be proportional to the visit ratio vector for both finite and infinite server semantics ($\boldsymbol{f_{F}}=\alpha_F \cdot \boldsymbol{v}^{(i)}$, $\boldsymbol{f_{\infty}}=\alpha_{\infty} \cdot \boldsymbol{v}^{(i)}$). Under finite server semantics at least one transition will be strongly enabled in steady state (otherwise the net is not live). Let t _i be one of those transitions, and assume we normalize the visit ratio with respect to it. Then $\alpha_F=n_i \cdot \boldsymbol{\lambda}[t_i]$ where n _i is the number of servers for transition t _i . Under infinite servers, if $\boldsymbol{m}$ is the steady state marking, it verifies that $\alpha_{\infty} = \min \limits_{p\in \,\!^\bullet{t_i}} \frac{\boldsymbol{m}[p]}{\boldsymbol{Pre}[p,t_i]} \cdot \boldsymbol{\lambda}[t_i] \leq \min \limits_{p\in \,\!^\bullet{t_i}} \boldsymbol{m}[p] \cdot \boldsymbol{\lambda}[t_i]$ ($\boldsymbol{Pre}[p,t_i] \in \mathbb{N}_{>0}$). Since the place that models the servers of t _i is input of the transition, $\min \limits_{p\in \,\!^\bullet{t_i}} \boldsymbol{m}[p] \leq n_i$ and so $\alpha_{\infty}\cdot \boldsymbol{v}^{(i)}=\boldsymbol{f_{\infty}}[t_i] \leq \boldsymbol{f_F}[t_i]=\alpha_F\cdot \boldsymbol{v}^{(i)}$.□

Therefore:

Theorem 1

Let $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ be a live mono-T-semiflow reducible PN system with every possible equilibrium P-configuration containing the support of a P-semiflow. For any probability distribution function for the firing of the transitions, the steady state throughput of the discrete model is better approximated by the continuous relaxation with infinite server semantics than with finite server semantics.

Proof

According to Proposition 5 in Júlvez et al. (2005), the steady state throughput of the discrete net system is upper bounded by the steady-state throughput of the continuous one under infinite server semantics. Using Proposition 2, the steady state throughput of the continuous net system with finite server semantics is greater or equal than the one with infinite server semantics.□

Example 2

Let us consider again the queuing network presented in Fig. 1. We have computed simulations for the discrete stochastic model (exponential distribution for servers) and the continuous model under infinite and finite (single-server) server semantics, using $\boldsymbol{\lambda}=\boldsymbol{1}$ (the servers are not represented in the figure to simplify it). In this net, every P-configuration contains the support of a P-semiflow (this will be proved in Example 6), so infinite server semantics will fit better. Simulating the model and measuring the flow of transition t ₁, the following results are obtained: the throughput is 0.1337 for the discrete model, 0.1667 for the continuous model under infinite server semantics, and 0.3333 for the continuous model under finite server semantics (i.e. two times bigger).

In general, proving that every P-configuration contains the support of a P-semiflow may be computationally expensive since the number of P-configurations may be large. However, there are net subclasses for which it is immediate. Take for example EQ nets (if $\,\!^\bullet{t_i} \cap \,\!^\bullet{t_j} \neq \emptyset$, $\boldsymbol{Pre}[\cdot,t_i]=\boldsymbol{Pre}[\cdot,t_j]$). For this class, every P-configuration contains a P-semiflow iff it is conservative, consistent and the rank of the token flow matrix equals to the number of equal conflicts (|SEQS|) minus one (Teruel and Silva 1996) (|SEQS| is defined as the number of equivalence classes defined by the continuous equal conflict relation with k = 1). Hence it can be verified in polynomial time. Moreover, if the initial marking is such that every P-semiflow is marked, the net is live as continuous (Recalde et al. 1999).

Corollary 1

Let $\mathcal{N}$ be an EQ net system that is consistent, conservative, $rank(\boldsymbol{C})=|SEQS|-1$ and $\boldsymbol{m_0}$ such that every P-semiflow is marked. In steady state, the continuous system $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ with infinite server semantics provides a throughput closer to the throughput of the discrete system than finite server semantics.

3.3 Discussion

Resources (and in particular servers) are usually shared among different operations. This leads to intuitively assert that finite server semantics approximation may lead to quite optimistic results. However, it may happen that it provides a throughput closer to the throughput of the discrete system.

Example 3

Let us consider the net system in Fig. 5 with $\boldsymbol{m_0}=[15,1,1,0]$. Assume that each transition has two dedicated servers and the speed of servers are 2,1,1. In steady state the throughput of all the transitions will be the same (the incidence matrix has only one minimal right annuller, $\boldsymbol{x}=[1,1,1]^T$, and the flow in steady state must be a T-semiflow). As discrete, the steady state throughput is 1.55 under exponential assumption for all transitions. If this model is seen as continuous with finite server semantics the maximum firing speed $\boldsymbol{\lambda}=2 \cdot [2,1,1]= [4,2,2]$ (because each transition has 2 servers), and the steady state flow is equal to 2. Under infinite server semantics $\boldsymbol{\lambda}=[2,1,1]$ and the steady state flow is 0.75. Clearly, finite server semantics provides a throughput which is closer to the throughput of the discrete system in steady state. However, we will see later that $P-\mathcal{C}_3=\{p_2,p_3,p_4\}$ is an equilibrium P-configuration that does not contain any P-semiflow, and Theorem 1 does not apply.

Fig. 5

Mono-T-semiflow net ($\boldsymbol{x}=[1,1,1]^T$) used in Example 3

This example also shows that the flow of the continuous model under infinite server semantics is not necessarily an upper bound of the throughput as discrete, what may came as a surprise: fluidification does not improve performance.

4 Monotonicity under infinite server semantics

4.1 Monotonicity results

In this section we will focus our attention on the timed contPN system under infinite server semantics and study some properties related to monotonicity. From the flow definition in Eq. 2 it is easy to observe that if the vector $\boldsymbol{\lambda}$ is multiplied by a constant k > 0 then at any reachable marking the flow will be also multiplied by k. Analogously, when the initial marking is multiplied by k, the system will be k times faster. But, what happens if only some components of $\boldsymbol{\lambda}$ or only some components of $\boldsymbol{m}_0$ are increased? In general, as happens for discrete nets, increasing the rate of a transition or the initial marking of a place may lead to a slower system (see examples in Subsection 2.2 in Júlvez et al. (2005)). This unexpected behavior is usually not desirable. For example, replacing a machine by a faster one or adding new machines in a production system should not decrease the throughput. In this section we will see that mono-T-semiflow reducible nets, under quite general conditions, have the a priori expected monotonicity property.

Theorem 2

Let $\langle \mathcal{N}, \boldsymbol{\lambda_1}, \boldsymbol{m_0}\rangle$ and $\langle \mathcal{N}, \boldsymbol{\lambda_2}, \boldsymbol{m_0}\rangle$ be mono-T-semiflow reducible contPN systems with $\boldsymbol{\lambda_1} \leq \boldsymbol{\lambda_2}$ , but visit ratio preserving. If the systems reach a steady state and both steady state P-configurations contain the support of a P-semiflow then the steady state flows verify $\boldsymbol{f_1} \leq \boldsymbol{f_2}$.

Proof

For i = 1,2, let $\boldsymbol{m_i}$ be the steady state marking of $\langle \mathcal{N}, \boldsymbol{\lambda_i}, \boldsymbol{m_0} \rangle$, and $\boldsymbol{y_i}$ a P-semiflow whose support is contained in one P-configuration defined by $\boldsymbol{m_i}$. Obviously, both $\boldsymbol{m_1}$ and $\boldsymbol{m_2}$ can be reached in the autonomous net system, thus $\boldsymbol{y_i} \cdot \boldsymbol{m_1}=\boldsymbol{y_i} \cdot \boldsymbol{m_2}$.

Let us focus on $\boldsymbol{f_2}$ and $\boldsymbol{y_2}$. Every place $p_{j\,2} \in ||\boldsymbol{y_2}||$ restricts the flow of at least one of its one output transitions, denoted by t _{j 2}, i.e.:

$$ \boldsymbol{f_2}[t_{j\,2}]=\boldsymbol{\lambda_2}[t_{j\,2}] \cdot \frac{\boldsymbol{m_2}[p_{j\,2}]}{\boldsymbol{Pre}[p_{j\,2},t_{j\,2}]} $$

(5)

Using the P-semiflow $\boldsymbol{y_2}$, we can write the token conservation law for $\boldsymbol{m_1}$ and $\boldsymbol{m_2}$, and taking $\boldsymbol{m_2}$ from the previous equation:

$$ \sum \limits_{p_{j\,2} \in ||\boldsymbol{y_2}||} \boldsymbol{y_2}[p_{j\,2}] \cdot \frac{\boldsymbol{Pre}[p_{j\,2},t_{j_2}] \cdot \boldsymbol{f_2}[t_{j\,2}]}{\boldsymbol{\lambda_2}[t_{j\,2}]}= \sum \limits_{p_{j\,2} \in ||\boldsymbol{y_2}||} \boldsymbol{y_2}[p_{j\,2}] \cdot \boldsymbol{m_1}[p_{j\,2}] $$

(6)

Now, $\boldsymbol{m_1}[p_{j\,2}]$ can be replaced using $\boldsymbol{f_1}$ because

$$\label{eq-ex11} \boldsymbol{f_1}[t_{j\,2}]= \boldsymbol{\lambda_1}[t_{j\,2}] \cdot enab(t_{j\,2},\boldsymbol{m_1}) \leq \boldsymbol{\lambda_1}[t_{j\,2}] \cdot \frac{\boldsymbol{m_1}[p_{j\,2}]}{\boldsymbol{Pre}[p_{j\,2},t_{j\,2}]}. $$

(7)

Moreover, $\boldsymbol{\lambda_1} \leq \boldsymbol{\lambda_2}$, so:

$$\begin{array}{lll} && \sum \limits_{p_{j\,2} \in ||\boldsymbol{y_2}||} \boldsymbol{y_2}[p_{j\,2}] \cdot \boldsymbol{m_1}[p_{j\,2}] \geq \\ &&{\kern10.5pt} \geq \sum \limits_{p_{j\,2} \in ||\boldsymbol{y_2}||} \boldsymbol{y_2}[p_{j\,2}] \cdot \frac{\boldsymbol{Pre}[p_{j\,2},t_{j_2}] \cdot \boldsymbol{f_1}[t_{j\,2}]}{\boldsymbol{\lambda_1}[t_{j\,2}]} \geq \\ &&{\kern10.5pt} \geq \sum \limits_{p_{j\,2} \in ||\boldsymbol{y_2}||} \boldsymbol{y_2}[p_{j\,2}] \cdot \frac{\boldsymbol{Pre}[p_{j\,2},t_{j_2}] \cdot \boldsymbol{f_1}[t_{j\,2}]}{\boldsymbol{\lambda_1}[t_{j\,2}]} \end{array}$$

(8)

The net is mono-T-semiflow reducible, and $\boldsymbol{\lambda_1}$ and $\boldsymbol{\lambda_2}$ keep the proportion of flows in continuous equal conflicts. Hence, both visit ratios will be the same, $\boldsymbol{v}^{(1)}>0$. Let $\boldsymbol{f_1}=k_1 \cdot \boldsymbol{v}^{(1)}$ and $\boldsymbol{f_2}=k_2 \cdot \boldsymbol{v}^{(1)}$. Therefore, merging Eq. 7 and Eq. 8:

$$ \sum \limits_{p_{j\,2} \in ||\boldsymbol{y_2}||} \boldsymbol{y_2}[p_{j\,2}] \cdot \frac{\boldsymbol{Pre}[p_{j\,2},t_{j_2}] \cdot \boldsymbol{v}^{(1)}[t_{j\,2}]}{\boldsymbol{\lambda_2}[t_{j\,2}]} \cdot (k_2-k_1) \geq 0 $$

(9)

And so k ₂ ≥ k ₁.□

This result an be extended to sets of rates.

Definition 4

Let $\langle \mathcal{N}, \boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ be a timed contPN system and let $\mathcal{L} \subseteq \mathbb{R}_{>0}^{|T|}$. The system $\langle \mathcal{N}, \boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ is said to be monotone for t _j in steady state w.r.t. $\boldsymbol{\lambda} \in \mathcal{L}$ if $\forall \boldsymbol{\lambda_1}, \boldsymbol{\lambda_2} \in \mathcal{L}$ with $\boldsymbol{\lambda_1} \leq \boldsymbol{\lambda_2}$, if these systems have steady states, the associated steady state flows verify $\boldsymbol{f_1}[t_j] \leq \boldsymbol{f_2}[t_j]$.

In the case of mono-T-semiflow reducible net systems, since the steady state flow is proportional to the visit ratio vector defined by the net structure and routing (speeds at CEQs), if a system is monotone for a given t _j , it is monotone for ∀ t ∈ T. Therefore, it can be said that the net system is monotone (i.e. it is monotone for all transitions).

Theorem 3

Let $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ be a timed mono-T-semiflow reducible contPN system under infinite server semantics and $\mathcal{L} \subseteq \mathbb{R}_{>0}^{|T|}$ visit ratio preserving. If for all $\boldsymbol{\lambda} \in \mathcal{L}$ the possible equilibrium P-configurations of $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ contain the support of a P-semiflow then the timed system is monotone in steady state with respect to $\boldsymbol{\lambda} \in \mathcal{L}$.

Proof

Applying to all $\boldsymbol{\lambda_1}, \boldsymbol{\lambda_2} \in \mathcal{L}$ Theorem 2, the conclusion is verified.□

Example 4

Let us consider the contPN in Fig. 5. This net is mono-T-semiflow with $\boldsymbol{x}=[1,1,1]$ and has 4 P-configurations: $P-\mathcal{C}_1=\{p_1,p_2,p_3\}$, $P-\mathcal{C}_2=\{p_1,p_4,p_3\}$, $P-\mathcal{C}_3=\{p_4,p_2,p_3\}$ and $P-\mathcal{C}_4=\{p_4, p_3\}$, and two minimal P-semiflows: $\boldsymbol{y_1} = p_1+p_2+p_3$ and $\boldsymbol{y_2} = p_1+4\cdot p_3 + p_4$. Therefore there are two P-configurations that contain a P-semiflow, $P-\mathcal{C}_1$ and $P-\mathcal{C}_2$, one P-configuration that contains the support of a P-flow, $P-\mathcal{C}_3$ ($\boldsymbol{y_3}=\boldsymbol{y_1}-\boldsymbol{y_2}$) but no P-semiflow, and one P-configuration that does not contain the support of any P-flow, $P-\mathcal{C}_4$.

• 1) Let $\boldsymbol{m_0}=[1,1,0,15]$. We will see that for all $\boldsymbol{\lambda} \in \mathbb{R}_{>0}^{|T|}$ the only possible equilibrium P-configurations are $P-\mathcal{C}_1$ and $P-\mathcal{C}_2$. Both contain P-semiflows, so using Theorem 3 the timed system is monotone with respect to $\boldsymbol{\lambda}\in \mathbb{R}_{>0}^{|T|}$ (for this initial marking).

First, let us observe that $P-\mathcal{C}_3$ is not a possible equilibrium P-configuration. To be an equilibrium P-configuration, the following system of equations should be satisfied:

$$\label{sys1} \left\{ \begin{array}{ll} m_1 + m_2 + m_3 = 2 & \text{(a) first P-semiflow } \\ m_1 + 4 \cdot m_3 + m_4 = 16 & \text{(b) second P-semiflow } \\ m_1 \geq m_4 & \text{(c) } f_1 \text{ restricted by } p_4 \\ m_4 \geq m_2 & \text{(d) } f_2 \text{ restricted by } p_2 \end{array} \right. $$

(10)

where m ₁, m ₂, m ₃, m ₄ and f ₁,f ₂,f ₃ is a possible steady state in $P-\mathcal{C}_3$. From Eq. 10.a $\Longrightarrow m_1 \leq 2$ and m ₃ ≤ 2. Moreover, Eq. 10.c implies m ₄ ≤ m ₁ ≤ 2. Therefore, m ₁ + 4·m ₃ + m ₄ ≤ 2 + 8 + 2 = 12 and so Eq. 10.b cannot be satisfied.

Assume now that $P-\mathcal{C}_4$ is the steady state P-configuration, therefore the following system should be satisfied:

$$\label{sys2} \left\{ \begin{array}{ll} m_1 + m_2 + m_3 = 2 & \text{(a) first P-semiflow } \\ m_1 + 4 \cdot m_3 + m_4 = 16 & \text{(b) second P-semiflow } \\ m_1 \geq m_4 & \text{(c) } f_1 \text{ restricted by } p_4 \\ m_2 \geq m_4 & \text{(d) } f_2 \text{ restricted by } p_4 \\ \end{array} \right. $$

(11)

According to Eqs. 11.a and Eq. 11.b, m ₄ ≥ 8 and m ₂ ≤ 2 (because of Eq. 11.a); thus Eq. 11.d is not true. Therefore Eq. 11 has no solution and $P-\mathcal{C}_4$ cannot be an equilibrium P-configuration.

Thus for $\boldsymbol{m_0}=[1,1,0,15]^T$ the only possible equilibrium P-configurations, for any $\boldsymbol{\lambda}\in \mathbb{R}_{>0}^{|T|}$, are $P-\mathcal{C}_1$ and $P-\mathcal{C}_2$. Both contain the support of a P-semiflow, thus the timed system is monotone w.r.t. $\boldsymbol{\lambda}\in \mathbb{R}_{>0}^{|T|}$ (Theorem 3). In Fig. 6 it is shown the non decreasing monotonicity of the throughput w.r.t. λ ₂.

Fig. 6

Throughput of the contPN system in Fig. 5 for $\boldsymbol{m_0}=[1,1,0,15]^T$ and different values of λ ₂ (λ ₁ = λ ₃ = 1)

• 2) Let $\boldsymbol{m_0}=[15,1,1,0]$. For this marking, $P-\mathcal{C}_2$, $P-\mathcal{C}_3$, $P-\mathcal{C}_4$ can be equilibrium configurations if appropriate values for $\boldsymbol{\lambda}$ are chosen. For example: $\boldsymbol{m_2}=[1,13,3,6]^T$ corresponding to $P-\mathcal{C}_2$ is an equilibrium marking for $\boldsymbol{\lambda_2}=[6,1,2]^T$ with $\boldsymbol{f_2}=\boldsymbol{6}$; $\boldsymbol{m_3}=[13.67,3,0.33,4]^T$ corresponding to $P-\mathcal{C}_3$ is an equilibrium marking for $\boldsymbol{\lambda_3}=[3,2,18]^T$ with $\boldsymbol{f_3}=\boldsymbol{1}$; $\boldsymbol{m_4}=[10.5,4.5,2,0.5]^T$ corresponding to $P\!-\!\mathcal{C}_4$ is an equilibrium marking for $\boldsymbol{\lambda_4}\!=\![8,4,1]^T$ with $\boldsymbol{f_4}\!=\!\boldsymbol{2}$. Since some possible equilibrium P-configurations do not contain the support of a P-semiflow, monotony cannot be guaranteed.

In Fig. 7 it is sketched the evolution of the throughput of the net system for $\boldsymbol{m_0}=[15,1,1,0]^T$ and $\boldsymbol{\lambda}=[1,\lambda_2,1]^T$ with 0 < λ ₂ ≤ 5. It can be seen that it is not monotonic. Even a discontinuity exists at λ ₂ = 0.5. When 0 < λ ₂ < 0.5, the equilibrium P-configuration is $P-\mathcal{C}_2$ and the throughput is increasing with λ ₂. For λ ₂ ≥ 0.5 the steady state P-configuration is $P-\mathcal{C}_3$ that contains the support of a P-flow (but not of a P-semiflow) and the steady state throughput is decreasing (the conditions of Theorem 3 are not satisfied). Therefore, for $\boldsymbol{m_0}=[15,1,1,0]^T$ the system is not monotone in steady state w.r.t. $\boldsymbol{\lambda} \in \mathbb{R}_{>0}^{|T|}$.

Fig. 7

Throughput of the contPN system in Fig. 5 for $\boldsymbol{m_0}=[15,1,1,0]^T$ and different values of λ ₂

• 3) Let us now study the monotonicity of the same contPN with $\boldsymbol{m_0}=[15,1,1,0]^T$ w.r.t $\boldsymbol{\lambda} \in \mathcal{L}_1$ where $\mathcal{L}_1=\{ [\lambda_1,\lambda_2,\lambda_3]^T | \lambda_1= \lambda_3=1, 0 < \lambda_2 < 0.5 \}$.

First, $P-\mathcal{C}_4$ cannot be an equilibrium P-configuration. If it were, p ₄ restricts the flows of t ₁ and t ₂ in steady state, and so since the steady state flow verifies f ₁ = f ₂ = f ₃, $\lambda_2 \cdot m_4 = \lambda_1 \cdot \frac{m_4}{2}=\frac{m_4}{2}$. Because we are assuming λ ₂ < 0.5, m ₄ = 0 and f ₁ = f ₂ = f ₃ = 0, i.e., the system is in a deadlock. Notice that f ₃ is defined by m ₃, so m ₃ = 0. Using the P-semiflows: m ₁ + m ₂ = 17 and m ₁ = 19 which cannot be satisfied.

If $P-\mathcal{C}_3$ were the equilibrium P-configuration, since the steady state flow verifies f ₁ = f ₂ = f ₃, then $\lambda_1 \cdot \frac{m_4}{2} = \lambda_2 \cdot m_2 = \lambda_3 \cdot m_3$. But λ ₁ = λ ₃ = 1, and so $\frac{m_4}{2} = \lambda_2 \cdot m_2 = m_3$. Hence, the following system of equations should have a solution:

$$\label{sys3} \left\{ \begin{array}{ll} m_1 + m_2 + m_3 = 17 & \text{(a) first P-semiflow } \\ m_1 + 4 \cdot m_3 + m_4 = 19 & \text{(b) second P-semiflow } \\ m_1 \geq m_4 & \text{(c) } f_1 \text{ restricted by } p_4 \\ m_4 \geq m_2 & \text{(d) } f_2 \text{ restricted by } p_2 \\ \frac{m_4}{2} = \lambda_2 \cdot m_2 = m_3 & \text{(e) steady state flows} \\ \end{array} \right. $$

(12)

Using Eq. 12.e, m ₄ = 2 λ ₂ ·m ₂ and considering Eq. 12.d: 2 λ ₂ ·m ₂ ≥ m ₂. But m ₂ > 0 because the system cannot deadlock (see the reasoning for $\mathcal{C}_4$) therefore 2 ·λ ₂ ≥ 1 that cannot be satisfied since 0 < λ ₂ < 0.5. Hence, the only possible equilibrium P-configurations are $P-\mathcal{C}_1$ and $P-\mathcal{C}_2$ that contain the support of a P-semiflow. Therefore the time contPN system is monotone w.r.t. $\boldsymbol{\lambda} \in \mathcal{L}_1$.

Let us now consider monotonicity w.r.t. the initial marking.

Theorem 4

Let $\langle\mathcal{N} ,\boldsymbol{\lambda} \rangle$ be a mono-T-semiflow reducible contPN under infinite server semantics, and let $\boldsymbol{m_1} \leq \boldsymbol{m_2}$ . If for i = 1, 2 $\langle \mathcal{N}, \lambda , \boldsymbol{m_i}\rangle$ reaches a steady state and the steady state P-configuration contains the support of a P-semiflow, then the steady state flows verify $\boldsymbol{f_1} \leq \boldsymbol{f_2}$.

Proof

According to Proposition 5 of Júlvez et al. (2005), $\boldsymbol{f_i}=\frac{1}{\gamma_i}\cdot \boldsymbol{v}^{(1)}$ with $\gamma_i=\max \left\{ \boldsymbol{y} \cdot \boldsymbol{PD} | \boldsymbol{y} \cdot \boldsymbol{C}\!=\!\boldsymbol{0}, \boldsymbol{y} \cdot \boldsymbol{m_i}\! =\! \boldsymbol{1}, \boldsymbol{y}\! \geq\! \boldsymbol{0} \right\}\!=\!\max \left\{ \frac{1}{\boldsymbol{y} \cdot \boldsymbol{m_i}} \cdot \boldsymbol{y} \cdot \boldsymbol{PD} | \boldsymbol{y} \cdot \boldsymbol{C}\!=\!\boldsymbol{0}, \boldsymbol{y}\! \geq\! \boldsymbol{0} \right\}$. Let us assume $\boldsymbol{m_{10}} \leq \boldsymbol{m_{20}}$. Then, for every P-semiflow $\boldsymbol{y}$, $\boldsymbol{y} \cdot \boldsymbol{m_1} \leq \boldsymbol{y} \cdot \boldsymbol{m_2}$ and so, γ ₁ ≥ γ ₂. Therefore, $\boldsymbol{f_1} \leq \boldsymbol{f_2}$.□

Monotonicity w.r.t. the initial marking can be studied also on a region as done in the case of the monotonicity w.r.t. $\boldsymbol{\lambda}$.

Definition 5

Let $\langle \mathcal{N}, \boldsymbol{\lambda}\rangle$ be a timed contPN and let $\mathcal{M} \subseteq \mathbb{R}_{>0}^{|P|}$. The system $\langle \mathcal{N}, \boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ is said to be monotone for t _j in steady state w.r.t. $\boldsymbol{m_0} \in \mathcal{M}$ if for all $\boldsymbol{m_1}, \boldsymbol{m_2} \in \mathcal{M}$ with $\boldsymbol{m_1} \leq \boldsymbol{m_2}$, these systems have steady states and the associated steady state flows verify $\boldsymbol{f_1}[t_j] \leq \boldsymbol{f_2}[t_j]$.

As in the case of the monotony w.r.t. $\boldsymbol{\lambda}$, Theorem 5 can be used to derive the following sufficient condition for monotonicity of a mono-T-semiflow net system w.r.t. the initial marking.

Theorem 5

Let $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ be a timed mono-T-semiflow reducible contPN system under infinite server semantics. If for all $\boldsymbol{m_0} \in \mathcal{M}$ the possible equilibrium P-configurations contain the support of a P-semiflow, then $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ is monotone in steady state w.r.t. $\boldsymbol{m_0} \in \mathcal{M}$.

Proof

Applying to all $\boldsymbol{m_1}, \boldsymbol{m_2} \in \mathcal{M}$ Theorem 4, the conclusion is verified.□

Example 5

Let us consider the contPN in Fig. 5. Assume $\boldsymbol{\lambda}=[1,1,1]^T$.

• 1) Let us study monotonicity w.r.t. $\boldsymbol{m_0} \in \mathcal{M}_1=\{ \boldsymbol{m}| m_1=0, m_2=m_3=1, m_4 >0 \}$.

$P-\mathcal{C}_4$ cannot be an equilibrium P-configuration. If it were, in steady state, p ₄ limits the flow of t ₁ and t ₂, but taking into account the T-semiflow: f ₁ = f ₂, thus $\frac{m_4}{2}=m_4$ (because λ ₁ = λ ₂ = 1), and the only solution is m ₄ = 0 . Therefore, from the T-semiflow, m ₃ = 0. Writing the P-semiflows we have: m ₁ + m ₂ = 2 and m ₁ = 4 + z, with z the initial marking of p ₄. Since z ≥ 0 these equations cannot be satisfied. Therefore $P-\mathcal{C}_4$ cannot be an equilibrium P-configuration.

For $\mathcal{C}_3$, the following system of equations should have a solution:

$$\label{sys4} \left\{ \begin{array}{ll} m_1 + m_2 + m_3 = 2 & \text{(a) first P-semiflow } \\ m_1 + 4 m_3 + m_4 = 4+z & \text{(b) second P-semiflow } \\ \frac{m_4}{2} = m_2 = m_3 & \text{(c) steady state flow} \\ m_1 \geq m_4 & \text{(d) $f_1$ restricted by $p_4$} \\ m_4 \geq m_2 & \text{(e) $f_2$ restricted by $p_2$} \end{array} \right. $$

(13)

where z is the initial marking of p ₄. From Eqs. 13.b–13.a: 3 ·m ₃ − m ₂ + m ₄ = z + 2. Replacing m ₃ and m ₄ using Eq. 13.c, 3 ·m ₂ − m ₂ + 2 ·m ₂ = z + 2, thus $m_2 = \frac{z+2}{4}$. Hence, any solution should be of the form: $[m_1,\frac{z+2}{4},\frac{z+2}{4},\frac{z+2}{2}]^T$ with $m_1 \geq \frac{z+2}{2}$ Eq. 13.d. But Eq. 13.a implies: $m_1 = 2 - \frac{z+2}{4} - \frac{z+2}{4} = \frac{-z + 2}{2}$ and combining with Eq. 13.d results $\frac{-z + 2}{2} \geq \frac{z + 2}{2} \rightarrow 2\cdot z \leq 0 \rightarrow z \leq 0$ which is impossible because z is the initial marking of p ₄.

Thus neither $P-\mathcal{C}_4$ nor $P-\mathcal{C}_3$ can be equilibrium P-configurations. Using Theorem 5 the timed net system is monotone w.r.t. the initial marking $\boldsymbol{m_0}$ in $\mathcal{M}_1$.

• 2) Let us consider $\mathcal{M}_2=\{[m_1,m_2,m_3,m_4]^T| m_1=15, m_3=1, m_4 = 0,m_2 >0 \}$. $P-\mathcal{C}_3$ and $P-\mathcal{C}_4$ can be equilibrium P-configurations and monotonicity can be lost. Indeed, simulating for $\boldsymbol{m_0}[p_2] \in [0,5]$ (Fig. 8), the throughput decreases, even deadlock is reached for $\boldsymbol{m_0}[p_2] \geq 3$. Hence the timed net system with $\boldsymbol{m_0} \in \mathcal{M}_2$ is not monotonic in steady state.

Fig. 8

Throughput of the contPN system in Fig. 5 for $\boldsymbol{m_0}=[15,z,1,0]^T$ and $\boldsymbol{\lambda}=[1,1,1]^T$

4.2 Some properties of non monotonicity

As an immediate consequence of Theorems 3 and 5, if all P-configurations defined by $\mathcal{N}$ (i.e., independently of $\boldsymbol{m_0}$), contain a P-semiflow, then the underlying net system is monotone in steady state w.r.t. the set of $\boldsymbol{\lambda} \in \mathbb{R}_{>0}^{|T|}$ that impose the same routing (visiting ratio), and w.r.t. $\boldsymbol{m_0}$ in ℝ. Moreover, we will prove that this P-semiflow condition when asked to all the P-configurations is in fact equivalent to an analogous P-flows condition (Corollary 2). Let us first consider the following lemma.

Lemma 1

Let $\mathcal{N}$ be a consistent join free net (i.e., ∀ t ∈ T, | ^∙ t| ≤ 1). For every P-flow $\boldsymbol{y}$ there exist a P-semiflow $\boldsymbol{y'}$ such that $||\boldsymbol{y}'|| \subseteq ||\boldsymbol{y}||$.

Proof

Dual of Theorem 9 of Teruel et al. (1997) (T-flows of CF nets).□

Theorem 6

Let $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ be a mono-T-semiflow reducible contPN system under infinite server semantics. If there exists a set $\mathcal{L}$ of rates, $\mathcal{L}$ visit ratio preserving, or a set of initial markings $\mathcal{M}$ , such that $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ is not monotone in steady state w.r.t. $\boldsymbol{\lambda} \in \mathcal{L}$ or w.r.t. $\boldsymbol{m_0} \in \mathcal{M}$ , then there exists a P-configuration that does not contain any P-flow.

Proof

If $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ is not monotone, applying Theorem 3 or Theorem 5, an equilibrium P-configuration exists that does not contain a P-semiflow. If this equilibrium P-configuration does not contain the support of any P-flow this is the requested P-configuration. Otherwise, assume that this equilibrium P-configuration contains one P-flow (or more). Let us consider the subnet $\mathcal{N}'$ defined by the set of all transitions together with the places that limit their flow in steady state, and let us call $\boldsymbol{C'}$ the token flow matrix of this subnet. Since the original net is mono-T-semiflow, it is consistent. The same T-semiflow of $\mathcal{N}$ is also a right annuller of $\boldsymbol{C'}$, hence $\mathcal{N}'$ is consistent.

If $\mathcal{N}'$ were a JF net, using Lemma 1 the support of a P-semiflow should be included in $\mathcal{N}'$, but that is impossible by assumption. Hence $\mathcal{N}'$ must have at least one join/synchronization. Let us call t _k this transition. Let p _i and p _j be the input places of t _k that belong to the P-configuration. Obviously, only one place restricts the flow of t _k . Let us assume p _i to be this one.

If we consider now that t _k is restricted by p _j and the other transitions are restricted by the same places as before, we obtain a new P-configuration (possibly a non-equilibrium one) in which place p _i has been removed. If this P-configuration contains a P-flow, repeat the reasoning. In the end this procedure will define a P-configuration that does not contain any P-semiflow (from hypothesis) or P-flow.□

Corollary 2

Let $\langle\mathcal{N} ,\boldsymbol{\lambda}, \boldsymbol{m_0}\rangle$ be a continuous mono-T-semiflow reducible net under infinite server semantics. If all the P-configurations contain the support of a P-flow, then the underlying net system is monotone in steady state w.r.t. $\boldsymbol{m_0} \in \mathcal{M}$ , $\forall \mathcal{M} \subseteq \mathbb{R}_{>0}^{|P|}$ , and w.r.t. $\boldsymbol{\lambda} \in \mathcal{L}$ , $\forall \mathcal{L} \subseteq \mathbb{R}_{>0}^{|T|}$ visit ratio preserving.

Example 6

Let us consider again the queuing network presented in Fig. 1. It has the following P-semiflows: $\boldsymbol{y_1}=p_2+p_4$, $\boldsymbol{y_2}=p_7+p_{9}$, $\boldsymbol{y_3}=p_8+p_{10}$ and $\boldsymbol{y_4}=p_1+p_2+p_3+p_5+p_6+p_7+p_8+p_{11}+p_{12}$. Since this net is EQ, all P-configurations contain the support of a P-semiflow (Teruel and Silva 1996). Hence, both kinds of monotonicity properties hold.

5 Checking structural monotonicity

This section deals with monotonicity results valid for family of $\boldsymbol{m}_0$, thus partially independent on the initial marking, based on the structural timed net $\langle \mathcal{N}, \boldsymbol{\lambda} \rangle$.

In Section 4, monotonicity of the throughput w.r.t. $\boldsymbol{\lambda}$ or $\boldsymbol{m}_0$ is proved for mono-T-semiflow reducible nets whose possible equilibrium P-configurations contain the support of a P-semiflow. Under the same hypothesis, plus liveness, in Section 3.2 it is proved that infinite server semantics provides a throughput closer to that of the discrete system in steady state than finite server semantics. Therefore, it is interesting to know the P-configurations that do not contain the support of a P-semiflow, because if they are possible equilibrium P-configurations the previous two properties may not hold.

The idea is to use boolean equations to represent the conditions the places in a P-configuration have to fulfill. Let γ _i be a boolean variable such that γ _i  = 1 iff p _i belongs to one P-configuration. Any P-semiflow will provide a boolean equation: the product of the boolean variables associated to the support of the P-semiflow should be 0 if the P-semiflow does not belong to the P-configuration. Moreover, if a transition is not a join ($|\,\!^\bullet{t_i}|=1$) its input place must belong to all P-configurations (it is an essential cover), therefore the boolean variables associated to those places are 1. For every synchronization, we should have another boolean equation ensuring that at least one input place is taken so that the solution is (or contains) a P-configuration. The solutions of this system of boolean equations provide P-configurations that do not contain the support of a P-semiflow.

Example 7

Let us consider the net in Fig. 5. This net has been used in Examples 4 and 5 where the P-configurations that do not contain the support of a P-semiflow were supposed to be known. These P-configurations can be computed, for example, using the above algorithm. This net has two P-semiflows: $\boldsymbol{y_1}\!=\!p_1\!+\!p_2\!+\!p_3$ and $\boldsymbol{y_2}\!=\!p_1\!+\!4\cdot p_3\!+\!p_4$, so the corresponding boolean equations are: γ ₁·γ ₂ ·γ ₃ = 0 and γ ₁·γ ₃ ·γ ₄ = 0. In order to cover transitions we need additional equations. For t ₁: γ ₁ + γ ₄ = 1 (m ₁ or m ₄ limit the flow of t ₁) and the same for t ₂: γ ₂ + γ ₄ = 1 (m ₂ or m ₄ limit the flow of t ₂). Clearly, p ₃ being the only input place in t ₃ is an essential cover, thus γ ₃ = 1. The following system of boolean equations is obtained:

$$ \label{eq-algo} \left\{ \begin{array}{ll} \gamma_1\cdot \gamma_2 \cdot \gamma_3=0 & \text{(a) First P-semiflow is not contained}\\ \gamma_1\cdot \gamma_3 \cdot \gamma_4=0 & \text{(b) Second P-semiflow is not contained}\\ \gamma_1+\gamma_4=1 & \text{(c) $t_1$ is covered}\\ \gamma_2+\gamma_4=1 & \text{(d) $t_2$ is covered} \\ \gamma_3=1 & \text{(e) $t_3$ is covered} \end{array} \right. $$

(14)

From Eq. 14.e, taking into account Eqs. 14.a and 14.b, $\gamma_1 \cdot \left( \gamma_2 + \gamma_4 \right)=0$. Because of Eq. 14.d: γ ₁ = 0; thus γ ₄ = 1 and γ ₂ = ⊘. Summarizing, γ ₁ = 0, γ ₂ = ⊘, γ ₃ = 1 and γ ₄ = 1. Thus the net has two P-configurations ($\mathcal{C}_1=\{p_3,p_4\}$, $\mathcal{C}_2=\{p_2,p_3,p_4\}$) that do not contain the support of a P-semiflow. Depending on the initial marking and the firing rates these P-configurations can or cannot be equilibrium P-configurations and the monotonicity may be lost (see Example 4).

Remark 1

It can be seen in Eq. 14 that for every transition with only one input place (there $|\,\!^\bullet{t_3}|=|\{p_3\}|=1$) a boolean equation γ ₃ = 1 is introduced. Before solving the equations, these variables can be removed reducing the number of variables. The interpretation in the PN is that t ₃ and p ₃ can be removed in the model because p ₃ belongs to all P-configurations. If all transitions with only one input place are removed, the net will contain only join transitions and the order of the system may be much lower.

According to Corollary 2, if all P-configurations contain the support of a P-flow, the timed net system is monotonic in steady state w.r.t. $\boldsymbol{m_0} \in \mathbb{R}_{>0}^{|P|}$ and w.r.t. $\boldsymbol{\lambda} \in \mathcal{L}$, $\forall \mathcal{L} \subseteq \mathbb{R}_{>0}^{|T|}$ visit ratio preserving.

A second algorithm can be used to check if all P-configurations contain the support of a P-flow. This second algorithm may fail, but this does not imply that the net system is not monotonic, since the net may include P-configurations not containing the support of a P-semiflow but which cannot be equilibrium P-configurations for a specific initial marking and transition rates (see Example 4). In fact, with this algorithm it is monotonicity for any subset of $\boldsymbol{\lambda}$ and $\boldsymbol{m_0}$ that is obtained.

The algorithm consists in: first, all P-configurations are computed (which is exponential) and then, each P-configuration is checked to see whether it contains the support of a P-flow. For the second step, let the token flow matrix of a P-configuration $P-\mathcal{C}_j$ be denoted by $\boldsymbol{C_j}$ ($\boldsymbol{C_j}$ is obtained from the token flow matrix of the original net by removing the rows not corresponding to $P-\mathcal{C}_j$). To check if $P-\mathcal{C}_j$ contains the support of a P-flow, is equivalent to check if $\exists \boldsymbol{y}\neq \boldsymbol{0}$ such that $\boldsymbol{y} \cdot \boldsymbol{C_j} = 0$ (polynomial time complexity).

Using this algorithm, we can check if all P-configurations contain the support of a P-flow. If the answer is negative, we can compute P-configurations not containing the support of a P-semiflow checking for each P-configuration $P-\mathcal{C}_j$ with the associated token flow matrix $\boldsymbol{C_j}$ if the following system has a solution: $\exists \boldsymbol{y}\geq 0$, $\boldsymbol{y} \neq 0$ such that $\boldsymbol{y} \cdot \boldsymbol{C_j} = 0$. If we prove that they cannot be equilibrium P-configurations, the system is monotone.

6 Case study

The PN system in Fig. 9 represents an assembly line with kanban strategy (see Zimmermann et al. (2001)). The system has two stages connected by transition t ₁₄. The first one is composed by three lines starting with p ₂, p ₃ and p ₄, three machines p ₂₃, p ₂₄ and p ₂₅ and three buffers p ₂₆, p ₂₇ and p ₂₈. The second stage has two lines that share the resource p ₁₈. The number of kanban cards are given by the markings of p ₂, p ₃, p ₄, p ₃₂.

Fig. 9

An assembly line with kanban strategy. The net is mono-T-semiflow (There exists no equal conflict to be reduced)

The number of reachable markings for the initial marking in the figure is 209704. Having so many states, we want to approximate the model with its continuous approximation. Considering that the firing of every transition takes 1 t.u., which firing semantics will approximates better the throughput in steady state?

First, it is easy to observe that every transition has at least one place with its marking not greater than one at every time moment, hence the discrete net has the same behavior under finite and infinite server semantics. Thus it is not necessary to make explicit the servers to compare the continuous approximations. This PN has 12 minimal P-semiflows covering all places so it is conservative and has one minimal T-semiflow covering all transitions so it is consistent, and mono-T-semiflow. Applying any algorithm from Section 5 we obtain that every P-configuration contains the support of a P-semiflow. Applying Theorem 1, the throughput in steady state of continuous model with infinite server semantics will be closer than finite server semantics to the throughput of the deterministic discrete net. This is obtained also by simulations. The throughput of the (discrete) timed PN is 0.125, of the continuous net with infinite server semantics is 0.167 while with finite server semantics is 1.

Observe that the conditions of Theorem 3 are also satisfied. Therefore, increasing the speed of some transitions or the marking of some places, the throughput of the contPN with infinite server semantics will be greater or equal.

7 Conclusions

Mono-T-semiflow reducible contPN have been discussed in this paper. First, a comparison between finite and infinite firing semantics, the two most used for timed contPN systems is provided. A “good” firing semantics for timed contPNs should provide a time evolution “similar” to the discrete model. Being a relaxation, an identical result is practically impossible to obtain. In the actual level of knowledge, in general it is difficult to answer to this question, although, in practice, infinite server semantics is usually better than finite server semantics. In this paper we have proved that for mono-T-semiflow reducible contPN systems with all the equilibrium P-configurations containing the support of a P-semiflow, the throughput in steady state with infinite server semantics is always closer to the throughput of the discrete net. Moreover, under the same conditions, monotonicity with respect to the firing rate $\boldsymbol{\lambda}$ and with respect to the initial marking $\boldsymbol{m_0}$ is obtained. Finally, two methods to check the conditions are presented.