pastravanu aplicatii retele petri

8/6/2019 Pastravanu Aplicatii Retele Petri

1/256

OCTAVIAN PSTRVANU

MIHAELA MATCOVSCHI CRISTIAN MAHULEA

APLICAII ALE REELELOR PETRIN STUDIEREA

SISTEMELOR CU EVENIMENTE DISCRETE

Editura Gh. ASACHI

2002


2/256


3/256

OCTAVIAN PSTRVANU

MIHAELA MATCOVSCHI CRISTIAN MAHULEA

APLICAII ALE REELELOR PETRIN STUDIEREASISTEMELOR CU EVENIMENTE DISCRETE

Editura Gh. ASACHI

2002


4/256

Editura GH. ASACHI

Universitatea Tehnic IaiBd. D. Mangeron nr. 67

6600, Iai, RomaniaTel: 0232 23.13.43

Fax: 0232 21.42.90

Director editur:Prof. univ. dr. ing. Mihail VOICU

Redactor:

Prof. Georgeta ANICULESEI

Refereni tiinifici:Prof. univ. dr. ing. Mihail Voicu

Prof. univ. dr. ing. Doru Pnescu

Colecia: Automatici informatic industrial

Octavian PSTRVANU, Mihaela MATCOVSCHI, Cristian MAHULEAUniversitatea Tehnic Gh. Asachi IaiFacultatea de Automatici CalculatoareBd. D. Mangeron 53A, 6600 Iaiemail: [email protected]

Descrierea CIP a Bibliotecii Naionale a RomnieiPSTRVANU, OCTAVIAN

Aplicaii ale reelelor Petri n studierea sistemelor cuevenimente discrete / Octavian Pstrvanu, Mihaela Matcovschi,Cristian Mahulea Iai: Editura Gheorghe Asachi, 2002.

p.: cm. 16,5 x 22,5

ISBN: 973-8292-86-7

I. Matcovschi, Mihaela

II. Mahulea, Cristian

517.938

681.5


5/256


6/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahuleaiigeneroase. Modul de organizare al lucrrii nu oblig la parcurgerea integral a textului,permind o lectur selectiv , orientat n conformitate cu nivelul de pregtire i problematica de interes a fiecrui cititor n parte, ghidarea realizndu-se cu multuurin pe seama cuprinsului anume elaborat cu un grad relevant de detaliere. Pe lngacest cuprins, o imagine general despre modul de integrare a capitolelor crii neconomia de ansamblu rezult din parcurgerea Capitolului 1.

n particular, lucrarea de fa (n totalitate, ori anumite poriuni ale ei) poateservi i drept suport pentru cursuri destinate studenilor sau pentru cursuri de

perfecionare destinate absolvenilor, stilul de prezentare bazndu-se pe principiileinstruirii graduale, cu acordarea unei ponderi importante exemplelor, studiilor practiceiutilizrii facilitilor software.

Pentru a reproduce soluiile asistate de calculator din lucrare, sau pentru adezvolta noi aplicaii sub Petri Net Toolbox, cititorii se pot adresa autorilor crii sprea intra n posesia unei versiuni de testare a acestui pachet, n regim gratuit.

Rod al unei colaborri de lung durat dintre trei cadre didactice de la Catedrade automatici informatic industrial a Universitii Tehnice "Gh. Asachi" din Iai,

prezenta lucrare pune n valoare att viziunea proprie a autorilor, creat n urmaconsultrii unui vast material bibliografic, ct i experiena dobndit de acetia nutilizarea reelelor Petri pentru modelarea, analiza i proiectarea sistemelor cuevenimente discrete. Cartea reflect totodat i preocuprile educaionale ale celor trei

autori care au preg

tit cursuri

i

edin

e de aplica

ii dedicate disciplinei Sisteme dinamicecu evenimente discrete existent din anul 1996 n planurile de nvmnt ale Facultiide Automatici Calculatoare din Iai.

n ncheiere, autorii doresc s i exprime gratitudinea fa de cei doi refereni, alecror personaliti academice marcante au girat apariia acestei cri, precumi fa decolectivul Editurii "Gh. Asachi" care a inclus volumul n planul su editorial.

Publicarea crii s-a bucurat de suportul financiar al Consiliului Naional pentru Finaarea nvamntului Superior, prin intermediul proiectului LICAP("Laborator de instruire n domeniul conducerii asistate de calculator a proceselor").

Mulumiri anticipate sunt adresate tuturor cititorilor, care, prin observaiile ce le

vor formula n urma consultrii acestei cri, vor contribui la ndeprtarea unor posibileneajunsuri ale textuluii la mbuntirea calitii.

Noiembrie 2002


7/256

Cuprins

Prefaa.............................................................................................................................. i

Cuprins........................................................................................................................... iiiAbstract and Contents................................................................................................... vii

Simboluri i notaii......................................................................................................... xi

Cap. 1.Introducere ..........................................................................................................1

Cap. 2. Modele de tip reea Petri netemporizat.............................................................7

Breviar teoretic ........................................................................................................................... 7

BT2.1. Conceptul de reea Petri netemporizat ..................................................................... 7

BT2.2. Terminologie uzual.................................................................................................. 8

BT2.3. Validarea i executarea tranziiilor n reele cucapacitate infinit evoluia strilor............................................................................... 9

BT2.4. Unele extensii pentru reele Petri netemporizate..................................................... 10

BT2.4.1. Reele Petri cu capacitate finit ....................................................................... 10

BT2.4.2. Reele cu probabiliti i prioriti ................................................................... 10

BT2.4.3. Reele cu arce inhibitoare ................................................................................ 11

BT2.5. Modelarea cu reele Petri ordinare .......................................................................... 11

BT2.5.1. Structuri tipice utilizate n modelare................................................................ 11

BT2.5.2. Capacitatea de modelare a unor subclase de reele Petri ordinare................... 12

Aplicaii (AP2.1 AP2.5)........................................................................................................ 14

Cap. 3. Studierea proprietilor comportamentale........................................................27

Breviar teoretic ......................................................................................................................... 27

BT3.1. Definirea proprietilor comportamentale ............................................................... 27

BT3.1.1. Accesibilitate ................................................................................................... 27

BT3.1.2. Mrginire ......................................................................................................... 27

BT3.1.3. Viabilitate ........................................................................................................ 28

BT3.1.4. Reversibilitate .................................................................................................. 28

BT3.2. Producerea fenomenului de deadlock n sistemele cu resurse partajate.................. 28

BT3.3.Arbori i grafuri de acoperire/accesibilitate ............................................................. 29

BT3.3.1. Arbori de acoperire/accesibilitate .................................................................... 29BT3.3.2. Grafuri de acoperire/accesibilitate ................................................................... 30


8/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. MahuleaivBT3.4. Ecuaia de stare........................................................................................................ 30

BT3.5. Proprieti ce decurg din apartenena reelelor la anumite subclase

de reele Petri ordinare .................................................................................................. 32

BT3.5.1. Criterii de viabilitate i siguran a mainilor de stare .................................... 33

BT3.5.2. Criterii de viabilitate i siguran a grafurilor marcate.................................... 33

Aplicaii (AP3.1 AP3.6)........................................................................................................ 34

Cap. 4. Controlul procedural al sistemelor cu evenimente discrete..............................49


BT4.1. Specificaii de proiectare pentru structurile de conducere ...................................... 49

BT4.2. Proiectarea structurilor de conducere prin tehnici de sintez hibrid...................... 50

BT4.2.1. Rafinarea operaiilor prin sintez descendent ................................................ 50

BT4.2.1.1. Prezentarea general a procedurii de rafinare .......................................... 50

BT4.2.1.2. Module standard utilizate n rafinare ....................................................... 52

BT4.2.2. Ataarea resurselor prin sintez ascendent .................................................... 55

BT4.2.2.1. Prezentarea general a procedurii de ataare a resurselor........................ 55

BT4.2.2.2. Detalierea Pasului 1 (ataarea resurselor specifice nepartajate) .............. 55

BT4.2.2.3. Detalierea Pasului 2 (ataarea resurselor de stocare)............................... 56

BT4.2.2.4. Detalierea Pasului 3 (ataarea resurselor specifice partajate) .................. 58

BT4.3. Proprieti caracteristice ale structurilor de conducere rezultate din sintez .......... 65

BT4.4. Funciuni de bazi consideraii de proiectare ale controlerului procedural .......... 66

BT4.4.1. Funciuni de baz ............................................................................................. 66

BT4.4.2. Consideraii de proiectare ................................................................................ 66

Aplicaii (AP4.1 AP4.3) ....................................................................................................... 67

Cap. 5. Studierea proprietilor structurale ..................................................................85


BT5.1. Definirea proprietilor structurale i criterii de caracterizare ................................ 85

BT5.1.1. Mrginire structural ....................................................................................... 85

BT5.1.2. Conservativitate ............................................................................................... 86

BT5.1.3. Repetitivitate.................................................................................................... 86

BT5.1.4. Consisten....................................................................................................... 87

BT5.1.5. Relaii ntre proprietile structurale ................................................................ 87

BT5.2. Invariani ................................................................................................................. 88

BT5.2.1. Definiia invarianilor ...................................................................................... 88

BT5.2.2. Invariani n reele duale i/sau inversate......................................................... 89

BT5.2.3. Criterii de caracterizare a invarianilori conexiuni cu

proprietile structurale ............................................................................................ 90

Aplicaii (AP5.1 AP5.4)........................................................................................................ 91

