Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

A-Processus dterministes :
Les Rseaux de Petri
Les Rseaux de Petri (RdP) permettent de modliser des systmes squentiels. Ils ont t invents par
Carl Adam Petri, un mathmaticien Allemand contemporain (do labsence daccent dans Petri). Il a
dfini un outil mathmatique trs gnral permettant de dcrire les relations existant entre des
conditions et des vnements et de modliser le comportement de systmes dynamiques vnements
discrets. Ces RdP datent de 1960-1962. Cest un outil trs gnral, modlisant aussi bien les
protocoles de communication informatiques que des systmes de production. Il est lorigine du Grafcet
(ce dernier tant spcialis dans la description de la commande de systmes automatiss).

Chapitre 1 : Les rseaux de Petri autonomes

1.1 NOTIONS DE BASE
Un exemple de rseau de Petri
P1
T1
P2

T6

T2
P3

P4

T3

T4

P5

P6
T5
P7

Nous retrouvons les lments de base classiques : la place, la transition et larc reliant soit une place
une transition soit une transition une place. On numrote les places P1, P2, et les transitions T1,
T2, Chaque place Pi peut avoir un nombre mi de marques, mi N . On appelle M le vecteur des
marquages dont les lments sont les mi. Dans notre exemple, M=!(1,0,0,1,0,0,2,0).
Franchissement de transition :
Lappellation autonome de ces rseaux de Petri vient du fait quon nassocie pas de condition,

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

dvnement, ni de temps aux transitions. Pour quune transition soit franchissable (ou valide), il faut et
il suffit quil y ait au moins un jeton dans chaque place en amont de la transition.
Le franchissement (ou tir) dune transition consiste retirer une marque chaque place en amont de la
transition et en rajouter une chaque place en aval de la transition.
Remarques :
Ces deux actions se font en mme temps : le franchissement dune transition nest pas divisible.
On peut remarquer quil ny a pas conservation du nombre de jetons.
Contrairement au Grafcet, lorsque deux transitions sont franchissables, on nen franchit quune la
fois.
lorsquune transition est valide, cela nimplique pas quelle soit immdiatement franchie. Ce nest
quune possibilit.
Pour les quatre situations ci-dessous, complter le marquage du rseau aprs
franchissement de T1 sil est possible.
P2

P1

P2

P1

T1

P2

P1

T1

P1

T1

P2
T1

P3

P4

P3

P4

P3

P4

P3

P4

P1

P2

P1

P2

P1

P2

P1

P2

T1

T1
P3

P4

P3

T1

T1
P4

P3

P4

P3

P4

1.2 MODLISATION PAR RDP

Le RdP autonome rcrit ce qui arrive. Il permet la description du fonctionnement, de ce qui arrive,
les transitions sont autonomes. Voici un exemple de description :
automobiliste
chez lui

voiture au garage

pied
en
voiture

Lvolution du systme est reprsent par lvolution du marquage.

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

1.3 RdP GNRALISS

On peut affecter des poids aux arcs. Lorsque quil y a un poids n sur larc qui part dune place Pi vers une
transition Tj, cela signifie que la transition est franchissable sil y a au moins n marques dans la place Pi.
Lors du franchissement de Tj, on retirera n marques la place Pi.
Sil y a un poids m sur larc qui part de la transition Tj vers la place Pk, lors du franchissement de Tj, on
ajoutera m jetons dans la place Pk.
Exemples :
P1

P2

P1

T1
P3

P2

P2

P1

T1
P4

P3

P1

P2

T1

T1

P4

P3

P2

P1

P4

P3

P2

P1

P4

P1

T1 3non tirable

P2

P1

T1

T1
P3

P4

P3

P2
T1

T1
P4

P3

P4

P3

P4

1.4 GRAPHE DES MARQUAGES ET ARBRES DE COUVERTURE

Le graphe des marquages est un graphe dont les noeuds correspondent un marquage du RdP et les
arcs, des franchissements de transitions.
Exemple :
0

P1

1
T1

P2

0
P3
T3

T2
P4

0 T1

P5

T3

T2

T2

0
1

T3

1
0

T4

T4

Sur ce graphe des marquages, on peut trouver toutes les proprits de ce RdP. On voit notamment que ce
RdP est born, sauf, vivant, rinitialisable, que T1T3T2T4 et T1T2T3T4 sont des squences rptitives
(donc le RdP est rptitif) et que 2.m1+m2+m3+m4+m5 = 2 (donc le RdP est conservatif).
Un arbre de couverture est un graphe particulier dans lequel il ny a pas de boucle ni de circuit.
Algorithme de construction de larbre de couverture.
Pas 1 : A partir du marquage initial M 0, on indique toutes les transitions valides et les marquages
successeurs correspondants. Si un de ces marquages est strictement suprieur M 0, on met w pour
chacune des composantes suprieures aux composantes correspondantes de M0.
Pas 2 : Pour chaque nouveau marquage Mi de larbre, on fait soit le pas 2.1 soit le pas!2.2
Pas 2.1 : Sil existe sur le chemin de M0 Mi (ce dernier exclu) un marquage Mj = Mi , alors Mi

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

na pas de successeur.
Pas 2.2 : Sil nexiste pas de marquage M k = M i sur le chemin de M0 M i , alors on prolonge
larbre en ajoutant tous les successeurs de M i . Pour chaque successeur M k de M i : (a) une
composante w de Mi reste une composante w de M k ; (b) sil existe un marquage M j sur le
chemin de M0 Mk tel que M k>Mj, alors on met w pour chacune des composantes suprieures
aux composantes de Mj.
Exemple :
P1
T1

T3
P2

P3
T2

Faire larbre de couverture de ce RdP.

1.5 PROPRITS
a) Notations et dfinitions
Le marquage dun RdP est donn par un vecteur colonne dont la ime composante est le nombre de
marques dans la place Pi. Pour faciliter lcriture, on crira le marquage sous sa forme transpose.
Exemple :
P1

1
T1

0
M0 = 0

P2

P3

T2

T3

P4

P5

0
0

ou
M 0 = (1,0,0,0,0)

T4

