RdP
Les extensions
Saoussen Cheikhrouhou
Systèmes à Evènements Discrets
Les réseaux de Petri autonomes sont parfois insuffisants pour modéliser et
valider des systèmes complexes ou spécifiques.
Beaucoup de travaux ont étendus les RdP autonomes pour leur adjoindre des
concepts intéressants :
Buts Extensions Concepts
Introduire la notion de quantité RdP Généralisés pondération des arcs
Distinguer les produits les uns des autres RdP Colorés coloration des jetons
Etude des performances temporelles RdP Temporisés temps
Prise en compte d'un grand nombre de RdP Continus marquage continu
types de produits
Prise en compte de flux de grandes RdP Lots
quantités
Introduction de processus stochastiques RdP Stochastiques probabilités
Automatismes et SED
Autres extensions des RdP..
Extension : Autres
Pour certains systèmes complexes, les RdP "basiques" ne suffisent pas.
Exemple : FIFO, capacités 4 Avec conservation
de l'ordre d'arrivée:
explosion
RdP colorés
RdP à prédicats
RdP à objets
Sans conservation
…
de l'ordre d'arrivée
des éléments
Automatismes et SED
RdP colorés
Extension : RdP colorés
Importants pour les systèmes de production (au sens large).
Permet la distinction de différents types de jetons
Exemple : FIFO, capacités 4 Avec conservation de
l'ordre d'arrivée: explosion
Nb Places = 2n
Nb Transi = 4n
Idée : au lieu de différencier
les places, on va différencier les
jetons.
Sans conservation
de l'ordre d'arrivée
des éléments
Extension : RdP colorés
Idée : au lieu de différencier les places, on va différencier les jetons.
Association à chaque jeton d'une couleur.
Association aux places d'ensembles de couleurs (couleurs possibles des
jetons de ces places)
Association aux transitions d'ensembles de couleurs de franchissement
Association aux arcs des fonctions permettant la description
du franchissement
le comportement du RdP va dépendre de la couleur des jetons.
Couleur neutre Fonction identité Id :
notée < ● > Id(Ci) = Ci
Extension : RdP colorés
Ensemble des couleurs : C = {Ca, .. ,Cz, Ca', .. ,Cz'}
Franchissement de la transition Ti pour la couleur Cx :
il faut un jeton de couleur fji(Cx) (ici, Ca) dans la place amont Pj et un
jeton de couleur fj'i(Cx) (ici, Ca') dans la place amont Pj'.
cela génère un jeton de couleur fjk(Cx) (ici, Cb) dans la place aval Pk et
un jeton de couleur fjk'(Cx) (ici, Cb') dans la place aval Pk' .
Pj [Ca, ..] Pj' [Ca', ..]
fj'i(Cx) = Ca'
f
(Cx) = Ca
ji
Ti [Cx, Cy, ..]
fik(Cx) = Cb
f (Cx) = Cb'
ik'
Pk [Cb, ..] Pk' [Cb', ..]
Extension : RdP colorés – Def formelle
Un RdP coloré est un sextuplet : R = <P,T,C,ω,Pré,Post,M0>
P : ensemble de places
T : ensemble de transitions
C : ensemble fini de couleurs
ω : fonction associant à chaque place et chaque
transition un ensemble de couleurs possibles
Pré et Post : fonctions des arcs. !! Chaque arc porte une
fonction f(C).
M0 : marquage initial
Extension : RdP colorés
C={g,d}
Marquage initial : un jeton g dans P.
P f(g) = d
g f(d) = g
ω(P) = C
f Id
T {g,d} D'après la fonction Id, seule la couleur g peut donc être
utilisée pour franchir T;
On génère alors un jeton f(g) dans P : un jeton d;
P
d
On peut de nouveau franchir T,
mais cette fois avec la couleur de f Id
franchissement d; T {g,d}
On revient ds l'état initial.
Extension : RdP colorés
Exemple : Atelier de fabrication
2 types de pièces et 2 machines à usiner
Extension : RdP colorés
Couleurs : M1 et M2 pour les machines, et P1 et P2 pour les types de pièces.
Fonctions : 2 fonctions, Pièce et Machine
• C = {P1, P2, M1, M2, P1.M1, P1.M2, P2.M1, P2.M2}
• ω(Pièces) = {P1, P2}
• ω(Machines) = {M1,M2}
• ω(Usinage) = ω(Debut) = ω(Fin)
Début = {P1.M1, P1.M2, P2.M1, P2.M2}
• Pièce(Pi.Mj) = Pi
Pièce Id Machine • Machine(Pi.Mj)=Mj
5*P1 M1
Pièces Usinage Machines
4*P2
M2
Id Machine
Pièce
Fin
Le dîner des philosophes
On veut modéliser le classique pb du dîner des philosophes.
Contraintes :
Table ronde.
Chaque philosophe est devant une assiette,
et il y a une fourchette entre chaque assiette.
Actions d'un philosophe : soit manger, soit penser.
Pour manger, un philosophe a besoin de ses 2 fourchette
s.
Faire la modélisation de ce système, dans le cas ou il n'y a
que deux philosophes :
1) Modéliser le comportement d'un seul philosophe;
2) Modéliser le comportement des deux philosophes.
Le dîner des philosophes
!!!!! Ceci est une simplification :
On considère les fourchettes comme un stock global.
C'est possible ici car tous les philosophes ont accès à toutes les
fourchettes.
Mais si par exemple 4 philosophes et 4 fourchettes : 2 philosophes voisins
ne peuvent pas manger, même s'il reste des fourchettes libres.
Le dîner des philosophes
Modèle pour 4 philosophes en RdP ordinaires :
Le dîner des philosophes
Modèle pour 4 philosophes en RdP colorés :
4 fourchettes différentes : F12 est la fourchette entre les philosophes 1
et 2
4 philosophes différentes : Phi1 à Phi4
Marquage initial
φ1 φ2 F12 F23
• C = {φ1, φ2, φ3, φ4, φ3 φ4 F34 F41
F12, F23, F34, F41,
φ1.F41.F12, φ2.F12.F23, φ3.F23.F34, φ4.F34.F41}
Id fa
• ω(Philosophes) = ω(Deb_Penser) = ω(Fin_Penser) =
ω(Penser)
= {φk} k{1,4} fc+fc'
• ω(Fourchettes) = {Fij} i,j {1,4} avec Id Id
j=(i+1)%4 (modulo)
• ω(Manger) = ω(Deb_Manger) = ω(Fin_Manger)
= {φ1.F41.F12, φ2.F12.F23, φ3.F23.F34,
Id Id
φ4.F34.F41} fd+fd'
Id fb
• fa(φk.x.y) = fb(φk.x.y) = φk k {1,4
• fc(x,Fij,y) = fd(x,Fij,y) = Fij i,j {1,4}
• fc'(x,y,Fij) = fd'(x,y,Fij) = Fij i,j {1,4}