Cap. 6. Modelede tip reea Petri cu temporizare determinist...................................103

Breviar teoretic ....................................................................................................................... 103

BT6.1. Reele cu tranziii temporizate............................................................................... 103

BT6.2. Reele cu poziii temporizate ................................................................................. 104


9/256

Cuprins v

BT6.3. Transformarea unei reele temporizate Tntr-o reea temporizatP..................... 105

BT6.4. Transformarea unei reele temporizatePntr-o reea temporizatT..................... 106

BT6.5. Comportarea periodic a reelelor Petri acoperite de invarianiP,

(parial) consistente, temporizate T............................................................................. 107

BT6.6. Comportarea periodic a reelelor Petri acoperite de invarianiP,

(parial) consistente, temporizateP............................................................................. 109

Aplicaii (AP6.1 AP6.8) ..................................................................................................... 110

Cap. 7. Modele de tip reea Petri cu temporizare stohastic......................................129


BT7.1. Principiile temporizrii stohastice ......................................................................... 129

BT7.2. Variabile aleatoare - scurt trecere n revist ........................................................ 130

BT7.2.1. Variabile aleatoare ......................................................................................... 130

BT7.2.2. Funcie de repartiie. Densitate de repartiie.................................................. 130

BT7.2.3. Funcii de variabile aleatoare......................................................................... 132

BT7.2.4. Caracteristici ale distribuiilor de probabilitate ............................................. 132

BT7.2.4.1. Valoare medie ........................................................................................ 132

BT7.2.4.2. Dispersie (varian) ................................................................................ 133

BT7.2.4.3. Moment de ordin p ................................................................................. 134

BT7.2.4.4. Covarian ............................................................................................. 134

BT7.2.5. Legea numerelor mari. Legi limit ................................................................ 135

BT7.2.6. Distribuii frecvent folosite n temporizarea stohastic ................................. 137

BT7.3. Procese stohastice.................................................................................................. 137

BT7.4. Modele de tip reea Petri cu temporizare stohastic .............................................. 138

Aplicaii (AP7.1 AP7.5) ..................................................................................................... 138

Cap. 8. Modele de tip reea Petri stohastic................................................................153


BT8.1. Reele Petri stohastice............................................................................................ 153

BT8.2. Proprieti ale legii de distribuie exponenial ..................................................... 154

BT8.3. Lanuri Markov omogene, continue n timp.......................................................... 155

BT8.3.1. Concepte de baz ........................................................................................... 155

BT8.3.2. Analiza tranziiilor de stare a unui lan Markov continuu i omogen............ 157

BT8.4. Proprieti ale reelelor Petri stohastice................................................................. 157

BT8.4.1. Construcia lanului Markov asociat unei reele Petri stohastice................... 157

BT8.4.2. Evaluarea performanelor unei reele Petri stohastice ................................... 158

BT8.4.3. Proprieti de conservare ............................................................................... 159

BT8.5. Reele Petri stohastice generalizate ....................................................................... 160

Aplicaii (AP8.1 AP8.4) ..................................................................................................... 161

Cap. 9. Modelede tip max-plus ...................................................................................175


BT9.1. Proprieti fundamentale ale algebrei (max, +) ..................................................... 175BT9.2 Operaii cu matrice i vectori definii pe algebra ( { },max, ) + ................... 176


10/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. MahuleaviBT9.3 Reprezentri de stare n algebra max-plus pentru reele Petri de tip graf marcat,

temporizateP.............................................................................................................. 178

BT9.4. Rezolvarea ecuaiei de stare .................................................................................. 181

BT9.5. Rezolvarea ecuaiei de ieire ................................................................................. 185

Aplicaii (AP9.1 AP9.4)...................................................................................................... 186

Cap. 10.Petri Net Toolbox descriere i utilizare /

Learning about Petri Net Toolbox ......................................................................201

Introduction Petri Net Toolbox at a First Glance................................................................ 201

Part I. Describing the Graphical User Interface (GUI) .......................................................... 204

I.1. Overview ..................................................................................................................... 204

I.2. Menu Bar..................................................................................................................... 204

I.3. Quick Access Toolbar ................................................................................................. 208

I.4. Drawing Area .............................................................................................................. 208

I.5. Drawing Panel ............................................................................................................. 208

I.6. Draw/Explore Switch .................................................................................................. 208

I.7. Simulation Panel ......................................................................................................... 209

I.8. Status Panel ................................................................................................................. 209

I.9. Message Box ............................................................................................................... 209

Part II. Exploiting the Toolbox .............................................................................................. 210

II.1. Building a Model ....................................................................................................... 210

II.2. Exploring Properties .................................................................................................. 216

II.3. Running a Simulation ................................................................................................ 217

II.4. Analyzing Simulation Results ................................................................................... 221

II.5. Max-Plus Models....................................................................................................... 222

II.6. Design ........................................................................................................................ 223

Appendix 1: XML file-format of a file containing a PN model............................................. 225

Appendix 2: Configuration File for the Petri Net Toolbox.................................................... 229

Bibliografie ..................................................................................................................231

Index i dicionar romn-englez ................................................................................. 235


11/256

APPLICATIONS OF PETRI NETS

IN STUDYING DISCRETE EVENT SYSTEMS

Abstract andContents

The book constructs a theoretical and practical framework, based on Petri net models, for

exploring event-driven dynamics. This framework encompasses both untimed and timed Petri

nets, the usage of the key concepts and results being illustrated by problems with analytical or

computer-aided solutions. For computational approaches, the software environment Petri Net

Toolbox, developed by the authors to ensure full compatibility with MATLAB, has been

used. The last chapter creates an overview of the capabilities and exploitation of this software.

The book is self-contained, but the bibliographic list suggests numerous works recommended

for getting a deeper insight into this field. The book was designed to answer the instructional

needs for a large area of potential beneficiaries, namely people interested in a gradual and

methodological training in discrete-event systems, which obviously includes undergraduate,

postgraduate and doctoral students, as well as research workers and practitioners.

Preface ............................................................................................................................. i

Contents (in Romanian) ................................................................................................. iii

Abstract and Contents (in English)............................................................................... vii

Symbols and Notations................................................................................................... xi

Chapter 1.Introduction ................................................................................................... 1

Chapter 2. Untimed Petri Net Models..............................................................................7

Theory ........................................................................................................................................ 7

BT2.1. The concept of untimed Petri net .............................................................................. 7

BT2.2. Terminology and basic concepts ............................................................................... 8

BT2.3. Transition enabling and firing in infinite-capacity Petri nets State evolution........ 9

BT2.4. Extensions of untimed Petri nets............................................................................. 10

BT2.4.1. Finite-capacity Petri nets ................................................................................. 10

BT2.4.2. Nets with probabilities and priorities............................................................... 10

BT2.4.3. Nets with inhibitor arcs.................................................................................... 11

BT2.5. Modeling with ordinary Petri nets ........................................................................... 11

BT2.5.1. Typical structures used in modeling with Petri nets........................................ 11

BT2.5.2. Some subclasses of ordinary Petri nets and their modeling power ................. 12

Applications (AP2.1 AP2.5) ................................................................................................. 14


12/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. MahuleaviiiChapter 3.Analysis Techniques for Behavioral Properties...........................................27

Theory ...................................................................................................................................... 27

BT3.1. Definitions of the behavioral properties.................................................................. 27

BT3.1.1. Reachability ..................................................................................................... 27

BT3.1.2. Boundedness .................................................................................................... 27

BT3.1.3. Liveness ........................................................................................................... 28

BT3.1.4. Reversibility..................................................................................................... 28

BT3.2. Deadlock in systems with shared resources ............................................................ 28

BT3.3. Coverability/accessibility trees and graphs ............................................................. 29

BT3.3.1. Coverability/accessibility trees........................................................................ 29

BT3.3.2. Coverability/accessibility graphs..................................................................... 30

BT3.4. State equation .......................................................................................................... 30

BT3.5. Behavioral properties induced by membership in some subclasses

of ordinary Petri nets ..................................................................................................... 32

BT3.5.1. Criteria for liveness and safeness of state machines........................................ 33

BT3.5.2. Criteria for liveness and safeness of marked graphs ....................................... 33


Chapter 4.Procedural Control of Discrete Event Systems............................................49

Theory ...................................................................................................................................... 49

BT4.1. Design specifications for the control structure........................................................ 49

BT4.2. Hybrid synthesis techniques.................................................................................... 50

BT4.2.1. Refinement of the operation places by topdown synthesis............................ 50

BT4.2.1.1. Overview of the procedure....................................................................... 50

BT4.2.1.2. Standard modules used in the refinement ................................................ 52

BT4.2.2. Addition of the resource places by bottom-up synthesis ................................. 55

BT4.2.2.1. Overview of the procedure....................................................................... 55

BT4.2.2.2. Detailing Step 1 (addition of the nonshared resource places).................. 55

BT4.2.2.3. Detailing Step 2 (addition of the buffer places)....................................... 56

BT4.2.2.4. Detailing Step 3 (addition of the shared resource places)........................ 58

BT4.3. Characteristic properties of the control structures resulted from synthesis............. 65

BT4.4. Basic actions and design issues of the proceduralcontroller .................................. 66

BT4.4.1. Basic actions .................................................................................................... 66

BT4.4.2. Design issues ................................................................................................... 66

Applications (AP4.1 AP4.3) ................................................................................................ 67

Chapter 5.Analysis Techniques for Structural Properties ............................................85

