Chapitre 7

Réseaux de Petri colorés

La modélisation d’un système réel peut mener à des réseaux de Petri de taille trop importante
rendant leur manipulation et/ou leur analyse difficile. La question est alors de modifier (étendre)
la modélisation par RdP de façon à obtenir des modèles RdP de plus petite taille. Cette question
a motivé l’introduction des RdPs généralisés, chapitre 5. Elle a été discutée dans la section 5.5.
Une telle classe de modèles y a été désignée par le terme d’abréviation. Dans le chapitre présent,
nous introduisons une autre classe d’abréviation, les RdPs colorés. Ils sont important pour la
modélisation de systèmes de production (au sens large). Ils ont été motivés par le fait suivant.
Une taille trop importante peut découler du fait que l’on ne peut pas distinguer entre elles les
différentes marques d’une place. Plusieurs marques dans une place peuvent modéliser un certain
nombre de pièces identiques dans un stock. Si le stock contient plusieurs types de pièces, des
places supplémentaires doivent être introduites pour sa modélisation.
Voir par exemple Figure 7.1. Le nombre de marques dans la place P3 correspond au nombre
de pièces de type 1 en stock. Le nombre de marques dans la place P4 correspond au nombre
de pièces de type 2 en stock. Le nombre de marques dans la place P7 indique le nombre d’em-
placements libres dans le stock. Si un stock est susceptible de contenir deux (respectivement n)
types de pièces, il doit donc être modélisé par au moins 3 (resp. n + 1) places. Peut-on ima-
giner une modification du modèle RdP qui permette de la modéliser par un nombre de places

P1 P2

T1 T2

P3 P4
P7
T4
T3

P5 P6

F IG . 7.1 – Stock contenant deux types de pièces

indépendant du nombre de types de pièces stockées ? Intuitivement, si on est capable de distin-

guer les différentes marques les unes des autres, on pourrait associer à chaque type de marques
un type de pièces. Deux places seraient alors nécessaires pour modéliser le stock : une place
dont le marquage indique le nombre (et le type) de pièces stockées et une place dont le marquage

69
70 C HAPITRE 7 RDP COLOR ÉS

indique le nombre d’emplacements libres. Pour distinguer les marques les unes des autres, on
introduit la notion de couleur.

7.1 Introduction aux RdPs colorés à travers des exemples

Exemple 1 : introduction de marques colorées Un système de production est constitué
d’une première machine avec son stock en sortie de capacité limitée à 3 produisant la pièce
a et d’une seconde machine avec son stock en sortie de capacité limitée à 3 produisant la pièce
b . L’état du système est caractérisé par :
– La première machine produit la pièce a (une marque dans la place P a1 )
– La première machine est en attente (une marque dans la place P a3 )
– Le nombre de pièces dans le stock de sortie de la première machine (nombre de marques
dans la place P a2 )
– Le nombre de places libres dans le stock de sortie de la première machine (nombre de
marques dans la place P a4 )
– La seconde machine produit la pièce b (une marque dans place P b1 )
– La seconde machine est en attente (une marque dans place P b3 )
– Le nombre de pièces dans le stock de sortie de la seconde machine (nombre de marques
dans la place P b2 )
– Le nombre de places libres dans le stock de sortie de la seconde machine (nombre de
marques dans la place P b4 )
L’état du système va évoluer quand se produit :
– le début de la production d’une pièce a par la première machine (franchissement de T a1 )
– la fin de la production d’une pièce a par la première machine (franchissement de la tran-
sition T a2 )
– le retrait d’une pièce a du stock de la première machine (franchissement de la transition
T a3 )
– le début de la production d’une pièce b par la seconde machine (franchissement de T b1 )
– la fin de la production d’une pièce b par la seconde machine (franchissement de la transi-
tion T b2 )
– le retrait d’une pièce b du stock de la seconde machine (franchissement de la transition
T b3 )
Au départ, la première machine attend tandis que la deuxième machine produit une pièce b.
Le stock de sortie de la première machine contient une pièce a et celui de la seconde deux
pièces b. On obtient le RdP représenté Figure 7.2 gauche. Ce système est constitué de deux
sous systèmes identiques (première machine avec son stock et seconde machine avec son stock)
chacun produisant un type de pièces différent. Cela suggère l’idée que l’on pourrait superposer
les RdPs représentant chacun des sous systèmes. Par contre, dans le RdP représentant le premier
sous système, une marque dans une place fait référence à tout ce qui a trait à la pièce a : première
machine occupée ou non, état du stock de la machine a. Dans le second RdP, une marque fait
référence à la pièce b. Si on superpose les deux RdPs, il est donc nécessaire de différencier deux
types de marque : une première que l’on baptise <a> qui correspond au marquage du premier
RdP et une seconde baptisée <b> correspondant au marquage du second RdP. On parle alors
de couleur1 . L’ensemble des couleurs est noté C = {< a >, < b >}. On obtient alors le RdP
coloré représenté Figure 7.2, droite. Chaque transition est alors validée pour une couleur.
– La transition T1 est validée pour la couleur <a> mais pas pour la couleur <b> : le
1
Le mot couleur fait évidemment référence à des marques qui seraient de couleur différente. Le document étant
reprographié en noir et blanc, on remplace le point de couleur par une lettre entre < et >.
G. S CORLETTI ET G. B INET V ERSION P ROVISOIRE DU 20 JUIN 2006 71

