Stéphane Gaubert (CMAP, École Polytechnique)

Stéphane Gaubert
École Polytechnique

21 Juin 2018, 14.00
salle des commissions, bât Polytech
Campus de St. Jérôme


Tropical analysis of timed Petri nets with priorities and application to performance evaluation of an emergency call center

We analyze a timed Petri net model of an emergency call center which processes calls with different levels of priority. The counter variables of the Petri net represent the cumulated number of events as a function of time. We show that these variables are determined by a piecewise linear dynamical system. We also prove that computing the stationary regimes of the associated uid dynamics reduces to the problem of computing a tropical prevariety, i.e., to solving a polynomial system over a tropical (min-plus) semifield. This leads to explicit formulae expressing the throughput of the uid system as a piecewise linear function of the resources, revealing the existence of different congestion phases. Numerical experiments show that the analysis of the fluid dynamics yields a good approximation of the real throughput. In this way, tropical geometry allows one to identify bottleneck resources. This works originates from a case study, concerning the analysis of the new organization of reception of the 17-18-112 emergency calls in the Paris area, currently deployed by Préfecture de Police. This is a joint work with Xavier Allamigeon and Vianney Boeuf.