Theory ...................................................................................................................................... 85

BT5.1. Definitions of the structural properties and criteria for their characterization ........ 85

BT5.1.1. Structural liveness............................................................................................ 85

BT5.1.2. Conservativeness ............................................................................................. 86

BT5.1.3. Repetitiveness.................................................................................................. 86

BT5.1.4. Consistency...................................................................................................... 87

BT5.1.5. Relationships between the structural properties .............................................. 87


13/256

Abstract and Contents ix

BT5.2. Invariants ................................................................................................................. 88

BT5.2.1. Definition of the invariants .............................................................................. 88

BT5.2.2. Invariants in reverse-dual nets ......................................................................... 89

BT5.2.3. Criteria for the characterization of invariants and their relationships

to structural properties.............................................................................................. 90


Chapter 6.Deterministic Timed Petri Net Models.......................................................103

Theory .................................................................................................................................... 103

BT6.1. Transition-timed nets............................................................................................. 103

BT6.2. Place-timed nets .................................................................................................... 104

BT6.3. Transforming a T-timed net into aP-timed net ..................................................... 105

BT6.4. Transforming aP-timed net into a T-timed net ..................................................... 106

BT6.5. Periodic behavior ofT-timed, (partially) consistent Petri nets, covered byP-

invariants..................................................................................................................... 107

BT6.6. Periodic behavior ofP-timed, (partially) consistent Petri nets, covered byP-

invariants..................................................................................................................... 109

Applications (AP6.1 AP6.8) .............................................................................................. 110

Chapter 7. Stochastic Timed Petri Net Models ............................................................129

Theory .................................................................................................................................... 129

BT7.1. Principles of stochastic timing............................................................................... 129

BT7.2. Random variables overview ............................................................................... 130

BT7.2.1. Random variables .......................................................................................... 130

BT7.2.2. Cumulative distribution function. Probability density function .................... 130

BT7.2.3. Functions of random variables....................................................................... 132

BT7.2.4. Characteristics of probability distributions.................................................... 132

BT7.2.4.1. Mean value (expectation)....................................................................... 132

BT7.2.4.2. Variance ................................................................................................. 133

BT7.2.4.3. k-th order moment .................................................................................. 134

BT7.2.4.4. Covariance ............................................................................................. 134

BT7.2.5. Law of large numbers. Limit Theorems ........................................................ 135

BT7.2.6. Probability distributions frequently used in stochastic timing ...................... 137

BT7.3. Stochastic processes. ............................................................................................. 137

BT7.4. Stochastic timed Petri nets .................................................................................... 138


Chapter 8. Stochastic Petri Net Models .......................................................................153

Theory .................................................................................................................................... 153

BT8.1. Stochastic Petri Nets.............................................................................................. 153

BT8.2. Properties of the exponential distribution ............................................................. 154

BT8.3. Continuous time homogenous Markov chains ...................................................... 155

BT8.3.1. Basic concepts ............................................................................................... 155


14/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. MahuleaxBT8.3.2. Analysis of state transitions for continuous time homogenous

Markov chains ........................................................................................................ 157

BT8.4. Properties of stochastic Petri nets.......................................................................... 157

BT8.4.1. Construction of the Markov chain associated with a stochastic Petri net...... 157

BT8.4.2. Performance evaluation of a stochastic Petri net........................................... 158

BT8.4.3. Conservativeness properties .......................................................................... 159

BT8.5. Generalized stochastic Petri nets........................................................................... 160


Chapter 9. Max-plus Models ........................................................................................175

Theory .................................................................................................................................... 175

BT9.1. Basic properties of the (max, +) algebra ............................................................... 175

BT9.2. Operations with vectors and matrices over the ( { }, max, ) + algebra ........ 176

BT9.3. State-space representations over the max-plus algebra

forP-timed marked graphs ......................................................................................... 178

BT9.4. Solving the state equation...................................................................................... 181

BT9.5. Solving the output equation................................................................................... 185


Chapter 10.Petri Net Toolbox overview and utilization /

Learning about Petri Net Toolbox ......................................................................201

Introduction Petri Net Toolbox at a First Glance................................................................ 201

Part I. Describing the Graphical User Interface (GUI) .......................................................... 204

I.1. Overview ..................................................................................................................... 204

I.2. Menu Bar..................................................................................................................... 204

I.3. Quick Access Toolbar ................................................................................................. 208

I.4. Drawing Area .............................................................................................................. 208

I.5. Drawing Panel ............................................................................................................. 208

I.6. Draw/Explore Switch.................................................................................................. 208

I.7. Simulation Panel ......................................................................................................... 209

I.8. Status Panel ................................................................................................................. 209

I.9. Message Box ............................................................................................................... 209

Part II. Exploiting the Toolbox .............................................................................................. 210

II.1. Building a Model ....................................................................................................... 210

II.2. Exploring Properties .................................................................................................. 216

II.3. Running a Simulation ................................................................................................ 217

II.4. Analyzing Simulation Results ................................................................................... 221

II.5. Max-Plus Models ....................................................................................................... 222

II.6. Design ........................................................................................................................ 223

Appendix 1: XML file-format of a file containing a PN model............................................. 225

Appendix 2: Configuration File for the Petri Net Toolbox.................................................... 229

Bibliography ................................................................................................................231Index and Romanian-English Dictionary ....................................................................235


15/256

Simboluri i notaii

mulimea numerelor reale

mulimea numerelor naturale (inclusiv 0)

mulimea numerelor ntregi

apartenen

incluziune strict

incluziune cu posibilitate de egal

*T transpusa matricei *

rang* rangul matricei *

|*| cardinalitatea mulimii *

x< y inegaliti < pe toate componentele

vectorilorx, y

x y inegaliti pe toate componentelevectorilorx, y

x)

P= {p1,..., pm} mulimea poziiilor unei

reele Petri

T= {t1,..., tn} mulimea tranziiilor unei

reele Petri

W(ti,pj) ponderea arcului de la ti lapj

W(pj, ti) ponderea arcului de lapj la tim

vectorul de marcaj

( )jM p marcajul poziieipj

0

mM vectorul marcajului iniial

0( )jM p marcajul iniial al poziieipj

N topologia unei reele Petri

(N, M0) topologia unei reele Petri cu un

marcaj iniial dat

suportul invariantului * ( de tip Psau

T) al unei reele Petri* mulimea predecesor (mulime de tranziii,

respectiv poziii) a mulimii * (mulime de

poziii, respectiv tranziii)

* mulimea succesor (mulime de tranziii,

respectiv poziii) a mulimii * (mulime de

poziii, respectiv tranziii)

= ti1 ti2... tik secven de executri de

tranziii fr precizarea vectorilor de

marcaj accesai

= ti1M1ti2M2... tikMk secven de executri

de tranziii, cu precizarea vectorilor de

marcaj accesain

vectorul numrului de executri de

tranziii din secvena

( )t numrul de executri ale tranziiei ti

din secvena

R(M0),R(N, M0) mulimea de accesibilitate

corespunztoare unui marcaj iniial dat

L(M0), L(N, M0) mulimea tuturor secven-elor de executri de tranziii, pornind

dintr-un marcaj iniial dat.