A partir de M 0, il y a une transition valide, T1. En franchissant T1, on arrive au marquage M1, M 1!=
(0,1,1,0,0). On note ceci : M0 (T1 M1.
On remarque que :
M 1 (T2 M2 = (0,0,1,1,0)
M 1 (T3 M3 = (0,1,0,0,1)
M 2 (T3 M4 = (0,0,0,1,1)
M 4 (T4 M0
On notera * M0 lensemble des marquages accessibles partir du marquage M 0. Pour notre
exemple, *M0 = {M0, M1, M2, M3, M4}.
A partir du marquage M 0, on peut franchir successivement T1 puis T2. On se retrouve avec le marquage

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

M 2. T1T2 est une squence de franchissement. On peut la noter S. On peut crire alors :
M 0 (T1T2 M2 ou bien M0 (S M2.
Une place Pi est borne pour un marquage initial M 0 si pour tout marquage accessible partir de M0 le
nombre de marques dans Pi est fini.
Un RdP est born pour un marquage initial M0 si toutes les places sont bornes pour M0.
Un RdP est sauf pour un marquage initial M 0 sil y a une marque au plus dans chaque place, pour tout
marquage accessible partir de M0.
Une transition Tj est vivante pour un marquage initial M 0 si pour tout marquage accessible
M i !!*M0, il existe une squence de franchissements S qui contienne la transition Tj, partir de M i .
Autrement dit, quelle que soit lvolution, il existera toujours une possibilit de franchir Tj.
Un RdP est vivant pour un marquage initial M0 si toutes ses transitions sont vivantes.
Un blocage est un marquage tel quaucune transition nest valide. Un RdP est dit sans blocage pour un
marquage initial M0 si aucun marquage accessible nest un blocage.
Pour les diffrents RdP ci-dessous, dire sils sont, votre avis, vivant, sans blocage
et borns. Expliquer.
P1

P1
T4

T1
P2

P2

P3

P1
T4

P2

T2

T2

P1
T4

P4

T1
P2

T1

T4

P4

P2
T3

P3
T3

P3

P1

P4

T3

P3

T2

T4

P4

T1
P2

T3

T2

T1

T4

P4

T1
T3

P1

T3

P3

T2

P3

T2

Un RdP a un tat d'accueil M a pour un marquage initial M 0 si pour tout marquage accessible
M i !!*M0, il existe Si tel que Mi (Si Ma.
Un RdP est rinitialisable pour un marquage initial M0 si M0 est un tat d'accueil.

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Dfinitions : On dit quil y a conflit quand une place a 2 transitions de sortie. On parle de conflit
structurel car cela ne dpend pas du marquage. Dans certains cas, le franchissement de lune des
transitions peut empcher le franchissement de lautre.

Le conflit devient conflit effectif quand il y a effectivement conflit. Cela dpend du marquage :

conflit effectif

pas de conflit effectif

Si chaque transition ne peut tre concerne que par un conflit au plus, , le RdP est simple.
Structures particulires :
Un graphe d t a t est un RdP telle
que toute transition a une place
dentre et une place de sortie.
Un graphe dvnement est un RdP
telle que toute place a exactement une
transition dentre et une transition de
sortie.
Un RdP est choix libre si pour
tout conflit Pi, Tj, Tk, ni Tj ni Tk na
dautre place dentre. Dans ce cas,
tous les conflits structurels sont
effectifs.
Un RdP est pur sil nexiste aucune
transition telle que une des places
dentre soit galement place de sortie.

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

1.6 INVARIANTS
A partir dun marquage initial, le marquage dun RdP peut voluer par franchissement de transitions : et
sil ny a pas de blocage, le nombre de franchissements de transitions est illimit. Nanmoins, on ne
pourra pas atteindre nimporte quel marquage et on ne pourra pas franchir nimporte quelle squence de
transitions. Des invariants permettent de caractriser certaines proprits des marquages accessibles et des
transitions franchissables, quelle que soit lvolution.
a) Composante conservative.
Soit un RdP n places. On a un invariant linaire de places sil existe une pondration sur le marquage
des places tel que!:
q1 m1 + q2 m2 + + qn mn = cste,
pour tout marquage accessible M!!*M0, les qi tant des nombres entiers naturels.
Lensemble des places P telles que leur pondration soit non nulle est une composante conservative.
Le rseau est dit conservatif si et seulement si lensemble de toutes les places du RdP forme une
composante conservative.
La proprit dtre composante conservative est indpendante du marquage initial. Par contre, la
constante de linvariant dpend du marquage initial.
En rgle gnrale, une composante conservative a une signification physique. Elle peut signifier soit quun
systme est dans un seul tat la fois, soit la conservation du nombre dentits.
Dans lexemple suivant :
automobiliste chez lui
P1
T1

T3

pied

P4

P3
T2

voiture au garage
P2

en
voiture

T4

les composantes conservatives sont :

{P1, P3, P4} : m1 + m3 + m4 = 1 (lautomobiliste est soit chez lui soit a pied soit en voiture)
{P2, P4} : m2 + m4 = 1 (la voiture est soit au garage soit avec lautomobiliste)
{P1, P2, P3, P4} : m1+m2+m3+2.m4 = 2.
b) Composantes rptitives

P1
T1

On revient lexemple :
Les squences de franchissements qui sont possibles partir du marquage M0 sont les
suivantes :
T1, T1T2, T1T2T3, T1T2T3T4, T1T2T3T4T1, etc La squence T1T2T3T4 est particulire

P2

P3

T2

T3

P4

P5

T4

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

car
M 0 (T1T2T3T4 M a. Cette squence ramne ltat initial. Cest une squence rptitive. Une
squence rptitive qui contient toutes les transitions est une squence rptitive complte.
Les squences sont dcrites en utilisant des expressions rgulires. Les rgles dcriture de ces expressions
sont :
T1+T2=T2+T1 T1 ou T2
T1T2 = (T1)(T2) T1 suivi de T2
T1T1 = T12
T1 2 fois de suite
T1T2T3
est une squence de longueur 3
l est une squence de longueur 0
T1* = l+T1+T1T1+T1T1T1+
T1(T2+T3) = T1T2 + T1T3
(T1+T2)T3 = T1T3 + T2T3
Toutes ces rgles restent valables en remplaant Ti par le symbole dune expression rgulire.
La squence S1 est un prfixe de S2 sil existe une squence S3 telle que : S1S3 = S2
Une squence rptitive minimale est une squence rptitive telle quaucun de ses prfixes stricts
(de longueur non nulle) nest une squence rptitive.
Lensemble T des transitions concernes par une squence rptitive est une composante rptitive.
Sil existe une squence rptitive telle que toutes les transitions du RdP soient concernes, le RdP est dit
rptitif.
Dans lexemple de lautomobiliste, il y a deux squences rptitives minimales : T1T2 ou T3T4. Aucune
de ces composantes ne contient toutes les transitions du RdP. Mais partir de ces composantes, on peut
construire dautres composantes rptitives. Lensemble de ces composantes peut scrire :
(T1T2+T3T4)*. On peut construire des squences rptitives compltes. Le RdP est rptitif.
REMARQUE : Aprs avoir prsent les proprits que peuvent possder certains rseaux, il importe
maintenant de savoir comment on va pouvoir trouver si tel rseau prsente telle ou telle proprits. Il
existe principalement 3 classes de mthodes pour rechercher les proprits dun RdP!: le graphe des
marquages ou arbre de couverture (voir 1.6), lalgbre linaire (1.8) ou des mthodes de rduction.

1.7 ALGBRE LINAIRE

Un RdP non marqu est un quadruplet Q=<P, T, Pr, Post> tel que :
P = {P1, P2, , Pn} est un ensemble fini et non vide de places ;
T = {T1, T2, , Tm} est un ensemble fini et non vide de transitions ;
Pr : PxT {0, 1} est lapplication dincidence avant ;
Post : PxT {0, 1} est lapplication dincidence arrire.
Pr (Pi, Tj) est le poids de larc Pi Tj. Ce poids est 1 si cet arc existe et 0 sinon. (Dans le cas dun RdP
gnralis, la valeur de Pr (Pi, Tj) est le poids port par larc, sil existe, 0 sinon.). De la mme faon,
Post (Pi, Tj) est le poids de larc Tj Pi.

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Exemple :
Dans cet exemple,
Pr (P1, T1) = 1 ;
Pr (P1, T2) = 0 ;
Post (P1, T1) = 0 ;
Post (P2, T1) = 1 ;

P1
T1

P2

P3

T2

T3

P4

P5

T4

Quelques notations :
Tj = {Pi P | Pr(Pi, Tj) > 0} = ensemble des places dentre de Tj
Tj = {Pi P | Post(Pi, Tj) > 0} = ensemble des places de sortie de Tj
Pi = {Tj T | Post(Pi, Tj) > 0} = ensemble des transitions dentre de Pi
Pi = {Tj T | Pr(Pi, Tj) > 0} = ensemble des transitions de sortie de Pi
Un RdP marqu est un doublet R = <Q, M0> dans lequel Q est un RdP non marqu et M0 est un
marquage initial.
On peut exprimer la condition de validation dune transition de la faon suivante : la transition Tj est
valide pour un marquage M si et seulement si M(Pi) Pr (Pi, Tj) pour tout Pi Tj.
On appelle matrice dincidence avant la matrice :
W- = [w-ij], o w-ij = Pr (Pi, Tj).
On appelle matrice dincidence arrire la matrice :
W+ = [w+ij], o w+ij = Post (Pi, Tj).
Pour lexemple prcdent, on a :
T1 T2 T3 T4
1 0 0 0 P1
0 1 0 0

P2

W- = 0 0 1 0

P3

0 0 0 1
0 0 0 1

T1 T2 T3 T4
0 0 0 1 P1
1 0 0 0

P2

W+ = 1 0 0 0

P3

P4

0 1 0 0

P4

P5

0 0 1 0

P5

et

On appelle matrice dincidence la matrice W = W+ - W- = [wij]. Dans notre exemple :

W=

T1
-1

T2
0

T3
0

T4
+1

P1

+1

-1

P2

+1

-1

P3

+1

-1

P4

+1

-1

P5

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Une colonne de cette matrice correspond la modification du marquage apport par le franchissement
de la transition correspondante. (Ex : en franchissant T1 si elle est franchissable, on retire une marque
dans P1 et on en ajoute une dans P2 et une dans P3).
quation fondamentale : Si on passe dun marquage Mi un marquage Mk par une squence de
franchissement S, cad Mi(S Mk, on a lquation :
Mk = Mi + W.S
o S est la squence de franchissement S mise sous forme vectorielle, llment j de ce vecteur tant le
nombre de fois quapparat la transition Tj dans la squence.
Exemple : calcul du marquage rsultant du tir de T2 partir du marquage : 1 marque dans P2, une marque
dans P3. (Pour le RdP prcdent).
0

-1

+1

+1

-1

+1

-1

+1

-1

+1

-1

Mi

0
.

1
0
0

-1

= 1

= 1

+1

0
Mk

Pour le RdP B du paragraphe 1.5, calculer le marquage aprs la squence de

franchissement : T1T3T4T1T3T4T1T2.
Composante conservative : Soit F un vecteur de pondration des places F = (q1, q2, ,
qn) tel que chaque qi est un nombre entier positif ou nul. Soit P(F) lensemble des places dont
le poids nest pas nul. P(F) est une composante conservative si et seulement si FT.W = 0.
Le vecteur F est appel un P-semi-flot.
Dans notre exemple, pour F= (1,1,0,1,0), FT.W = 0 donc P(F) = {P1, P2, P4} est une
composante conservative. Linvariant linaire de place est : m1 + m2 + m4 = 1. Il existe un
autre P-semi-flot pour cet exemple : G = (1, 0, 1, 0, 1).
Proprit : Si F1 et F2 sont deux P-semi-flots dun mme RdP, alors "(a,b) N, a.F1 +
b.F2 est un P-semi-flot.
Dans notre exemple, F+G = (2, 1, 1, 1, 1) est un P-semi-flot. Comme toutes les places
sont concernes par ce P-semi-flot, ce RdP est conservatif.
Proprit : Soient P(F) une composante conservative et F = (q1, q2, , qn) le vecteur
pondration correspondant. Toutes les places de P(F) sont bornes et lon a : M(Pi)
(FT.M0)/qi .
Composantes rptitives : Soit S une squence de franchissement et T(S) lensemble des
transitions qui apparaissent dans cette squence. T(S) est une composante rptitive si et
seulement si W.S = 0. Le vecteur S est appel un T-semi-flot. T(S) est une composante
rptitive croissante si W.S > 0. Remarque : tout T-semi-flot ne correspond pas forcment
une composante rptitive car il ne correspond pas ncessairement une squence de

10

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

franchissement.
Pr
od
uc

Ta
m

P
T

Ta
m
P

C
on
P
T

Pour ce RdP, donnez la matrice W, un P-semi-flot et un T-semi-flot, sil y en a.

1.8 MODLISATION PAR RDP

Les RdP permettent de reprsenter graphiquement certaines relations, de visualiser certaines
notions. En voici quelques exemples.

Synchronisation

(smaphore)

Paralllisme

Partage de ressource

Synchronisation

(rendez-vous)

11

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Capacit limite

Lecture

Gestion des cabines et des paniers dune piscine.

A lentre, un client qui a trouv une cabine libre y entre et se change en posant ses vtements dans la
cabine. Il demande ensuite un panier quil remplit pour librer la cabine. Aprs la baignade le client rentre
dans une cabine avec son panier, le vide et le libre. Ensuite, il se rhabille et libre la cabine.
Modliser le protocole avec un RdP en prenant comme hypothse quil y a 5
paniers et 3 cabines. Le nombre de clients la baignade est-il born? Le RdP est-il
born ? Montrer quil y a blocage.
Les philosophes.
Comme lindique la figure ci-dessous, quatre philosophes (phi1 phi4) sont autour dune table, disposant
de 4 baguettes (b1 b4) disposes entre eux. Un philosophe peut avoir essentiellement deux tats : il
pense ou il mange. Pour manger il a besoin des deux baguettes qui sont de chaque ct de lui. A ltat
initial, tous les philosophes pensent et les baguettes sont poses sur la table.
Dcrire par un RdP le protocole suivant : lorsquun philosophe veut manger, il
prend la baguette sa droite, puis celle sa gauche et se met manger. Quand
il a fini, il repose la baguette de droite puis celle de gauche. Montrer quil y a
blocage.

12

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Chapitre 2 : Les rseaux de Petri temporiss

Un RdP temporis est permet de dcrire un systme dont le fonctionnement dpend du temps. Les RdP
temporiss sont utiles pour lvaluation des performances dun systme. Soit les temporisations sont
associes aux places (RdP P-temporis) soit aux transitions (RdP T-temporis).

2.1 RSEAUX DE PETRI P-TEMPORISS

On associe une temporisation (valeur rationnelle positive) chaque place. On notera di la temporisation
de la place Pi.
Principe de fonctionnement : lorsquune marque arrive dans une place temporise, on dit quelle est
indisponible pendant un temps di. Quand le temps est coul, la marque devient disponible. Exemple!:

d1

T
P

d1

T
d2

d1

d2

d1

d2

d2

d2

d2
Fr
an
ch

d1

d1
la
mar
que

Fr
an
ch

la
mar
que

On parle de fonctionnement vitesse maximale quand on franchit toute transition ds quelle

devient franchissable. Dans ce cas de fonctionnement, on peut complter le graphe des marquages en
associant chaque arc du graphe reliant un marquage Mi un marquage Mj par la transition Tk le temps
sparant lobtention du marquage Mi du tir de la transition Tk. Pour lexemple prcdent, cela donne :
1

T1/0

M0

M1

T2/3
T1/2

1
0
M2

On remarque quaprs le passage de Mo M1, on a un fonctionnement priodique.

Proprit : Un RdP born fonctionnant vitesse maximale a toujours un comportement priodique au
bout dun temps fini.
Un RdP P-temporis fonctionne en vitesse propre si toute marque ne reste dans une place que pendant sa
dure dindisponibilit.

13

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

La frquence de franchissement Fj dune transition Tj est le nombre moyen de franchissements

dune transition par unit de temps, lorsque le rgime stationnaire est tabli.
Calcul des frquences de franchissement :
Dans notre exemple, le nombre moyen de marques dans la place P1 est : d1.F2 car les marques entrent
une frquence F2 et y restent un temps d1. De mme, dans P2, il y a en moyenne d2.F1 marques.
Comme le RdP est conservatif, on a :
d1.F2 + d2.F1 = Mo(P1) + Mo(P2).
On observe F1 = F2. d1=2 et d2=3. On en dduit F1 = F2 = 1/5.
On aurait pu crire aussi quen rgime stationnaire, le nombre de marques qui entrent dans une place est
gal au nombre de marques qui en sortent. Ce dernier nombre est gal, pour la place 1 de notre exemple
d1.F1. Ce raisonnement conduit une autre quation :
d1.F1 + d2.F2 = Mo(P1) + Mo(P2).
Ce qui donne le mme rsultat.
De faon gnrale, on a les relations suivantes :
Une relation liant les temporisations, les frquences et le marquage initial qui est associe chaque
invariant de marquage. Cette relation est une inquation car les frquences relles peuvent tre
infrieures celles qui correspondraient un fonctionnement vitesse propre. Cette quation peut
scrire :
X T. D . W+.F XT. M o
o X
est un P-semi-flot, D, une matrice diagonale telle que Dii = di, la temporisation associe la place Pi, F,
le vecteur des frquences de franchissement et Mo, le marquage initial.
Une relation entre les frquences de franchissement des transitions correspondant chaque invariant de
franchissement.
De ces relations on dduit les frquences de franchissement correspondant au fonctionnement vitesse
maximale (quand le problme est soluble). Ceci permet dvaluer certaines performances de systmes, le
franchissement dune transition pouvant correspondre laccomplissement dune tche, et le marquage
moyen dune place un nombre moyen de clients en attente dun service.

d1

T
P

d2

d3

Pour cet exemple, donner les frquences maximales de franchissement des deux
transitions.

14

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

2.2 RSEAUX DE PETRI T-TEMPORISS

On associe cette fois la temporisation aux transitions.
Principe de fonctionnement
Une marque peut avoir deux tats : - disponible (ou non rserve)
- ou bien rserve pour le franchissement dune transition.
Exemple de fonctionnement :
P
T

P
d1

P
T

d1

P
d2

P
d1

Fr
anc
hiss

d2

d1

T
P

d2

d1
Rs
erv
atio
n
de
la

d1

d2

d2

d1
la
mar
que
rse

Fr
anc
hiss

la
mar
que
rse

Remarque : on peut toujours passer dun RdP T-temporis un RdP P-temporis.

On peut, de la mme faon que pour les RdP P-temporiss, le fonctionnement vitesse maximale et le
fonctionnement vitesse propre. Dans le cas de lexemple prcdent, avec 1 marque dans la place P1 et 1
marque dans P2 au dpart, on obtient le graphe des marquages suivant :
1
1
M0

T1/2

T2/1

2
M1

1
1
M2

T1.T2/2
De mme que pour les RdP P-temporiss, le calcul des frquences maximales de franchissement se fait en
galant le nombre moyen de marques dans une place Pi au produit de la frquence de sortie Tj par dj (ou
la somme des [Link] sil y a plusieurs transitions de sortie de la place Pi).

15

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Processus stochastiques

Gnralits :
Un processus stochastique est une famille de variables alatoires X(t) valeur relles o t est un
paramtre rel. Lespace des paramtres ou espace temps T correspondant prendra essentiellement lune
des deux formes suivantes :
T = {0 ,1, 2, } ; on parlera de processus stochastique temps discret et on crira Xn au lieu de
X(t). Ce sera notamment le cas des chanes de Markov temps discret.
T = [0, ) ; on dira alors que {X(t) ; t 0} est un processus stochastique temps continu. Ce
sera le cas de tous les autres processus tudis dans ce cours.
On appellera espace des tats lensemble S des valeurs prises par toutes les variables alatoires dun
processus stochastique. Nous nous limiterons aux processus stochastiques tats discrets ; S sera
identifi un sous ensemble {1, 2, }.
La forme prise par un processus stochastique lors dune exprimentation du phnomne alatoire en
question est appel ralisation ou trajectoire de ce processus.
Voici quelques exemples de phnomnes physiques susceptibles dtre modlis par des processus
stochastiques.
Le nombre d appels arrivant dans un central tlphonique pendant un intervalle de temps [0, t] ;
Le nombre de dfaillances se produisant par jour dans un systme technique
La fortune du joueur aprs avoir jou n parties.
Le nombre de clients dans une file dattente un instant donn.

16

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Partie A : Les chanes de Markov

Une chane de Markov (CM) est un cas particulier de processus stochastique. Il en existe deux types : les
CM temps discret et les CM temps continu. Dans ce dernier cas, on les appelle aussi processus de
Markov.

1. Chanes de Markov temps discret

1.1 Introduction-Dfinition
Une grenouille (Zora) est sur un tang comprenant 4 nnuphars (numrots de 1 4). La grenouille
saute de nnupar en nnuphar. Le nnuphar destination du saut ne dpend que du nnuphar de dpart.
La grenouille na pas de mmoire. Si Xn reprsente le numro du nnuphar o est la grenouille aprs n
sauts, on peut dfinir : pij(n) = p(Xn+1 = j | Xn = i). Cest la probabilit conditionnelle que la grenouille
fasse un saut du nnuphar i au nnuphar j la date n. Ceci signifie implicitement que ces probabilits
conditionnelles ne dpendent pas du comportement antrieur linstant n de la grenouille :
pij(n) = p(Xn+1 = j | Xn = i) = p(Xn+1 = j | Xn = i, Xn-1 = 1)
p(Xn+1 = j | Xn = i, Xn-1 = 2)
p(Xn+1 = j | Xn = i, Xn-1 = 3)
p(Xn+1 = j | Xn = i, Xn-1 = 4)
La classe des processus verifiant cette proprit est caractrise par le fait que ltat prsent du processus,
cad son tat linstant n, rsume toute linformation ncessaire pour connatre son volution future.
En dautres termes, la prvision de cette dernire ne peut tre amliore par une connaissance
supplmentaire du pass du processus, cest dire par la connaissance de ses tats aux instants n-1.
Cette proprit (sans mmoire) est connue sous le nom de proprit de Markov. Elle sexprime par :
p(Xn+1 = j | Xn = i) = p(Xn+1 = j | Xn = i, Xn-1 = in-1, , X0=i0) pour n0 et j, i, in-1, ,i0 S
Une chane de Markov temps discret est un processus stochastique qui vrifie cette proprit.
Nous ne nous intresserons quau chanes de Markov homognes, cest dire pour lesquels les
probabilits de transition sont indpendantes du temps (pij(n) = pij).

1.2 Matrice et graphe des transitions

La matrice de transition dune CM temps discret est la matrice P compose des pij, probabilits de
transition. Cette matrice est carre, de dimension le nombre dtats possibles. Tous les termes sont
positifs ou nuls et infrieurs ou gaux 1 (puisquelle ne contient que des probabilits). La somme des
termes de chaque ligne est 1 (puisquil y a toujours 1 tat de destination).
Le graphe des transitions est form de points reprsentant les tats du processus et darcs correspondant
aux transitions possibles, cad pour lesquelles les probabilits pij sont non nulles.

17

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Exemple de Zora :
Matrice de trannsition :
0,1 0,5 0,4
P=

Graphe des transitions

0,5 0,3 0,2

0,4 0,6

0,5

0,5

0,1

0,5

0,4

0,3

0,5

0,4

0,5

0,6

0,5

TD A.1: fiabilit de deux lments en parallle

Soit un dispositif technique comprenant deux lments monts en
parallle et fonctionnant indpendamment lun de lautre. Chaque
lment a une fiabilit gale p au cours dune journe (cad quil a une
probabilit de 1-p de tomber en panne). Il ny a pas de possibilit de
rparation. Si Xn est le nombre dlments en panne au dbut de la n-ime
journe, dcrire la chane de Markov correspondante, sa matrice et son
graphe de transition.
Modifier la chane prcdente en stipulant quune machine en panne sera
rpare au cours de la journe suivante.
La suite du cours nous donnera la possibilit de rpondre aux questions du type :
Quelle est la distribution du nombre dlments en panne aprs 1, 2, 3, , n jours?
Quelle est la dure de bon fonctionnement de ce dispositif?

1.3 Loi de probabilit de Xn

Soit p k (n) = P(Xn=k) , pour n 0 et k S. Cest la probabilit que le processus soit dans ltat k
linstant n. On peut dfinir ainsi un vecteur ligne p(n) = [p1(n), p 2(n), ] dont la somme des termes
vaut 1. On a la relation suivante :
p(n+1) = p(n).P o P est la matrice de transition.
On peut en dduire :
p(n) = p(0).Pn
Dans lexercice prcdent (deux lments en parallle, sans rparation),
calculer la probabilit p en fonction de n.
AN : p=0,9.

1.4 Comportement asymptotique

Nous avons pu calculer p(n), les probabilits dtat en fonction de n. Ces dernires dpendent de p(0).
En fait, nous avons tudi le rgime transitoire du processus.
On constate souvent que la distribution p(n) converge vers une distribution limite quand n . Quand
cest la cas, cette dernire dfini le rgime permanent du processus. Ce rgime permanent nest pas

18

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

influenc par le choix de la distributuion initiale. On admet que le rgime permanent est atteint au bout
dun nombre fini de transitions.
Existe-t-il un rgime permanant pour la chane de Makov dfinie par :
1.
0 1
P=
1 0
2.
0,2 0,8
P=
0
1
3.
0,2 0,8
P=
0,1 0,9
Thorme : Si la matrice de transition P est telle quau moins une de ses puissances na que des termes
strictement positifs, alors, quelle que soit la distribution initiale p(0), quand n tend vers linfini :
p(n) p
Pn P*
p est un vecteur de probabilit strictement positif et P*, une matrice dont toutes les lignes sont
identiques au vecteur limite p.
Thorme : Si la valeur propre 1 de P est simple et si toute autre valeur propre de P est de module
strictement infrieur 1, alors les conclusions du thorme prcdent sont les mmes.
Une distribution de probabilit discrte p est appele stationnaire par rapport une matrice
stochastique!P si :
p.P = p.
Pour trouver les composantes du vecteur de distribution stationnaire, il existe 2 mthodes :
rsoudre le systme :
p.P = p
pk = 1
kS

en rsolvant les quations de balance : on interprte les probabilit pk comme des masses associes
aux tats k et le produits p k pkj comme des flux de masse entre les deux tats k et j. La rpartition
des masses p k est stationnaire si, lors dune transition, le flux dentre et gal au flux de sortie
pour chacun des tats
Thorme : Si p est la distribution limite dune chane de Markov, alors p est lunique distribution
stationnaire de cette chane.
TD A.2 : Trouver les distributions limite des chanes suivantes
1. Montrer que le chane de Markov dfinie par P converge et calculer la
distribution limite
1/2 1/2 0
P= 1/2 0 1/2
0

[Link] la matrice :

19

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

P=

0 2/3 1/3

0
0

1
0
0
0
a) Dessiner le graphe des transitions correspondant.
b) Calculer les valeurs propres de P. La chane est-elle convergente ?
c)Calculer la distribution stationnaire de ce processus.

1.5 Chanes de Markov absorbantes

Un tat k dune chane est dit absorbant si le processus ne peut plus quitter cet tat une fois quil y est
entr. En dautres termes, pkk = 1. Une chane de Markov est dite absorbante sil existe au moins un
tat absorbant et sil on peut passer de nimporte quel tat un tat absorbant.
Lorsquon a affaire une chane de Markov absorbante, on est gnralement intress par les deux
questions uivantes :
Combien de temps faudra-t-il pour que le processus soit absorb, tant donn son tat initial ? On
appellera ni le temps moyen jusqu labsorption en partant de i.
Sil existe plusieurs tats absorbants, quelle est la probabilit pour un processus dtre absorb par
un tat donn. On appellera bij la probabilit que le processus soit absorb dans j si son tat initial
est i.
Thorme : Les quantits ni sont solution du systme dquations :
ni=1+ piknk
kS'

o i est un tat non absorbant et S lensemble de tous les tats non absorbants
Thorme : Soit j un tat absorbant et S lensemble de tous les tat non absorbants. Alors les probabilits
bij (i S) sont solution du systme dquations :
bij=pij+ pikbkj
kS'

TD A.3
1 : calcul de dure de vie dune pice
Une certaine pice dquipement lectrique peut se trouver dans 3 tats :
1: bonne ; 2 : condition marginale ; 3 : dfaillante.
A la fin de chaque jour de service, ltat de la pice est enregistr. La
matrice de transition obtenue est :
0,7 0,2 0,1
P = 0,5 0,3 0,2
0
0
1
Calculer la dure de vie moyenne dune pice se trouvant initialement en
bonne condition.
2. promenade du scarabe

20

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Soit un ttrahdre rgulier dont les sommets sont numrots de 1 4. Un

scarabe qui se trouve initialement sur le sommet 1 se dplace pendant
chaque unit de temps le long dune arte. Arriv en un sommet, ilchoisit
avec la mme probabilit lune des trois artes pour continuer sa
promenade.
quel est le temps moyen pour atteindre pour la premire fois le
sommet 4 ?
Quelle est la probabilit datteindre 4 sil y a un mangeur de scarabe
en 2

2. Chane de Markov temps continu

2.1 La loi exponentielle
La loi exponentielle joue un rle fondamental dans la suite du cours. Considrons la dure T de bon
fonctionnement dun dispositif technique et admettons que T soit une loi exponentielle de taux l. La
fonction densit de probabilit de cette loi est :
f(t) = l e-l t
(t 0)
Sa fonction de rpartition est :
F(t) = P(T>t) = e-l t
Si un temps alatoire suit une loi exponentielle de taux l, le temps moyen sera : 1/l.
La figure ci-dessous reprsente f(t) et F(t) pour l = 1.
f(t)
1
F(t)
0,8
0,6
0,4
0,2
0

0,5

1,5

2,5

Proprits :
La loi exponentielle est sans mmoire. Cela signifie que la probabilit de bon fonctionnement
pendant un intervalle (u, u+t] dpend uniquement de la longueur t de cet intervalle et non pas de
sa position relative laxe temporel :
P(T > t+u | T u) = P(T > t) = e-l t
La loi exponentielle est la seule loi qui possde cette proprit.
La probabilit que ce dispositif tombe en panne dans lintervalle (t, t+dt] est [Link].
Soit T1, T2, T3, , Tn des variables alatoires indpendantes distribues selon des lois
exponentielles de paramtres l 1, l 2, , l n. Alors T = min(T1, T2, T3, , Tn) soit une loi

21

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

exponentielle de paramtre l1 + l 2 ++ln.

2.2 Dfinitions
Dfinition : Une chane de Markov homogne temps continu et nombre fini dtats est un processus
stochastique {X(t), t 0} tel que :
P[X(t+dt) = j | X(t) = i] = pij(dt).
O pij(dt) est la probabilit dtre dans ltat j aprs un intervalle de temps dt sachant que ltat courant
est i. On peut dfinir par qij, le taux de transition de ltat i ltat j (ji).
p (dt)
qij = limdt0 ij
dt
Le temps de passage de la chane de ltat i ltat j est un temps alatoire qui suit une loi exponentielle
de taux qij.
Le temps pendant lequel la chane de Markov reste dans ltat i est le plus petit des temps de passage de
cet tat i un autre tat. Daprs la dernire proprit des lois exponentielle, le temps de sjour de la
chane dans cet tat i suit une loi exponentielle de taux (quon appellera taux de sortie de ltat i) :
qii = - qij
ji

Remarque : On peut considrer que le fonctionnement dune chane de Markov temps continu a le
fonctionnement suivant : dans un tat, le processus reste un temps alatoire qui suit une loi
exponentielle de taux -qi i. A la sortie de cet tat, le processus choisi son tat destinantion suivant le
probabilits : -qij/qi i.
La matrice Q ainsi construite est appele matrice de transition ou gnratrice de la chane de Markov.
On peut associer chaque chane de Markov un graphe orient construit de la faon suivante : chaque
tat i du processus est reprsent par un noeud. Il y a un arc entre un noeud i et un noeud j i si et
seulement si llment i, j de la matrice Q est non nul. On donne alors un poids larc i, j : le taux de
transition de ltat i ltat j. Cest llment i, j de la matrice Q.
Exemple : Soit la chane de Markov (qui pourrait reprsenter le comportement de Zora) dfinie par son
gnrateur :
-3 2 1
Q = 0 -2 2
1 0 -1
Sa reprsentation graphique est en figure ci dessous.
2
2
1
1

1
3

2.3 Loi de probabilit de x(t)

Si x(t) est le vecteur dont les lments sont les probabilits de prsence du processus dans ses tats, on

22

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

peut crire :
x(t)=x(t).Q
x(0) est la distribution initiale de probabilit de prsence dans les tats.
La rsolution de lquation diffrentielle ci-dessus donne :
x(t) = x(0). eQ.t
Dans la pratique, on ne sintressera qu deux types de problmes : le comportement asymptotique de ces
chanes (voir paragraphe suivant) soit les temps dabsorption des chanes absorbantes (voir paragraphe
daprs).

2.4 Comportement asymptotique

On constate souvent souvent que la distribution x(t) converge vers une distribution limite quand t .
Quand cest la cas, cette dernire dfini le rgime permanent du processus. Ce rgime permanent nest
pas influenc par le choix de la distributuion initiale.
On diffrentie deux catgories dtats : les tats transitoires dont la probabilit de prsence du processus
dans cet tat tend vers 0 quand t tend vers linfini. Les autres tats sont appels ergodiques.
Une distribution de probabilit p est appele stationnaire par rapport une gnratrice Q si :
p.Q = 0.
Pour trouver les composantes du vecteur de distribution stationnaire, il existe 2 mthodes :
rsoudre le systme :
p.Q = 0
pk = 1
kS

en rsolvant les quations de balance : on interprte les probabilit xk comme des masses associes
aux tats k et le produits xk qkj comme des flux de masse entre les deux tats k et j. La rpartition
des masses xk est stationnaire si, lors dune transition, le flux dentre et gal au flux de sortie
pour chacun des tats
Si p est la distribution limite dune chane de Markov, alors p est lunique distribution stationnaire de
cette chane.

2.5 Chanes de Markov absorbantes

Un tat k dune chane est dit absorbant si le processus ne peut plus quitter cet tat une fois quil y est
entr. En dautres termes, qkk = 0. Une chane de Markov est dite absorbante sil existe au moins un
tat absorbant et sil on peut passer de nimporte quel tat un tat absorbant. Nous ne nous
intresserons quaux chanes de Markov nayant quun seul tat absorbant. (si tel nest pas le cas, il suffit
de rassembler tous les tats absorbants en un seul). Le gnrateur Q peut donc se mettre sous la forme :

Q=

00

23

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

o v est un vecteur colonne vrifiant :

v= - S.e
pour assurer la nullit des sommes par ligne des lments de Q, e tant un vecteur colonne de
dimension approprie dont tous les lments valent 1. La distribution initiale est concentre sur les tats
transitoires sans perte de gnralit :
x(0) = ( a , 0 )
o a est un vecteur ligne contenant les probabilits initiales de prsence dans les tats transitoires.
Ce qui nous intresse dans ces chanes absorbantes cest le temps que va mettre le processus pour arriver
dans ltat absorbant.
Proprit : La fonction de rpartition de cette loi de probabilit est la fonction probabilit de prsence
du processus dans ltat absorbant en fonction du temps.
En rsolvant les quations diffrentielles dvolution de la chane, on trouve :
f(t) = [Link].v
Il peut tre plus commode de calculer la Transforme de Laplace de cette densit de probabilit :
F(p) = TL (f(t)) = a.(pI-S)-1.v
o I est la matrice identit de dimension adquate.
Le temps moyen dabsorption se calcule alors :

T=

t.f(t) dt
t=0

TD A.4 Promenade de ZORA

Nous nous intressons prsent au comportement de la grenouille Zora au
cours du temps (et non plus aux sauts seulement). Nous observons le
comportement modlis par la chane de Markov temps continu
suivante :
2
5
2
1

1. Trouver la gnratrice correspondante. Calculer les probabilits p12, p41,

p23, p34.
2. Le taux de sortie de ltat 2 est 5. Cela signifie que le temps de sjour de
Zora sur le nnuphar 2 suit une loi exponentielle de taux 5. Quel est le
temps de sjour moyen de Zora sur ce nnuphar si lunit de temps est
lheure.
3. Calculer les probabilits stationnaires de prsence de Zora sur chacun
des nnuphars.
4. Il y a un hron au dessus du nnuphar 4. Calculer la densit de probabilit
du temps que mettra Zora pour rencontrer le hron sachan quau dpart,
Zora est sur le nnuphar 1.

24

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Partie B : Les Rseaux de files dattente

1. Introduction
Les Rseaux de Files dAttente (RFA) permettent de modliser et danalyser les systmes de type
clients/serveurs.

Un peu dhistoire :
Ils ont t introduits pour ltude des premiers systmes tlphoniques, pour connaitre le taux
doccupation des lignes et des standards. Plus tard, ils ont servi en recherche oprationnelle et en
fiabilit. Plus tard encore, en informatique, ils ont permis de prvoir le taux dutilisation dun serveur ou
dun rseau. En ce qui concerne les systmes de production, il est clair que lon peut aisment considrer
les pices comme des clients et les machines comme des serveurs. Les applications sont alors
nombreuses!: taux doccupation machine, temps de sjour dune pice dans le systme de production,
nombre de pices dans les stocks intermdiaires. Voir figure 1.

2. Prsentation dune station

Une station est un systme o les clients arrivent pour recevoir un service. Si le serveur ou les serveurs
sont occups, ils attendent leur tour.
Schema d'une station :
File d'attente

Serveur(s)

Arrive

Dpart

Figure 2 : reprsentation dune station

Dfinitions :
La file d'attente : Elle peut tre finie ou infinie. Dans ce dernier cas, elle peut modliser un stock
capacit illimite. Quand un client essaye dentrer dans une station dont la file dattente limite est
pleine, on considre que le client est perdu.
Le ou les serveurs : On parle dun monoserveur lorsquil y a un serveur qui traite les clients les uns
aprs les autres. Cest le cas des guichets par exemple. On parle de multiserveur quand plusieurs clients
sont servis en mme temps, parcequil y a plusieurs serveurs. Cest le cas dun rayon fromage dans les
supermarchs par exemple. La notion de serveur infini est plus abstraite. Il correspond au cas o tous
les clients qui arrivent peuvent tre servis immdiatement. Cela suppose que la file dattente derrire un

25

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

tel serveur nest pas utile. Cest le cas des rayons botes de conserve dans les supermarchs par exemple.
Certains convoyeurs peuvent galement tre considrs comme tels.
Discipline de service : Ordre dans lequel les clients dans la file seront retirs pour tre servis. La
discipline par dfaut est PAPS (Premier Arriv, Premier Servi) ou FIFO (First In, First Out). Si une
autre discipline est utilise (comme DAPS ou LIFO ou bien alatoirement ou autre), il faut la prciser.
Processus d'arrive : dcrit le temps entre deux arrives successives de clients. Ce temps peut tre
dterministe (il faut donner sa valeur) ou bien alatoire (il faut alors prciser la loi : loi de Poisson,
d'Erlang ou autre et les paramtres qui permettent de la dfinir).
Processus de service : dcrit le temps que met un serveur pour trater un client. Mmes remarques
que ci-dessus.

Notation de Kendall
Pour prciser en 2 lettres et 2 nombres les principaux paramtres de la file d'attente : A/B/C/K.
A et B : Processus d'arrive et Processus de service
M : loi de Poisson (nous en verrons une dfinition au chapitre suivant) ou loi exponentielle
D : Dterministe
G : gnrale
C : le nombre de serveurs
K : La capacit de la file (omise si infinie)
Exemples :
Une caisse de supermarch dont larrive de clients suit une loi de poisson et telle que le temps de
service (temps de traitement dun client) suive une loi exponentielle peut tre considre comme une
station M/M/1
Un salon de Coiffure dont larrive des clients suit une loi de poisson et telle que le temps de service
(temps de coiffage dun client) suive une loi grrale ( prciser) qui comprend 2 coiffeurs et 4 places
assises pour attendre peut tre considr comme une station M/G/2/4
Un convoyeur vitesse constante et qui na quune entre et une sortie et dont larrive des clients suit
une loi de poisson peut tre considr comme une station M/D/
Un petit train touristique dont larrive des touristes suit une loi de poisson et telle que le temps de
service (temps mis par le train pour faire le tour de la ville) est constant et qui a 100 places assises ne
peut pas tre considr comme une station M/D/100.
Expliquez pourquoi.

26

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

3. Etude dune station

On peut vouloir tudier une station en isolation. Bien sr, lorque les processus darrive et de service
sont dterministes, le comportement de la station est galement dterministe et une tude est inutile.
Par contre, lorsque ces processus sont alatoires, selon sil y a un ou plusieurs serveurs, si la file est
capacit limite ou non, il devient difficile dintuiter le nombre moyen de clients en attente par exemple.

Performances souhaites
Ltude dune station doit permettre de connatre son comportement et plus particulirement, certaines
grandeurs qui semblent importantes. Certaines dentre elles sont indpendantes des processus
d'arrive/de service, elles dpendent seulement de leur moyenne :
dbit des clients : X
taux d'utilisation du serveur
Dautres, dpendent des processus d'arrive/de service :
nombre moyen de clients dans la station : Q (clients en attente + clients en train dtre servis)
temps de rponse du client (entre lentre et la sortie de la station) : W (temps dattente + temps de
service)
Une loi relie certaines de ces grandeurs, la loi de Little :

Q = W.X
Pour connatre ces grandeurs, il faut et il suffit de calculer :
P(n) = probabilit d'avoir n clients dans la station, n N.
Etudier une station cest trouver P(n), pour tout n. Dans le cadre de mthodes analytiques, on trouvera
P(n) par calcul. On peut aussi le trouver par simulation. Une fois quon a P(n), pour tout n, on peut
connatre :

Q=

n P(n)

n=0

car Q est la moyenne du nombre de clients dans la station. Le dbit des clients vaut, sil ny a qu1
serveur :
X = m.(1 - P(0))
o [Link] le dbit du serveur lorsque celui-ci est occup. Si la file dattente est illimite et que lon appelle
l le dbit dentre des clients et si l < m alors X = l en rgimle permanent. On peut alors connatre le
temps de passage myen du client dans la station :
W=Q/X

Etude de la M/M/1
Nous allons particulirement tudier une station dont les processus darrive des clients et de service
sont repectivement un processus de poisson et une loi exponentielle. Ces processus dits markoviens sont
particulirement pratiques dans le cadre dun tude analytique car le comportement de la station peut

27

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

tre dcrit par un processus Markovien de naissance et de mort.

Dfinition : On dit quun processus de comptage (dvnements arrivant alatoirement) {N(t)} est un
processus de Poisson sil satisfait aux trois conditions suivantes :
Le processus N(t) est homogne dans le temps. Ceci veut dire que la probabilit davoir k
vnements dans un intervalle de longueur donne t ne dpend que de t et non pas de la position
de lintervalle par rapport laxe temporel.
Le processus N(t) est accroissements indpendants ce qui signifie que pour tout systme
dintervalles disjoints, les nombres dvnements sy produisant sont des variables alatoires
indpendantes.
La probabilit que deux vnements ou plus se produisent dans un petit intervalle dt est
ngligeable par rapport la probabilit quil ny ait quun seul vnements. En termes plus prcis :
pk(t) = o(dt) si k2,
pk(t) = [Link] + o(dt) pour k=1 et
pk(t) = [Link] + o(t) pour k=0.
Le coefficient l est appel densit ou intensit du processus poissonien.
Thorme : Le coefficient l est gal au nombre moyen dvnements par unit de temps.
Thorme : Un processus de comptage est un processus de Poisson de paramtre l si les intervalles de
temps entre deux vnements conscutifs sont des varaibles alatoires indpendantes obissant la
mme loi exponentielle de paramtre l.
Il y a donc un lien troit entre processus de Poisson et loi exponentielle. Cest pourquoi ils sont
reprsents, dans la notation de Kendall par la mme lettre : M comme Markovien. On parlera de
processus de poisson pour une loi darrive de clients parceque cest un processus de comptage ou de
renouvellement et on parlera de temps suivant une loi exponentielle pour les processus de service.
Lorsque les processus darrive et de service sont markoviens, on peut parler dtat de la station. Ces
tats sont : 0 client dans la station, 1 clients, 2 clietns, etc... On passe de ltat i ltat i+1 si un client
arrive cest dire en suivant une loi exponentielle de taux l. On passe de ltat i ltat i-1 si un client
est servi cest dire en suivant une loi exponentielle de taux m (m est le taux de service du serveur). Pour
quun tel systme ne diverge pas (nombre de clients fini), il est indispensable que l < [Link] une
reprsentation shmatique de ce processus :
l
0

l
1

l
2

l
n

3
m

Figure 4 : processus de naissance et de mort

Il nous faut maintenant chercher P(n), la probabilit davoir n clients dans la station. Cest aussi la
probabilit dtre dans ltat n du processus markovien ci-dessus. On peut crire les quations
dvolution du processus :
P(0)
= m P(1) - lP(0)
t
P(1)
= lP(0) + mP(2) - (l + m) P(1)
t

puis dire quen rgime stationnaire, la partie gauche des quations est nulle. Ce qui nous donne, pour
tout n :

28

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

P(n) = l . P(0)
m
Pour calculer P(0), il suffit de rappeler que les P(i) sont les probabilits dtre dans un tat et que :

p(i) = 1
i=0

Do, dans le cas de la M/M/1 :

P(0) = 1 - r

avec : r = l/m (r < 1)

Nous pouvons alors connatre les performances dune telle station :

Dbit :

X = m (1 - P(0)) = l

Nombre moyen de clients dans la station :

Q=

n.P(n) =

n=0

r
1-r

Nombre moyen de clients en attente (nombre de clients dans la station - clients en train dtre servis) :
Q-r
Temps de rponse moyen :
W=

Q
= 1
X m-l

Temps dattente (temps de rponse - temps de service) :

W- 1
m
Ces rsultats ne sont valables que pour une M/M/1.
Analyse d'une file unique M/M/1
Etude de l'attente dans un organisme public:
Un organisme public est ouvert, chaque jour ouvrable, de 9h 17h sans
interruption. Il accueille en moyenne 64 usagers par jour. Un guichet unique
sert traiter le dossier de chaque usager, ceci dans un temps moyen de
deux minutes et demie. Les usagers font la queue dans l'ordre de leur
arrive. Mme si la queue est importante, on ne refuse aucun usager.
Une tude statistique a permis de conclure que la dure alatoire des
services suit une loi exponentielle et que les arrives des usagers forment
un processus de Poisson. On suppose que le rgime permanent est
rapidement atteint.
1. Donner la notation de Kendall de cette file d'attente, le temps moyen
pass attendre et le temps moyen pass dans l'organisme par
chaque usager.
2. Quelle est, en moyenne et par heure, la dure pendant laquelle
l'employ du guichet ne s'occupe pas des usagers ?

29

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

3. Quelle est la probabilit d'observer une file d'attente de plus de k

usagers derrire celui en cours de service ?

Extensions de la M/M/1
la M/M/1/N

Cette fois, on limite la capacit de la station (serveur + attente) N clients. Le processus de naissance et
de mort quivalent se transforme en :
l

1
m

2
m

l
N

3
m

On a toujours :
n

P(n) = l . P(0)
m
Cette fois, pour calculer P(0), on utilise :
N

p(i) = 1

i=0

Do :
P(0) =

1-r
1 - r N+1

On peut alors calculer les performances souhaites : Q, W, X.

la M/M/C
La capacit de la station nest plus limite mais il y a C serveurs en parallle. Chacun de ces serveurs a un
taux m (chaque serveur met en moyenne un temps de 1/m pour servir un client).
La nouvelle condition de stabilit est
l < C.m
Cette station se comporte comme le processus de naissance et de mort suivant :
l

1
m

2
2m

3
3m

l
C

4m

Cm

l
C+1

C m

Cm

Etude des performances de deux machines en parallle:

On dispose de deux machines en parallle qui ont un stock d'entre
commun et on envisage de les remplacer par une machine deux fois plus
rapide. Les pices arrivent suivant un processus de Poisson de taux l, et le
temps de service des machines est distribu exponentiellement (taux l
pour la machine unique et l/2 pour les deux machines en parallle).
Comparer les performances de la machine unique celles des deux
machines en parallle.

30

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

4. Modliser par un Rseau de files dattente

(RFA)
Un RFA est un rseau de stations interconnectes. Il peut dcrire un processus comprenant plusieurs
serveurs travers desquels circulent des clients. Par exemple, dans un supermarch, certains clients
passent de la station fromage la station fruits et lgumes pour finir aux caisses. On distingue
plusieurs types de RFA :

RFA Ouvert et RFA Ferm

RFA ouvert : Les clients arrivent de lextrieur, circulent dans le rseau travers diffrentes stations,

puis quittent le rseau. Pour dcrire un tel rseau, il faut prciser :

la description de chaque station (hormis le processus darriv qui cette fois est fix par le rseau luimme),
le processus darrive des clients dans le rseau,
le cheminement des clients dans le rseau (routage).
Exemple :
q
p

1-p
1-q

RFA ferm : Il ny a ni arrive ni dpart de clients. Leur nombre est donc [Link] dcrire un tel

rseau, il faut prciser :

la description de chaque station (hormis le processus darriv qui est fix par le rseau),
le nombre total de clients dans le rseau,
le cheminement des clients dans le rseau (routage).
Exemple :
q

1-p

1-q

RFA mono ou multi classe

Il peut circuler dans un rseaux plusieurs classes de clients. Les clients dune mme classe ont tous un
comportement identique (temps de service et cheminement identique). Pour dcrire un rseau
multiclasse, il faut dcrire
chaque station pour chaque classe de clients,

31

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

le cheminement pour chaque classe de clients,

le processus darrive pour chaque classe de clients (pour les rseaux ouverts) ou,
le nombre total de clients pour chaque classe de clients (pour les rseaux ferms).
Remarques :
Il existe mme des rseaux multiclasses mixtes : ouvert pour certaines classes et fermes pour les autres.
Un client peut changer de classe. (On dfinit alors une chane : lensemble des classes auxquelles peut
appartenir un mme client.)
Exemples de modlisation parun rseau de files d'attente
1. Modlisation d'une station de ski:
On considre une petite station de ski qui contient 3 pistes et 3 tlskis
permettant l'accs ces 3 pistes. Avant d'aller skier, les skieurs doivent
obligatoirement passer l'une des deux caisses pour acheter un forfait qui
les autorisera accder aux pistes. Ils prennent alors le tlski 1 (en faisant
ventuellement la queue dans l'ordre d'arrive) pour se rendre en haut de
la piste 1. Arrivs l haut, ils peuvent descendre la piste 1 et reprendre le
mme tlski (on suppose que le temps moyen pass sur une piste par un
skieur est indpendant du nombre de skieurs sur la piste). Ils ont galement
la possibilit de prendre l'un ou l'autre des tlskis 2 et 3 qui les
emmneront plus haut et leur donneront accs aux pistes 2 et 3,
respectivement. Arrivs en bas des pistes 2 ou 3, ils peuvent reprendre l'un
quelconque des tlskis 2 et 3, ou alors redescendre la piste 1. A la fin de la
journe, ils quittent la station aprs avoir rejoint le bas de la piste 1.
Modliser cette station de ski par un rseau de files d'attente.
2. Modlisation d'un systme de production:
On considre un atelier flexible dans lequel circulent trois types de pices
pl. p2, et p3. Il comporte les quatre postes de travail suivants:
un poste de chargement, C
deux centres d'usinage, CUl et CU2 et
un poste d'inspection, I.
Les pices brutes qui arrivent l'atelier sont fixes sur des palettes et se
dplacent ensuite dans l'atelier en respectant la gamme suivante:
p1 :
Chargement
c
CU1 c
Inspection
p2:
Chargement
c
CU1 c
CU2 c Inspection
p3:
Chargement
c
CU2 c
Inspection (1/5)
Modliser cet atelier par un rseau de files d'attente dans les deux cas
suivants:
1. Les palettes sont en nombre suffisant.
2. On a un seul type de palettes, en nombre limit N. On a toujours des
pices brutes l'entre de l'atelier.

32

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

5. Analyse dun rseau

On considre un RFA ouvert contenant M stations interconnectes de manire quelconque.
1

p01

p12

p24

p13

p40

p34=1

p03

p20

p43

Les clients arrivent de lextrieur du rseau avec un taux l (pas dhypothse sur la distribution darrive
pour le moment). Ils se dirigent vers la file i avec une probabilit p0i
M

p0 i = 1 et p0 i 0.

i=1

Lorsquun client a fini son service dans la file i, il va la station j avec la probabilit pij.
On a : pi1 + pi2 + ... + pi M 1.
Le client quitte le rseau avec la proba :
M

pi 0 = 1 - pi j.
j=1

On dfinit le taux de visite dun client une station i, vi comme le nombre moyen de passages cette
station i au cours du sjour du client dans le rseau. Les vi sont solution (unique) de :
M

vi = p0 i + vj pj i;

i = 1, ... ,M;

j=1

On a aussi besoin de connatre mi , le taux de service de la station i.

Supposons le rseau en rgime permanent. Soit Xi le nombre moyen de clients arrivant (et quittant) la
station i par unit de temps. (un rgime stationnaire nest possible que si Xi < m i ). En considrant tous les
clients qui arrivent la station i, on peut crire un ensemble dquations linaires reliant les quantits
inconnues Xi :
M

Xi = l.p0 i + Xj pj i;

i = 1, ... ,M;

j=1

Remarque : on a Xi = [Link] .
Peu de restrictions ont t faites jusqu prsent mais si lon veut aller plus loin dans ltude du rseau et
trouver les probas stationnaires et les autres performances, il faut faire un certain nombre dhypothses

Hypothses de la forme produit.

Les rseaux vrifiant ces hypothses sont appels rseaux de Jackson.

33

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

1. Le processus darrive des clients extrieurs est un processus de poisson.

2. Le cheminement des clients dans le rseau est Markovien cest dire quil ne dpend que de la dernire
station visite et pas des autres.
3. Chaque station contient ci serveurs de temps de service moyen ti = 1/mi .
les files sont illimites
elles sont gres en PAPS
le temps de service est distribu exponentiellement.
Dans ces conditions, la probabilit stationnaire p(n) est donne par :
M

p(n) = p(n1 , n2 ,

,nM) =

pi(ni)
i=1

o p(ni ) est la proba stationnaire davoir ni clients dans une station M/M/ci en isolation, avec une charge
ri = Xi /mi .
Remarques :
Le nombre de clients dans une station donne ne dpend pas du nombre de clients
dans les stations voisines.
La station i se comporte comme si elle tait alimente par un processus de Poisson de taux Xi.
Les hypothses ne sont que des conditions suffisantes.

Performances
On tudie chaque file en isolation => longueur moyenne Qi, temps de rponse moyen Wi. Puis, pour le
rseau, on a tout simplement :
M

Q=

i=1

Qi

et

W=

Q
l

ou

W=

vi .Wi

i=1

Etude du temps de rponse dans un atelier :

On considre un atelier contenant deux centres d'usinage (CU1 et CU2), un
poste d'inspection (IN) et un poste de rparation (REPAR). Les pices
arrivent dans l'atelier avec un taux moyen l et vont, soit au poste CU1
avec une probabilit p01. soit au poste CU2 avec une probabilit p02. (Au
poste CU1, le temps moyen de service est T1, et au poste CU2, il est de T2).
Les pices quittant CU1 et CU2 sont mises sur un convoyeur (CV) qui les
emmne au poste d'inspection au bout d'un temps T3. Aprs avoir pass un
temps moyen de T4 l'inspection, une proportion p40 des pices quittent
l'atelier et les autres vont au poste de rparation o elles passent un temps
moyen T5 avant de retourner l'inspection.
1. Donner le modle rseau de files d'attente de l'atelier.
2. En supposant qu'il existe un rgime stationnaire, donner le dbit de
chacune des stations du rseau en fonction de l.
On prendra p01 = p02 = 0.5 et p40 = 0.9.
3. Quelles sont les conditions sur l pour qu'il existe un rgime stationnaire
?
4. Donner les hypothses pour avoir un rseau de files d'attente forme
produit. Sous ces hypothses, calculer le temps moyen pass par une
pice dans l'atelier, W, en fonction de l.
On prendra T1 = T2 = 2, T3 = 10, T4 = 1 et T5 = 5.

34

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Diffrence Rseaux de Petri/Rseaux de Files

d'attente
RFA :
existe depuis longtemps. De nombreux logiciels de simulation sont partis dune base de RFA : QNAP
2, Simulog, Arena.
intrt : tude de systmes pas trop complexes mais avec des lois de services ou des processus d'arrive
complexes (mme en analyse).
modle naturel pour les systmes manufacturiers

RDP :
assez rcent peu de logiciels mais en dveloppement : Design CPN, Petri Maker
modlisation rigoureuse, avec une base mathmatique et graphique.
Facile simuler et analyser
intrt : modlise des systmes complexes mais ne tient pas compte des lois particulires (en analyse).

Bibliographie
Processus stochastiques, Alan Ruegg, Mthodes mathmatiques pour lingnieur, Presses polytechniques
romandes 1989, 150p.

Trs pdagogique. On retrouve les principaux rsultats.

Introduction aux files dattente, E. Gelembe, G. Pujolle, Collection techniques et sciences des
tlcommunications, Eyrolles 1982.

Contient les rsultats de base.

Rseaux de files dattente - modlisation et traitement numrique, E. Gelembe, G. Pujolle, J.
Labetoulle, R. Marie, M. Metivier, W. Stewart, Editions hommes et techniques 1980.

Rsultats plus pointus

Queueing Systems, L. Kleinrock, Wiley, New York, Vol 1 : 1975, Vol 2 : 1976.

Trs complet.
Du grafcet aux rseaux de Petri 2me dition, R. David, H. Alla, Trait des nouvelles technologies, srie
Automatique, Herms, 1992, 499p.

Contient les rsultats de base en RdP.

Rsultats et perspectives en automatique, chapitre 4 : Evaluation de performances des systmes de
production, pp171-234, R. David coordonateur, Trait des nouvelles technologies, srie automatique,
1988.

Fait le point sur les diffrentes mthodes dvaluation de performances de systmes squentiels
Les rseaux de Petri pour la conception et la gestion des systmes de production, J.M. Proth, X.
Xie,,Masson 1994.

Utilisation des RdP pour les systmes de production.

35

Modlisation et analyse des systmes de production

PolytechTours dpartement Productique 2me anne

J.P. Chemla

Etapes dune analyse

Systme de production
Modlisation :

Simplification plus ou moins grande du systme physique

(ex : des stocks finis peuvent se modliser en stock infinis)
Hypothses concernant les donnes
(ex : lois de service)
Trs fidle, non exploitable

Modle (RFA, RdP, ...)

Non fidle, trs exploitable

Analyse
Simulation

Mthodes analytiques

reproduction pas pas

de l'volution du modle

quations / rsolution
thorie des processus Markoviens

Simplifications physiques rduites

(on peut pratiquement tout prendre en
compte).
Permet de connatre le transitoire et le
permanent.
Approche la ralit de prs mais pas exact.

Modle exploitable facilement.

Peu de simplification des donnes.
Rapide.
Exact ou approximatif.

Difficile de revenir en arrire pour savoir

comment changer les paramtres pour
amliorer les performances.
Analyse des rsultats complique d'o une
ncessaire simplification des donnes.
Dure longtemps.

Simplifications physiques indispensables

et importantes.
Ne permet la connaissance que du
rgime permanent.

Performances du modle

Analyse des rsultats

Figure 1 : analyse dun systme
de production

36