Ta1 Tb1
{<a>,<b>} T1
Pa1 Pa3 Pb1 Pb3
P1 <a>
<b> P3
Ta2 Tb2
{<a>,<b>} T2

Pa2 Pa4 Pb2 Pb4 <a>

<a>
<a> P4
<b> P2 <b>
<b>

Ta3 Tb3 {<a>,<b>} T3

F IG . 7.2 – Machines a et b avec leurs stocks de sortie, RdP (gauche) et RdP coloré (droite)

franchissement de T1 pour la couleur <a> consiste à enlever une marque <a> dans la
place P3 et à ajouter une marque <a> dans la place P1 ;
– La transition T2 est validée pour la couleur <b> mais pas pour la couleur <a> : le
franchissement de T2 pour la couleur <b> consiste à enlever une marque <b> dans les
places P1 et P4 et à ajouter une marque <b> dans les places P2 et P3 ;
– La transition T3 est validée pour les couleurs <a> et <b> : le franchissement de T3 pour
la couleur <a> (respectivement <b>) consiste à enlever une marque <a> (resp. <b>)
dans la place P2 et à ajouter une marque <a> (resp. <b>) dans la place P4.
On associe à chaque transition l’ensemble des couleurs pour lesquelles le franchissement est
envisagé : par exemple pour T1 , l’ensemble {<a>, <b>}.
Le passage du RdP (Figure 7.2 gauche) au RdP coloré (Figure 7.2 droite) est appelé pliage,
le passage du RdP coloré au RdP dépliage.
Le marquage d’un RdP coloré est maintenant défini pour chaque couleur. Par exemple, sur
le RdP coloré représenté Figure 7.2
2 droite,
3 le marquage
0
6 1 7
– pour la couleur < a > est : 6 7
4 1 5;
2
2 3
1
6 2 7
– pour la couleur <b> est : 6 4 0 5.
7

1
Le marquage peut être ainsi défini par une matrice où chaque colonne correspond à une couleur :
<2
a> <3b>
P1 0 1
M0 = P2 6 1 2 7
6 7
P3 4 1 0 5
P4 2 1
Il peut être aussi défini comme une application qui à une couleur donnée associe un marquage :
2 3 2 3
0 1
6 1 7 6 2 7
< a > 7! 6 7
4 1 5 et < b > 7! 4 0 5
6 7

2 1
72 C HAPITRE 7 RDP COLOR ÉS

Le marquage est donc une application de C ! N4 . Pour ne pas alourdir l’écriture, cette appli-
cation est définie en utilisant des notations formelles :
2 3 2 3 2 3
0 1 <b>
6 1 7 6 7 6 7
6 7 < a > + 6 2 7 < b > = 6 < a > + 2< b > 7 .
4 1 5 4 0 5 4 <a> 5
2 1 2< a > + < b >
Pour une place donnée, le marquage est une application de C ! N.
Quand il n’y a pas de couleur associée à une marque, on parle d’une marque de couleur neutre.
Elle est notée < • >.

Exemple 2 : introduction de fonctions associées aux arcs Un système de production est

constitué d’une seule machine avec son stock en sortie de capacité limitée à 3. Cette machine
produit soit la pièce a soit la pièce b. Le RdP de ce système de production peut être obtenu à
partir des RdPs modélisant les deux sous systèmes dans l’exemple précédent par2 :
– la mise en commun de la machine pour la fabrication des pièces a et b (fusion des places
P a3 et P b3 en la place P3 ) ;
– la mise en commun du stock de sortie de la machine (fusion des places P a4 et P b4 en la
place P4 ).
Au départ, une pièce a a déjà été produite et stockée. La machine est disponible. On obtient
alors le RdP représenté Figure 7.3, à gauche. Le RdP coloré obtenu par pliage est représenté