M0[>Mk vectorul de marcaj Mk este

accesibil din vectorul de marcaj M0 prin

secvena de executri de tranziii

K(pj) capacitatea poziieipj

simbol utilizat n construcia arborilor

sau grafurilor de acoperire pentru reelele

nemrginite

C(ti1, ti2) capacitatea de jetoane dintre

tranziiile ti1, ti2


16/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahuleaxiin m

A matricea de inciden de intrare

asociat unei reele Petrin m+ A matricea de inciden de ieire

asociat unei reele Petrin m+

= A A A matricea de inciden

asociat unei reele Petri

uk vector de executare (de control)

C circuit orientat

( )kC numrul total de jetoane aflate pe

circuituluik

C n marcajul M

0( )

kC numrul total de jetoane aflate pe

circuitului kC n marcajul iniial M0

( )k

D C ntrzierea total pe circuitulk

C

spaiul eantioanelor (mulimea tuturor

realizrilor posibile ale unui experiment)

E spaiul evenimentelor

P funcia de probabilitate

( ), ,P E cmp de probabilitate

[ | ]P A B probabilitatea condiional de

apariie a evenimentului A n ipoteza c

s-a produs evenimentulB

X variabil aleatoare

F funcia de repartiie a unei variabile

aleatoare

p densitatea de repartiie a unei variabile

aleatoare discrete

f densitatea de repartiie a unei variabile

aleatoare continue

M[ ]X valoarea medie a variabilei aleatore

X

Var[ ]X dispersia (variana) variabilei

aleatoareX

deviaie standard a variabilei aleatoare

X

operaie definit pe { } prin

{ }max ,a b a b =

operaie definit pe { } prin

a b a b = +


17/256

Capitolul1

Introducere

La nivelul introductiv pe care i-l propune acest capitol, convenim ca, n funcie decontextul exprimrii, prin sistem cu evenimente discrete s nelegem fie un sistem real,fie un model matematic (ce descrie funcionarea unui sistem real), a crui evoluie esteraportat la apariia unor evenimente. Astfel, producerea evenimentelor joac rolul decauz pentru dinamica sistemului i are drept efect modificare strilor sistemului,evideniind o cert similitudine cu aa-numita tratare pe stare a sistemelor continue saudiscrete n timp. Mai mult chiar, i n cazul unui sistem cu evenimente discrete se poatevorbi despre o funcie de tranziie a strilor, care formalizeaz riguros faptul c sistemultrece dintr-o stare n alta numai ca urmare a producerii unui eveniment i c sistemul

pstreaz starea n care se afl pn la producerea unui nou eveniment.Analogia cu sistemele continue sau discrete n timp, pe care le vom referi sub

numele de sisteme clasice trebuie ns utilizat concomitent cu nelegerea corect icomplet a deosebirilor privind interpretarea cauzal a comportrii. Dac n cazulsistemelor clasice, cauzele i efectele sunt valorile unor semnale, care, cel puin sub raport

teoretic, prin variaii acoper intervale (adic mulimi cu aceeai cardinalitate ca ), ncazul sistemelor cu evenimente discrete, mulimea evenimentelorce pot aprea, precum imulimea strilor n care poate tranzita sistemul sunt discrete (adic au cel multcardinalitatea lui ). Dac dinamica sistemelor clasice este raportat la un ceas sincronce msoar scurgerea uniform a timpului (continuu, sau discret - eantionat cu o anumit

perioad), dinamica sistemelor cu evenimente discrete se raporteaz la un ceas asincron,care marcheaz succesiunea evenimentelor i, nu n mod obligatoriu, momentele de

producere a lor. n cosecin, modelele de tip ecuaii difereniale sau cu diferene cepopuleaz literatura sistemelor clasice s-au dovedit neadecvate pentru descrierea

dinamicilor pilotate de evenimente, motiv pentru care a fost necesar s se recurg lainstrumente matematice de alt factur.


18/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea2Sistemele cu evenimente discrete s-au individualizat ca direcie proprie de

cercetare n ultimii 10 15 ani, avnd un impact considerabil asupra dezvoltriitehnologice din diverse arii ale ingineriei, cum ar fi: sisteme de fabricaie, sisteme detransport, sisteme de comunicaii, sisteme de operare i platforme software dedicate,

precum i asupra controlului de tip procedural a numeroase clase de procese automatizate.n perioada mai sus amintit, domeniul Sistemelor cu evenimente discrete s-a fondat dintr-un nucleu interdisciplinar, construit prin aportul a grupuri de cercettori cu formaiitiinifice diferite i alimentat de o serie de resurse distincte din spaiul informaticiiteoretice i a matematicilor aplicate, dintre care cele mai importante ar fi: teoriaautomatelori a limbajelor formale, teoria reelelor Petri, teoria sistemelor de ateptare,teoria algebric a sincronizrii, analiza perturbaiilor (Cao and Ho, 1990). n acest

context heterogen, este dificil i poate chiar hazardat a localiza, n timp, un anumitmoment sau o anumit lucrare, de ale cror semnificaii s se lege actul de natere alnoului domeniu. Exist ns cteva contribuii de pionierat care au precizat fermconexiunile cu descrierile i principiile generale ce guverneaz sistemele dinamice i care,astfel, au deschis perspectiva ca ansamblul preocuprilor din domeniu s poat fi ncadratn amplul edificiu al tiinei sistemelor, drept o nou entitate, recte Sisteme cu evenimentediscrete. Dintre respectivele lucrri amintim: (Ho and Cassandras, 1983), (Cohen et al.,1985), (Ramadge and Wonham, 1987).

Astzi, n urma unui proces de maturizare alert, nsoit de numeroase succese pe plan teoretic i aplicativ, domeniul Sistemelor cu evenimente discrete a dobndit orecunoatere general ca direcie de cercetare pe deplin conturat, figurnd la poziia93C65 n clasificarea comun realizat n anul 2000 de ctre prestigioasele publicaiiZentralblatt MATH i Mathematical Reviews. Cu toate acestea, istoria relativ recenta domeniului face ns ca nici n prezent s nu dispunem de un suport teoretic unificat,capabil de a asigura compatibilitatea ntre metodologiile de sorginte matematic diferit,enumerate n paragraful anterior. n sensul unei atare unificri, pai notabili au fostrealizai de (Bacelli, 1992), (Cassandras, 1993), (Cassandras et al., 1995), (Lewis et

al., 1995).Cum era de ateptat, drumul pn la conturarea unui punct de vedere teoreticatotcuprinztor scoate la lumin multiple dificulti n construirea punilor de legtur, unrol nsemnat jucndu-l i inerenta atitudine de conservare a tradiiilor de cercetaremanifestat de diferite colective. Dei la nivel general, atare puni deja exist, preferina

pentru un anumit instrument de investigare este uzual motivat de specificul problematiciii de experiena acumulat n abordarea acelei problematici.

Concomitent cu progresul Sistemelor cu evenimente discrete ca domeniu decercetare, acest domeniu i-a fcut apariia i ca obiect de studiu n planurile denvmnt ale universitilor occidentale, americane i japoneze, fiind binecunoscut


19/256

Cap. 1. Introducere 3

dinamismul lor n preluarea i diseminarea noutilortiinifice. Urmare a heterogenitii

domeniului nsui, cursurile respective se caracterizeaz printr-o varietate destul de mare amodalitilor de tratare. Totodat, edinele de aplicaii ce acompaniaz orele de predare anoiunilor teoretice sunt orientate pe diferite medii software ce permit simularea, analizai sinteza sistemelor cu evenimente discrete. Fiecare dintre aceste medii exploateaz unanumit suport teoretic, actualmente existnd instrumente fiabile, produse de firme cuexperien, care se bazeaz pe teoria automatelor (ca de exemplu State-Flow (MathWorks,1997)), pe teoria reelelor Petri (ca de exemplu software-urile prezentate n (Mortensen,2003)), pe teoria sistemelor de ateptare (ca de exemplu ARENA (Kelton et al., 2002), peteoria algebric a sincronizrii (ca de exemplu Scilab (Cohen et al., 2001)).

Pornind de la realitatea curent a domeniului (att din perspectiva tiinific ct ididactic), am considerat c elaborarea unei lucrri cu caracter monografic, care sasigure, deopotriv, accesibilitatea lecturii pentru cititorii nefamiliarizai cu problematicastudiat, trebuie s permit o incursiune ct mai complet n universul Sistemelor cuevenimente discrete, realizat gradual, ghidat ntr-o manier unic sub raportulinformaiilori al limbajului de exprimare. Astfel, am decis s structurm materialul pefundamentul teoretic al reelelor Petri, care, pe parcursul celor patru decenii scurse de la

prezentarea tezei de doctorat a matematicianului german Carl Adam Petri (Petri, 1962), audemonstrat o deosebit flexibilitate n abordarea a numeroase tipuri de probleme practice,

precum i o mare capacitate de extindere ca sfer de operare, prin nglobarea unor punctede vedere tot mai complexe.

Reelele (grafurile) propuse n (Petri, 1962) dispuneau de un mecanism capabil dea guverna, pe principiile algebrei boolene, evoluia unui vector cu elemente numerenaturale, avnd semnificaie de stare, fr precizarea momentelor efective de timp cndaveau loc modificrile strii. Cercetrile ulterioare au condus i la ncorporareainformaiilor temporale (Ramamoorthy and Ho, 1980), (Ajmone Marsan et al., 1985),astfel nct, n prezent, pentru studierea sistemelor cu evenimente discrete, avem la

dispoziie modele de tip reea Petri netemporizat (care permit studii calitative) i,respectiv, de tip reea Petri temporizat (care permit studii cantitative). Introducereatemporizrii s-a realizat de aa manier nct s permit nuanrile de model deterministsau stohastic, binecunoscute din cazul sistemele clasice.

Aceste rafinri ale conceptului iniial formulat de Petri (rafinri care nu includ, ntotalitate, extinderile propuse n literatur) evideniaz att resursele oferite pentrumodelare, ct i compatibilitatea cu alte instrumente i tipuri de modele. Reelele Petri potmodela fenomenele specifice sistemelor cu evenimente discrete, cum ar fi succesiunea (oevoluie succede alteia), alegerea sau conflictul (selectarea uneia din mai multe posibilitide evoluie), concurena (startarea unor evoluii paralele), sincronizarea (ncheierea unorevoluii paralele), excluderea mutual (condiionarea reciproc a unor evoluii), care pot fi


20/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea4formulate n contexte temporizate sau netemporizate. Pe de alt parte, informaiile

coninute de alte modaliti de descriere a dinamicii sistemelor cu evenimente discrete(automate, sisteme de ateptare, reprezentri de stare max-plus) pot fi grefate cu uurin pe arhitectura modelelor de tip reea Petri. n plus, studiul reelelor Petri este uzualacompaniat de o abordare la nivel vizual, prin reprezentri grafice expresive. Drepturmare, literatura de specialitate raporteaz o larg utilizare a reelelor Petri n modelare,analizi proiectare, acoperind o arie semnificativ de procese controlate secvenial, de ladinamica unor entiti individuale (David et Alla, 1992), (Zurawski and Zhou, 1994), ladinamica unor entiti colective (sisteme mari eng. large scale systems), ca de exemplu,sisteme hardware i software (Peterson, 1981), (Levi and Agrawala, 1990), procesechimice (Yamalidou et al., 1990), sisteme de fabricaie (Desrochers and Al-Jaar, 1993),

(Zhou and DiCesare, 1993), (Lewis et al., 1995), roboi i sisteme de transport (Freedman,1991), (Cassandras et al., 1995), sisteme de comunicaii (Nissanke, 1997).

Lucrarea noastr caut s ilustreze pe parcursul a opt capitole cele mai importantedintre aspectele punctate anterior. Modul de nlnuire al capitolelor a avut n vederecreterea treptat a complexitii problematicii, precum i posibilitatea stabilirii unorconexiuni relevante inter-capitole. S-a reuit, astfel, o acoperire a elementelor definitorii

pentru formalismul reelelor Petri i utilizarea acestuia n practic, contextuluinetemporizat fiindu-i alocate primele cinci capitole, iar contextului temporizat,

urmtoarele trei capitole.Contextul netemporizat trateaz modelarea, analiza i proiectarea din perspectiva

dinamicilor coordonate doar la nivel logic, momentele de apariie a evenimentelor fiindordonate ca succesiune, dar fr precizarea lor concret i fr utilizarea unor durateconcrete de timp. n context temporizat, modelarea, analiza i proiectarea includinformaii concrete privind momentele i/sau duratele de timp, considerate de naturdeterminist sau stohastic.

n linii mari vorbind, proprietile calitative ce fac obiectul tehnicilor de analizisintez pe modele netemporizate sunt robuste n raport cu orice variaie de factur

temporal i se refer la funcionarea ansamblului sistemic fr incidente de procedurtehnic (ntr-o manier repetabil, fr aglomerri sau blocri n realizarea serviciilor). Pede alt parte, analiza i sinteza pe modele temporizate vizeaz proprietile cantitative nsensul de indici de performan asociabili unor criterii de eficien economic (de tipulservicii realizate n unitatea de timp, grad de ocupare a prestatorilor de servicii etc.).

Fiecare din cele opt capitole conine un breviar teoretic urmat de un numr deaplicaii ce exemplific conceptele, rezultatele i metodele din breviar. n aplicaii se faceapel att la reele Petri fr semnificaii de modele ale unor dinamici reale (ce permitexersarea noiunilor teoretice), ct i la reele Petri care modeleaz funcionarea unorsisteme fizice (ce asigur ancorarea cunotinelor teoretice pe terenul intuiiei


21/256

Cap. 1. Introducere 5

fenomenologice). Pentru aceleai sistemele fizice sunt construite iniial modele

netemporizate concentrnd atenia asupra proprietilor comportamentale i structurale, iarulterior se adaug informaii legate de timp, spre a utiliza modelele temporizate ninvestigaii cantitative. Soluiile prezentate pentru aplicaii au n vedere, deopotriv,varianta analitic i cea asistat de calculator; n general, pentru aplicaiile decomplexitate redus sunt date rezolvri analitice, pentru aplicaiile de complexitate mediesunt date rezolvri analitice i asistate de calculator, iar pentru aplicaiile de complexitatemare sunt date numai rezolvri asistate de calculator.

Pentru studiile prin simulare precum i pentru rezolvarea asistat de calculator aaplicaiilor se utilizeaz software-ul Petri Net Toolbox(Mahulea et al., 2001), (Matcovschi

et al., 2002), (Matcovschi et al., 2003), proiectat, implementat i testat n cadrul Catedreide Automatic i Informatic Industrial a Facultii de Automatic i Calculatoare dinIai. Acest software a fost anume conceput pentru exploatare sub mediul MATLAB careeste familiar instruirii n Automatic. Ajuns deja la versiunea 2.0, el ofer o interfa cuutilizatorul foarte prietenoas ce asigur definirea reelelor sub form grafic, simulareacu faciliti multiple de animaie i accesul la instrumente de analizi sintez ce acopertoate dezvoltrile teoretice din prezenta lucrare.

Ultimul capitol al lucrrii realizeaz o trecere n revist a principalelorcaracteristici ale software-uluiPetri Net Toolbox, n limba englez, urmrind structura de

informaii disponibil n Help-ul on-line al produsului. Dup cunotinele noastre, PetriNet Toolboxeste singurul produs disponibil sub MATLAB care utilizeaz reelele Petri nexplorarea sistemelor cu evenimente discrete, exceptnd dou pachete elaborate recent, ianume (Svdov and Hanzlek, 2001), care nu posed interfa grafic proprie, utilizndinterfaa software-ului Petri-Maker (Mortensen, 2003), i (Iordache and Antsaklis, 2002),care nu are nici un fel de interfa grafic, topologiile reelelor fiind descrise directmatriceal.

Elaborat n spiritul tendinelor actuale de cercetare i educaie din domeniul

sistemelor cu evenimente discrete, cartea are un pronunat caracter de originalitate pentruliteratura tehnic din Romnia, raportat la lucrrile existente cu tematic asemntoare(Stnescu et al., 1996), (Leia i Atilean, 1998), (Jucan i iplea, 1999), (Mnzu iCernega, 2001). Acest caracter rezult din ponderea acordat aplicaiilor, din maniera lorde prezentare detaliat (menit s ilustreze att tratarea analitic, ct i modul de implicarea software-ului) i din rolul jucat de Petri Net Toolboxca instrument ce extindesubstanial aria de exploatare a MATLAB-ului. Totodat precizm faptul c tehnicileilustrate prin aceste aplicaii nu fac uz de ntreaga instrumentaie pus la dispoziie de teoriareelelor Petri, ci, ca urmare a unei selecii judicioase, se concentreaz pe acele abordri acror eficien a fost validat de un numr mare de implementri practice, raportate nliteratur. Consecveni ideii de a menine accesibilitatea i complexitatea noiunilor teoretice


22/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea6la un nivel mediu, am procedat la excluderea unor tematici mai dificile, care sunt referite

frecvent drept extensii ale formalismului de baz al reelelor Petri, cum ar fi: reele Petricolorate (pentru care recomandm cititorului lucrrile (Jensen, 1992, 1994, 1997)), reele Petriinterpretate, continue i hibride (pentru care recomandm cititorului lucrarea (David et Alla,1992)), reele Petri n supervizare (pentru care recomandm cititorului lucrarea (Antsaklisand Moody, 1998).

n conceperea, structurarea i realizarea acestei cri, o contribuie major a avutlucrarea (Pastravanu, 1997) pe baza creia s-au organizat cursul i edinele de aplicaii ladisciplina Sisteme dinamice cu evenimente discrete de la Facultatea de Automatic iCalculatoare din Iai. edinele de aplicaii respective au oferit i cadrul necesar pentru

verificarea robusteii software-ului Petri Net Toolbox i pentru validarea pe o baterielarg de teste a algoritmilor implementai.


23/256

Capitolul2Modele de tip reea Petri netemporizat

Breviar teoretic

BT2.1. Conceptul de reea Petri netemporizat

O reea Petri (eng. Petri net) se compune dintr-un tip particular de graf orientatnotatNi ostare iniial 0 , denumitmarcaj iniial(eng. initial marking).

GrafulNal reelei Petri este orientat, ponderat i bipartit, constnd din dou tipuri denoduri, denumite poziii sau locaii (eng. place) i respectiv tranziii (eng. transition); arceleorientate (eng. arc) unesc fie o poziie cu o tranziie, fie o tranziie cu o poziie. Nu exist arcecare s conecteze dou poziii ntre ele, sau dou tranziii ntre ele. Ca simbolizare grafic,

poziiile se reprezint prin cercuri, iar tranziiile prin bare sau dreptunghiuri. Arcele suntetichetate cu ponderile lor (eng. weight) (valori ntregi, pozitive); un arc cu ponderea kpoate fi

privit ca o mulime de karce paralele cu pondere unitar. Etichetele pentru pondere unitar seomit n reprezentrile grafice uzuale.

Un marcaj sau ostare atribuie fiecrei poziii un numr ntreg mai mare sau egal cu 0.Dac un marcaj atribuie poziiei p ntregul 0k , se spune cp este marcat cu kjetoane(eng. token). Din punct de vedere grafic, n cercul corespunztor poziiei p se vor plasa kdiscuri. Orice marcaj Meste un vector coloanmdimensional, unde m noteaz numrul total

al poziiilor. Componenta i a vectorului [ ]1 2( ) ( ) ( )T

mM M p M p M p= , notat ( )iM p

reprezint numrul de jetoane din poziia pi. Din motive de concizie a scrierii, n unelecapitole ale acestei cri un marcaj M va fi, de asemenea, reprezentat prin m-uplul( )1 2( ), ( ), , ( )mM p M p M p= .

Aspectele prezentate anterior se formalizeaz matematic prin urmtoarea definiie.

O reea Petri este un cvintuplu, ( )0, , , ,P T F W M =PN n care:

{ }1 2, , , mP p p p= este mulimea poziiilor sau locaiilor (finit); { }1 2, , , nT t t t = este mulimea tranziiilor (finit); ( ) ( )F P T T P este mulimea arcelor; { }: 1, 2,3,W F este funcia de ponderare a arcelor; { }0 : 0,1,2,3,M P este funcia de marcaj iniial.


24/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea8Cteva comentarii sunt necesare pentru a aprofunda detaliile acestei formalizri:

1. MulimilePi Tsunt disjuncte, P T= .2. Pentru a asigura obiectul definiiei de mai sus, mulimile P i T satisfac condiia

P T .3. Definiia funciei de ponderare se poate extinde pe mulimea tuturor perechilor ordonate

din ( ) ( )P T T P , considernd ( ) ( ) { }: 0,1,2,3,...W P T T P , cu observaia c,

pentru acele perechi care nu sunt n mulimea F, valoarea funciei W este 0 i acesteperechi nu sunt reprezentate grafic. Mulimea Fcorespunde perechilor a cror pondereeste nenuli numai acestea sunt reprezentate grafic.

4. Definiia unei reele Petri consider implicit c toate poziiile reelei pot conine un numrorict de mare de jetoane. Se spune c reeaua este cu capacitate infinit.

5.

O structur de reea PetriN= (P, T,F, W) fr nici o specificaie referitoare la marcaj seva nota cuN, notaie care desemneaztopologia reelei.6. O reea Petri cu un marcaj iniial 0 se va nota prin 0( , )N .7. O reea Petri cu un marcaj oarecare Mse va nota prin ( , )N .n problemele de modelare ce utilizeaz conceptele de condiii i evenimente, poziiilereprezint condiii i tranziiile reprezint evenimente. O tranziie (eveniment) posed unnumr de poziii de intrare i ieire, care reprezintpre-condiii i respectiv post-condiii

pentru evenimentul n cauz. Prezena unui jeton ntr-o poziie trebuie neleas ca valoarelogic adevrat pentru condiia asociat respectivei poziii.

BT2.2. Terminologie uzual

Dac o poziie p este att poziie de intrare, ct i de ieire pentru o tranziie t, atunci pi tformeaz o buclautonom (eng.self-loop). O reea Petri care nu conine bucle autonome senumete pur (eng. pure). O bucl autonom poate fi ntotdeauna transformat ntr-o buclneautonom prin adugarea simultan a unei poziii i a unei tranziii formale (eng. dummy).Orice reea impur poate fi transformat ntr-o reea pur.

O reea Petri se numete ordinar (eng. ordinary) dac toate arcele sale au pondereunitar. Dac ntr-o reea Petri exist cel puin un arc a crui pondere este mai mare dect 1,atunci se spune c reeaua respectiv estegeneralizat.

Fie F mulimea tuturor arcelor unei reele Petri N. Se numesc mulimepredecesor(eng.pre-set) i mulimesuccesor(eng.post-set) a tranziiei t(fig. BT2.2.1.(a)) dou mulimide poziii definite prin:

{ }| ( , )t p p t F = = mulimea tuturor poziiilor de intrare ale lui t;

i, respectiv, prin:{ }| ( , )t p t p F = = mulimea tuturor poziiilor de ieire ale lui t.

Se numesc mulimepredecesori mulimesuccesora poziiei p (fig. BT2.2.1.(b)) doumulimi de tranziii definite prin:

{ }| ( , )p t t p F = = mulimea tuturor tranziiilor de intrare ale luip;

i, respectiv, prin:{ }| ( , )p t p t F = = mulimea tuturor tranziiilor de ieire ale luip.


25/256

Cap. 2. Modele de tip reea Petri netemporizat 9

Fig. BT2.2.1.Ilustrarea grafica mulimilor predecesori succesor(a) Mulimile de poziii t i t ; (b) Mulimile de tranziii p i .

Acelai mod de notare, i anume { } , { } , se utilizeaz pentru a desemna mulimeapredecesori, respectiv, succesor a unei mulimi de tranziii sau a unei mulimi de poziii,notat generic{ } . Evident, mulimile predecesori succesor ale unei mulimi de tranziii sunt

dou mulimi de poziii, iar mulimile predecesori succesor ale unei mulimi de poziii suntdou mulimi de tranziii.

BT2.3. Validarea i executarea tranziiilorn reele cu capacitate infinit evoluia strilor

Marcajul unei reele Petri are semnificaia de stare a reelei i se poate modifica nconformitate cu urmtorul procedeu denumit regula tranziiei (validare i executare) (ilustraren AP2.1).

a) Se spune c o tranziie teste validat (eng. enabled) dac fiecare poziie de intrare(predecesor) p a lui t este marcat cu cel puin ( , )W p t jetoane, unde ( , )W p t

noteaz ponderea arcului de lap la t.b) O tranziie validat poate sau nu s fie executat sau declanat (eng. fired), dup

cum evenimentul asociat tranziiei are sau nu loc.c) Executarea unei tranziii validate ndeprteaz ( , )W p t jetoane din fiecare poziie de

