Télécharger le fichier original (Mémoire de fin d’études)
RÈseaux de Petri stochastiques bien formÈs
Nous prÈsentons dans ce chapitre, le modËle de rÈseau de Petri non sto-chastique (WN1) et le modËle stochastique (SWN). Pour plus de dÈtails sur les SWN, le lecteur pourra se rÈfÈrer aux rÈfÈrences [2, 10]. Notre prÈsentation est basÈe sur la thËse[10].
RÈseaux de Petri bien formÈs (WN)
Les WN ont ÈtÈ introduits dans [4] comme des rÈseaux de Petri colorÈs sur lesquels di Èrentes contraintes sont appliquÈes. Le but de ces contraintes est de permettre une utilisation directe de la structure du rÈseau pour dÈvelopper des algorithmes d’analyse. Les contraintes imposÈes sont de trois types :
les domaines de couleurs sont des produits cartÈsiens de domaines de bases appelÈs classes ou classes de couleurs ÈlÈmentaires ; les fonctions de couleurs sont construites ‡ partir de fonctions ÈlÈmen-taires (identitÈ, di usion et successeur) ; le modËle met en avant les symÈtries du systËme. Les comportements
1 Well formed Net asymÈtriques sont pris en compte par le partitionnement des classes en sous-classes statiques et manipulÈes par l’ajout de garde sur les fonctions de couleur et sur les transitions. Nous rappelons les constituants essentiels des rÈseaux de Petri colorÈs : les jetons possËdent une couleur d’un ensemble donnÈ qui permet de modÈliser les caractÈristiques de di Èrentes entitÈs (couleur) d’un mÍme type (ensemble de ces couleurs) ; les places et les transitions possËdent un domaine de couleur : le domaine de couleurs d’une place est le type de jetons qu’elle peut contenir ; celui d’une transition dÈ nit le type des valeurs employÈes pour son franchis-sement : le choix d’une couleur de ce type donne une instanciation de la transition pour laquelle on teste le franchissement ; les matrices d’incidence : ce sont des fonctions que l’on Èvalue pour tester le franchissement d’une transition, Ètant donnÈe une couleur c. Le rÈsultat est un multi-ensemble de jetons colorÈs des places d’entrÈe (et de sortie). Un multi-ensemble sur un ensemble ni et non vide Y (Bag(Y)) est une application de Y vers N.
lÈments constitutifs d’un WN
Le modËle des rÈseaux bien formÈs est construit de maniËre structurÈe. Les di Èrents objets composant le systËme sont regroupÈs en classes ÈlÈmentaires. Ces classes d’objets peuvent Ítre ordonnÈes et sont vues comme des ensembles contenant des ÈlÈments de mÍme type. Des associations de ces classes d’objets sont faites pour former des domaines de couleurs. Domaine de couleur, classes de base et sous-classes statiques DÈ nitions 2.1.1 Un domaine de couleur est un produit cartÈsien ni de classes ÈlÈmentaires. Chaque classe de couleurs ÈlÈmentaire est un ensemble ni, non vide, de couleurs terminales dont la dÈ nition ne dÈpend d’aucune autre couleur. L’ensemble des classes ÈlÈmentaires est notÈ Cl = fC1; ¢ ¢ ¢ Ckg o˘ Ci \Cj = ;, 8i; j 2 [1::k]. Un domaine de couleur est notÈ de faÁon gÈnÈrale par C = hC1e1 £::: £Ckek i o˘ ei dÈsigne le nombre de fois (un entier positif ou nul) qu’apparaÓt la classe Ci dans C. Lorsque tous les ei sont nuls, le domaine de couleur est le domaine neutre, que l’on note †. Une classe ÈlÈmentaire peut Ítre partitionnÈe en sous-classes statiques Di;q a n de regrouper au sein d’une mÍme classe des ÈlÈments de mÍme type mais de comportement di Èrent. Si Ci comporte k sous-classes statiques, on a alors Ci = [ Di;q. q=1:::k La structuration permet de traduire au niveau du modËle la symÈtrie dans le comportement des entitÈs modÈlisÈes. Il a ÈtÈ dÈmontrÈ que ces symÈtries pouvaient Ítre maintenues durant la phase d’analyse du modËle : le graphe symbolique d’accessibilitÈ (que nous allons voir plus loin) peut Ítre calculÈ ; chaque noeud (marquage symbolique) correspond ‡ un ensemble de mar-quages ayant un comportement similaire vis ‡ vis des symÈtries de couleurs dans chaque classe de base. Le besoin d’Ètendre le formalisme des WN en Èvaluation de performance a conduit ‡ la dÈ nition des SWN [5]. L’intÈrÍt principal de ce modËle est la possibilitÈ d’avoir une rÈduction due aux symÈtries de la chaÓne de Markov dÈrivÈe du rÈseau de Petri stochastique colorÈ.
Les fonctions de couleur
Les fonctions de couleur dÈ nissent le comportement des objets lors d’un franchissement des transitions. Dans les systËmes rÈels, les di Èrents types d’actions pouvant Ítre accomplies conduisent ‡ des choix, choix d’un proces-seur sur lequel doit s’exÈcuter une t‚che, di usion d’un message broadcast ‡ tous les sites ou dans un rÈseau en anneau ou les sites sont ordonnÈs, le site choisi pour recevoir le message est celui qui suit immÈdiatement le site courant. Pour prendre en compte de tels phÈnomËnes, il su t de dÈ nir dans le modËle un nombre restreint de fonctions de couleurs. Les arcs d’un rÈseau W N sont valuÈs par ces fonctions de couleur qui sont des sommes pondÈrÈes de tuples de fonctions de couleurs ÈlÈmentaires. Les W N sont construits sur trois fonctions de base [2] : la fonction identitÈ (XCi ) permet de sÈlectionner une instance de Ci la fonction de di usion (AllCi ) permet de considÈrer tous les ÈlÈments de Ci, elle est utilisÈe pour les opÈrations de di usion. la fonction successeur (!XCi ) permet de sÈlectionner le successeur d’une instance de Ci ; elle est utilisÈe pour prendre en compte les techniques de numÈrotation.
Table des matières
Introduction
1 Réseaux de Petri Stochastiques
1.1 Réseaux de Petri
1.2 Réseaux de Petri Stochastiques
1.2.1 Propriétés d’un réseau de petri (stochastique)
1.2.2 Indices de performance
1.3 Réseaux de Petri Stochastiques Généralisés
2 Réseaux de Petri stochastiques bien formés
2.1 Réseaux de Petri bien formés (WN)
2.1.1 Éléments constitutifs d’un WN
2.1.2 Dénition formelle des réseaux bien formés
2.1.3 Les réseaux réguliers et les réseaux ordonnés
2.1.4 Le graphe symbolique d’accessibilité
2.2 Réseaux de Petri stochastiques bien formés (SWN)
2.2.1 Sémantique stochastique d’un réseau de Petri bien form
2.2.2 Dénition des réseaux de Petri stochastiques bien form
2.2.3 Indices de performance
3 PERFSWN Graphique
3.1 PERFSWN : présentation générale
3.1.1 GreatSPN
3.1.2 Scilab
3.1.3 Environnement utilisateur
3.1.4 Algorithme de travail
3.1.5 Structure générale
3.2 L’Interface Graphique
3.2.1 Génération de scripts Scilab
3.2.2 Intégration de Scilab
3.2.3 Algorithme de travail
Conclusion
