Computing Transience Bounds of Emergency Call Centers: A Hierarchical Timed Petri Net Approach

Xavier Allamigeon, Marin Boyet, Stéphane Gaubert

When a major incident occurs—a natural disaster, a large-scale accident, or a pandemic surge—emergency call centers are flooded. For managers of these critical systems, the most pressing question isn't just "Can we handle this?" but "How long until we are back to normal?"

In their paper, Computing Transience Bounds of Emergency Call Centers: a Hierarchical Timed Petri Net Approach, researchers Xavier Allamigeon, Marin Boyet, and Stéphane Gaubert provide a rigorous mathematical framework to answer exactly that.

TL;DR

The authors develop a method to calculate an explicit upper bound on the "catch-up time"—the time it takes for an emergency call center to return to a steady state after a massive surge in calls. By modeling the center as a hierarchical timed Petri net and translating it into a Semi-Markov Decision Process (SMDP), they prove that well-staffed systems recover in finite time and provide a concrete formula to estimate that duration.

What Problem Does This Paper Address?

Emergency call centers (like the French SAMU) are complex systems involving multiple types of agents (assistants and doctors) and synchronized tasks. Standard queueing theory often focuses on "steady-state" performance—how the system behaves on average.

However, emergency management is often defined by transience: sudden, massive "bulks" of arrivals that temporarily overwhelm the system. Existing models often struggle to provide a constructive, finite time bound for when the system "catches up" to its regular regime. The authors aim to fill this gap by providing a "security margin" analysis: if you have more staff than the average demand, how quickly does that extra capacity "absorb" a sudden spike of $M$ extra calls?

Methods

The researchers employ a sophisticated chain of mathematical translations:

  1. Continuous Timed Petri Nets: They model the call center's workflow (picking up, orienting, consulting, etc.) using Petri nets. To make the math tractable, they use a "continuous approximation," treating calls as a fluid (infinitesimal tokens) rather than discrete units.
  2. SMDP Equivalence: They show that the dynamics of these Petri nets are equivalent to the value functions of Semi-Markov Decision Processes (SMDPs). This allows them to use powerful tools from optimal control and dynamic programming.
  3. Stochastic Shortest Path (SSP) Reduction: The problem of measuring the "deviation" from the normal regime is reduced to a Stochastic Shortest Path problem. In this view, "recovering" is equivalent to reaching a "cost-free" sink state (the normal regime).
  4. Hierarchical Structure: The "secret sauce" is the hierarchical assumption. Because emergency tasks follow a natural order (you can't consult a doctor before an assistant picks up), the underlying state space has a partial ordering. This hierarchy is what allows them to prove that recovery happens in finite time, rather than just asymptotically.

Datasets

The paper does not use a large-scale external dataset. Instead, it uses a case study based on the SAMU (French emergency medical services) in the Paris area. They use realistic parameters for:

  • Call arrival rates ($\lambda$).
  • The fraction of calls requiring a doctor ($\pi$).
  • Average task durations ($t_1, t_2, t_3$) for different stages of the call.
  • Staffing levels for assistants ($N_A$) and physicians ($N_P$).

Key Insights and Ideas

  • Finite Time Convergence: Unlike many Markovian models where systems only approach equilibrium at $t \to \infty$, the authors show that for hierarchical systems, the trajectory actually hits the stationary regime exactly in finite time.
  • The "Security Margin": The recovery speed is governed by the difference between the system's maximum capacity ($\lambda'$) and the actual input rate ($\lambda$). If this margin is small, recovery takes a very long time.
  • The Value of Hierarchy: The paper demonstrates that the natural "flow" of tasks in a call center isn't just a logistical reality; it's a mathematical property that guarantees system stability and predictable recovery bounds.

Key Results

The primary result is an explicit upper bound for the global catch-up time ($\theta^*$):

$$\theta^* \leq d \times t_{max} + d^+ \times \frac{M}{\lambda' - \lambda}$$

Where:

  • $M$ is the size of the sudden bulk of calls.
  • $\lambda' - \lambda$ is the "security margin" (excess capacity).
  • $d$ and $d^+$ are constants derived from the "depth" of the task hierarchy.
  • $t_{max}$ is the maximum duration of a single task.

In a concrete example (Figure 3), the authors show how different components of the system (assistants vs. doctors) catch up at different rates, with the entire system eventually "locking in" to the steady-state slope.

Limitations and Future Work

  • Fluid Approximation: By using continuous Petri nets, the model ignores the "jitter" and randomness of individual discrete calls. While this is excellent for large-scale surges, it might be less accurate for very small call volumes.
  • Constant Durations: The current model assumes task durations are constant. The authors suggest that extending this to stochastic durations (where $t_i$ is a random variable) is a logical next step.
  • Tightness of the Bound: The authors acknowledge that while the order of their bound ($M/\text{margin}$) is optimal, the multiplicative constant ($d^+$) could likely be tightened in future research.

Summary updated

Abstract

A fundamental issue in the analysis of emergency call centers is to estimate the time needed to return to a congestion-free regime after an unusual event with a massive arrival of calls. Call centers can generally be represented by timed Petri nets with a hierarchical structure, in which several layers describe the successive steps of treatments of calls. We study a continuous approximation of the Petri net dynamics (with infinitesimal tokens). Then, we show that a counter function, measuring the deviation to the stationary regime, coincides with the value function of a semi-Markov decision problem. We establish a finite time convergence result, exploiting the hierarchical structure of the Petri net. We obtain an explicit bound for the transience time, as a function of the initial marking and sojourn times. This is based on methods from the theory of stochastic shortest paths and non-linear Perron–Frobenius theory. We illustrate the bound on a case study of a medical emergency call center.
BibTeX
@inproceedings{allamigeon2022computing,
  author = {Xavier Allamigeon and Marin Boyet and Stéphane Gaubert},
  title = {{Computing Transience Bounds of Emergency Call Centers: A Hierarchical Timed Petri Net Approach}},
  booktitle = {Petri Nets},
  year = {2022},
  url = {https://openreview.net/forum?id=omDkOmFns4},
}

Loading related content...

Figure