intrare (predecesor) p a lui t i adaug ( , )W t p jetoane la fiecare poziie de ieire

(succesor)p a lui t, unde ( , )W t p este ponderea arcului de la tlap.

O tranziie fr nici o poziie de intrare se numete tranziie surs (eng. source). Otranziie fr nici o poziie de ieire se numete tranziie receptor (eng. sink). Modul deoperare al acestor tranziii este urmtorul:

a) O tranziie surs este necondiionat validat (fr a fi obligatoriu ca s se execute).Executarea ei produce jetoane.

b) Executarea unei tranziii receptor consum jetoane, fr a produce jetoane.

n teoria reelelor Petri netemporizate se consider c executarea unei tranziii nuconsum timpi cjetoanele pot rmne n poziii pentru orice duratde timp (orict de mic

sau orict de mare). ntruct executarea unei tranziii este instantanee, se consider ctranziiile se execut numai secvenial, adic nu se poate vorbi de dou tranziii executate

t

t t

poziii de intrarepentru t

poziii de ieirepentru t

(a)

tranziii de intrarepentrup

tranziii de ieirepentrup

p p

p

(b)


26/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea10simultan (sau n paralel). Aceste presupuneri fac ca modelul de tip reea Petri netemporizat sfie utilizat numai pentru investigarea proprietilor logice, calitative, care nu depind de timp.

