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

Xavier Allamigeon, Marin Boyet, Stephane Gaubert

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. Then, 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.

Introduction

When a major incident occurs—such as a natural disaster, a large-scale accident, or a pandemic surge—emergency call centers are immediately flooded. For managers of these critical systems, the most pressing question is not just whether the system can handle the load, but how long it will take to return to a normal, congestion-free state.

In their research, Xavier Allamigeon, Marin Boyet, and Stéphane Gaubert provide a rigorous mathematical framework to answer this. 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.

The Challenge of Transience

Emergency call centers, such as the French SAMU (emergency medical services), are complex systems involving multiple types of agents—assistants and doctors—and synchronized tasks. Standard queueing theory often focuses on "steady-state" performance, describing how the system behaves on average over long periods.

However, emergency management is defined by transience: sudden, massive surges 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. This paper addresses this gap by providing a "security margin" analysis: if a center has more staff than the average demand requires, how quickly can that extra capacity absorb a sudden spike of $M$ extra calls?

Modeling Framework: Hierarchical Timed Petri Nets

The researchers employ a sophisticated chain of mathematical translations to solve this problem. First, they model the call center's workflow—including picking up, orienting, and consulting—using Petri nets. To make the mathematics tractable for large-scale surges, they utilize a "continuous approximation," treating calls as a fluid (infinitesimal tokens) rather than discrete units.

Figure 1: The hierarchical Petri net model (left) and its corresponding state-space representation (right) used to analyze call center dynamics.

A key insight is the hierarchical assumption. Because emergency tasks follow a natural order (e.g., an assistant must pick up before a doctor can consult), the underlying state space has a partial ordering. This hierarchy is what allows the researchers to prove that recovery happens in finite time, rather than just asymptotically.

Mathematical Foundations

The dynamics of these Petri nets are shown to be equivalent to the value functions of Semi-Markov Decision Processes (SMDPs). This allows the use of tools from optimal control and dynamic programming. Specifically, the problem of measuring the "deviation" from the normal regime is reduced to a Stochastic Shortest Path (SSP) problem. In this view, "recovering" is equivalent to reaching a "cost-free" sink state representing the normal regime.

Case Study: The French SAMU

The paper illustrates these bounds using a case study based on the SAMU in the Paris area. The model incorporates realistic parameters, including:

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

Results: Explicit Recovery Bounds

The primary contribution 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.

The recovery speed is governed by the difference between the system's maximum capacity and the actual input rate. If this margin is small, recovery takes a significantly longer time. The case study demonstrates 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.

Conclusion and Future Directions

This research demonstrates that the natural "flow" of tasks in a call center is not just a logistical reality; it is a mathematical property that guarantees system stability and predictable recovery bounds. While the current fluid approximation is excellent for large-scale surges, future work may extend the model to include stochastic task durations and further tighten the multiplicative constants in the recovery bound.

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. Then, 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 Stephane 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},
}
Figure