Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

AVERTISSEMENT Ce document est le fruit d'un long travail approuvé par le jury d

AVERTISSEMENT Ce document est le fruit d'un long travail approuvé par le jury de soutenance et mis à disposition de l'ensemble de la communauté universitaire élargie. Il est soumis à la propriété intellectuelle de l'auteur. Ceci implique une obligation de citation et de référencement lors de l’utilisation de ce document. D'autre part, toute contrefaçon, plagiat, reproduction illicite encourt une poursuite pénale. Contact : ddoc-theses-contact@univ-lorraine.fr LIENS Code de la Propriété Intellectuelle. articles L 122. 4 Code de la Propriété Intellectuelle. articles L 335.2- L 335.10 http://www.cfcopies.com/V2/leg/leg_droi.php http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm b\'v ù $ E/Pt t q s /+ N" d'ordre THESE présentée à L'UNIVERSITE DE METZ, FACULTE DES SCIENCES UFR MATHEMATIQUES, INFORMATIQUE, MECANIQUE pour obtenir le titre de DOCTEUR Spécialité SCIENCES DE L'INGENIEUR (mention : AUTOMATIQUE) p[u Feng CHU sujet de la thèse CONCEPTION DBS SYSTBMBS DE PRODUCTION A L'AIDB DES RBSEAUX DE PETRI : VERIFICATION INCREMENTALB DBS PROPRIBTES QUALITATIVBS Soutenance prévue le l0 Avril 1995 devant le Jury composé de : M. Pierre LADET M. Oérard MOREL M. Jean-Claude GENTINA BIBLIOTHEOUE UNIVERSITAIRE DE METZ ' | iltil iltil ilil til ]il til tlil til tilt til til til o22 420553 1 Rapporteurs .s/ry ssl+ Examinateurs TABLE DES MATIBRES CHAPITRE I. . INTRODUCTION GENERALE 1.1 Motivations.. .........2 1.2 Hypothèsedetravail...... ..........4 1.3 Plandelathèse ........6 CHAPITRE II. . ETAT DE L'ART 2.1 Introduction ........ ..........9 2.2 Déftnltions de base.. .. .. .. . . 9 2.2.1 DéfrnitiondesréseauxdePetri ...........9 2.2-Z Règles de franchissement ... . ...1 I 2.2.3 Matriced'incidenceetéquationfondamentale..... .........13 2.3 Propriétés qualitatives et propriétés comportementales .. ...14 2.3.1 hopriétés comportementales...... .....15 2.3.I.1 Aneignabilité. ...........15 2.3.I.2 Bornitude. .......15 2.3.1.3 Vivacité et sans blocage.... .............16 2.3.I.4 Réversibilité et états d'accueil . . . -. . .. . 18 2.3.1.5 Persistance.... ....19 2.3.2 Propriétésqualitatives ..........19 2.3.2.1 Vivacité stmcturelle .....20 2.3.2.2 Répétitivité et consistance .. . . ...... ...20 2-3-2-3 Bornitude structurelle et conservation........ .......--..21 2.4 Méthodes d'analyse...... ........23 2.4.1 Méthodesfaisantintervenirl'algèbrelinéaire. ....-..24 2.4.2 Arbre des marquages atteignables et arbre de recouvrement. . . . . .... ...26 2.4.3 Techniques deréduction..... .....29 2.4.4 Méthodes utilisant les verrous et les trappes..... ....32 2.5 Sous-classes de réseaux de Petri ..........34 2.5. I Graphes d'événements . ...34 2.5.2 Machinesàétats .....35 2.5.3 Réseaux de Petri à choix libre . . . ... ....36 2.5.4 Réseaux de Petri à choix asymétrique . . ... .. . .. . . .. .37 2.5.5 Réseaux de Petri acycliques .. . ...37 2.5.6 Réseaux de Petri purs .. .. ... ....38 2.6 Conclusion.. ....40 CHAPITRE III. . VERIFICATION INCR,EMENTALE DE LA CONSISTANCE ET DE LA CONSERVATION 3.1 Introduction ....42 3.2 Une méthode de vérification de la consistance........... .................43 3.2. I Forme standard dérivée d'une matrice et base des t-invariants . . . . . .. . .43 3.2.2 Une méthode de vérification de la consisrance ......46 3.3 Ajout et fusion de places ....... . .. .51 3.3.1 Ajoutdeplaces ....... .....51 3.3. I . 1 Cas où le rang de la matrice d'incidence resre inchangé . .. ....51 3 .3 .l .2 Cas où le rang de la matrice d'incidence au_qmenre . . . . . .5 3 3.3.2 Fusion de places .......55 3.4 Ajout et fusion de transitions .... .. .....58 3.4.1 Cas où le réseau existant est consisranr.... .....58 3.4.1.1 Cas où le rang de la matrice d'incidence resre inchangé . . . . . . .58 3.4.I .2 Cas où le rang de la matrice d'incidence augmente . . . . .61 3.4.2 Cas où le réseau existant n'est pas consisranr . . . . .. .68 3.4.3 Fusion de nansitions ......71 3.5 Ajout d'un sous-réseau de Petri . . . . . . .. .75 3.5.1 Cas où le rang de la matriced'incidence resre inchangé. .........76 3.5.2 Cas où le rang de la matrice d'incidence augmenre .. .. ... .78 3.6 Synthèse des résultats .......80 3.7 Conclusion.. ........81 CHAPITRE IV. . VERIFICATION INCREMENTALE DE LA BORNITUDE STRUCTURELLE ET DE LA REPETITIVITE 4.1 Introduction. . . . ... .. .83 4.2 Ajout de places etlou de transitions . . ... .84 4.2.1 Réseaux de Petri structurellement bornés ....84 4.2.2 Réseaux de Petri absolument bornés ........88 4.3 Fusion de transitions et de places . . . . . .91 4.3.1 Fusiondetransitions ......91 4.3.2 Fusion de places .........93 4.4 Intégration par des places et recherche du composant structurellement borné maximal. ........ .. .97 4.4. 1 Intégration de deux sous-réseaux en ajoutant des places. . .. .....98 4.4.2 Recherche du composant structurellement bomé maximal. .... 100 ........ .... .........101 4.6 Conclusion. ..............102 CHAPITRE V. . VERIFICATION INCREMENTALE DE L'ABSENCE DE BLOCAGE 5.1 Introduction. ......104 5.2 Ajoutoe transitio;;.................... .... 106 5.3 Ajout de places ... . . ll2 5.3.1 Détermination des verrous minimaux du réseau............................... ll9 5.3.2 Détermination de la base des verrous ......I21 5.4 Calcul de la rappe maximale contenue dans un velrou .. 124 5.5 Absence de blocage.... ...126 5.5. 1 Vérification de l'absence de blocage pour un réseau de Petri ordinaire... .. 126 5.5.2 Recherche de marquages initiaux pour I'absence de blocage .... .. . . . 131 5.6 Vivacité de sous-classes de réseaux de Petri. . . .. . . 136 5.6. I Vivacité des réseaux à choix asymétrique...... . .. . 136 5.6.2 Vivacité et réversibilité des graphes d'événements augmentés de places de ressources partagées ..... 139 5.7 Modèles des gammes de fabrication . .. 150 5.7.1 Lignedefabrication. ........151 5.7 .2 Ligne d'assemblage/désassemblage . ...... 151 5 .7 .3 Ligne avec conflit .. ...... 152 5.8 Synthèse des résultats .... 155 5.9 Conclusion.. ......156 CHAPITRE VI. . CONCLUSION GENERALE 6.1 Synthèsedu travail...... ........158 6.2 Dircctionsderecherche. .........159 Bibliographie ..162 CHAPITRE I II\TRODUCTIOI\ GENERALE 1.1 MOTIVATIONS Dans un monde où la concurrence s'intensifie, I'augmentation de productivité devient un facteur crucial pour la survie des entreprises. En outre, I'évolution des technologies est de plus en plus rapide. Ces deux tendances exigent qu'un système de production puisse fabriquer une large variété de produits en petites séries. [æs systèmes automatisés et flexibles connus sous le nom d'ateliers flexibles permettent justement d'atteindre cet objectif grâce à I'intégration de moyens multi-tâches et à I'automatisation des activités. Un atelier flexible est typiquement un système à événements discrets dont les principales caractéristiques sont les suivantes [DES et al. 94] Parallélisme : Dans un système de production flexible, plusieurs opérations peuvent être exécutées simultanément; Asynchronisme : Différentes opérations nécessitent des temps d'exécution différents; Evolution d'événements : La fin d'une opération peut conduire à l'initiation de plusieurs nouvelles opérations. L'ordre de ces opérations n'est pas nécessairement unique; Conflit : ll est possible que plusieurs processus demandent une ressource commune en même temps. Un atelier flexible, qui autorise I'utilisation adéquate des moyens n-rulti-tâches et de multi- ressources, permet effectivement d'augmenter la productivité. En revanche, une mauvaise conception peut engendrer des situations de blocage, c'est-à-dire des situations où aucune opération ne peut plus être exécutée. Par ailleurs, l'initiation simultanée de plusieurs opérations qui demandent une même ressource fait aussi apparaître des situations de conflit. Une riésolution inadfouate des phénomènes de conflit non seulement ralentit la production, mais peur aussi conduire à des situations de blocaee. Pour éviter ces types de phénomènes, il faut que le système soit correctement conçu et qu'iI soit bien contrôlé. La complexité des systèmes de production flexible rend indispensable le développement d'un outil qui fournit une aide à la conception et à I'analyse, à l'évaluation et au contrôle de ces systèmes. Ceci est precisément I'objectif ultime de notre étude. Pour atteindre cet objectif, il faut un support puissant qui permette de modéliser correctement les systèmes étudiés. Les réseaux de Petri (que I'on désigne parfois par RdP pour raison de simplification) sont réputés pour leur capacité de répondre à cette demande. De nombreux travaux sont consacrés à l'évaluation et au contrôle des systèmes modélisés par des réseaux de Petri. Dans notre étude, nous nous concentrons sur I'aspect d'aide à la conception en exploitant la capacité d'analyse des réseaux de Petri. Un réseau de Petri est un outil à la fois mathématique et graphique. Comme outil mathématique, il permet d'analyser les propriétés du système de production et de caractériser les activités du système par un ensemble d'équations d'état. En tant qu'outil graphique, c'est un graphe biparti constitué de places et de transitions (représentées respectivement par des cercles et par des barres) reliées par des arcs. Les places peuvent représenter les stocks tampons et certaines places, dites places de ressources, contiennent des jetons qui représentent des ressources éventuellement partagées entre plusieurs tâches. Les transitions peuvent représenter les opérations. La structure du réseau permet de modéliser également le parallélisme, la synchronisation, la concurrence et le conflit. Les places sont associées à une certaine distribution de jetons qui constitue le marquage du réseau. Les jetons permettent de modéliser la dynamique du système. Le nombre de jetons dans une place indique Ia quantité de matièrcs premières ou de produits semi-finis dans le stock tampon représenté par la place, ou le nombre de ressources partagées disponibles. Un marquage définit donc un état possible du système. Depuis que Dr. Carl A. Petri a introduit la théorie des réseaux de Petri, ceux-ci n'ont cessé uploads/Ingenierie_Lourd/ chu-feng-smz9507.pdf