Pentru o reea Petri N cu un marcaj iniial M0, urmrind executarea secvenial atranziiilor, se pot determina marcajele succesive ale reelei. Procesul de modificare amarcajului (strii) reelei poate fi descris ntr-o manier sintetic printr-un arbore sau printr-ungraf (diferit de graful reelei Petri!), ce poart denumirea de arbore, respectiv, graf deaccesibilitate (eng. reachability tree/graph) (ilustrare n AP2.4). Aceste concepte sunt detaliaten BT3.3 din capitolul 3, cu referire la situaia mai general a arborelui/grafului de acoperire(eng. coverability tree/graph).

BT2.4. Unele extensii pentru reele Petri netemporizate

BT2.4.1. Reele Petri cu capacitate finit

Pentru regula de validare a unei tranziii prezentat anterior s-a presupus c fiecare poziie arecapacitate infinit. n modelarea sistemelor fizice este firesc a considera o limit superioar anumrului de jetoane pe care l poate conine fiecare poziie, asociind fiecrei poziii pcapacitatea sa (eng. capacity), notatK(p), definit ca numrul maxim de jetoane ce pot ficoninute np. O astfel de reea se numete cu capacitate finit.

ntr-o reea cu capacitate finit, pentru validarea unei tranziii t este necesarurmtoarea condiie suplimentar: numrul de jetoane n fiecare poziie de ieire p a lui tnu

poate s depeasc capacitatea poziiei respective,K(p), atunci cnd ts-ar executa (ilustrare n

AP2.1). n acest caz, regula tranziiei se va numi regula stricta tranziiei spre a o deosebi decea enunat n paragraful BT2.3, care mai este uneori referit drept regula simpla tranziiei.

Fiind dat o reea Petri de capacitate finit (N, M0) este posibil de aplicat fie regulastrict a tranziiei direct pentru reeaua (N, M0), fie regula simpl a tranziiei pentru o reeatransformat adecvat, notat ( 0, N ). Presupunnd c reeaua N este pur, urmtorul

algoritm permite construcia reelei ( 0, N ) plecnd de la (N, M0), prin metoda poziiilor

complementare:Pas 1. Pentrufiecare poziiep, se adaug o poziie complementarp', al crei marcaj iniial

este dat de 0 0( ) ( ) ( )p K p M p = .

