Reseaux De Petri

VADE-MECUM

DE

L'ÉTUDIANT EN RÉSEAUX DE PETRI

par Stéphane MARIEL

Avant Propos

Les réseaux de Petri, quoique peu à la mode, ne sont pas

préhistoriques, on les doit aux travaux du mathématicien

allemand Carl Adam Petri dans les années 60.

Ils ont surtout été étudiés en Europe et au MIT et sont à

l'origine du GRAFCET utilisé dans l'industrie française et

maintenant européenne.

Ils devraient aussi faire leur apparition dans la prochaine

version de la norme UML (2) et sont aussi parfois utilisés dans

l'industrie du jeu vidéo.

I.NOTATIONS ET RÈGLES DE FRANCHISSEMENT

1.Places, transitions et arcs

Un réseau de Petri est :

• un graphe,

• formé de deux types de noeuds appelés places et

transitions reliés par des arcs orientés,

• et biparti, c'est-à-dire qu'un arc relie alternativement une

place à une transition et une transition à une place.

Lorsqu'une place est reliée à une transition par un arc : Pitj,

on parle de place en entrée de tj.

Lorsqu'une transition est reliée à une place par un arc tjPi,

on parle de place en sortie de tj.

Une transition sans place en entrée est une transition source,

une transition sans place en sortie est une transition puits.

Source Puits

2.Marquages

Chaque place d'un réseau de Petri peut

contenir une ou plusieurs marques (on

parle aussi de jetons). La configuration

complète du réseau, avec toutes les

marques positionnées, forme le

marquage et définit l'état du réseau (et

donc l'état du système modélisé).

Dans la suite on traitera principalement des réseaux marqués,

et de l'évolution des marquages.

3.Franchissement de transitions

Pour rendre compte de

l'évolution du système

modélisé, les réseaux de Petri

intègrent un formalisme

permettant de passer d'un

marquage à un autre : c'est le

franchissement des transitions.

Une transition est

franchissable si chacune des

places en entrée comporte au

moins un jeton.

Pour les transitions

franchissables, on définit le

franchissement effectif selon

les règles suivantes :

• le franchissement est une

opération indivisible (atomique),

• un jeton est consommé dans chaque place en entrée,

• un jeton est produit dans chaque place en sortie.

4.Réseaux particuliers

Le graphe associé à un réseau de Petri peut être très

complexe. Un certain nombre de situations présente un intérêt

particulier :

1. les graphes d'états

Dans ce cas chaque transition ne dispose que d'une place en

entrée et une place en sortie.

2. les réseaux sans conflits

Dans lesquels chaque place n'a qu'une transition en sortie.

3.

...