Réseaux de Petri Fluides et Discrets

Bruno Gaujal INRIA, Sophia-Antipolis.

                           gaujal@sophia.inria.fr

Équations d’évolution Nous utilisons des réseaux de Petri temporisés [1] avec des poids sur les arcs pour modéliser des systèmes à événements discrets avec un trafic à rafales (arrivées et départs de clients groupés). Pour ces réseaux de Petri, nous utilisons une variable d’état bien choisie : les compteurs. X_{i}(t) est le nombre de tirs initiés par la transition i à la date t. On décompose alors les transitions en celles qui ont une dynamique (min,+) (synchronisations) et celles qui ont une dynamique (+, ×) (routages). Cela se traduit par une partition du vecteur X(t) en deux sous-vecteurs (Y (t), Z(t)). Si le réseau de Petri considéré est mis sous forme canonique, on peut alors décrire son comportement sous forme d’équations récursives sur les variables (Y (t), Z(t) dans l’algèbre (min, +) (avec les opérateurs vectoriels (⊕, ⊗)) et dans l’algèbre classique (voir [2]):

Y (k) = ⨁_{l=1}^{K} (A_{l} ⊗ Y (k − l) ⊕ B_{l} ⊗ Z(k − l))  (1)

Z(k) = H (∑_{l=1}^{K} (P_{l} × Z(k − l) + Q_{l} × Y (k − l)) + R) ,  (2)

où K est une borne sur les temps de tirs, les matrices A_{l}, B_{l}, P_{l}, Q_{l} dépendent de la topologie du système, R représente les entrées et H est la fonction de routage.

Réseaux fluides La principale difficulté dans l’analyse des équations (1)-(2), est la fonction de routage H. Si on la remplace par une matrice, H, qui donne les proportions asymptotiques des routages, on obtient le réseau fluide associé avec un fluide circulant dans le réseau au lieu de jetons. Ses équations d’évolution sont similaires mais plus simple, la deuxième équation devenant linéaire (voir [6]).

Relations réseaux fluides - réseaux discrets Les lemmes suivants se démontrent en utilisant les propriétés des opérateurs (min,+) et aussi linéaires mis en jeu dans les équations d’évolution ([2, 3, 5]).

Lemme 1. Le réseau discret est structurellement vivant si et seulement si le réseau fluide associé l’est aussi.

Lemme 2. Le nombre total de tirs dans un réseau discret à entrée simple et avec un routage i.i.d. est égal à la quantité totale de tirs dans le réseau fluide associé.

Lemme 3. Le nombre moyen de tirs au temps k dans un réseau à routage i.i.d. est inférieur à la quantité moyenne de tirs pour le réseau fluide associé. Si de plus le réseau est à entrée simple et acyclique, ces deux quantités sont égales.

Aspects calculatoires Les lemmes précédents permettent d’utiliser l’approximation fluide d’un réseau de Petri pour mettre au point des algorithmes efficaces de calcul des quantités suivantes:

• L’absence d’interblocages: L’absence d’interblocages dans le réseau discret peut être déduite des matrices H du modèle fluide associé. Si leurs rayons spectraux sont supérieurs à 1, il n’y aura aucune famine dans le réseau fluide mais aussi dans le réseau discret (utilisation du lemme 1).

• Le nombre total de tirs: Si les routages dans chaque transition sont i.i.d., alors le nombre total de tir d’un réseau de Petri est calculable par un procédé de point fixe qui fonctionne de façon parallèle et asynchrone. Si de plus, les routages dans chaque transition sont i.i.d., et si le réseau est à entrée simple, alors, en utilisant l’approximation fluide, le problème se réduit par passage à la limite à un calcul de vecteurs propres (utilisation du lemme 2).

• Le nombre moyen de tirs: Si le réseau est à entrées simples et acyclique, le nombre de tirs moyen peut être calculé par un procédé parallèle-préfixe (utilisation du lemme 3).

References

[1] F. Baccelli, G. Cohen, and B. Gaujal. Recursive equations and basic properties of timed Petri nets. Discrete Event Dynamic Systems: Theory and Applications, 1(4), 1992.

[2] F. Baccelli, S. Foss, and B. Gaujal. Free choice nets, an algebraic approach. IEEE Transaction on Automatic Control, 1996. To appear.

[3] F. Baccelli and B. Gaujal. Liveness in petri nets, an algebraic approach. Technical Report RR 2839, INRIA, 1996.

[4] F. Baccelli, G. Gohen, G.J. Olsder, and J.-P. Quadrat. Synchronization and Linearity. Wiley, 1992.

[5] B. Gaujal. Liveness in weighted routed nets. Technical Report RR 2899, INRIA, 1996.

[6] B. Gaujal. Some algebraic considerations for efficient computations in timed petri nets. In HICSS, Maui, Hawaii, January 1996.

[7] P. Glasserman and D.D. Yao. Monotone structure in discrete-event systems. Wiley, 1994.