Pas 2. ntrefiecare tranziie ti unele poziii complementare p'se traseaz arce suplimentare,(t,p') sau (p',t), cu ponderile W(t, p') = W(p,t), respectiv W(p',t) = W(t,p), astfel nctsuma jetoanelor n poziiapi n poziia complementar corespunztoarep's fie egalcu capacitateaK(p), att nainte, ct i dup executarea tranziiei t(adic s se asiguresatisfacerea condiiei ( ) ( ) ( )p M p K p + = ).

Subliniem faptul cmetoda nu adaugtranziii suplimentare (ilustrare n AP2.2). Grafurile deaccesibilitate ale reelelor (N, M0) i ( 0, N ) sunt izomorfe n sensul c prezint aceleai

secvene posibile de executare a tranziiilor.

BT2.4.2. Reele cu probabilitii prioriti

n unele modele de tip reea Petri dou sau mai multe tranziii modeleaz evenimente dintrecare unul i numai unul se poate produce la un moment dat (n conflict). Implicit se consider


27/256


c probabilitile de apariie a acestor evenimente sunt egale. n cazul n care aceast presupunere nu este n conformitate cu sistemul fizic modelat, probabilitile de apariie a

evenimentelor n conflict pot fi asignate n mod explicit ca probabiliti de executare atranziiilor care modeleaz evenimentele respective (ilustrare n AP2.5).

De asemenea, atunci cnd se dorete a impune modul de alegere a tranziiei careurmeaz a fi executat dintre dou sau mai multe tranziii validate simultan se poate utiliza oreea Petri cuprioriti care const dintr-o reea Petriobinuiti o relaie de ordine parialntre tranziiile reelei (ilustrare n AP2.3).

BT2.4.3. Reele cu arce inhibitoare

Introducerea arcelor inhibitoare extinde capacitatea de modelare a reelelor Petri. Un arc

inhibitor conecteaz o poziie la o tranziie i are rolul de a inversa logica de validare iexecutarea a acesteia. Tranziia respectiv este validat numai dac numrul de jetoane dinpoziia de intrare a arcului inhibitor este strict mai mic dect ponderea arcului. Arcul inhibitorse reprezint grafic printr-un segment ce conecteaz cele dou noduri, avnd un mic cerc lacaptul dinspre tranziia inhibat. Nu exist arce inhibitoare care conecteaz o tranziie la o

poziie (ilustrare n AP2.3).

BT2.5. Modelarea cu reele Petri ordinare

BT2.5.1. Structuri tipice utilizate n modelare

Structurile tipice utilizate n modelarea sistemelor cu evenimente discrete prin intermediulreelelor Petri sunt prezentate sintetic n fig. BT2.5.1.

Fig. BT2.5.1.Structuri tipice utilizate n modelarea cu reele Petri

(a) Conflict, decizie sau alegere liber; (b) Alegere liberextins;

(c) Alegere asimetric; (d) Paralelism sau concuren; (e) Confuzie simetric;(f) Confuzie asimetric; (g) Sincronizare; (h) Post-condiie comun.


28/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea12BT2.5.2. Capacitatea de modelare a unor subclase de reele Petri ordinare

Reelele Petri ordinare pot fi organizate n subclase definite pe baza unor considerentetopologice. Apartenena unei reele la o anumit subclas este reflectat n capacitatea demodelare, n sensul c reeaua nu va putea conine toatestructurile tipice definite n seciunea

precedent, ci numai o parte din acestea (n funcie de subclasa creia i aparine). Aceastpartajare pe subclase va servi, n seciunea BT3.5 din capitolul 3, la formularea unor tehnicidedicate analizei anumitor proprieti comportamentale pentru aceste tipuri de reele.

Maina de stare (eng.state machine) este o reea Petri ordinar n care fiecare tranziie tare o singur poziie de intrare i o singur poziie de ieire. Formaliznd, avem:

: | | | | 1t T t t = = , (BT2.5.1)

unde | | noteaz cardinalitatea (numrul de elemente al) mulimii .

Referindu-ne la structurile tipice ilustrate n fig. BT2.5.1, se constat c o main destare conine numai alegeri libere i post-condiii comune (ilustrare n AP2.5).

Graful marcat(eng. marked graph) sau graful de evenimente (eng. event graph) este oreea Petri ordinar n care fiecare poziie p are o singur tranziie de intrare i o singurtranziie de ieire. Formaliznd, avem

: | | | | 1p P p p = = . (BT2.5.2)

n termenii structurilor tipice ilustrate n fig. BT2.5.1, se constat c un graf marcatconine numai concurene i sincronizri (ilustrare n AP2.4 i AP2.5).

Termenul de graf marcat sau graf de evenimente se datoreaz faptului c acest tip dereea Petri poate fi reprezentat printr-ungraf orientatunipartit(care posed un singur tip denoduri!) n care nodurile corespund tranziiilor (adic evenimentelor), arcele corespund

poziiilor, iar jetoanele se plaseazpe arce (adic arcele sunt marcate) (ilustrare n AP2.4).Astfel regula tranziiei se aplic nodurilor grafului orientat, o executare constnd, n aceastreprezentare grafic, n ndeprtarea unui jeton de pe fiecare din arcele de intrare ale noduluin cauzi adugarea unui jeton pe fiecare din arcele de ieire.

Reeaua cu alegeri libere (eng.free choice net) este o reea Petri ordinar n care oricearc ce iese dintr-o poziiep este caracterizat prin una din urmtoarele dou situaii:

(i) estesingurularc care pleac dinp,sau:

(ii) estesingurularc care intr ntr-o anumit tranziie (adic n acea tranziie nu maiintr nici un alt arc, n afara celui ce pleac dinp).

Avem urmtoarea formalizare:

: | | 1 sau ( ) { }p P p p p = . (BT2.5.3)

Aceast descriere matematic este echivalent cu implicaia:

1 2 1 2 1 2, : | | | | 1p p P p p p p

= = . (BT2.5.4)


29/256


Condiia (BT2.5.4) trebuie privit ca o relaxare a condiiei (BT2.5.2). Totodat,condiia (BT2.5.4) relaxeazi condiia (BT2.5.1).

Examinnd aceste particulariti prin prisma structurilor tipice ilustrate n fig. BT2.5.1,se constat c o reea cu alegeri libere conine numai alegeri libere, post-condiii comune,concurene i sincronizri.

Reeaua cu alegeri libere extinse (eng. extended free-choice net) este o reea Petriordinar n care este satisfcut condiia:

1 2 1 2 1 2, :p p P p p p p

= . (BT2.5.5)

Condiia (BT2.5.5) trebuie privit ca o relaxare a condiiei (BT2.5.4).n termenii structurilor tipice discutate, ilustrate n fig. BT2.5.1, se constat c o reea

cu alegeri libere extinse conine numai alegeri libere, alegeri libere extinse, post-condiiicomune, concurene i sincronizri.

Reeaua cu alegeri asimetrice (eng. asymmetricchoice net), sau reeaua simpl, este oreea Petri n care este satisfcut condiia:

1 2 1 2 1 2 1 2, : ( sau )p p P p p p p p p

. (BT2.5.6)

Condiia (BT2.5.6) trebuie privit ca o relaxare a condiiei (BT2.5.5).Referindu-ne la structurile tipice ilustrate n fig. BT2.5.1, se constat c o reea cu

alegeri asimetrice conine numai alegeri libere, alegeri libere extinse, alegeri asimetrice, post-condiii comune, concurene, sincronizri i confuzii asimetrice (ilustrare n AP3.5 i AP3.6).

Examinnd definiiile subclaselor de reele Petri ordinare formulate mai sus, seconstat c ntre acestea exist relaiile de incluziune reprezentate grafic n fig. BT2.5.2.

Fig. BT2.5.2.Relaiile de incluziune ntre subclasele de reele Petri ordinare.

Mainide stare

(BT2.5.1)

Grafurimarcate

(BT2.5.2)

Reele cu alegeri libere(BT2.5.4)

Reele cu alegeri libere extinse(BT2.5.5)

Reele cu alegeri asimetrice(BT2.5.6)

Reele Petri ordinare


30/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea14Tabelul BT2.5.1. sintetizeaz informaiile referitoare la capacitatea de modelare a

diferitelor subclase de reele Petri ordinare n raport cu structurile tipice ce au fost prezentate

n seciunea BT2.5.1.

Tab. BT2.5.1.Prezentare sintetica capacitii de modelare a diferitelor subclase de reele Petri.

Structur

Clas

Alegeri

libere

Alegeri

libere

extinse

Alegeri

asimetrice

Concu-

rene

Confuzii

simetrice

Confuzii

asimetrice

Sincro-

nizri

Post-

condiii

comune

Main de stare DA DA

Graf marcat DA DA

Reea cu alegeri

libereDA DA DA DA

Reea cu alegeri

libere extinseDA DA DA DA DA

Reea cu alegeri

asimetriceDA DA DA DA DA DA DA

Reea Petri

ordinarDA DA DA DA DA DA DA DA

Capacitatea de modelare crete n sensul acceptrii de noi structuri tipice, aceastcretere fiind perfect compatibil cu relaiile de incluziune stabilite ntre subclase n

paragraful anterior (vezi i fig. BT2.5.2). Dar, dup cum va reiei din seciunea urmtoare,creterea capacitii de modelare face ca criteriile de analiz a proprietilor comportamentales devin tot mai complexe i mai dificil de aplicat. Din acest motiv, insistm asupranecesitii elaborrii unor modele ct mai puin sofisticate, care s fie capabile s surprindacele detalii de funcionare ce trebuie avute n vedere pe parcursul analizei sau proiectrii.

Aplicaii

AP2.1.

Pentru reelele Petri cu topologia i marcajul iniial indicat n fig. AP2.1.1, s se precizezecare dintre tranziii sunt validate i marcajul ce rezult dup executarea fiecreia din acestetranziii n cazurile urmtoare:1. reelele au capaciti infinite;2. reelele au capaciti finite dup cum urmeaz:

(i) pentru reeaua din fig. AP2.1.1.(a): 1 3( ) ( ) 2K p K p= = , 2( ) 1K p = ;(ii)pentru reeaua din fig. AP2.1.1.(b): 1 2 3( ) ( ) ( ) 1K p K p K p= = = ;(iii)pentru reeaua din fig. AP2.1.1.(c): 1( ) 2K p = , 2( ) 3K p = , 3 4( ) ( ) 1K p K p= = .


31/256


p1

t1

p2

t2

p3t3

t4

p1

t1

p2

t2p3 t3

p1

t1

p2

p3

t3

t4

p4t2

t52

2

23

wObs. noteaz arc cu pondere w>1

(a) (b) (c)

Fig. AP2.1.1.Reelele Petri studiate n AP2.1.

Soluie

1. Aplicnd regula simpl a tranziiei reelei din fig. AP2.1.1.(a) cu marcajul iniial

( )0 2,1,0M = se obine:

tranziia t1 este validat deoarece ( ) ( )0 1 1 1,p W p t > ; prin executarea lui t1 se ajungedin 0 la marcajul ( )1 1,2,0M = ;

tranziia t2 este validat deoarece ( ) ( )0 2 2 2,p W p t = ; prin executarea lui t2 seajunge din 0 la marcajul ( )2 3,0,0M = ;

tranziia t3 este validat deoarece ( ) ( )0 1 1 3,p W p t > i ( ) ( )0 2 2 3,p W p t = ; prinexecutarea lui t3 se ajunge din 0 la marcajul ( )3 1,0,1M = .

Analog, pentru reeaua din fig. AP2.1.1.(b) cu marcajul iniial ( )0 1,1,0M = rezult:

tranziia t1 este validat deoarece ( ) ( )0 1 1 1,p W p t > ; prin executarea lui t1 se ajungedin 0 la marcajul ( )1 1,2,0M = ;

tranziia t2 este validat deoarece ( ) ( )0 2 2 2,p W p t = ; prin executarea lui t2 seajunge din 0 la marcajul ( )2 3,0,0M = ;

tranziia t3 este validat deoarece ( ) ( )0 1 1 3,p W p t > i ( ) ( )0 2 2 3,p W p t = ; prinexecutarea lui t3 se ajunge din 0 la marcajul ( )3 1,0,1M = .

Pentru reeaua din fig. AP2.1.1.(c) cu marcajul iniial ( )0 2,0,0,1M = , aplicarea regulii simple

a tranziiei conduce la: tranziia t1 este validat deoarece ( ) ( )0 1 1 1,p W p t > ; prin executarea lui t1 se ajunge

din 0 la marcajul ( )1 0,3,0,2M = ;

tranziia t5 este validat deoarece ( ) ( )0 4 4 5

,p W p t = ; prin executarea lui t2 se

ajunge din 0 la marcajul ( )2 4,0,0,0M = .


32/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea162. innd cont de marcajele la care s-ar ajunge prin executarea tranziiilor validatedeterminate la punctul 1 i de capacitile finite precizate ale poziiilor, prin aplicarea regulii

stricte a tranziiei se obine:(i) pentru reeaua din fig. AP2.1.1.(a), singura tranziie validat este t3 deoarece

( ) ( )0 1 1 3,p W p t > , ( ) ( )0 2 2 3,p W p t = i ( ) ( ) ( )3 0 3 3 3,K p M p W t p> + ; prin

executarea lui t3 se ajunge din 0 la marcajul ( )3 1,0,1M = ;

(ii)pentru reeaua din fig. AP2.1.1.(b) sunt validate: tranziia t2 deoarece ( ) ( )0 2 2 2,p W p t = ; prin executarea lui t2 se ajunge

din 0M la marcajul ( )2 3,0,0M = ;

tranziia t3 deoarece ( ) ( )0 1 1 3,p W p t > , ( ) ( )0 2 2 3,p W p t = i( ) ( ) ( )3 0 3 3 3,K p M p W t p= + ; prin executarea lui t3 se ajunge din 0 la

marcajul ( )3 1,0,1M = ;

(iii)pentru reeaua din fig. AP2.1.1.(c) nici una dintre tranziii nu este validat.

AP2.2.

Transformai reeaua Petri cu capacitate finit din fig. AP2.2.1, ntr-o reea Petri cu capacitateinfinit.

( )

( ) ( ) ( )3

1 2 4

1K p

K p K p K p

=

= = =

Fig. AP2.2.1.Reeaua Petri cu capacitate finitstudiatn AP2.2.

Soluie

Utiliznd metoda poziiilor complementare cu referire la poziia p3, se adaug poziia 3p

astfel nct s fie satisfcute urmtoarele relaii:( ) ( )

( ) ( )

( ) ( ) ( )

3 3 3 3

3 3 3 3

0 3 3 0 3

, , 1,

, , 1,

1 1 0.

W t p W p t

W t p W p t

M p K p M p

= =

= =

= = =

p2

p1

p3 t5

t3

p4

t2

t4

t1


33/256


34/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea18ca n fig. AP2.3.2.(a), n lipsa altor precizri, cei doi consumatori vor avea drepturi egale de aconsuma, ceea ce nseamn c modelul nu rspunde n totalitate cerinelor din enun. Pentru a

include n model i informaiile referitoare la disciplina de consum, se va asigna prioritate 0tranziiei t3i, respectiv, prioritate 1 tranziiei t5.

O variant echivalent cu alocarea prioritilor o constituie controlul tranziiei t5printr-un arc inhibitor conform figurii AP2.3.2.(b); astfel, dacp3 conine jeton/jetoane, t5 vafi validat numai cndp5 nu conine jeton (adic primul consumator nu solicit produs).

(a) (b)

Fig. AP2.3.2. Modelul de tip reea Petri al sistemului cu un productori doi consumatori:

(a) asignnd tranziiei t3 prioritate mai mare dect tranziiei t5;(b) utiliznd arc inhibitor pe tranziia t5.

AP2.4.

Se consider un protocol de comunicaii, adaptat dup (Desrochers and Al-Jaar, 1993),reprezentat prin modelul din fig. AP2.4.1. Semnificaiile poziiilor i tranziiilor sunt

prezentate n tabelele AP2.4.1, respectiv AP2.4.2.1. S se precizeze succesiunea de executri de tranziii care, plecnd din marcajul iniial din

fig. AP2.4.1, asigur revenirea la acest marcaj.2. S se specifice succesiunea de evenimente corespunztoare transmiterii complete a unui

mesaj.3. S se precizeze clasa de reele Petri creia i aparine acest model.


35/256


t1

t5

t4

t6

t3

t2

p1 p2

p8p7

p3

p6

p4 p5

Fig. AP2.4.1. Modelul de tip reea Petri al unui protocol de comunicaii.

Tab. AP2.4.1. Semnificaiile poziiilor din modelul prezentat n fig. AP2.4.1.

Poziie Condiie

p1 Emitorul (E) pregtete mesajul.

p2 Buffer-ul de comunicaie (B) conine mesajul.

p3 Receptorul (R) este pregtit pentru recepie.

p4 (E) ateapt semnalul de confirmare (acknowledge ACK).

p5 (R) primete mesajul.

p6 (E) primete semnalul de confirmare (ACK).

p7 (B) conine semnalul de confirmare (ACK).

p8 (R) proceseaz mesajul primit.

Tab. AP2.4.2. Semnificaiile tranziiilor din modelul prezentat n fig. AP2.4.1.

Tranziie Eveniment

t1 (E) ncepe transmisia mesajului.

t2 (R) ncepe primirea mesajului

t3 (E) termin de primit semnalul de confirmare (ACK) i ncepe pregtirea unuinou mesaj.

t4 (R) termin primirea mesajului i ncepe transmisia semnalului de confirmare(ACK) i procesarea mesajului.

t5 (R) termin procesarea i ncepe pregtirea pentru recepionarea unui nou mesaj.

t6 (E) ncepe primirea semnalului de confirmare (ACK).


36/256

Aplicaii ale reelelor PetriO. Pstrvanu, M. Matcovschi, C. Mahulea20Soluie

1. Arborele de accesibilitate furnizat de Petri Net Toolboxn mod grafic i semnificaiamarcajelor sunt prezentate n fig. AP2.4.2. Se poate observa c, plecnd din marcajul iniialM0, succesiunea de executri de tranziii 1 2 4 5 6 3t t t t t t = asigur revenirea la acesta.

Fig. AP2.4.2.Arborele de accesibilitate pentru reeaua Petri din fig. AP2.4.1.

2. Pe baza semnificaiei fizice a tranziiilor din modelul studiat, succesiunii de tranziii determinat la punctul precedent i corespunde urmtoarea succesiune de evenimente care auloc la transmiterea complet a unui mesaj:

(E) ncepe transmisia mesajului (t1). (E) ncepe primirea semnalului de confirmare (ACK) (t2). (R) ncepe primirea mesajului (t

4).

(R) termin primirea mesajului i ncepe transmisia semnalului ACK i procesareasemnalului (t5).

(R) termin procesarea i ncepe pregtirea pentru recepionarea unui nou mesaj (t6). (E) termin de primit semnalul ACKi ncepe pregtirea unui nou mesaj (t3).

Observaie: Se poate observa c, n afar de secvena precizat anterior, mai exist ncdou secvene de executri de tranziii care, plecnd din marcajul iniial, asigur revenirea laacesta, i anume 1 2 4 6 5 3t t t t t t = i 1 2 4 6 3 5t t t t t t = . Deoarece duratele operaiilor care au

loc n sistemul fizic nu sunt implicate n modelul logic reprezentat de reeaua Petri

netemporizat, nu se poate preciza ordinea n care se vor executa tranziiile t5i t6. (Pentruinterpretarea n context temporizat, vezi AP6.2.)


37/256


3. Reeaua Petri prezentat n fig. AP2.4.1 face parte din clasa grafurilor marcate Datorittipului particular de reea, drept reprezentare grafic se poate utiliza un graf unipartit, conform

fig. AP2.4.3.

Fig. AP2.4.3. Modelul de tip graf marcat al protocolului de comunicaiireprezentat sub formde graf orientat unipartit.

AP2.5.

Se consider reeaua Petri avnd topologia din fig. AP2.5.1. Poziiile au capacitile

1( ) 1K p = i 2( ) 1K p = .

Fig. AP2.5.1. Topologia reelei Petri utilizatn AP2.5.

1. Pentru marcajul iniial 0 1( ) 1M p = i 0 2( ) 0M p = , s se execute simularea n variantaSteppentru 4 evenimente nregistrnd rezultatele simulrii ntr-un fiier de tip jurnal. Se va citijurnalul i

pastravanu aplicatii retele petri

Documents