---
abstract: 'We study a continuous dynamics for a class of Petri nets which allows the routing at non-free choice places to be determined by priorities rules. We show that this dynamics can be written in terms of policies which identify the bottleneck places. We characterize the stationary solutions, and show that they coincide with the stationary solutions of the discrete dynamics of this class of Petri nets. We provide numerical experiments on a case study of an emergency call center, indicating that pathologies of discrete models (oscillations around a limit different from the stationary limit) vanish by passing to continuous Petri nets.'
address:
- 'INRIA and CMAP, École polytechnique, CNRS, Université de Paris-Saclay'
- 'École des Ponts ParisTech INRIA and CMAP, École polytechnique, CNRS, Université de Paris-Saclay Brigade de sapeurs-pompiers de Paris'
author:
- Xavier Allamigeon
- Vianney Bœuf
- Stéphane Gaubert
title: Stationary solutions of discrete and continuous Petri nets with priorities
---

[^1]

Introduction
============

Context {#context .unnumbered}
-------

The study of continuous analogues of Petri nets dates back to the works of David and Alla [@david1987continuous] and Silva and Colom [@silva1987structural] in 1987. It has given rise to a large scope of research in the field of Petri nets. Whereas classical (discrete) Petri nets belong to the class of discrete event dynamic systems, the circulation of tokens in continuous Petri nets is a continuous phenomenon: tokens are assumed to be fluid, [*i.e.*]{}, a transition can fire an infinitesimal quantity of tokens. In this way, the continuous dynamics can be represented by a system of ordinary differential equations or differential inclusions.

Continuous Petri nets are usually introduced as a relaxed approximation of Petri nets, that helps understanding some of the properties of the underlying discrete model, allowing one to overcome the state space explosion that can occur in the latter. The continuous framework can also be seen as a scaling limit of a class of stochastic Petri nets (see [@darling2008diff]), where the marking $M_p$ of place $p$ in the fluid model is the finite limit of $M_p(N)/N$, with $N$ being a scaling ratio tending to infinity, and where the firing times of transitions follow a Poisson distribution.

An important effort has been devoted to the comparison between continuous nets and their discrete counterparts. For example, the relationship between reachability of continuous Petri nets and of discrete Petri nets is well understood (see [@recalde1999autonomous]). A recent introduction to continuous models can be found in [@vazquez2013introduction], while a more extensive reference is [@david2010discrete].

In order to evaluate the long-term performance of Petri nets, one has to characterize the stationary or steady states of the Petri nets dynamics. Cohen, Gaubert and Quadrat [@cohen1995asymptotic] introduced an approximation of a discrete Petri net by a fluid, piecewise affine dynamics with finite delays, and showed that the limit throughput does exist for a class of consistent and free choice Petri nets. In the more recent work of Gaujal and Giua [@gaujal2004optimal], the result is extended to larger classes of Petri nets, and the stationary throughputs are computed as the solutions of a linear program. The results obtained using this fluid approximation hardly apply to the discrete model, up to a remarkable exception identified by Bouillard, Gaujal and Mairesse [@bouillard2006extremal] (bounded Petri nets under total allocation). This reference illustrates the many difficulties that arise from the discrete setting (*e.g.*, some firing sequences may lead to a deadlock).

In the continuous dynamics setting, with time attached to transitions, Recalde and Silva [@recalde2000pn] showed that the steady states of free choice Petri nets as well as upper bounds of the throughputs in larger classes of Petri nets can be determined by linear programming. However, in general, the asymptotic throughputs are non-monotone with respect to the initial marking or the firing rates of the transitions [@mahulea2006performance]. An example of oscillations in infinite time around a steady state is also given in [@mahulea2008steady].

Contributions {#contributions .unnumbered}
-------------

We propose a continuous dynamics of Petri nets where time is attached to places and not to transitions. The main novelty is that it handles a class of Petri nets in which tokens can be routed according to priority rules (Section \[sec:semantics\]). We initially studied this class in [@allamigeon2015performance] in the discrete setting, motivated by an application to the performance analysis of an emergency call center.

We show that the continuous dynamics can equivalently be expressed in terms of [*policies*]{}. A policy is a map associating with every transition one of its upstream places. In this way, the dynamics of the Petri net can be written as an infimum of the dynamics of subnets induced by the different policies. The policies reaching the infimum indicate the places which are bottleneck in the Petri net. On any time interval in which a fixed policy reaches the infimum, the dynamics reduces to a linear dynamics (Section \[sec:policies\]).

We characterize the stationary solutions in terms of the policies of the Petri net. This allows us to set up a correspondence between the (ultimately affine) stationary solutions of the discrete dynamics that were described in [@allamigeon2015performance] and the stationary solutions of the continuous dynamics (Section \[sec:4\]). We also relate the continuous stationary solutions to the initial marking of the Petri net. This relies on restrictive assumptions, in particular the semi-simplicity of a 0 eigenvalue of a matrix associated with a policy.

We finally provide some numerical simulations of the continuous dynamics. We consider a model of emergency call center with two hierarchical levels for handling calls, originating from a real case study (17-18-112 call center in the Paris area) [@allamigeon2015performance]. On this Petri net, numerical experiments illustrate the convergence of the trajectory towards the stationary solution. This exhibits an advantage of the continuous setting in comparison to the discrete one, in which, for certain values of the parameters, the asymptotic throughputs computed by simulations differ from the stationary solutions (Section \[sec:numerical experiments\]).

Related work {#related-work .unnumbered}
------------

The motivation of this work stems from our previous study [@allamigeon2015performance], in which we addressed the same class of Petri nets with priorities in the discrete setting, and applied it to the performance analysis of an emergency call center. The discrete dynamics is shown there to be given by piecewise affine equations (tropical analogues of rational equations). The idea of modeling priority rules by piecewise affine dynamics originated from Farhi, Goursat and Quadrat [@farhi], who applied it to a special class of road traffic models. In the discrete setting, limit time-periodic behaviors can occur. They may lead to asymptotic throughputs different from the affine stationary solutions of the dynamics, a pathology which motivates our study of a continuous version of the dynamics.

The “continuization” of our dynamics draws inspiration from the original continuous model where time is attached to transitions. In particular, the situation in which the routing of a token at a given place is influenced by the firing times of the output transitions through a race policy has received much attention, see [@vazquez2013introduction]. Here, we address the situation in which the routing is specified by priority or preselection rules which are independent of the processing rates. To do so, it is convenient to attach times to places, instead of attaching firing rates to transitions. We point out in Remark \[rk:comparison\] that our model can be reduced to a variant of the standard continuous model [@vazquez2013introduction] in which we allow immediate transitions and require non-trivial routings to occur only at these transitions. A benefit of our presentation is to allow a more transparent comparison between the continuous model and the discrete time piecewise affine models studied in [@cohen1995asymptotic; @gaujal2004optimal; @allamigeon2015performance].

The use of the term “policy” refers to the theory of Markov decision processes, owing to the analogy between the discrete time dynamics and the value function of a semi-Markovian decision process. Note that in the context of continuous Petri nets, policies are also known as “configurations”, see [@mahulea2006performance] for an example.

Continuous dynamics of Petri nets {#sec:semantics}
=================================

General notation {#sec:notations}
----------------

A Petri net consists of a set ${\mathcal{P}}$ of places, a set ${\mathcal{Q}}$ of transitions and a set of arcs $\mathcal{E} \subset ({\mathcal{P}}\times {\mathcal{Q}}) \cup ({\mathcal{Q}}\times {\mathcal{P}})$. Every arc is given a valuation in ${\mathbb{N}}$. Each place $p \in {\mathcal{P}}$ is given an initial marking $M^0_p \in {\mathbb{N}}$, which represents the number of tokens initially occurring in the place.

We denote by $a^+_{qp}$ the valuation of the arc from transition $q$ to place $p$, with the convention that $a^+_{qp}=0$ if there is no such arc. Similarly, we denote by $a^-_{qp}$ the valuation of the arc from place $p$ to transition $q$, with the same convention. We set $a_{qp} := a^+_{qp} - a^-_{qp}$. The ${\mathcal{Q}}\times {\mathcal{P}}$ matrix $A = (a_{qp})_{q \in {\mathcal{Q}}, p \in {\mathcal{P}}}$ is referred to as the *incidence matrix* of the Petri net, and its transpose matrix $C := A{^\mathsf{T}}$ as its *token flow matrix*. We also denote by $C^+$ (resp. $C^-$) the ${\mathcal{P}}\times {\mathcal{Q}}$ matrix with entry $a_{qp}^+$ (resp. $a_{qp}^-$), so that $C = C^+ - C^-$. We limit our attention to *pure* Petri nets, [*i.e.*]{}, Petri nets with no self-loop: for every pair $(q,p)$, at least one of $a^+_{qp}$ and $a^-_{qp}$ is zero.

We denote by $q{^{\textrm{in}}}$ the set of upstream places of transition $q$ and by $q{^{\textrm{out}}}$ the set of downstream places of transition $q$. Similarly, we use the notation $p{^{\textrm{in}}}$ and $p{^{\textrm{out}}}$ to refer to the sets of input and output transitions of a place $p$.

Petri nets with free choice and priority routing
------------------------------------------------

In this paper, we consider a class of Petri nets in which places are either free choice or subject to priority. Recall that a place $p\in {\mathcal{P}}$ is said to be *free choice* if either all the output transitions $q \in p{^{\textrm{out}}}$ satisfy $q{^{\textrm{in}}}= \{p\}$ (*conflict*, see Figure \[fig:configuration\](a)), or $|p{^{\textrm{out}}}| = 1$ (*synchronization*, see Figure \[fig:configuration\](b)). A place is *subject to priority* if its tokens are routed to output transitions according to a priority rule. We refer to Figure \[fig:configuration\](c) for an illustration. For the sake of simplicity, we assume that each place subject to priority has exactly two output transitions, and that any transition has at most one upstream place subject to priority. Given a place $p$ subject to priority, we denote by $q^+(p)$ and $q^-(p)$ its two output transitions, with the convention that $q^+(p)$ has priority over $q^-(p)$. For the sake of readability, we use the notation $q^+$ and $q^-$ when the place $p$ is clear from context.

The set of transitions such that every upstream place $p$ satisfies $|p{^{\textrm{out}}}| = 1$ is referred to as ${\mathcal{Q}_\textsf{sync}}$ and the set of free choice places that have at least two output transitions is referred to as ${\mathcal{P}_\textsf{conflict}}$. We denote by ${\mathcal{P}_\textsf{priority}}$ the set of places subject to priority. The sets $({\mathcal{P}_\textsf{conflict}}){^{\textrm{out}}}$, ${\mathcal{Q}_\textsf{sync}}$ and $({\mathcal{P}_\textsf{priority}}){^{\textrm{out}}}$ form a partition of ${\mathcal{Q}}$. Figure \[fig:configuration\] hence summarizes the three possible place/transition patterns that can occur in this class of Petri nets.

![Conflict, synchronization and priority patterns[]{data-label="fig:configuration"}](main-FINAL-figure0.pdf)

Continuous dynamics and routing rules
-------------------------------------

We now equip the Petri net with a continuous semantics. Given a transition $q$, we associate a flow $f_q(t)$ which represents the instantaneous firing rate of transition $q$ at time $t$. We also associate with each place $p$ a [*marking*]{} $M_p(t)$, which is a continuous real valued function of the time $t$. In the case of [*discrete*]{} timed Petri nets, one typically requires that every token stays a minimum time in the place, — at this stage, the token may be considered as [*under processing*]{} — before becoming available for the firing of output transitions. To capture this property in the continuous setting, we assume that the marking $M_p(t)$ can be decomposed as $M_p(t)=m_p(t)+w_p(t)$, where $m_p(t)$ is the quantity of tokens under processing and $w_p(t)$ is the quantity of tokens waiting to contribute to the firing of an output transition.

We associate with each place $p$ a time constant $\tau_p>0$. Each token entering in a place is processed with the rate $1/\tau_p$. This leads to the following differential equation: $$\label{eq:mp}
  \dot{m}_p(t) = \sum_{q \in p{^{\textrm{in}}}}a_{qp}^+f_q(t) - \dfrac{m_p(t)}{\tau_p} \, .$$ The evolution of the number of tokens waiting in place $p$ is described by the relation: $$\label{eq:wp}
  \dot{w}_p(t) = \dfrac{m_p(t)}{\tau_p} - \sum_{q\in p{^{\textrm{out}}}} a_{qp}^- f_{q}(t) \, .$$ Moreover, for all transition $q$, we require that $$\min_{p\in q{^{\textrm{in}}}, \, w_p(t)=0}\Big(
\dfrac{m_p(t)}{\tau_p} - \sum_{q'\in p{^{\textrm{out}}}} a^-_{q'p}f_{q'}(t)\Big)  =0 
\,.
\label{eq:earliest}$$ In particular, this implies that at least one place $p \in q{^{\textrm{in}}}$ verifies $w_p(t) = 0$. In this case, means that each of the upstream places $p$ that has a zero quantity of waiting tokens ($w_p(t)=0$) must satisfy $\dot{w}_p(t)\geq 0$, and that at least one of these places satisfies $\dot{w}_p(t)=0$. In other words, there is at least one *bottleneck* upstream place $p$ of $q$, which has no waiting tokens and whose outgoing flow $\sum_{q'\in p{^{\textrm{out}}}} a^-_{q'p}f_{q'}(t)$ coincides with its processing flow ${m_p(t)}/{\tau_p}$.

The relation provided in  can be simplified in the case of conflict and synchronization patterns. In more detail, if $q$ has a unique upstream place $p$, and this place is free choice ([conflict]{}), then  reduces to: $$\label{eq:conflict}
\dfrac{m_p(t)}{\tau_p} - \sum_{q'\in p{^{\textrm{out}}}} a^-_{q'p}f_{q'}(t) =0 \,.$$ Now, if $q$ has several upstream places, which are all free choice ([synchronization]{}), then reads as: $$\label{eq:sync}
f_{q}(t) = \min_{p\in q{^{\textrm{in}}}, \, w_p(t)=0} \dfrac{m_p(t)}{a^-_{qp}\tau_p} \, .$$ This equation also holds if $|q{^{\textrm{in}}}| = 1$ and if the upstream place of $q$ has a single output transition.

We respectively denote by $m(t)$, $w(t)$ and $f(t)$ the vectors of entries $m_p(t)$, $w_p(t)$ and $f_q(t)$.

Albeit the dynamics that we presented so far is piecewise affine, a trajectory $t \mapsto (m(t), w(t), f(t))$ may be discontinuous. Indeed, in , the set of the places over which the minimum is taken may change over time. If at time $t$, there is a new place $p \in q{^{\textrm{in}}}$ such that $w_p(t)$ cancels, and if the quantity ${m_p(t)}/(a^-_{qp}\tau_p)$ is sufficiently small, then the minimum in  (and subsequently the flow $f_q(t)$) discontinuously jumps to the latter value.

Initial conditions of the dynamics are specified by a pair $(m(t_i),w(t_i))$ such that the minimum in  makes sense, [*i.e.*]{}, at least one $w_p(t_i)$ is equal to $0$ for each set of places $q{^{\textrm{in}}}$. One can easily show that if the set $\{ p \in q{^{\textrm{in}}}\colon w_p(t) = 0\} $ is nonempty for all transition $q \in {\mathcal{Q}}$ at time $t = t_i$, then it remains nonempty for all time $t \geq t_i$.

The dynamics – may admit different trajectories for a given initial condition. These correspond to different routings of tokens in places with several output transitions. However, each of these trajectories satisfies the conservation law: $$\label{eq:flow_conservation_eq}
  \dot{m}(t) + \dot{w}(t) = C f(t) \, ,$$ where $C$ is the token flow matrix of the Petri net. Recall that a *P-invariant* of the Petri net refers to a nonnegative solution $y$ of the system $y{^\mathsf{T}}C = 0$. In the discrete setting, a P-invariant corresponds to a weighting of places that is constant for any reachable marking, meaning that the quantity $y {^\mathsf{T}}M$ is preserved under any firing of transition. An analogous statement holds in the continuous setting:

Given a P-invariant $y$ of the Petri net, the quantity $y{^\mathsf{T}}(m(t) + w(t))_{p \in {\mathcal{P}}}$ is independent of $t$.

In particular, if the entries of $y$ are all positive, then the Petri net is bounded, [*i.e.*]{}, each function $t \mapsto M_p(t)$ is bounded.

The proof consists in multiplying both sides of  by the invariant $y$. It follows that the derivative of $y{^\mathsf{T}}(m(t) + w(t))_{p \in {\mathcal{P}}}$ is zero. If the entries of $y$ are all positive, then $\bigl(y{^\mathsf{T}}(m(0) + w(0))_{p \in {\mathcal{P}}}\bigr)/y_p$ is an upper bound to the marking of any place $p$.

The following proposition collects several homogeneity properties of the continuous dynamics:

\[thm:prop2\] Let $(m(t),w(t),f(t))$ be a trajectory solution of the dynamics –, with the initial markings $(m_p(0))_{p \in {\mathcal{P}}}$, and the holding times $(\tau_p)_{p \in {\mathcal{P}}}$ and let $\alpha \in {\mathbb{R}_{> 0}}$, then:

(i) $(\alpha m(t), \alpha w(t), \alpha f(t))$ is a trajectory solution of the dynamics, associated with the initial markings $(\alpha m_p(0))_{p \in {\mathcal{P}}}$.

(ii) $(m(t/\alpha),w(t/\alpha),(1/\alpha)f(t/\alpha))$ is a trajectory solution of the dynamics, associated with the holding times $(\alpha \tau_p)_{p \in {\mathcal{P}}}$ and the same initial conditions.

(iii) let $x$ be a vector of the kernel of $C$, and $D = \text{diag}(\tau)$ be the ${\mathcal{P}}\times {\mathcal{P}}$ diagonal matrix such that $D_{pp} = \tau_p$, then $(m(t) + \alpha D C^+ x, w(t), f(t) + \alpha x)$ is a trajectory solution of the dynamics, associated with the initial markings $(m(0) + \alpha D C^+ x)$.

The first two statements derive easily from the homogeneity properties of Equations –. For the third statement, one can note that adding $\alpha x_q$ to the $f_q(t)$ and adding $\alpha \sum_{q\in p{^{\textrm{in}}}} a_{qp}^+ x_q$ to the $m_p(t)/\tau_p$ in – does not change the right hand sides of  and , or the expression within the minimum in . For  and , this is due to the fact that $(C^+ - C^-) x = C x = 0$.

We now complete the description of the continuous dynamics by additional equations which arise from the specification of routing rules. Such rules occur in the following two situations:

Given $p \in {\mathcal{P}_\textsf{conflict}}$, we suppose that tokens are routed according to a stationary distribution specified by weights $\mu_{qp} > 0$ associated with each output transition $q$. Therefore, $$\label{eq:conflict_routing}
  \forall p \in {\mathcal{P}_\textsf{conflict}}, \; \forall q \in p{^{\textrm{out}}}, \quad a^-_{qp}f_q(t) = \mu_{qp} \dfrac{m_p(t)}{\tau_p} \, .$$

Let $p \in {\mathcal{P}_\textsf{priority}}$, and $q_+$ and $q_-$ be the two output transitions, as illustrated in (c). In order to specify that the flow is routed in priority to transition $q_+$, we require that: $$\begin{aligned}
f_{q_+}(t) &= \min_{r \in q_+{^{\textrm{in}}}, \, w_r(t) = 0} \dfrac{m_r(t)}{a^-_{q_+{r}}\tau_r} \,,
\label{eq:p1}\\
f_{q_-}(t) &= \begin{cases}
    \min_{r \in q_-{^{\textrm{in}}}\setminus \{{p}\},  w_r(t) = 0} \dfrac{m_r(t)}{a^-_{q_-r}\tau_r} & \text{if}\  w_{{p}}(t) \neq 0 \, ,\\
\min \Bigl(\dfrac{m_{{p}}(t)}{a^-_{q{p}}\tau_{{p}}} - \dfrac{a^-_{q_+{p}}}{a^-_{q{p}}}f_{q_+}(t) \, , \min_{r \in q_-{^{\textrm{in}}}\setminus \{{p}\}, w_r(t) = 0} \dfrac{m_r(t)}{a^-_{q_-r}\tau_r}
\Big) 
& \text{if}\  w_{{p}}(t) = 0 \, .
    \end{cases} 
\label{eq:p2}\end{aligned}$$

The expression of $f_{q_-}(t)$ in , when $w_{p}=0$, indicates that only the outgoing flow from ${p}$ that is not already consumed by the priority transition $q_+$ is available to $q_-$.

The first two properties of homogeneity in Proposition \[thm:prop2\] are still satisfied by the dynamics extended by the routing rules –.

\[rk:comparison\] We already mentioned in the introduction that our model differs from the standard continuous Petri net model in which transitions are equipped with firing rates, in the sense that in the latter model, the flows of the output transitions of a given place are pairwise independent. To overcome this limitation, *immediate transitions* have been introduced [@recalde2006improving]. These transitions come with the specification of routing rules, for instance, in the case of conflict pattern. In this way, our model could be reduced to a classical continuous model enriched with immediate transitions. In this reduction, we require timed transitions to have exactly one upstream place and one downstream place, so that all the routing is determined by immediate transitions, which inherit the equations defined in our place-timed dynamics.

Simply put, our model is the continuous analogue of discrete Petri nets equipped with “holding durations”, in which tokens are frozen during processing, whereas the usual continuous Petri net model can be seen as the continuous analogues of Petri nets with “enabling durations”, in which transitions preempt tokens. We refer to [@bowden2000brief] for a discussion on the meaning of time in Petri nets.

Policies and bottleneck places {#sec:policies}
==============================

The analysis of the piecewise affine dynamical system – leads to introduce the notion of [*policy*]{}. Fixing a policy allows one to solve the dynamics on a region where it is linear. We shall see in that policies also arise in the characterization of stationary solutions.

Even if our continuous dynamics holds for more general classes of Petri nets, we focus in the following on strongly connected, autonomous Petri nets, so that each transition has at least one upstream place.

We observe that the dynamics of Petri nets with free choice and priority routing –, and – is linear on each region where the arguments of the minimum operators do not change. More precisely, at any time $t$, for any transition $q \in {\mathcal{Q}}$, there exists a place $p \in q{^{\textrm{in}}}$ such that $w_p(t)=0$ and $p$ is the unique upstream place of $q$ or $p$ realizes the minimum in the expression , or of $f_q(t)$. Place $p$ is then referred to as the *bottleneck place* of transition $q$ at time $t$.

We define a *policy* $\pi$ as a function from ${\mathcal{Q}}$ to ${\mathcal{P}}$, which maps any transition $q$ to one of its upstream places $p_{\pi}(q) \in q{^{\textrm{in}}}$. A policy is meant to indicate the bottleneck place of each transition $q$. We denote by $S_{\pi}$ the [*selection matrix*]{} associated with $\pi$, that is, the ${\mathcal{Q}}\times {\mathcal{P}}$ matrix such that $(S_{\pi})_{qp} = 1$ if $p = p_{\pi}(q)$, and $0$ otherwise. In particular, $(S_{\pi})_{qp} = 1$ implies that $a_{qp} < 0$.

Note that, if $p$ realizes the minimum in one of the equations , or  for some transition, then $p$ also realizes the minimum in . The converse is not true if places are subject to priority. For $p$ denoting a priority place and $q_+$ its priority output transition, if $p$ realizes the minimum in  for transition $q_+$, then, $p$ does not necessarily realize the minimum in . In other words, our definition of a bottleneck place is dependent on the routing rules of the net.

We point out that notions comparable to policies are used in [@mahulea2006performance] in the context of continuous Petri nets with time attached to transitions.

The dynamics of a Petri net can be expressed in terms of the different policies of the net: at any time $t$, there is a policy $\pi^*$ (we can note $\pi^*(t)$ if we want to emphasize the dependence on time) such that $$\forall q \in {\mathcal{Q}}\, , \quad w_{p_{\pi^*}(q)}(t) = 0 \,, $$ and $$\begin{aligned}
  &\forall q \in {\mathcal{Q}}\text{ s.t.\ } p_{\pi^*}(q) \not\in ({\mathcal{P}_\textsf{conflict}}\cup {\mathcal{P}_\textsf{priority}}) \,, \; \dfrac{m_{p_{\pi^*}(q)}(t)}{\tau_{p_{\pi^*}(q)}} = a^-_{qp_{\pi^*}(q)} f_q(t) \,,\\
  &\forall q \in {\mathcal{Q}}\text{ s.t.\ } p_{\pi^*}(q) \in {\mathcal{P}_\textsf{conflict}}\,, \quad \dfrac{m_{p_{\pi^*}(q)}(t)}{\tau_{p_{\pi^*}(q)}} = \dfrac{a^-_{qp_{\pi^*}(q)}}{\mu_{qp_{\pi^*}(q)}} f_q(t) \,,\\
  &\forall q_+ \in {\mathcal{Q}}\text{ s.t.\ } p_{\pi^*}(q_+) \in {\mathcal{P}_\textsf{priority}}\,, \; \dfrac{m_{p_{\pi^*}(q_+)}(t)}{\tau_{p_{\pi^*}(q_+)}} = a^-_{q_+p_{\pi^*}(q_+)} f_{q_+}(t) \,,\\
  &\forall q_- \in {\mathcal{Q}}\text{ s.t.\ } p_{\pi^*}(q_-) \in {\mathcal{P}_\textsf{priority}}\,, \; \dfrac{m_{p_{\pi^*}(q_-)}(t)}{\tau_{p_{\pi^*}(q_-)}}
   = a^-_{q_-p_{\pi^*}(q_-)} f_{q_-}(t)
   + a^-_{q_+p_{\pi^*}(q_+)} f_{q_+}(t) \,.
\end{aligned}$$

Now, for any policy $\pi$, we denote by ${C^-_{\pi}}$ the ${\mathcal{Q}}\times {\mathcal{Q}}$ matrix such that the right-hand side of this system of equations reads ${C^-_{\pi}}f(t)$ , where $f(t)$ is the vector of the $(f_q(t))_{q \in {\mathcal{Q}}}$. In particular, the above system writes $$S_{\pi^*} \left(\dfrac{m(t)}{\tau}\right) = {C^-_{\pi^*}}f(t) \,,$$ where $(m(t)/\tau)$ is the vector of the $(m_p(t)/\tau_p)_{p \in {\mathcal{P}}}$. The diagonal entries of ${C^-_{\pi}}$ are positive. Moreover, if we order each transition of type $q_+$ before its associated transition $q_-$, the matrix ${C^-_{\pi}}$ becomes lower triangular.[^2] Hence, ${C^-_{\pi}}$ is invertible. Matrix ${C^-_{\pi}}$ can be seen as a specification of the downstream token flow matrix of the Petri net $C^-$ (introduced in Section \[sec:notations\]), associated with the policy $\pi$.

With this notation, the continuous dynamics of Petri nets with free choice and priority routing reads:

\[eq:matrix\_dyn\_system\] $$\begin{aligned}
  f(t) &= \inf_{\pi \text{ s.t. } S_{\pi} w (t) = 0} ({C^-_{\pi}})^{-1} S_{\pi} \left( \dfrac{m(t)}{\tau} \right) \label{eq:matrix_dyn_f} \,,\\
  \dot{m}(t) &= C^+ f(t) - \dfrac{m(t)}{\tau} \label{eq:matrix_dyn_dot_m} \,,\\
  \dot{w}(t) &= \dfrac{m(t)}{\tau} - C^- f(t) \label{eq:matrix_dyn_dot_w} \,,
  \end{aligned}$$

where the infimum must be understood for the partial order over ${\mathbb{R}}^{\mathcal{Q}}$ induced by $\leq$. Note that there is at least one policy $\pi^*$ (depending on $t$) attaining the infimum. It suffices to choose the policy $\pi^*$ introduced earlier ([*i.e.*]{}, to choose a policy that attains the minimum componentwise).

By choosing an upstream place for each transition, a policy actually defines a candidate “bottleneck net” of the Petri net, that is, a subnet with all the transitions of the original Petri net, and such that each transition has a unique upstream place. On each of these subnets, the dynamics is linear and yields a unique trajectory for a given initial condition. The trajectory is solved on a subnet of the original Petri net, but one can easily recover the solution over the whole Petri net. This applies to the original dynamics of the system, on any time interval over which the infimum is reached by a constant policy, as stated in the following proposition.

\[thm:fc\_prio\_unicity\] Suppose that there is a policy $\pi^*$ which reaches the infimum in  for all time $t$ in the interval $[t_i, t_f]$. Then the dynamics of the Petri net with free choice and priority routing reduces to a linear system, which admits a unique solution, given the initial conditions $(m(t_i), w(t_i))$.

If $\pi^*$ reaches the infimum for any $t \in [t_i, t_f]$, then the continuous dynamics of the Petri net reads:

\[eq:const\_pi\_dyn\_system\] $$\begin{aligned}
  {C^-_{\pi^*}}f(t) &= S_{\pi^*} \left(\dfrac{m(t)}{\tau} \right) \label{eq:const_pi_dyn_f} \,, \\
  \dot{m}(t) &= C^+ f(t) - \dfrac{m(t)}{\tau} \label{eq:const_pi_dyn_dot_m} \,, \\
  \dot{w}(t) &= \dfrac{m(t)}{\tau} - C^- f(t) \label{eq:const_pi_dyn_dot_w} \,, \\
  S_{\pi^*} w (t) &= 0  \,, \label{eq:const_pi_dyn_w}
  \end{aligned}$$

which is a linear system.

We multiply  by $S_{\pi^*}$, and replace the term $S_{\pi^*} (m(t)/\tau)$ by its expression given in . This leads to: $$S_{\pi^*} \dot{m}(t) = S_{\pi^*}C^+ f(t) - {C^-_{\pi^*}}f(t) \,.$$

Let $D = \text{diag}(\tau)$ be the ${\mathcal{P}}\times {\mathcal{P}}$ diagonal matrix such that $D_{pp} = \tau_p$, then $D_{\pi} \mathrel{:=} S_{\pi} D {S_{\pi}}{^\mathsf{T}}$ is the ${\mathcal{Q}}\times {\mathcal{Q}}$ diagonal matrix such that $(D_{\pi})_{qq} = \tau_{p_{\pi}(q)}$. Equation  then writes $S_{\pi^*} m(t) = D_{\pi^*} {C^-_{\pi^*}}f(t)$. This leads to: $$\dot{f}(t) = ({C^-_{\pi^*}})^{-1} D_{\pi^*}^{-1} \left( S_{\pi^*} C^+  -  {C^-_{\pi^*}}\right) f(t) \, ,$$ which is an ordinary differential system. Moreover, the $f(t_i)$ can be obtained from the $m(t_i)$ by , so that this system admits a unique solution $f$ for all $t \in [t_i, t_f]$.

Given this solution $f$, one can successively solve the differential system in ${m}$ given by  and the differential system in ${w}$ given by , whose initial conditions are known, so that the whole dynamics admits a unique trajectory.

Stationary solutions {#sec:4}
====================

In this section, we prove that the stationary solutions of the continuous and discrete dynamics of a timed Petri net with free-choice and priority routing are the same. To do so, we first recall in Section \[sec:stationary\_discrete\] the formulation of the discrete dynamics and the associated stationary solutions given in [@allamigeon2015performance].

Stationary solutions of the discrete dynamics {#sec:stationary_discrete}
---------------------------------------------

The discrete dynamics of Petri nets with free choice and priority is expressed in terms of *counter variables* associated with transitions and places. Given a transition $q$, the counter variable $z_q: {\mathbb{R}_{\geq 0}}\to {\mathbb{N}}$ denotes the number of firings of $q$ that occurred up to time $t$ included. Similarly, the counter variable of place $p$ is a function $x_p:{\mathbb{R}_{\geq 0}}\to {\mathbb{N}}$ which represents the number of tokens that have visited place $p$ up to time $t$ included (taking into account the initial marking). On top of being non-decreasing, the counter variables are *[[càdlàg]{}]{}* functions, which means that they are right continuous and have a left limit at any time.

In this setting, the parameter $\tau_p$ associated with the place $p$ represents a minimal holding time. It is shown in [@allamigeon2015performance] that, if tokens are supposed to be fired as early as possible, the counter variables satisfy the following equations (we generalize the equations to the case with valuations):

\[eq:discrete\] $$\begin{aligned}
 \forall p \in {\mathcal{P}}\,&, \quad x_p(t) =  M_p^0  + \sum_{q\in p{^{\textrm{in}}}} a^+_{qp} z_q(t) \, , \label{eq:pnpriority1} \\
 \forall p \in {\mathcal{P}_\textsf{conflict}}\,&, \quad \sum_{q \in p{^{\textrm{out}}}} a^-_{qp} z_q(t) = x_p(t - \tau_p) \, ,\label{eq:pnpriority2} \\
 \forall q \in {\mathcal{Q}_\textsf{sync}}\,&, \quad z_q(t) = \min_{p \in q{^{\textrm{in}}}} x_p(t - \tau_p) / a^-_{qp} \, ,\label{eq:pnpriority3}
 \end{aligned}$$ $$\begin{aligned}
\forall & p \in {\mathcal{P}_\textsf{priority}}\,, \nonumber\\
 &
 z_{q_+}(t) = \min\biggl( 
\Bigl(\dfrac{1}{a^-_{q_+p}}x_p(t-\tau_p) - \dfrac{a^-_{q_-p}}{a^-_{q_+p}} \lim_{s \uparrow t} z_{q_-}(s) \Bigr),\min_{{r \in q_+{^{\textrm{in}}}, r \neq p}} \dfrac{1}{a^-_{q_+r}}x_r(t - \tau_r) \biggr)\, ,
 \label{eq:pnpriority4} \\
&
z_{q_-}(t) = \min \biggr(
\Bigl(\dfrac{1}{a^-_{q_-p}}x_p(t-\tau_p) - \dfrac{a^-_{q_+p}}{a^-_{q_-p}} z_{q_+}(t)\Bigr),
\min_{{r \in q_-{^{\textrm{in}}}, r \neq p}}\dfrac{1}{a^-_{q_-r}} x_r(t - \tau_r) \biggr) \, ,
\label{eq:pnpriority5}\end{aligned}$$

where $q_+$ ($q_-$) is the priority (non priority) output transition of $p \in {\mathcal{P}_\textsf{priority}}$.

Note that if all the holding times $\tau_p$ are integer multiples of a fixed time $\delta$, the left limit $\lim_{s \uparrow t}z_{q_-}(s)$ in  can be replaced by $z_{q_-}(t-\delta)$. This is helpful in particular to simulate these equations.

In the setting of [@allamigeon2015performance], all conflicts are solved by a stationary distribution routing. The equivalent of the routing rule introduced to solve conflicts in the continuous setting is obtained here by allowing the tokens to be shared in fractions, so that the counter functions take real values. This corresponds to a *fluid approximation* of the discrete dynamics. In this setting, for each $p \in {\mathcal{P}_\textsf{conflict}}$ and $q\in p{^{\textrm{out}}}$, we fix $\mu_{qp}>0$, giving the proportion of the tokens routed from $p$ to $q$. We have: $$\forall p \in {\mathcal{P}_\textsf{conflict}}\, , \, \forall q \in p{^{\textrm{out}}}\,, \quad z_q(t) = \dfrac{\mu_{qp}}{a^-_{qp}} x_p(t - \tau_p) \ . 
\label{eq:pnpriority6fluid}$$

The stationary solutions of the discrete dynamics are defined as functions $x_p$ and $z_q$ satisfying the relations – and which ultimately behave as affine functions, [*i.e.*]{}, $x_p(t) =  u_p + t \rho_p$ and $z_q(t) = u_q + t \rho_q$ for all $t$ large enough. In this case, $\rho_p$ (resp. $\rho_q$) represents the asymptotic throughput of place $p$ (resp. transition $q$). We have shown in [@allamigeon2015performance Theorem 3] that these stationary solutions are precisely given by following system (we generalize the equations to the case with valuations):

\[eq:fixpoint\_germ\_rho\] $$\begin{aligned}
\forall p \in {\mathcal{P}}\, , \qquad \rho_p& = \sum_{q \in p{^{\textrm{in}}}} a^+_{qp} \rho_q \label{eq:fixpoint_germ1_rho} \,, \\
\forall p \in {\mathcal{P}_\textsf{conflict}}\, , \forall q \in p{^{\textrm{out}}}\, , \qquad \rho_q & = \mu_{qp} \rho_p / a^-_{qp}
\label{eq:fixpoint_germ2_rho} \,, \\
\forall q \in {\mathcal{Q}_\textsf{sync}}\, , \qquad \rho_q & = \min_{p \in q{^{\textrm{in}}}} \rho_p/a^-_{qp} \label{eq:fixpoint_germ3_rho}\,, \\
\forall p \in {\mathcal{P}_\textsf{priority}}\, , \qquad
\rho_{q_+} &= \min_{r \in q_+{^{\textrm{in}}}} \rho_r / a^-_{q_+r} \label{eq:fixpoint_germ4_rho}\,, \\
\forall p \in {\mathcal{P}_\textsf{priority}}\, , \quad
\rho_{q_-} = \min \Big(
&{\big(\rho_p - a^-_{q_+p}\rho_{q_+}\big)}/{a^-_{q_-p} }, \min_{r \in q_-{^{\textrm{in}}}\setminus \{ p \}} {\rho_r}/{a^-_{q_-r}} \Big) \,,
\label{eq:fixpoint_germ5_rho} \end{aligned}$$

\[eq:fixpoint\_germ\_u\] $$\begin{aligned}
\forall p \in {\mathcal{P}}\, &, \quad u_p = M_p^0 + \sum_{q \in p{^{\textrm{in}}}} a^+_{qp} u_q \label{eq:fixpoint_germ1_u} \,, \\
\forall p \in {\mathcal{P}_\textsf{conflict}}\, , \forall q \in p{^{\textrm{out}}}&, \; u_q = (\mu_{qp}/a^-_{qp}) (u_p - \rho_p \tau_p) 
\label{eq:fixpoint_germ2_u} \,,\end{aligned}$$ $$\forall q \in {\mathcal{Q}_\textsf{sync}}\, , \quad u_q  = \min_{p \in q{^{\textrm{in}}}, \rho_q = \rho_p} (u_p - \rho_p \tau_p)/a^-_{qp} \label{eq:fixpoint_germ3_u} \,,$$ $$\begin{aligned}
\forall p &\in {\mathcal{P}_\textsf{priority}}\, , \nonumber\\ 
u_{q_+} & = \begin{dcases}
\min
\begin{multlined}[t]
\Big( (u_p - \rho_p \tau_p - a^-_{q_-p}u_{q_-})/a^-_{q_+p}, \\
\min_{r \in q_+{^{\textrm{in}}}\setminus \{p\}, \, \rho_{q_+} = \rho_r} (u_r - \rho_r \tau_r)/a^-_{q_+r} \Big) \end{multlined}
\quad &\text{if } \rho_{q_-} = 0 \, ,
 \\
\min_{r \in q_+{^{\textrm{in}}}\setminus \{p\}, \, \rho_{q_+} = \rho_r} (u_r - \rho_r \tau_r)/a^-_{q_+r} \quad &\text{otherwise,}
\end{dcases}\label{eq:fixpoint_germ4_u}
\\
u_{q_-} & = \begin{dcases}
\min
\begin{multlined}[t]
\Big( (u_p - \rho_p \tau_p - a^-_{q_+p} u_{q_+})/a^-_{q_-p}, \\
\min_{r \in q_-{^{\textrm{in}}}\setminus \{p\}, \, \rho_{q_-} = \rho_r} (u_r - \rho_r \tau_r)/a^-_{q_-r} \Big)
\end{multlined}
\quad &\!\!\! \text{if } \rho_{q_-} + \rho_{q_+} = \rho_p \, ,
 \\
\min_{r \in q_-{^{\textrm{in}}}\setminus \{p\}, \, \rho_{q_-} = \rho_r} (u_r - \rho_r \tau_r)/a^-_{q_-r} \quad &\text{otherwise.}
\end{dcases}\label{eq:fixpoint_germ5_u}\end{aligned}$$

The above equations are expressed in a more compact form in [@allamigeon2015performance], using a semiring of germs of affine functions, which encodes lexicographic minimization operations.

Stationary solutions of the continuous time dynamics {#sec:stationary_continuous}
----------------------------------------------------

In the continuous setting, we define a *stationary solution* as a solution $(m,w,f)$ of the continuous dynamics such that for any place, ${m_p}$ is constant and ${w_p}$ is affine ($\dot{w_p}$ is constant). The following theorem provides a characterization of the stationary solutions.

\[th:1\] A triple $(m,w,f)$ of vectors of resp. $|{\mathcal{P}}|$, $|{\mathcal{P}}|$ and $|{\mathcal{Q}}|$ functions from ${\mathbb{R}_{\geq 0}}$ to ${\mathbb{R}_{\geq 0}}$, with all the $m_p$ constant and all the $w_p$ affine, is a stationary solution of the continuous dynamics if and only if the following conditions hold:

$$\begin{aligned}
  \dfrac{m}{\tau} &= C^+ f
  \, , \label{eq:mpcns} \\
  \dot{w} &= \dfrac{m}{\tau} - C^- f
  \, , \label{eq:wpcns} \\
  C f &\geq 0 \, ,\label{eq:stat_nodes_law} \\
\shortintertext{and there exists a policy $\pi^*$, such that}
\label{eq:wp_annuler}
\forall t \,, \quad S_{\pi^*} w(t) &= 0 \, , \\
\label{eq:right_annuler}
\left( S_{\pi^*} C^+  -  {C^-_{\pi^*}}\right) f &= 0 \, .\end{aligned}$$

Note that the existence of an $f \gneq 0$ that satisfies  provides a simple algebraic necessary condition to the existence of a stationary flow in a Petri net. This corresponds to the net being [*partially repetitive*]{} (see [@murata1989petri] for a definition).

Equations  and  are derived from  and , with $\dot{m} =0$ for a stationary solution.

In a stationary solution, for any place $p$, $\dot{w}_p$ is constant, so that one cannot have $\dot{w}_p < 0$, otherwise this would yield $\lim_{t \rightarrow \infty} w_p(t) = -\infty$. Therefore, by , $(m/\tau) \geq C^- f$, and by , we can replace $(m/\tau)$ by $C^+ f$, and get .

As the $\dot{w}$ are constant, if, for some place $p$ and at some time $t_0 > 0$, $w_p(t_0) = 0$, then $\dot{w}_p =0$, (otherwise it would contradict $w_p(t) \geq 0$ for $0 \leq t < t_0$ or for $t > t_0$). Hence, the set of places $p$ such that $w_p(t) = 0$ is independent of time for $t > 0$.

Moreover, the $m_p$ are constant, so that, if a policy $\pi$ attains the minimum in  at some time, then it attains the minimum at any time. This means that, if $(m, w, f)$ is a solution of the continuous dynamics, then there exists a policy $\pi^*$ such that: $$\begin{aligned}
  \forall t \,, \quad S_{\pi^*} w(t) &= 0 \, , \\
  {C^-_{\pi^*}}f &= S_{\pi^*} \left( \dfrac{m}{\tau} \right) \,.\end{aligned}$$ Now, by  again, we can replace $m/\tau$ by $C^+ f$ in the above equation, and we get Equations  and .

Conversely, suppose that a triple of functions $(m,w,f)$ satisfies the conditions of the theorem, with policy $\pi^*$. We prove that the the relations given in  describing the dynamics are satisfied. First, and  are derived from  and , with $\dot{m}_p = 0$. We also note that, in Equations  and , replacing the term $C^+ f$ by $m/\tau$ (by ) leads to the following equations: $$\begin{aligned}
  C^- f &\leq \dfrac{m}{\tau}  \label{eq:stationary_ineq_mp} \,, \\
  f &= (C_{\pi^*}^-)^{-1} S_{\pi^*} (\dfrac{m}{\tau})\,. \label{eq:right_annuler_mp}\end{aligned}$$

Equations  and  show that $\pi^*$ attains the equality in . Hence, in order to prove , it is sufficient to prove that, for any $\pi$, we have $${C^-_{\pi}}f \leq S_{\pi} \left(\dfrac{m}{\tau}\right)\,. \label{eq:to_prove}$$ We prove this inequality row by row. Let $q$ be a transition. We distinguish the following cases:

-   if $q \in {\mathcal{Q}_\textsf{sync}}$, then $(C^- f)_{p_{\pi}(q)} = ({C^-_{\pi}}f)_q$ for any $\pi$ (for any choice of an upstream place of $q$) so that  follows from .

-   if $q$ has a unique upstream place $p$, with $p \in {\mathcal{P}_\textsf{conflict}}$, then for any $\pi$, $p_{\pi}(q) = p_{\pi^*}(q)$ so that  follows from .

-   assume now that $q_+$ is the priority transition of a place $p$ subject to priority. Then, by , $m_p/\tau_p \geq a^-_{q_+p} f_{q_+} + a^-_{q_-p} f_{q_-} \geq a^-_{q_+p} f_{q_+}$ and for $r \in q_+{^{\textrm{in}}}\setminus \{p\}$, ${m_r}/{\tau_r} \geq a^-_{{q_+}r} f_{q_+}$. Finally, for any $r \in q_+{^{\textrm{in}}}$, $a^-_{q_+p} f_{q_+} \leq {m_r}/{\tau_r}$. This proves .

-   let $q_-$ be the non priority transition of a place $p$ subject to priority. Then $(C^- f)_{p_{\pi}(q_-)} = ({C^-_{\pi}}f)_{q_-}$ for any policy $\pi$, so that  follows from .

As a consequence of , we obtain a correspondence between the stationary solutions of the continuous dynamics and the stationary solutions of the discrete dynamics. In order to highlight the parallel between the discrete and the continuous setting, we denote by $f_p$ the processing flow $m_p/\tau_p$ for every place $p$.

\[coro:corresp\]

(i) Suppose $(m,w,f)$ defines a stationary solution of the continuous dynamics. Then, for the initial marking $M_p^0= m_p$, setting $\rho:=f$, $u_p:=M_p^0$, and $u_q:=0$ yields a stationary solution of the discrete dynamics.

(ii) Conversely, suppose $(\rho,u)$ is a stationary solution of the discrete dynamics. Then, defining $f:=\rho$, setting $m_p:=\rho_p\tau_p$ for every place $p$, and defining $w$ according to  and yields a stationary solution of the continuous dynamics.

Both statements are straightforward. We point out that  reads $\rho_p = C^+ \rho_q$ and that – are equivalent to $\rho_q = \min_{\pi} ({C^-_{\pi}})^{-1} S_{\pi} \rho_p$. The same relationship between the $f_q$ and the $f_p$ was established in the proof of Theorem \[th:1\].

An important problem is to relate the stationary flow to the initial marking. On top of the relations given by the invariants of the Petri nets, most results in this direction are limited to nets without priorities, as they rely on monotonicity properties of the dynamics. The next theorem identifies, however, a somehow special situation in which such a relation persists even in the presence of priority. This applies in particular to the Petri net of the next section.

If a trajectory of the continuous Petri net converges towards a stationary solution $(m^{\infty},w^{\infty},f^{\infty})$, if for this trajectory, there exists a policy $\pi$ that reaches the infimum in  at any time, and if $0$ is a semi-simple eigenvalue of $(S_{\pi} C^+ - {C^-_{\pi}})$ associated with this policy, then $f^{\infty}$ is uniquely determined by the initial marking.

(Recall that the eigenvalue $\lambda$ of a matrix $B$ is said to be [*semi-simple*]{} if the dimension of its eigenspace is equal to its algebraic multiplicity, that is, to the multiplicity of $\lambda$ as the root of the characteristic polynomial of $B$. In particular, if $0$ is a semi-simple eigenvalue of $B$, then the kernel of $B$ and its range space are complementary subspaces.)

Under the conditions of the theorem, there exists a policy $\pi$ such that, for any $t$, $$\begin{aligned}
  S_{\pi} \dot{m}(t) &= (S_{\pi}C^+ - {C^-_{\pi}}) f(t) \,,  \label{eq:eq1} \\
  S_{\pi} m(t) &= D_{\pi} {C^-_{\pi}}f(t) \,,\end{aligned}$$ as shown in the proof of Proposition \[thm:fc\_prio\_unicity\].

Since $0$ is a semi-simple eigenvalue of $(S_{\pi}C^+ - {C^-_{\pi}})$, the same property holds for the matrix $(S_{\pi}C^+ - {C^-_{\pi}}) (D_\pi {C^-_{\pi}})^{-1} =  (S_{\pi}C^+ ({C^-_{\pi}})^{-1} - I)D_{\pi}^{-1}$. Therefore, the kernel of this matrix and its range space are complementary subspaces. We denote by $Q$ the projection onto the former along the latter.

By , we obtain that $Q S_{\pi} \dot{m}(t) = Q (S_{\pi}C^+ - {C^-_{\pi}}) f(t) = 0$, so that $Q S_{\pi} {m}(t)$ is independent of time, and $$Q S_{\pi} {m}(0) = Q S_{\pi}m_{\infty} = Q D_{\pi} {C^-_{\pi}}f_{\infty} \,.$$ Moreover, as $(m^{\infty},w^{\infty},f^{\infty})$ is a stationary solution of the continuous dynamics, Equation  holds and $D_{\pi} {C^-_{\pi}}f_{\infty}$ belongs to the kernel of $(S_{\pi}C^+ ({C^-_{\pi}})^{-1} - I)D_{\pi}^{-1}$. Therefore, $$f_{\infty} = ({C^-_{\pi}})^{-1} D_{\pi}^{-1} Q S_{\pi} {m}(0)\,. \qedhere$$

Experimental results {#sec:numerical experiments}
====================

In this section, we illustrate our results on the model of an emergency call center with two treatment levels, introduced in [@allamigeon2015performance]. In this simplified model of an emergency call center, emergency calls are handled by a first level of operators who dispatch them into three categories: extremely urgent, urgent and non urgent. Non-urgent calls (proportion $\mu_4$ of the calls) are entirely processed by level 1 operators. Extremely urgent ($\mu_2$) and urgent calls ($\mu_3$) are transfered to level 2 operators. Extremely urgent calls have priority over urgent calls (but cannot interrupt a talk between an operator of level 2 and an urgent call).

This emergency call center can be modeled by a Petri net with free choice and priority routing, as depicted in Figure \[fig:call\_center\]. Place $p_3$ is a conflict place with a fluid stationary routing, with proportions $\mu_2$, $\mu_3$, $\mu_4$, representing the dispatching of calls into the categories “extremely urgent”, “urgent” and “non urgent” respectively. Every arc has a valuation equal to one. The initial marking $M_1^0$ (resp. $M_2^0$) of place $p_1$ ($p_2$) denotes the available number of operators of level 1 (level 2) in the call center.

It was observed in [@allamigeon2015performance] that the discrete dynamics has a pathological feature: when certain arithmetic relations between the time delays are satisfied, the discrete time trajectory may not converge to a stationary solution, and its asymptotic throughput may differ from the throughput of the stationary solution. It follows from our correspondence result (Corollary \[coro:corresp\]) that the continuous dynamics has the same stationary solutions. We shall observe that, in this continuous setting, the trajectory converges towards a stationary solution, so that the former pathology vanishes.

To compute the (fluid approximation) of the discrete dynamics, simulations have been performed in exact (rational) arithmetics, using the GMP library [@gmplib]. The throughput of transitions $q_5$ and $q_6$ (see Figure \[fig:call\_center\]), for the discrete dynamics, are compared in  to the throughputs of the stationary solutions, computed by Equations  and .

![Petri net of a simplified emergency call center. Place $p_2$ is subject to priority routing. The initial markings of the places different from $p_1$ and $p_2$ are null. The holding times $(\tau_1,\tau_2,\tau_3,\tau_4,\tau_5,\tau_6,\tau_7,\tau_8,\tau_9,\tau_{10})$ are the following: $(0.01, 0.01, 0.01, 4, 3, 3, 1, 0.01, 6, 7)$.[]{data-label="fig:call_center"}](main-FINAL-figure1.pdf)

The dynamics expressed by –, and – belongs to the class of hybrid automata [@henzinger2000theory], which can handle piecewise linear but discontinuous dynamics like ours. We simulate our dynamics with the tool SpaceEx [@frehse2011spaceex], which is a verification platform for hybrid systems. The particularity of SpaceEx is that it computes a sound over-approximation of the trajectories.

At the scale of Figure \[fig:phasesDiagramm\], the lower and upper bounds to the values of the throughputs, computed by SpaceEx, coincide with the shape of the stationary throughputs curve. Table \[tab:1\] compares the numerical values of these lower and upper bounds to the stationary throughputs for a few values of $M_2^0/M_1^0$. We observe that the over-approximation computed by SpaceEx provides an accurate estimate of the stationary throughput computed via Equations –. This tends to show that the continuous dynamics converges towards the stationary throughputs, unlike the discrete dynamics.

Note that the experiments made with SpaceEx did not terminate for $M_2^0/M_1^0 = 0.6$: this seems to be related with the larger number of switches between the states of the automaton at this frontier between two different phases.

![Comparison of the throughputs of the discrete dynamics simulations with the theoretical throughputs (fluid model). []{data-label="fig:phasesDiagramm"}](main-FINAL-figure2.pdf)

          $M_2^0/M_1^0$         0.2         0.4     0.6     0.8     1.0     1.2
  --------------------- ----------- ----------- ------- ------- ------- -------
               $\rho_5$       2.857       5.714   8.333   8.333   8.333   8.333
      $f_5^{\text{up}}$       2.865       5.716       —   8.338   8.339   8.340
    $f_5^{\text{down}}$       2.849       5.707       —   8.328   8.328   8.327
               $\rho_6$           0           0   0.238   3.095   5.952   8.333
      $f_6^{\text{up}}$   $< 0.001$   $< 0.001$       —   3.107   5.968   8.340
    $f_6^{\text{down}}$           0           0       —   3.083   5.936   8.327

  : Lower and upper bounds of the throughputs of the continuous dynamics computed by SpaceEx, and comparison to the stationary throughputs[]{data-label="tab:1"}

Conclusion
==========

We introduced a hybrid dynamical system model for continuous Petri nets having both free choice and priority places, and showed that there is a correspondence between the stationary solutions of the continuous dynamics and the discrete one. An advantage of the continuous setting is that some pathologies of the discrete model (failure of convergence to a stationary solution) may vanish. This is the case in particular on a case study (emergency call center). We leave it for further work to see under which generality the convergence to the stationary solution can be established.

Acknowledgments {#acknowledgments .unnumbered}
---------------

An abridged version of the present work appeared in the Proceedings of the conference Valuetools 2016. We thank the referees for their detailed comments and for pointing out relevant references.

[MRTRS08]{}

Xavier Allamigeon, Vianney B[œ]{}uf, and St[é]{}phane Gaubert. Performance evaluation of an emergency call center: tropical polynomial systems applied to timed [P]{}etri nets. In [*FORMATS*]{}, pages 10–26. Springer, 2015.

Anne Bouillard, Bruno Gaujal, and Jean Mairesse. Extremal throughputs in free-choice nets. , 16(3):327–352, 2006.

Fred DJ Bowden. A brief survey and synthesis of the roles of time in [P]{}etri nets. , 31(10):55–68, 2000.

Guy Cohen, Stéphane Gaubert, and Jean-Pierre Quadrat. Asymptotic throughput of continuous timed [P]{}etri nets. In [*CDC*]{}, 1995.

Ren[é]{} David and Hassane Alla. Continuous [P]{}etri nets. In [*8th European Workshop on Application and Theory of [P]{}etri nets*]{}, volume 340, pages 275–294, 1987.

Ren[é]{} David and Hassane Alla. . Springer Science & Business Media, 2010.

R.W.R. Darling and J.R. Norris. Differential equation approximations for [M]{}arkov chains. , 5:37–79, 2008.

Nadir Farhi, Maurice Goursat, and Jean-Pierre Quadrat. Piecewise linear concave dynamical systems appearing in the microscopic traffic modeling. , pages 1711–1735, 2011.

Goran Frehse, Colas Le Guernic, Alexandre Donz[é]{}, Scott Cotton, Rajarshi Ray, Olivier Lebeltel, Rodolfo Ripado, Antoine Girard, Thao Dang, and Oded Maler. Space[E]{}x: Scalable verification of hybrid systems. In [*CAV*]{}, pages 379–395. Springer, 2011.

Bruno Gaujal and Alessandro Giua. Optimal stationary behavior for a class of timed continuous [P]{}etri nets. , 40(9):1505–1516, 2004.

Torbjörn Granlund and [the GMP development team]{}. , 6.1.1 edition, 2016. <http://gmplib.org/>.

Thomas A Henzinger. The theory of hybrid automata. In [*Verification of Digital and Hybrid Systems*]{}, pages 265–292. Springer, 2000.

Cristian Mahulea, Laura Recalde, and Manuel Silva. On performance monotonicity and basic servers semantics of continuous [P]{}etri nets. In [*Discrete Event Syst., 2006 8th International Workshop on*]{}, pages 345–351. IEEE, 2006.

Cristian Mahulea, Antonio Ramirez-Trevino, Laura Recalde, and Manuel Silva. Steady-state control reference and token conservation laws in continuous [P]{}etri net systems. , 5(2):307–320, 2008.

Tadao Murata. etri nets: Properties, analysis and applications. , 77(4):541–580, 1989.

Laura Recalde, Cristian Mahulea, and Manuel Silva. Improving analysis and simulation of continuous petri nets. In [*2006 IEEE CASE*]{}, pages 9–14. IEEE, 2006.

Laura Recalde and Manuel Silva. fluidification revisited: Semantics and steady state. , pages 279–286, 2000.

Laura Recalde, Enrique Teruel, and Manuel Silva. Autonomous continuous p/t systems. In [*[P]{}etri [N]{}ets*]{}, pages 107–126. Springer, 1999.

Manuel Silva and José Manuel Colom. On the structural computation of synchronic invariants in p/t nets. In [*8th European Workshop on Application and Theory of [P]{}etri nets*]{}, volume 340, pages 237–258, 1987.

C Renato V[á]{}zquez, Cristian Mahulea, Jorge J[ú]{}lvez, and Manuel Silva. Introduction to fluid [P]{}etri nets. In [*Control of Discrete-Event Systems*]{}, pages 365–386. Springer, 2013.

[^1]: The three authors were partially supported by the programme “Concepts, Syst[è]{}mes et Outils pour la Sécurité Globale” of the French National Agency of Research (ANR), project “DEMOCRITE”, number ANR-13-SECU-0007-01, and by the PGMO program of EDF and Fondation Mathématique Jacques Hadamard. The first and last authors were partially supported by the programme “Ingénierie Numérique & Sécurité” of ANR, project “MALTHY”, number ANR-13-INSE-0003.

[^2]: We recall that, in our class of Petri nets, we assume that each transition has at most one upstream place subject to priority, so that this re-ordering is valid.