Ta1 Tb1 f
{<a>,<b>}
Id
T1
Pa1 P3 Pb1 P1 < > P3
Id
Ta2 Tb2 {<a>,<b>} T2 f
Id f
< >
Pa2 P4 Pb2 <a> P2 < > P4
Pliage
Id
Depliage T3 f
Ta3 Tb3 {<a>,<b>}

F IG . 7.3 – Machine avec son stock de sortie produisant a et b, RdP (gauche) et RdP coloré
(droite)

Figure 7.3, à droite :

– les places P a1 et P b1 se plient en la place P1 : une marque dans la place P a1 correspond à
une marque <a> dans P1 , une marque dans la place P b1 correspond à une marque <b>
dans P1 ;
– les places P a2 et P b2 se plient en la place P2 : une marque dans la place P a2 correspond à
une marque <a> dans P2 , une marque dans la place P b2 correspond à une marque <b>
dans P2 ;
2
voir sous section 2.2.2.2, page 31.
G. S CORLETTI ET G. B INET V ERSION P ROVISOIRE DU 20 JUIN 2006 73

– les marquages des places P3 et P4 ne sont pas modifiés ;

– les transitions T a1 et T b1 se plient en la transition T1 ; de même, T a2 et T b2 se plient en
T2 et T a3 et T b3 se plient en T3 .

Comment définir la validation d’une transition ? Dans le cas de la transition T1 , une marque
de couleur neutre dans la place P3 signifie que la machine est disponible pour commencer à
produire la pièce a (franchissement de la transition T1 pour la couleur <a>) ou pour commencer
à produire la pièce b (franchissement de la transition T1 pour la couleur <b>). Cela est décrit
dans le RdP coloré en associant une fonction f à l’arc reliant la place P3 à la transition T1 .
L’argument de cette fonction est la couleur pour laquelle la validation de la transition T1 est
envisagée. La valeur prise par cette fonction correspond au nombre de marques (quelles que
soient leurs couleurs) nécessaire pour valider la transition pour la couleur considérée. Il s’agit
donc d’une application de C dans l’ensemble des applications de C ! N, ce qui est noté
C ! (C ! N). Dans l’exemple, pour valider la transition T1
– pour la couleur <a>, P3 doit avoir au moins une marque de couleur neutre :
f(< a >) =< • >
– pour la couleur <b>, P3 doit avoir au moins une marque de couleur neutre :
f(< b >) =< • > .
P re(P3 , T1 ) n’est plus ici un entier naturel mais une application de C dans l’ensemble des
applications de C ! N. Par simplicité, on préfère définir P re(P3 , T1 ) à l’aide de fonctions
annexes comme la fonction f : P re(P3 , T1 ) = f.

A partir du moment où la place P3 contient au moins une marque de couleur neutre, le fran-
chissement de T1 peut donc se faire pour la couleur <a> ou la couleur <b>. Dans l’exemple
considéré, il consiste à retirer une marque de la place P2 et à ajouter dans la place P1 une marque
de la couleur pour laquelle le franchissement de T1 a été décidé. On dit que la fonction identité
notée Id est associée à l’arc reliant la transition T1 à la place P1 :
Id(< a >) =< a > et Id(< b >) =< b > .
La fonction identité peut être définie comme une application de C dans C ! {0, 1} telle que
Ω
Id(< ck >)(< ck >) = 1
8l 6= k, Id(< ck >)(< cl >) = 0
Dans le cas de la transition T2 , le franchissement peut se faire par rapport à la couleur < a >
(resp. < b >) : si une marque < a > (resp. < b >) est disponible dans la place P1 et une
marque < • > est disponible dans P3 , le franchissement consiste alors à enlever ces marques
pour mettre une marque de couleur < a > (resp. < b >) dans P2 et une marque de couleur
neutre dans P3 . La fonction Id est donc associée aux arcs reliant P1 à T2 et T2 à P2 . La fonction
f est associée à l’arc reliant T2 à P3 . Ce raisonnement s’applique aussi au reste du RdP.

Suite de l’exemple 2 : introduction de couleurs complexes Lorsque l’on examine le RdP

coloré représenté Figure 7.3, on constate qu’il est constitué par la double répétition d’un même
motif. On peut donc envisager une nouvelle opération de pliage.
– Les places P1 et P2 se plient en une place Pu : il est alors nécessaire de distinguer entre
les pièces a (resp. b) dans la machine en cours de fabrication et celles qui sont stockées.
Pour cela, la couleur est maintenant définie par un doublet < ., . > dont le premier terme
fait référence au type de pièce (a ou b) et le second au lieu où se trouve la pièce (m pour
la machine ou s pour le stock). On parle alors de couleur complexe.