Réseaux de Petri Fluides et Discrets
Bruno Gaujal
INRIA,
Sophia-Antipolis.
gaujal@sophia.inria.fr
Ce résumé.dvi,Ce résumé.ps
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.
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 
(avec les
opérateurs vectoriels 
) et dans
l'algèbre classique (voir [2]):
où K est une borne sur les temps de tirs, les matrices
dépendent de la topologie du système,
R représente les entrées et 
est la fonction de routage.
La principale difficulté dans l'analyse des équations
(1)-(2), est la fonction de routage .
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]).
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]).
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.
Réseaux de Petri Fluides et Discrets
This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
The command line arguments were:
latex2html -split 0 resume-gaujal.tex.
The translation was initiated by Gaubert on Sun Feb 16 18:12:44 MET 1997
Gaubert
Sun Feb 16 18:12:44 MET 1997