Retele Petri Instrument de Modelare

Summary

This paper follows the deepening of Petri networks, is structured in five chpaters when you through as many definitions and applications of networks Petri.

In the first chapter recall some generalities about Petri networks, such as structure, marking Petri networks, their operating rules, state- space of a Petri network all those mentioned are structured as in a systematic way to emphasize information that we have.

Of this chapter we find out in a Petri network is composed namely a 4- tuplu

C = (P, T, I, O), then to deepen the marked Petri networks marking is an assingnment of tokens of a Petri network locations. In terms of operation of a Petri network it is controlled by the number and distribution Petri network chips, here we have the state – space of a Petri network is defined by the marking of this is the set of all markings.

In chapter two we modeling using Petri networks, which were designed especially fot these thing. Many systems, especially those with separate components, can be modeled using Petri networks. Here we have events and conditions first paragraph, where events are actions that occur in the system, their appearance is controlled by the state of system, it can be described as a lot of conditions, terms of being a predicate or a description logic system state, hence we have a condition that can be either true or false, the associated application of this paragraph pointing very detailed what i said above.

Finally reported and other behavioral elements of Petri networks such as parallelism, coordination, mutual exclusion, producer- consumer problem example.

In chapter three an analysis on Petri network that consists of safety, edges, conservation, sustainability, triggering sequences, accesible and coverage.

In chapter four which are entitled to technical analysis follow matrix equations ,

there are two major techniques for analyzing Petri networks, which will be presented in this section they provide mechanisms for solving some of the earlier problems, the main technique

Petri network is used to analyze tree accessibility, the other technique assuming matrix equations. The most important element is the tree so to speak accessibility tree of accessibility is a lot of accessibility Petri networks. Reduction to a finite representation can be achieved by several methods we must find a way to limit new bookmarks this operation is facilitated by dead nodes, ie markings where no transition not possible, they are called terminal nodes.

Last paragraph of this chapter deals with detection and error handling, recommended that the detection of errors to be in an early stage for their solution in a later stage be as easy. Methodologies developed to date, considers only detect errors in the equipment, as long as their treatment is performed on the most appropriate level. Error handling should be suitable for every level of production system, the level of equipment, errors must be determined and, if possible defective car must be repaired automatically.

Last chapter entitled nesting Petri networks represent the striking applications of this work which concludes importance, usefulness and not least dexterity working with networks Petri. Petri networks are nested Petri net where tokens can be Petri net itself, called chip networks (TN-Token Nets). Ability to change the chip network TN is following advantages:

updating collection protocols; Change processes continue; The ability to shape decisions as different parties. To consider a nested Petri net introduces special type of colored networks.

The key to proper functioning of a system are essentially: normal course, stability and error handling where possible. Nested Petri networks have gradually developed and demonstrated by customizing properties of stability.

The book presents basic concepts, properties and analysis techniques for Petri networks classical. Type workflow Petri networks by the existence of property developers ensure stability system building process flows (workflow) that ensure proper conduct correct processes.

Cuprins

Introducere ………………………………………………………………………………………………………….pag 6

Capitolul 1: Definitii fundamentale…………………………………………………………………………pag 8

1.1: Structura unei retele Petri…………………………………………………………………….pag 8

1.2: Marcajele retelelor Petri………………………………………………………………………pag 10

1.3: Reguli de functionare pt retelele Petri……………………………………………………pag 11

1.4: Spatiul starilor unei retele Petri…………………………………………………………….pag 12

Capitolul 2: Modelarea cu ajutorul retelelor Petri……………………………………………………..pag 16

2.1: Evenimente si conditii…………………………………………………………………………pag 16

2.2: Concurenta si conflicte………………………………………………………………………..pag 20

2.3: Alte elemente comportamentale……………………………………………………………pag 21

Capitolul 3: Analiza retelelor Petri…………………………………………………………………………pag 27

3.1: Proprietati si caracteristici……………………………………………………………………pag 27

3.2: Secvente de declansare………………………………………………………………………..pag 30

3.3: Accesibilitate si acoperire……………………………………………………………………pag 31

Capitolul 4:Tehnici de analiza……………………………………………………………………………….pag 32

4.1: Arbore si accesibilitate………………………………………………………………………..pag 32

4.2: Siguranta si marginire…………………………………………………………………………pag 34

4.3: Detectarea si tratarea erorilor……………………………………………………………….pag 35

Capitolul 5: Imbricarea retelelor Petri…………………………………………………………………….pag 38

5.1: Retele fluxuri de lucru extinse……………………………………………………………..pag 39

5.2: Stabilitatea retelelor EWF……………………………………………………………………pag 39

5.3: Operatii cu retele EWF……………………………………………………………………….pag 40

5.4: Imbricarea retelelor…………………………………………………………………………….pag 42

5.5: Tratarea erorilor…………………………………………………………………………………pag 46

Concluzii ……………………………………………………………………………………………………………pag 48

Bibliografie………………………………………………………………………………………………………….pag 49

Introducere

Rar vom gasi o ramificatie a Informaticii în care cercetarea sa stagneze sau sa se desfasoare anevoios. Retelele Petri [16], [13] nu fac exceptie–dovada sunt multiplele aplicatii practice dezvoltate pe baza acestora. În general, însă, Retele Petri sunt considerate mai dificil de abordat, dar trasatura mea definitorie o constituie predilectia pentru tot ceea ce înseamnă o provocare, prin urmare în Retelele Petri am văzut o oportunitate în acest sens.

Sistemele cu evenimente discrete s-au individualizat ca direcție proprie de cercetare în ultimii 20 – 30 de ani, având un impact considerabil asupra dezvoltării tehnologice din diverse arii ale ingineriei, cum ar fi: sisteme de fabricație, sisteme de transport, sisteme de comunicații, sisteme de operare și platforme software dedicate, precum și asupra controlului de tip procedural a numeroaselor clase de procese automatizate. Domeniul sistemelor cu evenimente discrete se constituie dintr-o serie de resurse distincte ca: teoria automatelor și a limbajelor formale, teoria rețelelor Petri, teoria sistemelor de așteptare, teoria algebrică a sincronizării, analiza perturbațiilor.

In lucrare se prezinta fundamentul teoretic al rețelelor Petri [13], [16], care pe parcursul celor aproape cinci decenii de la prezentarea tezei de doctorat a matematicianului german Carl Adam Petri, au arătat o deosebită flexibilitate în abordarea numeroaselor tipuri de probleme practice, precum și o mare capacitate de extindere ca sferă de operare, prin înglobarea unor puncte de vedere tot mai complexe.

Rețelele Petri au fost introduse de către Carl Adam Petri în anii 60, la acel moment modelele matematice folosite pentru modelarea sistemelor reale distribuite erau sistemele tranziționale de tip stare-acțiune (automate finite). Pornind de la aceste modele C.A. Petri a introdus ideea de modelare a sistemelor distribuite, divizând sistemul în anumite elemente care ar caracteriza stările locale ale sistemului modelat și caracterizând evoluția sistemului printr-o execuție concurentă a unor acțiuni locale. Ele formalizează descrierea concurenței, conflictului și sincronizării în sistemele distribuite într-o manieră inductivă.

În multe domenii de cercetare comportarea sistemului real se studiază nu direct pe sistem, ci indirect, cu ajutorul modelului. Modelul – întrunește proprietățile caracteristice pentru obiectul sau sistemul studiat. Studiind modelul sistemului dat se pot deduce informații noi fără a avea cheltuieli costisitoare.

Teoria rețelelor Petri s-a dezvoltat în două direcții [13]:

1.Teoria formală a rețelelor Petri – care elaborează mijloacele, metodele și noțiunile necesare pentru utilizarea rețelelor Petri.

2. Teoria aplicativă a rețelelor Petri – care are drept scop utilizarea rețelelor Petri la modelarea nemijlocită a sistemelor, analiza lor și obținerea rezultatelor.

Modelarea sistemelor distribuite cu ajutorul rețelelor Petri se efectuează la nivel de stare: se determină ce acțiuni se produc în sistem, care stări preced acestor acțiuni și în ce stări va trece sistemul după producerea acțiunilor. Simulând modelul de stări prin rețele Petri se obține descrierea comportamentului sistemului.

Rețelele Petri au cunoscut o dezvoltare vertiginoasă, deoarece bineficiază de trei atuuri fundamentale: simplitate, generalitate, adaptabilitate.

Analiza rezultatelor obținute prin simulare permite să cunoaștem stările în care s-a aflat sau nu sistemul, care sunt, în principiu, stările neaccesibile, însă o astfel de analiză nu oferă informații despre caracteristicile numerice care determină stările sistemului.

De aceea au apărut tipuri noi de rețele Petri care încearcă să înlăture aceste neajunsuri – rețele Petri cu priorități, rețele Petri colorate, rețele Petri cu inhibiție, rețele Petri cu auto-modificare, rețele Petri cu resetare, rețele Petri FIFO, rețele Petri controlate prin cozi, rețele Petri controlate prin automate, rețele Petri condiționale, rețele Petri selective, rețele Petri cu salturi, rețele Petri temporizate (ultimele reprezintă unul din tipurile de rețele Petri supuse studiului în prezenta lucrare).

În prezent rețelele Petri au numeroase aplicații și sunt utilizate în diverse domenii: inginerie, modelarea proceselor de afaceri, deoarece dispun de o reprezentare grafică foarte accesibilăstemelor cu evenimente discrete se constituie dintr-o serie de resurse distincte ca: teoria automatelor și a limbajelor formale, teoria rețelelor Petri, teoria sistemelor de așteptare, teoria algebrică a sincronizării, analiza perturbațiilor.

In lucrare se prezinta fundamentul teoretic al rețelelor Petri [13], [16], care pe parcursul celor aproape cinci decenii de la prezentarea tezei de doctorat a matematicianului german Carl Adam Petri, au arătat o deosebită flexibilitate în abordarea numeroaselor tipuri de probleme practice, precum și o mare capacitate de extindere ca sferă de operare, prin înglobarea unor puncte de vedere tot mai complexe.

Rețelele Petri au fost introduse de către Carl Adam Petri în anii 60, la acel moment modelele matematice folosite pentru modelarea sistemelor reale distribuite erau sistemele tranziționale de tip stare-acțiune (automate finite). Pornind de la aceste modele C.A. Petri a introdus ideea de modelare a sistemelor distribuite, divizând sistemul în anumite elemente care ar caracteriza stările locale ale sistemului modelat și caracterizând evoluția sistemului printr-o execuție concurentă a unor acțiuni locale. Ele formalizează descrierea concurenței, conflictului și sincronizării în sistemele distribuite într-o manieră inductivă.

În multe domenii de cercetare comportarea sistemului real se studiază nu direct pe sistem, ci indirect, cu ajutorul modelului. Modelul – întrunește proprietățile caracteristice pentru obiectul sau sistemul studiat. Studiind modelul sistemului dat se pot deduce informații noi fără a avea cheltuieli costisitoare.

Teoria rețelelor Petri s-a dezvoltat în două direcții [13]:

1.Teoria formală a rețelelor Petri – care elaborează mijloacele, metodele și noțiunile necesare pentru utilizarea rețelelor Petri.

2. Teoria aplicativă a rețelelor Petri – care are drept scop utilizarea rețelelor Petri la modelarea nemijlocită a sistemelor, analiza lor și obținerea rezultatelor.

Modelarea sistemelor distribuite cu ajutorul rețelelor Petri se efectuează la nivel de stare: se determină ce acțiuni se produc în sistem, care stări preced acestor acțiuni și în ce stări va trece sistemul după producerea acțiunilor. Simulând modelul de stări prin rețele Petri se obține descrierea comportamentului sistemului.

Rețelele Petri au cunoscut o dezvoltare vertiginoasă, deoarece bineficiază de trei atuuri fundamentale: simplitate, generalitate, adaptabilitate.

Analiza rezultatelor obținute prin simulare permite să cunoaștem stările în care s-a aflat sau nu sistemul, care sunt, în principiu, stările neaccesibile, însă o astfel de analiză nu oferă informații despre caracteristicile numerice care determină stările sistemului.

De aceea au apărut tipuri noi de rețele Petri care încearcă să înlăture aceste neajunsuri – rețele Petri cu priorități, rețele Petri colorate, rețele Petri cu inhibiție, rețele Petri cu auto-modificare, rețele Petri cu resetare, rețele Petri FIFO, rețele Petri controlate prin cozi, rețele Petri controlate prin automate, rețele Petri condiționale, rețele Petri selective, rețele Petri cu salturi, rețele Petri temporizate (ultimele reprezintă unul din tipurile de rețele Petri supuse studiului în prezenta lucrare).

În prezent rețelele Petri au numeroase aplicații și sunt utilizate în diverse domenii: inginerie, modelarea proceselor de afaceri, deoarece dispun de o reprezentare grafică foarte accesibilă și au o semantică bine definită care permite o analiză formală a comportamentului și proprietăților sistemelor modelate.

În lucrare sunt utilizate metodele teoriei invarianților algebrici și metodele structurilor de accesibilitate și de acoperire pentru verificarea proprietăților structurale ale claselor de rețele Petri studiate.

Studierea proprietăților rețelelor Petri temporizate, formularea și rezolvarea noilor probleme, precum și găsirea unor clase cât mai largi de rețele Petri temporizate pentru care proprietățile lor pot fi verificate pe baza studierii proprietăților rețelelor Petri suport respective (netemporizate).

S-a urmarit:

1. Studierea tehnicilor de analiză a rețelelor Petri temporizate cum ar fi: tehnica invarianților, structurile de accesibilitate și de acoperire.

2. Decidabilitatea unor probleme puse în legătură cu rețelele Petri temporizate: viabilitate, mărginire, accesibilitate, acoperire, pseudo-viabilitate.

3. Definirea rețelelor Petri temporizate cu salturi și a structurilor de acoperire respective.

4. Decidabilitatea unor probleme puse în legătură cu rețele Petri temporizate cu salturi: accesibilitate, acoperire, mărginire, viabilitate, reducere.

5. Definirea rețelelor fluxuri de lucru temporizate precum și a proprietăților acestora: corectitudinea, mărginirea, viabilitatea.

6. Decidabilitatea proprietății de corectitudine a WF rețelelor temporizate.

7. Definirea mulțimii proceselor pentru rețele Petri temporizate.

Utilizand noțiunea de rețea flux de lucru temporizată permite verificarea proprietății de corectitudine a rețelei Petri. Considerând proprietățile de viabilitate și mărginire drept unele din cele mai importante într-un sistem distribuit sunt teoreme care fac legătura dintre aceste proprietăți și proprietatea de corectitudine a unor clase mai restricționate de rețele flux de lucru temporizate. Utilizând aceste teoreme se poate arăta că problema corectitudinii este decidabilă pentru aceste clase. A fost introdusă noțiunea de mulțime a proceselor unei rețele flux de lucru temporizate, precum și algoritmul determinării acestei mulțimi. De se poate arăta că pentru o anumită clasă de rețele flux de lucru temporizate mulțimea proceselor ei coincide cu mulțimea proceselor rețelei flux de lucru suport respective.

Lucrarea are ca prim obiectiv prezentarea conteptelor de baza ale retelelor Petri, a instrumentelor de analiza a lor insotite de exemple ilustrative. Al obitctiv este acela de a construi un model pentru traterea exceptiilor intr-un proces de fabricatie. In acest scop s-au preluat extensii ale retelelor Petri [13],[13], [13], [13] [13] si [15]. Particularitetile cerute de compexitatea sistemului modelat au impus utilizarea conceptelor retelelor Petri colorate [7] si [20]. Utilizand retele workflow extinse si imbricate, s-a dezvoltat modelul in care exceptiile sunt elemente de retele imbricate. Ca si instrument de slimulare s-a utilizat un produs [23] dezvoltat la Universitatea Tehnica din Iasi.

CAPITOLUL 1

DEFINITII FUNDAMENTALE

1.1. Structura unei retele Petri

O retea Petri este compusa [13], [16] din patru parti – o multime de locatii S;

– o multime da tranzitii T;

– o functie de intrare I;

– o functie de iesire O;

Functiile de intrare si iesire sunt relatii intre T si S.

Functia de intrare I este o functie de la o tranzitie la o colectie de locatii care poarta numele de locatii de intrare ale tranzitiei.

Functia de iesire O este o functie de la o tranzitie la o colectie de locatii care poarta numele de locatii de iesire ale tranzitiei.

Teoria rețelelor Petri a fost inițiată de Carl Adam Petri în 1962 în încercarea sa de a dezvolta o teorie matematică adecvată studierii sistemelor distribuite în care comunicarea, sincronizarea, paralelismul și concurența ocupă un loc important. Aplicațiile rețelelor Petri în domenii inginerești, social-economice sau învățământ le-au propulsat în centrul atenției cercetătorilor la foarte scurt timp de la apariția lor. Comparate cu alte modele orientate în mod direct spre modelarea limbajelor de programare concurente, rețelele Petri si-au dovedit eficiența și într-un cadru de acest gen.

Definitia 1: O structura de retea Petri C este un 4- tuplu C=(P,T,I,O), unde:

P= {} este o multime finita de locatii, n ≥ 0;

T= {} este o multime finita de tranzitii, m ≥ 0;

Multimea locatiilor si multimea tranzitiilor sunt disjuncte P∩T=.

I:T este functia de intrare, o functie de la multimea tranzitiilor la colectia de locatii.

O:T este functia de iesire, o functie de la multime tranzitiilor la colectia de locatii.

Definitia 2:Definim functia de intrare I si functia de iesire O dupa cum urmeaza:

I:T unde:

#(t

Definitia 3: Un graf de retea Petri este un “multigraf orientat bipartit” G= (V,A) unde V=este o multime de varfuri si A={} este un multiset de arce directionate .

Reteua V poate fi partitionata in doua retele disjuncte P si T astfel incat

V= P si pentru fiecare arc distinct daca atunci fie .

Mai jos vom reprezenta grafic un graf de reta Petri care corespunde urmatoarei structuri reprezentata ca un 4-tuplu C=(P,T,I,O), unde:

P ={}

T ={}

FIG 1:Un graf de retea Petri

FIG 2: Duala retelei Petri din figura 1

Duala unei retele Petri C =(T, P, I, O) rezultata din interschimbarea locatiilor si tranzitiilor. Structura grafului se pastreaza, interschimband cercurile si barele grafului pentru a indica schimbarea suferita. Cea de-a doua figura 2 indica duala retelei din figura 1. Duala este o afirmatie, un punct de vedere, des utilizat in teoria grafurilor si de asemenea un concept interesant vizavi de retelele Petri, dar fiind un proces mai complicat, fiind greu de definit mai ales duala unei retele Petri marcate, nu s-a folosit in cercetarea asupra retelelor Petri, mai jos incercam sa aprofundam retelele Petri marcate.

1.2. Marcajele retelelor Petri

Un marcaj este o asignare de jetoane a locatiilor unei retele Petri. Conceptul de jeton este fundamental in teoria retelelor Petri (la fel locatiile si tranzitiile). Jetoanele sunt asignate locatiilor unei retele Petri si pot fi gandite ca apartinand acestora.

Definitia 4:Un marcaj al unei retele Petri C = (P, T, I, O) este o functie de la multimea locatiilor P la multimea numerelor naturale N, si anume .

Marcajul poate fi, de asemenea, definit ca un vector n-dimensional unde n= card(P),

Definitiile apartenente uni marcaj ca o functie si ca un vector se bazeaza, in mod evident, pe relatia .Deoarece numarul de jetoane care poate asignate unei locatii a unei retele Petri este nemarginit, exista o infinitate de marcaje pentru o retea Petri. Multimea tuturor marcajelor pentru o retea Petri cu n locatii este multimea tuturor vectorilor n- dimensionali din . Aceasta multime infinita este bineinteles nenumarabila.

1.3.Reguli de functionare pentru retele Petri

Functionarea unei retele Petri este controlata de numarul si distributia jetoanelor in reteaua Petri [4]. O retea Petri se executa prin declansarea tranzitiilor. O tranzitie se declanseza prin mutarea jetoanelor din locatiile de intrare si crearea de noi jetoane care sunt distribuite in locatiile de iesire. O tranzitie este posibila daca fiecare dintre locatiile sale de intrare contine un numar de jetoane mai mare sau egal cu numarul de arce de la acea locatie la tranzitie. In locatiile de intrare sunt jetoane care permit o tranzitie ele fiind jetoane de validare.

Definitia 5: O tranzitie dintr-o retea Petri marcata C= (P, T, I, O) cu marcajul este permisa daca pentru toate .

O tranzitie se declanseaza prin mutarea tuturor jetoanelor posibile din locatiile de intrare si depozitarea lor in fiecare locatie de iesire, cate un jeton pentru fiecare arc de la tranzitie la locatie.

Definitia 6: O tranzitie intr-o retea Petri marcata cu marcajul se poate declansa de fiecare data cand este posibila. Declansarea unei tranzitii posibile produce un nou marcaj definit de relatia:

FIG 3:Schimbarea marcajului unei locatii cand o tranzitie se declanseaza. Fiecare locatie poate sa nu fie intrare sau iesire a tranzitiei, bineinteles in figura avem doar cazul in care multiplicarea este zero sau unu.

Exemplu: avem urmatoarea figura:

FIG 4: Retea Petri marcata pentru a arata regulile de declansare.

Tranzitiile sunt posibile.

Deci, consideram reteaua Petri marcata, ca in figura 4 . Cu acest marcaj, trei tranzitii sunt posibile si anume , tranzitia tnefiind posibila deoarece nu se afla nici un jeton in nici una din locatiile aferente si anume care sunt amandoua intrari ale tranzitiei t. Putem observa ca declansarea lui muta cate un jeton din fiecare intrare si depoziteaza cate un jeton in fiecare iesire.

1.4.Spatiul starilor unei retele Petri

starea unei retele Petri este definita de marcajul sau

spatiul starilor unei retele Petri este multimea tuturor marcajelor, adica , schimbarea de stare cauzata de declansarea unei tranzitii este definita de o functie de schimbare δ numita functie de tranzitie.

Definitia 7: functia de tranzitie δ: pentru o retea Petri C = (P, T, I, O) cu marcajul si tranzitiile este definita daca si numai daca .

Data fiind o retea Petri C = (P, T, I, O) cu marcajul initial , putem executa reteaua Petri prin declansari succesive de tranzitii. Declansarea unei tranzitii posibile in marcajul initial produce un nou marcaj . In marcajul nou, putem declansa orice tranzitie posibila, si anume , ceea ce determina aparitia unui nou marcaj . Si de aici putem continua cu aceasta operatie atata timp cat exista cel putin o tranzitie posibila in fiecare marcaj. Daca ajungem la la un marcaj in care nici o tranzitie nu este posibila, atunci nici o tranzitie nu poate sa se declanseze, si deci functia de tranzitie este nedefinita pentru toate tranzitiile, de aici deducem ca executia trebuie sa se opreasca.

Definitia 8: Pentru o retea Petri C = (P, T, I, O) cu marcajul , un marcaj este „direct accesibil”din daca exista o tranzitie astfel incat .

Definitia 9: Multimea de accesibilitate pentru o retea Petri C = (P, T, I, O) cu marcajul este cea mai mica multime de marcaje definita dupa cum urameaza:

–

– daca

Mai jos prezentam o aplicatie pentru a ne familiariza cu ceea ce definesc retelele Petri:

A. 1.

Pentru rețelele Petri cu topologia și marcajul inițial indicat în fig. AP2.1.1, să se precizeze

care dintre tranziții sunt validate și marcajul ce rezultă după executarea fiecăreia din aceste

tranziții în cazurile următoare:

1. rețelele au capacități infinite;

2. rețelele au capacități finite după cum urmează:

(i) pentru rețeaua din fig. A.1. (a): K( p1) = K( p3 ) = 2 , K( p2 ) =1;

(ii) pentru rețeaua din fig. A.2. (b): K( p1) = K( p2 ) = K( p3 ) =1;

(iii) pentru rețeaua din fig. A.3. (c): K( p1) = 2 , K( p2 ) = 3, K( p3) = K( p4 ) =1.

Soluție:

1. Aplicând regula simplă a tranziției rețelei din fig. 29.(a) cu marcajul inițial M0 = (2,1,0) se obține:

• tranziția t1 este validată deoarece M0 (p1) >W( p1,t1) ; prin executarea lui t1 se ajunge

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

• tranziția t2 este validată deoarece M0( p2) =W( p2 ,t2) ; prin executarea lui t2 se

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

• tranziția t3 este validată deoarece M0( p1) >W(p1,t3) și M0( p2) =W(p2 ,t3) ; prin

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

Analog, pentru rețeaua din fig. A.1.(b) cu marcajul inițial M0 = (1,1,0) rezultă:

• tranziția t1 este validată deoarece M0( p1) >W( p1,t1) ; prin executarea lui t1 se ajunge

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

• tranziția t2 este validată deoarece M0( p2) =W( p2 ,t2 ) ; prin executarea lui t2 se

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

• tranziția t3 este validată deoarece M0( p1) >W( p1,t3) și M0 (p2) =W(p2 ,t3) ; prin

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

Pentru rețeaua din fig. A.1.(c) cu marcajul inițial M0 = (2,0,0,1) , aplicarea regulii simple

a tranziției conduce la:

• tranziția t1 este validată deoarece M0 (p1) >W (p1,t1) ; prin executarea lui t1 se ajunge

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

• tranziția t5 este validată deoarece M0 (p4) =W(p4 ,t5) ; prin executarea lui t2 se

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

2. Ținând cont de marcajele la care s-ar ajunge prin executarea tranzițiilor validate determinate la punctul 1 și de capacitățile finite precizate ale pozițiilor, prin aplicarea regulii

stricte a tranziției se obține:

(i) pentru rețeaua din fig.29.(a), singura tranziție validată este t3 deoarece:

M0 ( p1 ) >W ( p1,t3 ) , M0 (p2) =W (p2 ,t3) și K (p3) > M0( p3) +W (t3, p3) ; prin

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

(ii) pentru rețeaua din fig.29.(b) sunt validate:

• tranziția t2 deoarece M0( p2) =W(p2 ,t2) ; prin executarea lui t2 se ajunge

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

• tranziția t3 deoarece M0 (p1) >W( p1,t3) , M0 (p2 )=W( p2 ,t3) și

K (p3) = M0( p3) +W(t3, p3) ; prin executarea lui t3 se ajunge din M0 la

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

(iii) pentru rețeaua din fig.29.(c) nici una dintre tranziții nu este validată.

CAPITOLUL 2

MODELAREA CU AJUTORUL RETELELOR PETRI

Retelele Petri au fost proiectate si folosite mai ales pentru modelare [1], [3]. Multe sisteme, dar mai ales cele cu componente separate, pot fi modelate cu ajutorul retelelor Petri, sistemele pot fi de tipuri diferite: computer hardware, sisteme fizice, computer software, etc. In particular retelele Petri pot modela fluxul de informatii sau alte resurse dintr-un sistem.

2.1. Evenimente si conditii

Evenimentele si conditiile permit reperzentarea unui sistem din punctul de vedere al retelelor Petri, si putem defini sau detalia aceste doua aspecte, in felul urmator:

evenimentele sunt actiuni care au loc in sistem, aparitia lor fiind controlata de starea sistemului, ea putand fi descrisa ca o multime de conditii.

conditiile fiind un predicat sau o descriere logica a starii sistemului, de aici avem ca o conditie poate fi fie adevarata fie falsa.

preconditii reprezinta faptul ca evnimentele sunt actiuni,ele se pot produce si pentru ca ele sa se poata produce este necesar ca anumite conditii sa fie adevarate.

aparitia evenimentului poate determina ca preconditiile sa nu mai fie adevarate, si poate stabili ca alte conditii, numite postconditii sa fie adevarate.

Exemplu: consideram problema modelarii unui atelier simplu, atelierul asteapta pana cand apare un ordin si apoi il prelucreaza si il trimite afara pentru distribuire. Conditiile pentru sistem sunt:

atelierul este in asteptare

a sosit un ordin si este in asteptare

atelierul prelucreaza ordinul

prelucrarea ordinului sa incheiat

Evenimentele pot fi:

sosirea unui ordin

atelierul incepe prelucrarea ordinului

atelirul termina prelucrarea ordinului

ordinul este trimis spre distribuire

Preconditiile evenimentului 2 sunt evidente: a si b.

Postconditia evenimentului 2 este c

Similar putem defini preconditiile si postconditiile celorlalte evenimente si sa construim urmatorul tabel cu rezultatele obtinute:

O astfel de reprezentare asupra unui sistem poate fi usor modelata ca o retea Petri, conditiile sunt modelate ca locatii si evenimentele sunt modelate prin tranzitii. Intrarile unei tranzitii sunt preconditiile evenimentului corespunzator, iesirile sunt postconditiile. Aparitia unui eveniment eclanseaza tranzitia corespunzatoare, o conditie adevarata este data de existenta unui jeton in locatia corespunzatoare conditiei, cand o tranzitie declanseaza, muta jetoanele de validare reprezentand indeplinirea postconditiilor.

Avem mai jos reteaua Petri din figura 5 care este un model de retea Petri pentru exemplul de mai sus cu atelierul.am etichetat fiecare tranzitie si locatie cu evenimentul sau conditia corespunzatoare.

FIG 5:Un model de retea Petri pentru un atelier simplu

Bineinteles ca putem modela si sisteme mai complicate, atelierul poate avea trei masini diferite si doi operatori si . Operatorul poate opera masinile , iar operatorul poate opera masinile . Lucrarile necesita doua stagii de prelucrare, mai intai acestea trebuie prelucrate de masina , apoi de oricare dintre celelalte doua masini.

Deci avem sistemul cu urmatoarele conditii:

A sosit o lucrare si asteapta sa fie prelucrata de

O lucrare a fost prelucrata de si asteapta sa fie prelucrata si de celelalte masini

Prelucrarea lucrarii s-a terminat

Masina este libera

Masina este libera

Masina este libera

Operatorul este liber

Operatorul este liber

Masina este operata de

Masina este operata de

Masina este opearata de

Masina este operata de

Aici pot aparea urmatoarele evenimente:

Soseste un ordin

Operatorul porneste prelucrarea lucrarii pe masina

Operatorul termina prelucrarea lucrarii pe masina

Operatorul porneste prelucrarea lucrarii pe masina

Operatorul termina prelucrarea lucrarii pe masina

Operatorul porneste prelucrarea lucrarii pe masina

Operatorul termina prelucrarea lucrarii pe masina

Operatorul porneste prelucrarea lucrarii pe masina

Operatorul termina prelucrarea lucrarii pe masina

Ordinul de livrare este trimis

Preconditiile si postconditiile fiecarui eveniment sunt urmatoarele:

Reteaua Petri pentru acest sistem este reprezentata in figura de mai jos:

FIG 6: Un exemplu de atelier mai complex, modelat ca o retea Petri

Un exemplu similar poate fi prezentat pentru un sistem de calcul care proceseaza sarcini de la un dispozitiv de intrare si scoate rezultatele pe un dispozitiv de iesire, sarcinile apar pe dispozitivul de intrare, cand procesorul este liber si se afla o sarcina pe dispozitivul de intrare atunci incepe prelucrarea sarcinii. Dupa ce prelucrarea este completa, acesta este trimisa pe dispozitivul de iesire, iar procesorul continua operatia cu o alta sarcina daca mai exista vreuna disponibila sau asteapta pana cand o noua sarcina pe dispozitivul de iesire, acest sistem poate fi modelat ca in figura de mai jos:

FIG 7: Modelarea ca o retea Petri a unui sistem de calcul simplu.

2.2.Concurenta si conflicte

O problema este paralelismul inerent, in modelul de retea Petri, doua evenimente care sunt permise si nu interactioneaza se pot produce independent, nu este necesara sincronizarea evenimentelor, decat daca acest lucru este cerut de catre sistemul care este modelat[13] [7].

O alta caracteristica majora a retelelor Petri este natura lor asincrona, nu exista o masura inerenta pentru fluxul de timp intr-o retea Petri. Din punct de vedere logic definim o ordine partiala a aparitiei evenimentelor. Evenimentele consuma cantitati diferite de timp in viata reala si variabilitatea lor este reflectata in modelele realizate cu ajutorul retelelor Petri prin faptul ca se realizeaza controlul secventei de evenimente fara a depinde de notiunea de timp. Astfel in figura 7 evenimentul „un job este terminat” trebuie sa fie ulterior evenimentului „a

inceput un job” , totusi nici o informatie nu este data si nici necesara, referitor la cantitatea de timp necesara pentru executarea unei sarcini. Ordinea aparitiei evenimentelor este una este una din cele mai multe permise de structura de baza, acestea conduc la un nedeterminism aparent in executia retelelor Petri, daca la orice moment este posibila mai mult de o tranzitie, atunci oricare dintre cele cateva tranzitii posibile poate fi urmatoarea ce se va declansa.

Declansarea nederteminista si nesimultana a tranzitiilor in modelarea sistemelor concurente este indicata de figura 8, in acesta situatie cele doua tranzitii posibile nu se afecteaza reciproc in nici un fel.

FIG 8: Concurenta FIG 9: Conflict

Cele doua tranzitii se pot Aici tranzitiile sunt in conflict deoarece

declansa in orice ordine declansarea oricareia jetonul din pva fi

mutat,astfel imposibila declansarea celeilalte

In figura 9 avem situatia in care simultaneitatea este mai dificil de manevrat, care poate fi controlata prin definirea de evenimente care nu apar simultan.

Cu toate aceste informatii pe care le-am mentionat putem intelege complet sistemele ce urmeaza sa fie modelate cu ajutorul retelelor Petri pentru a realiza o modelare corecta a comportamentului sistemului. Din nefericire, multe dintre cercetarile asupra retelelor Petri s-au axat asupra proprietatilor unei retele date sau ale unei clase de retele.

2.3. Alte elemente comportamentale

2.3.1 Paralelism

Paralelismul (sau concurenta) il putem introduce acum in mai multe moduri, consideram cazul a doua procese concurente, fiecare dintre ele putand fi reprezentat printr-o retea Petri, de aceea reteaua Petri compusa, care este pur si simplu reuniunea retelelor petri pentru fiecare din cele doua procese, poate reprezenta executia concurenta a celor doua procese.

In figura 10 este exemplificat grafic procesul de paralelism sau concurenta.

FIG 10: Paralelism sau concurenta

2.3.2. Coordonare

Paralelismul este util in solutionarea unei probleme numai daca procesele concurente pot coopera in solutionarea problemei. O astfel de cooperare presupune informatii si resurse comune pentru procese. Acest acces comun trebuie controlat pentru a asigura functionarea corecta a sistemului. Diverse probleme de coordonare s-a propus in literatura pentru a ilustra tipurile de probleme care pot aparea intre procesele ce coopereaza.

2.3.3. Problema excluziunii mutuale

Plecam de la presupunerea ca anumite procese au acces comun la o variabila, inregistrare, fisier sau alta data interna. Putem citi valoarea datei la care se are acces comun sau putem scrie o noua valoare, aceste doua operatii sunt de obicei operatii primare, adica pentru a modifica valoarea datei cu acces comun, un proces trebuie mai inatai sa citeasca vechea valoare, apoi sa calculeze noua valoare si in cele din urma sa scrie in loc noua valoare. Dar pot sa apara probleme daca doua procese incearca sa execute in acelasi timp aceasta secventa de instructiuni. Pentru a preveni acest tip de probleme, este necesara folosirea unui mecanism pentru excluziunea mutuala care este o tehnica de a defini un cod de intrare si iesire astfel incat un singur proces sa poata avea acces la o resursa comuna la un moment dat. Codul care apeleaza obiectul cu acces comun si are nevoie de protectie pentru a nu intra in interferenta cu alte procese se numeste sectiune critica. Deci avem ca in momentul in care un proces isi executa portiunea sa „critica” asteapta mai intai ca nici un alt proces sa nu isi execute aceasta portiune apoi „blocheaza” accesul la acesta, prevenind accesul altui proces in portiunea sa critica. In cele din urma intra in portiunea sa critica, o executa si atunci cand o paraseste o „deblocheaza” pentru a permite altor procese sa o acceseze. Aceasta problema este rezolvata cu ajutorul unei retele Petri cum avem in figura de mai jos:

FIG 11: excluziunea mutuala- accesul la scetiunea critica a celor doua procese este controlat astfel incat cele doua procese nu- si pot executa simultan secitunea critica.

Locatia m reprezinta permisiunea de a intra in sectiunea critica. Pentru ca un proces sa intre in sectiunea critica, trebuie sa aiba un jeton in care sa anunte ca se doreste intrarea in sectiunea critica, si de asemenea trebuie sa existe un jeton in m care sa semnalizeze permisiunea de a intra, daca ambele procese doresc sa intre simultan atunci tranzitiile sunt in conflict si numai una dintre ele se poate declansa.

2.3.4. Problema producator– consumator

Aceasta problema implica de asemenea un obiect la care avem acces comun, doar ca de aceasta data acest obiect este specificat a fi un buffer. Procesul producator creeaza obiecte care sunt puse in buffer, procesul consumator asteapta pana cand un obiect a fost pus in buffer, il ia de acolo si il consuma.

FIG.12. Problema producator/consumator modelata ca o retea Petri.

O varianta la aceasta problema este problema multipli producatori/ multipli consumatori, mai multi producatori produc articole care sunt plasate intr-un buffer comun pentru mai multi consumatori. Figura 12 reprezinta reteaua Petri solutie a acestei probleme unde pornim sistemul cu s jetoane in locatia initiala a procesului producator si t jetoane in locatia initiala a procesului producator si t jetoane in locatia initiala a procesului consumator.

FIG.13.Problema multipli producatori/multipli consumatori. Sunt s producatori si t consumatori.

O alta varianta este problema producator/consumator pentru un buffer finit. In aceasta versiune a problemei producator/ consumator, se cunoaste ca buffer-ul dintre producator si consumator este finit, adica are numai n locatii pentru articole. De aceea producatorul nu poate intodeauna sa produca atat de rapid pe cat doreste, dar trebuie sa astepte daca consumatorul este incet si buffer-ul plin.

Figura de mai jos este o solutie la aceasta problema. Bufferul finit este reprezentat de doua locatii: B reprezinta numarul de articole care au fost produse dar nu au fost inca consumate iar C reprezinta numarul de locatii libere in buffer, initial C are n jetoane si B nici unul.

Daca bufferul se umple, atunci C nu va avea nici un jeton, iar B va avea n jetoane. In acest punct, daca producatorul incearca sa puna un alt articol in buffer, va fi oprit deoarece nu exista nici un jeton in C pentru a valida aceasta tranzitie.

FIG.14. Problema producator/consumator cu buffer finit.bufferul, reprezentat prin locatiile B si C este limitat la cel mult n articole.

2.3.5. Problema filozofilor care iau masa impreuna.

Aceasta problema a fost sugerata de Dijkstra(1968) si priveste (in cazul nostru cinci) filozofi care gandesc si mananca alternativ. Filozofii sunt asezati la o masa mare rotunda pe care se afla o cantitate mare de preparate chinezesti. Intre fiecare filozof se afla cate un betisor. Totusi pentru a putea manca sunt necesare doua betisoare, de aceea fiecare filozof trebuie sa ridice ambele betisoare, adica atat pe cel situat in stanga sa cat si pe cel din dreapta sa.

Figura de mai jos ilustreaza reteaua Petri solutie a acestei probleme, locatiile c1,…,c5 reprezinta betisoarele, fiecare fiind liber are cate un jeton in marcajul initia. Fiecare filozof este reprezentat prin doua locatii Mi si Ei reprezentand starile de meditare, respectiv cea in care mananca. Pentru a trece de la starea de meditatie la cea in care mananca ambele betisoare trebuie sa fie disponibile, asa dupa cum modelam mai jos.

FIG.15. Problema filozofilor care iau masa impreuna. Fiecare filozof este modelat prin doua locatii meditare(Mi) si mancare (Ei).

CAPITOLUL 3

Analiza retelelor Petri

3.1.Proprietati si caracteristici

Am ilustrat puterea retelelor Petri, ele sunt capabile sa modeleze o mare varietate de sisteme, reprezentand corect interactiunile intre diferitele tipuri de actiuni care pot aparea.

Totusi modelarea ca atare are o utilitate marginita, este necesara analiza sistemului modelat, aceasta modelare conducand catre concluzii importante asupra comportamentului sistemului modelat, de aceea in acest capitol vom prezenta tehnici de analiza pentru retelele Petri [13] [16], [7].

Siguranta

Pentru o retea Petri care modeleaza un dispozitiv real, una dintre cele mai importante proprietati este siguranta, o locatie din reteaua Petri este sigura daca numarul de jetoane din acea locatie nu este niciodata mai mare decat 1.

Definitia 10. O locatie a unei retele Petri C=(P,T,I,O) cu marcajul initial este sigura daca pentru toate , o retea este sigura daca fiecare locatie din retea este sigura.

Atata timp cat o locatie nu este intrare multipla sau iesire multipla a unei tranzitii, este posibila fortarea acelei locatii ca sa fie sigura, tranzitiile care folosesc ca intrare sai iesire, se modifica dupa cum urmeaza:

daca atunci se adauga .

daca atunci se adauga

Scopul acestei noi locatii este acela de a reprezenta conditia „ este goala ”, de aceea cele doua sunt complementare, adica are un jeton numai daca nu are nici unul, si invers.

Orice tranzitie care muta un jeton din trebuie sa depoziteze unul in si viceversa.

O locatie care are o multiciplitate de doi pentru o tranzitie va primi doua jetoane la declansarea tranzitiei respective, si de aceea nu poate sa fie sigura, de exemplu in figura 16 avem o retea Petri simpla pe care o fortam sa fie sigura figura 17.

FIG.16. Retea Petri care nu este sigura.

FIG.17. Reteaua Petri din figura de mai sus „fortata” sa fie sigura.

Marginire

Siguranta este un caz special al proprietatii mai generale de marginire.

Definitia 11. O locatie € P a unei retele petri C=(P,T,I,O) cu un marcaj initial este k-sigura daca pentru fiecare . O locatie care este 1-sigura este numita simplu sigura.

De aici o locatie este marginita daca este kj – sigura pentru unii kj. O retea Petri este marginita daca toate locatiile sale sunt marginite.

Conservativitatea

Retelele Petri pot fi folosite pentru a modela sisteme de alocare a resurselor, ele pot modela cererile, alocarile si eliberarile pentru dispozitivele de intrare/iesire dintr-un sistem computational.

FIG.18. O retea Petri care nu este strict conservativa.

FIG.19. O retea Petri strict conservativa care este echivalenta cu reteaua din figura 18.

Conservativitatea este o proprietate importanta, aratam ca jetoanele care reprezinta resursele nu sunt nici create si nici distruse, ca sa facem acest lucru cel mai simplu ar fi sa cerem ca numarul de jetoane sa fie constant.

Definitia 12. O retea Petri C=(P,T,I,O) cu marcajul initial este strict conservativa daca pentru toate .

Pentru o vedere mai larga, totusi consideram figura 18 care reprezinta o retea strict conservativa deoarece declansarea oricarei tranzitii t1 sau t2 va micsora numarul de jetoane cu 1, in timp ce declansarea oricarei dintre tranzitiile t3 sau t4 va adauga un jeton la marcaj, convertim reteaua Petri din figura 18 la reteaua Petri din figura 19 care este strict conservativa.

Definitia 13. O retea Petri C=(P,T,I,O) cu marcajul initial este conservativa cu respectarea unui vector de ponderi daca pentru toate .O retea Petri este strict conservativa cu respectarea vectorului de ponderi (1,…,1),retelele Petri sunt conservative cu respectarea vectorului de ponderi (0,…,0).

Viabilitatea

Consideram un sistem cu doua resurse diferite q si r si doua procese a si b, daca ambele procese au nevoie de ambele resurse, va fi nevoie sa le foloseasca in comun, pentru asta vom cere fiecarui proces sa ceara o resursa si mai tarziu sa o elibereze. Procesul a cere mai intai resursa q si apoi resursa r, eliberand in final atat resursa q cat si resursa r, procesul b similar, doar ca cere mai intai resursa r si apoi resursa q, figura 20 ilustreaza aceste doua procese si alocarea resurselor cu ajutorul unei retele Petri.

3.2.Secvente de declansare

O alta abordare a analizei se concentreaza mai mult asupra secventelor de tranzitii ce se declanseaza doar asupra starilor. Aceasta abordare este legata de viabilitate. Putem determina daca o secventa anume de tranzitii ce se declanseaza este posibila, sau daca este posibila orice secventa dintr-o multime de secvente ce se declanseaza, aceste intrebari ca de analiza introduc conceptul de limbaj al retelelor Petri.

FIG.20. Alocarea resurselor pentru doua procese a si b si doua resurse q si r.

3.3.Accesibilitate si acoperire

Multe dintre problemele pe care le-am mentionat pana acum se concentreaza asupra marcajelor accesibile. Probabil cea mai simpla problema este problema accesibilitatii.

Definitia 14. Problema accesibilitatii – o retea Petri cu marcajul initial si un marcaj .

Definitia 15. Problema acoperirii- o retea Petri C cu marcajul initial exista un marcaj accesibil .

O alta utilizare a probemelor de tip accesibilitate ar fi sa ridicam la patrat continutul unor locatii, concentrandu-se numai asupra potrivirilor sau acoperind continutul unor cateva locatii importante, aceste probleme pot fi complicate in continuare daca vom dori sa stim accesibilitatea sau acoperirea pentru o multime de marcaje, problemele rezultate astfel se numesc problema accesibilitatii multimii si problema acoperirii multimii.

CAPITOLUL 4

Tehnici de analiza

Exista doua tehnici majore de analiza a retelelor Petri, ele ofera mecanisme de solutionare pentru cateva dintre problemele anterioare, tehnica principala folosita pentru analiza retelelor Petri este arborele accesibilitate, cealalta tehnica presupunand ecuatii cu matrice[13], [4], [16].

4.1. Arbore si accesibilitate

Arborele de accesibilitate reprezinta multimea de accesibilitate a unei retele Petri, pentru a ilustra cele afirmate vom considera figura 21, marcajul initial este (1 0 0), in acest marcaj doua tranzitii sunt posibile t1 si t2, deoarece consideram intreaga multime de accesibilitate, definim noi noduri in arborele de accesibilitate pentru marcajele care rezulta din declansarea ambelor tranzitii.

FIG.21. O retea Petri marcata pentru a ilustra constructia unui arbore de accesibilitate.

Daca aceasta procedura, adica cea din figura de mai jos, este repetata la infinit fiecare marcaj accesibil va fi eventual produs. Totusi, arborele de accesibilitate rezultat s-ar putea foarte bine sa fie infinit si deci arborele de accesibilitate sa fie infinit. In figura de mai jos observam foarte bine acest ciclu infinit.

FIG.22. Construirea unui arbore de accesibilitate.

Reducerea la o reprezentare finita poate fi realizata prin mai multe metode. Trebuie sa gasim o metoda de a limita noile marcaje (numite noduri de frontiera) introduse la fiecare pas, aceasta operatie este facilitata de nodurile moarte, adica acele marcaje in care nici o tranzitie nu este posibila, ele se numesc noduri terminale.

Mai exista o metoda care poate fi folosita pentru a reduce arborele de accesibilitate la o reprezentare finita, pentru aceasta consideram o secventa σ de tranzitii care se declanseaza, care incepe cu un marcaj μ, cu exceptia faptului ca are cateva jetoane „suplimentare” in unele locatii, ceea ce inseamna ca , deoarece decansarile tranzitiilor nu sunt afectate de jetoanele suplimentare, secventa σ poate fi declansata din nou, incepand din si terminand in . Deoarece efectul secventei de tranzitii σ a fost sa adauge jetoane la marcajul μ, la aceasta noua declansare va mai aduga inca jetoane la marcajul , astfel incat . Reprezentam numarul infinit de marcaje care rezulta din aceste tipuri de bucle folosind un simbol special ω, pe care il putem gandi ca „infinit” si care reprezinta un numar de jetoane care poate fi facut arbitrar de mare. Pentru orice constanta a, definim operatiile , singurele necesare pentru construirea arborelui de accesibiliate.Algoritmul incepe prin definirea marcajului initial ca radacina a arborelui, si initial, nod de frontiera. Atata timp cat exista noduri de frontiera, ele sunt procesate de algoritm.

Fie x un nod de frontiera ce urmeaza sa fie procesat atunci:

Daca exista un alt nod y in arbore care nu este nod de frontiera si are acelasi marcaj asociat adica atunci nodul x este un nod duplicat.

Daca nici o tranzitie nu este posibila pentru marcajul μ[x], atunci x este nod terminal.

Pentru toate tranzitiile tj € T care sunt posibile in μ[x] creeaza un nou nod z in arborele de accesibilitate. Marcajul μ[z] asociat cu acest nou nod este pentru fiecare locatie pi:

daca

daca exista un nod y pe drumul de la radacina la nodul x cu .

Altfel, .

Un arc etichetat tj este directionat de la nodul x la nodul z, nodul x este redefinit ca un nod interior; nodul z devine un nod frontiera. Cand toate nodurile au fost clasificate ca terminale, duplicate sau interioare, algoritmul se opreste.

FIG.23. Arborele de accesibilitate pentru reteua Petri din figura 21.

4.2. Siguranta si marginire

O retea Petri este sigura daca numarul de jetoane din fiecare locatie este cel mult 1.

O retea Petri este marginita daca exista un intreg k astfel incat numarul de jetoane din fiecare locatie sa nu fie mai mare de k..

O retea Petri este marginita daca si numai daca simbolul ω nu pare niciodata in arborele sau de accesibilitate.

Aparitia simbolului ω ca parte a unui arbore de accesibilitate arata ca numarul de jetoane este „potential nelimitat” ; exista o secventa de tranzitii ce se declanseaza care poate fi repetata de un numar arbitrar de ori pentru a creste numarul de jetoane la un numar arbitrar nelimitat, acest simbol indicand prin pozitia sa care locatie nu este marginita.

Conservativitate

O retea Petri este conservativa daca nu pierde sau castiga jetoane, ci doar le muta. De aceea doua jetoane pot fi interpretate ca un jeton care mai tarziu determina o tranzitie sa se declanseze, creeand doua jetoane, un vector de ponderi defineste valoarea unui jeton in fiecare locatie; ponderile sunt nenegative, o retea Petri este conservativa cu respectarea unui vector de ponderi daca suma ponerilor jetoanelor este contanta peste toate marcajele accesibile.

Conservativitatea poate fi efectiv testata folosind arborele de accesibilitate, acesta fiind finit, suma ponderilor poate fi calculata pentru fiecare marcaj, iar daca sumele sunt aceleasi pentru fiecare marcaj accesibil, atunci reteaua este conservativa cu respectarea ponderilor date, iar daca sumele nu sunt egale reteaua nu este conservativa.

Acoperirea

O ultima problema care poate fi rezolvata cu ajutorul arborelui de accesibilitate este cea a acoperirii. Determinam pentru un marcaj dat daca un marcaj este accesibil, dat fiind un marcaj initial μ, construim arborele de accesibilitate, apoi cautam orice nod x, cu , daca nu se gaseste un astfel de nod, marcajul nu este acoperit de nici un marcaj accesibil, iar daca este gasit un astfel de nod, μ[x] da un marcaj accesibil care acopera.

Drumul de la radacina la marcajul acoperitor defineste secventa de tranzitii care conduce de la marcajul initial la marcajul acoperitor, iar marcajul asociat cu acel nod defineste marcajul acoperitor. Din nou simbolul ω trebuie tratat ca reprezentand o multme infinita de valori, daca o componenta a marcajului acoperitor este ω, atunci va exista o bucla in drumul de la radacina la marcajul acoperitor , e necesar sa parcurgem aceasta bucla de un numar de ori suficient de mare pentru a creste componentele corespunzatoare astfel incat sa nu fie mai mici decat marcajul dat.

4.3. Detectarea și tratarea erorilor

Se recomandă ca depistarea erorilor să se facă într-o fază incipientă, pentru ca o soluționare a acestora într-o fază ulterioară să fie cât mai facilă. Metodologiile elaborate până în prezent, consideră detectarea erorilor numai la nivelul echipamentelor, atât timp cât tratarea lor este executată pe cel mai apropiat nivel [22], [17].

Erorile care pot sa apară sunt:

Blocaje/deadlock ( aflarea într-o stare care nu permite executarea altui proces);

Ciclare/livelock (posibilitatea executării proceselor, dar fără progres);

Procese moarte/dead task care nu pot fi executate niciodată.

În cazul sistemelor de producție automată putem considera două tipuri de detectare a erorilor: – erori determinate prin monitorizarea parametrilor dispozitivelor specifice;

– erori ce nu pot fi determinate direct în etapa de monitorizare.

În general, metodele de detectare a erorilor pot fi grupate în trei categorii [19] [21]:

bazate pe model/model-based: starea actuală și viitoare (dintr-un model matematic) sunt comparate pentru determinarea erorii;

bazate pe cunoaștere/knowledge-based: modele calitative sunt asociate cu modele euristice pentru determinarea cauzei erorii;

bazate pe semnal/Signal-based: analiza spectrală nu poate fi incorporată în orice model.

Din punct de vedere teoretic, metoda bazată pe model ajunge la un grad înalt de maturitate, pentru sistemele liniare de control cu mici incertitudini. Modelarea bazată pe cunoaștere este aplicată cu succes în detectarea erorilor.

În cazul metodei bazată pe cunoaștere, detectarea și tratarea erorilor se poate face în următorii pași:

detectare;

culegerea datelor parametrilor operaționali date de senzori;

identificarea stării operaționale (normale sau anormale);

determinarea cauzei erorii;

tratare.

4.3.1.Detectarea erorilor

Etapa de extragere a datelor implică aparate de măsură, pentru măsurarea fenomenelor fizice (dacă este posibil, fără interferența cu acestea). În general, culegerea datelor este un proces continuu și care nu poate depista situațiile anormale.

Etapa de identificare afectează analiza extragerii datelor la recunoașterea poziției/stării parametrilor. Aceasta determină o discrepanță între generația actuală și generația ulterioară.

Etapa de diagnosticare trebuie să determine cauzele erorilor. Metodele de diagonsticare pot fi grupate in:

symptom-based unde cunoștințele/experiența despre istoria proceselor sau experiența/cunoașterea statistică este organizată în cadru sistemelor expert care asociază intrări cu simptome euristice.

Raționament calitativ(qualitative reasoning) sistemele fizice pot fi descrise de o structură în ordinea determinării comportamentelor date de condițiile inițiale. Descrierea comportamentului poate fi un graf ce conține stările sistemului.

Construcția grafului care descrie aceste comportări ce pot fi soluționate/executate în două etape:

bazate pe cunoașterea umană despre procese, care stabilesc relațiile dintre variabile și definesc criterii de alegere pentru stările următoare.

Bazate pe înregistrarea datelor, unde pot fi aplicate aproximări probabilistice pentru căutarea celei mai probabile rețele de încredere(interval).

4.3.2. Tratarea erorilor

Tratarea erorilor trebuie să fie adecvată pentru fiecare nivel al sistemului de producție. În nivelul de echipament, erorile trebuie să fie determinate și, dacă este posibil, mașina defectă trebuie reparată automat [13], [14].

În funcție de tipul erorii, se selectează o procedură de reparare. În general, cea mai bună selectare a unei proceduri trebuie să aibă la baza evitarea valorilor la limită a parametrilor și evitarea efectelor colaterale.

Procesul de soluționare a erorilor poate fi realizat în două moduri:

Ajustarea parametrilor operaționali fără schimbarea/reorganizarea structurii logice a mașinii;

Utilizarea resurselor redundante.(acest tip al redundanței poate da o performanță scăzută care este neadecvată și conduce la o creștere a complexității)

Figura 24 arată structura suportabilității/toleranței erorilor mașinii bazate pe ajustarea parametrilor operaționali. De reținut este faptul că se presupune că erorile se produc numai pe obiectele de control (analizate). În general, interacțiunea umană este luată în considerare în etapa de monitorizare și comanda dispozitivelor de luare a deciziilor pe durata proceselor normale. Interacțiunea umană poate de asemenea să fie efectuată în fazele de programare și mentenanță.

Controlorul și supervizorul coexistă în această structură. Supervizorul verifică performanța și controlorul definește procedurile care conduc la secvențele/operațiile care repară erorile. În general, informația de la controlor la supervizor conține semnale filtrate sau caracteristici extrase; astfel, tratarea informației este distribuită, permițând interpretări locale și selectarea informației trimise.

Fig. 24. Structura suportabilității/tolerantei erorilor mașinii

În momentul apariției unei probleme la nivelul celulei de producție, pentru tratarea erorii, se identifică alte echipamente din aceeași celulă care pot să efectueze în întregime sau parțial funcțiile echipamentului neoperativ, acestea preiau sarcinile echipamentului defect, până când echipamentul respectiv ajunge operativ.

La nivelul producției, tratamentul erorilor este efectuat de reprogramarea rutelor fluxului de material în celule.

Metodologia care prevede mijloacele de modelare a sistemului consideră detectarea, tratarea erorilor, și analiza proprietăților diferitelor soluții, ca fiind esențiale pentru proiectarea și implementarea unei autonomii și flexibilități mai mari a sistemelor de producție.

CAPITOLUL 5

Imbricarea rețelelor Petri

Se va proiecta un model pentru tratarea exceptiilor si a erorilor, pentru care definim retele Petri extinse si imbricate. Pentru a construi un sistem mai flexibil al managementului fluxului de producție se poate utiliza rețelelor Petri imbricate . Pentru găsirea unei soluții este necesar să se cunoască toate etapele, situațiile de excepție și orice combinație a acestora, folosind abilitatea, modificarea structurală a proceselor, chiar inlocuirea subproceselor sau extinderea lor. Presupunem dată o colecție (bibliotecă) a protocoalelor care vor fi utilizate ca blocuri de bază pentru construcția unor protocoale mai complexe .

Rețelele Petri imbricate sunt rețele Petri în care jetoanele pot fi rețele Petri însăși, numite rețele jeton ( TN-Token Nets)[5], [6], [7], [8]. Capacitatea de modificare a rețelelor jeton TN are următoarele avantaje:

actualizarea colecției de protocoale;

Modificarea proceselor continue;

Capacitatea de modelare a deciziilor luate ca părți diferite.

Pentru a introduce rețele Petri imbricate [5], [6] considerăm un tip special de rețele colorate [8]. Presupunem că mulțimea U conține valoarea negru, corespunzătoare obiectelor ce nu conțin informații.

Într-o rețea colorată, fiecare locație este mapată cu un tip, care este o submulțime a lui U. Mai presupunem că L este mulțimea etichetelor pentru tranziții astfel încât τ L. Fiecărei etichete îi este asociat un număr natural unic, denumit rangul etichetei. Atunci definim mulțimea etichetelor de tranziție . Eticheta τ este o etichetă ”silențioasă”/fără efect.

Definiție 16 [15]: O rețea colorată peste universul U este un 6-uplu (P,T,F,ʋ,ρ, ), unde

P, T sunt două mulțimi nevide (reprezentând mulțimea locațiilor și respectiv mulțimea tranzițiilor), PT = ;

este mulțimea arcelor

ʋ este o locație dată ca o funcție cu dom(ʋ)=P, astfel încât ʋ(p)U, pentru orice p;

ρ este o funcție de tranziție cu dom(ρ)=T, astfel încât , pentru orice , unde și ;

este o funcție de etichetare cu dom()= și ran().

Definitia 17: Fiind dată o rețea colorată N=(P,T,F,ʋ,ρ, ) peste universul U, un marcaj pentru N este o funcție MN, astfel încât pentru orice pși orice u, M(p,u)˃0 implică . Mulțimea tuturor marcajelor a rețelei colorate este dată de .

O rețea cu marcaj colorat peste U este o pereche (N,M), unde N este o rețea colorată peste U și M este un marcaj colorat din N.

O rețea colorată definește un sistem de tranziție care furnizează stările observabile ale rețelei.

Definiția 18. O relație ternară este definită ca cea mai mică relație astfel încât pentru orice (N;M) , și Mai putem scrie și numai dacă există un marcaj astfel încât În final, înseamnă că există o secvență astfel încât . În acest caz putem spune că este accesibilă în (N,M).

5.1. Rețele fluxuri de lucru extinse

Rețelele fluxuri de lucru ( rețea WF) [1], [14] [15] au o locație inițială și una finală, și orice locație sau tranziție este o cale direcționată din locația inițială spre cea finală. Extindem noțiunea rețea WF la un model special/excepție astfel încât tranzițiile trebuie sa termine execuția rețelei curente [43],[58].

Definiția 19: O rețea colorată N=(P,T,F,ʋ,ρ, ) peste universul U este o rețea fluxuri de lucru extinsă cu locația inițială i, și locația finală f și mulțimea tranzițiilor de excepție dacă:

1. Ø;

2. ;

3. pentru oricedacă și numai dacă dacă și numai dacă Ø;

4. pentru orice nod există o cale/drum de la i la n;

5. pentru orice nod există o cale de la n la un nod în .

Rețele EWF conferă un număr de avantaje din mai multe puncte de vedere ale modelării între care menționăm faptul că acestea fac o distincție clară între o terminare normală și o terminare generată de o excepție. Spre deosebire de rețelele tradiționale fluxuri de lucru WF, o atenție specială se acorda mutării tuturor jetoanelor prezente în sistem când era întâlnită o situație de exceptie, în rețelele EWF aceasta cerință nu se utilizează[17].

Definiția 20: Fie N o rețea extinsă de fluxuri de lucru (EWF) cu o locație inițială i și una finală f, și fie . Marcajul rețelei (N,M) este denumit inițial, respectiv final, dacă și numai dacă , respectiv . Inițializarea init(N) lui N este rețeaua marcată .

5.2. Stabilitatea rețelelor EWF

O altă proprietate naturală a rețelelor EWF este stabilitatea. Rețelele clasice WF. sunt stabile dacă de la orice marcaj intermediar se ajunge la marcajul final. Proprietatea de soliditate/stabilitatea mai este uneori denumită terminare normală.

Definiția 21: O rețea EWF N=(P,T,F,ʋ,ρ, ) cu o locație inițială i și una finală f peste universul U se numește stabilă dacă și numai dacă pentru orice

fiecare sau există a.î. pentru un ;

implică m=Ø pentru orice .

Din noțiunea de stabilitate formalizată în definiția 21, reiese faptul că pentru orice stare posibilă întotdeauna există o posibilitate de a completa execuția până intr-o stare finală, sau de a raporta o excepție. O a doua cerință a stabilității este faptul că nu se ajunge la o stare finală fără o execuție completă. În cazul rețelelor WF clasice, a doua condiție a stabilității este redundantă.

Definiția 22. O rețea WF este stabilă dacă și numai dacă:

pentru orice stare M accesibilă din starea inițială i, există o secvență de tranziții ce permite stării M să ajungă în starea finală f:

starea f este numai starea accesibilă din starea i cu cel puțin un jeton în locația f:

nu există tranziții moarte, adicăastfel încât .

Proprietatea de stabilitate redă dinamica rețelelor WF. Din prima cerință a definiției 21 reiese faptul că dintr-o stare intermediară (posibilă din starea inițială) întotdeauna se poate ajunge într-o stare finală. A doua cerință specifică faptul că în momentul în care avem un jeton în starea finală, toate celelalte locații trebuie să fie goale/vide. În majoritatea cazurilor, noțiunea de terminare proprie/normală este asociată primelor două cerințe ale definiției anterioare. A treia cerință a definiției, afirmă faptul că din starea inițială prin intermediul unei tranziții se poate ajunge la o nouă locație (stare).

Lema 1: Fie N=( P, T, F ,ʋ, ρ, ) o rețea stabilă EWF peste universul U. Fie , și . Fie unde

și

, pentru și și pentru orice .

Atunci rețeaua este o rețea stabilă EWF peste U.

Remarcam că t este o tranziție de excepție având , pentru orice .

Lema 2: permite folosirea unei aproximări incrementale pentru a modela în primul rând cu o execuție normală evenimentul apoi adăugarea excepției.

5.3. Operații cu rețele EWF

Una dintre cele mai importante facilități oferite de modelarea cu rețele Petri este evidențiera concurenței (paralelismului), sincronizării și a conflictelor. Deoarece sistemele reale sunt complexe și este necesară o modularizare a lor se impune asigurarea unor facilități de compunere [14].

Vom considera orice rețea ca fiind rețea EWF. Mulțimea tuturor rețelelor EWF marcate, sunt notate Nw (MW). Considerăm numărul predicatelor și operațiilor pe rețele și rețele cu marcaj, pentru a converti o rețea într-o rețea cu marcaj, adăugând un marcaj inițial corespunzător și pentru orice rețea cu marcaj, putem verifica dacă este un marcaj inițial și unul final.

Două rețele pot fi combinate pentru a construi o nouă rețea utilizînd compunere secvențială, paralelă și alegere. Mai mult, compunerea paralelă poate fi aplicată rețelelor marcate și compunerea secvențială rețelelor și rețelelor marcate. Operații similare sunt definite și pentru rețelele fluxuri de lucru.

Lema 3: Pentru orice N1,N2NW ,. Mai mult și + este asociativă, iar și + sunt comutative. Dacă sunt stabile atunci sunt de asemenea stabile.

Rolul compunerii secvențiale este de a extinde procesul de rulare cu o nouă funcționalitate. Astfel definim compunerea secvențială ca o operație pe rețele cu marcaj și rețele (simple) după cum urmează , iar compunerea paralelă: , unde sunt rețele EWF cu marcaj.

Operațiile rețelelor cu marcaj satisfac următoarea lemă:

Lemma 4 Pentru orice {N1,M1),(N2,M2)Mw și NNw, (N1, M1) ·N Mw, și (N1, M1) || (N2, M2) Mw. mai mult, · este asociativă și || este comutativă.

Compunerea paralelă și alegerea sunt congruente in raport cu EWF-bisimilaritea și compunerea secvențială este congruentă dacă primul operator este stabil .

Teorema 1: Fie rețele EWF, astfel încât . Atunci . Fie rețele EWF cu .Atunci și .

5.4. Imbricarea rețelelor

Considerăm un univers inițial U0 ce conține valori de bază, cum ar fi valori intregi, valori compuse cum ar fi perechile/cuplu, liste și mulțimi ale valorilor compuse. Universul următor și mulțimile rețelelor sunt definite recursiv prin următoarea definiție:

Definiția 23: Mulțimile N0, M0 ale rețelelor și marcajul rețelei de adâncime zero este definit ca mulțimile rețelelor colorate și rețelelor marcate colorate cu peste universul U0.. Pentru fiecare n > 0 valoarea universului Un mulțimile Nn, Mn ale rețelelor și rețelelor marcate ale adâncimii n sunt definite recursiv: Un= Un-1Mn-1 și Nn și Mn ca mulțimea rețelelor colorate și a rețelelor cu marcaj color peste universul Un. mulțimea Nw = Un≥0 Nn,Mw = Un≥0 Mn și Uw = U0 Mw.

Observăm că definiția recursivă a noțiunii de rețea imbricată marcată de adâncime n permite jetoanelor să fie colorate de rețele imbricate de adâncime n-1.

Exemplu: considerăm că mulțimea U0 conține doar numere naturale. In figura 25 se folosește N1 ca jeton în rețeaua N0.

Teorema 2. Fie L o colecție de protocoale a rețelelor EWF stabile. Atunci, orice termen al rețelei imbricate EWF (cu marcaj) care se obține din L și o operație de compunere este stabil.

Exemplu 2: Considerăm rețeaua Petri imbricată pentru două operații/activități desfășurate in cadrul Autoliv Lugoj. (producția de airbag-uri)[37].

Operațiile de tăiere și impachetare sunt prezentate detaliat pentru a permite formarea unei imagini complete asupra procesului. Pentru operația de tăiere, etapele sunt:

Se va introduce bara metalica pentru fixare in rola de material tinand cont de sensul de de bobinare a rolei care se va instala pe mașină, se va ridica cu ajutorul motostivuitorului și se va fixa in suportul masinii.

Materialul trebuie aliniat astfel încât marginea materialului să fie perpendicular pe senzor. Senzorul are rolul de aliniere automată a marginii materialului.

La incărcarea materialului în mașină. acesta va fi introdus minim până la jumătatea mașinii după care se va realiza selectarea Datum-pointului pentru primele piese.

Taie perna cu punctul de referinta indicat folosind markerul.

Verificarea vizuală unor eventuale defecte:- defecte de țesătura șı a invelisului de silicon referitoare la catalogul de standarde acceptate vor fi separate in cutia de rebuturi.

Ia elementul decupat și deschide gâtul.

Introdu bara pentru a te asigura că nu este lipit.

Pune perna în zona de așteptare a următoarei operații de la stația alăturată.

Operația de împachetare:

Inainte de a pune in cutie, pentru fiecare bucată se apasă pe butonul numărătorului pentru a urmări exact numărul de piese în cutie.

In cutia de plastic se așează o pungă de plastic albastră in care se vor impătura produsele, scopul acesteia este să protejeze airbagurile.

Se introduc 16 cortine în cutie, toate fiind orientate cu gâtul intr-o singură parte.

Se pune un sul de carton în partea dreaptă a cutiei

Aceași parte se impătura de 2 ori in cutie

Se pune un sul de carton in partea stangă a cutiei

Aceași parte se impătura de 2 ori în cutie

După ce s-au pus în cutie 16 OPW-uri cu h-sock-urile introduse, se scoate eticheta de cutie,se ștampilează și se pune deasupra OPW-urilor.

Ultima operație este reprezentată de împăturarea pungii deasupra produselor. Fiecare cutie se va pune pe palet

Modelarea celor două operații cu rețele Petri este cea din figura 27.

a) b)

Fig. 27. Modelarea operației de tăiere și ambalare cu rețele Petri.

În figura 27. a) este prezentată o rețea imbricată, adică jetonul Rețea2 este rețeaua din figura 27. b).

Verificarea fluxului de lucru conține trei componente principale:

– verificarea structurii (are ca scop studierea consistenței fluxului de lucru, adică determinarea ,dacă este cazul, a blocajelor, ciclării sau/și lipsa sincronizării);

– verificare temporară ( restricțiilor temporare le sunt atribuite importante specificații ale fluxului de lucru);

– verificarea resurselor/ analiza performanțelor (verificarea resurselor are ca scop stabilirea stării resurselor pentru a nu apărea conflicte între activități).

Din paragrafele anterioare, stabilitatea rețelei Petri implică o terminare normală, adică activitățile/operațiile sunt finalizate fără probleme.

În cazul în care nu există stabilitate, avem o terminare anormală. Această terminare anormală se datorează aparițiilor unor erori. Pentru remedierea acestora este necesară o detectare/determinare într-un timp cât mai scurt, pentru ca activitățile care urmează să poată fi duse la final (terminare proprie).

Analiza operației de tăiere, duce la apariția următoarelor defecte:

A: Perna tăiată cu caracteristici greșite;

B: Operația de capsare a eșuat

C:Tăiere prea aproape de linia neagră

FIG.28. Subretea pentru tratarea defectelor A.

Similar ca in figura 28 se pot construi subretele si pentru defectele scrise la punctele B si C.

5.5. Tratarea erorilor

În derularea unui proces/activitate de producție se produce o stare de excepție. În acel moment, se introduce într-o locație un jeton cu un anumit atribut (culoare) și locația respectivă este intrare într-o subrețea care tratează excepția/eroarea respectivă (rețele imbricate).

Tranziția care declanșează excepția acționează dacă atributul în cauză are o anumită culoare. Tranziția face verificarea culorii cu ajutorul funcției de etichetare.

În teoria clasică a rețelelor Petri, jetonul este la un moment dat un parametru al stării. În modelele construite și derivatele rețelelor Petri, în funcție de context, jetoanele primesc semnificații particulare, cum ar fi:

identificator, care identifică un obiect real;

atribute sau culori, care particularizează prin valorile lor anumite situații.

În funcție de context, prin Id-jeton vom înțelege un atribut(culoare), și unde va fi cazul vom specifica faptul că Id-jeton identifică un obiect, iar acolo unde va fi cazul vom preciza că jetonul va avea anumite atribute (culori).

Extensie pentru tratarea erorilor

Definim o rețea SM1WF în care pentru o roare specifică () într-o anumită locație din rețeaua tranziția care generează eroarea, plasează în locația un jeton de culoare .

Rețelei originale îi conectăm de tip imbricare câte o subrețea pentru fiecare tip de eroare. Tranziția poate genera un număr de erori simultan. În acest caz Id-jeton reprezintă .

Definiție: Numim rețea extinsă , o rețea SM1WF în care pentru fiecare defect tranziției care generează eroarea i se atașează o locație de ieșire , în care la momentul apariției eroriii prin acțiunea tranziției se plasează un jeton cu culoarea

Teoremă: Rețeaua construită în definiția anterioară este stabilă.

Dem: Pentru a demonstra stabilitatea rețelei, considerăm că toate jetoanele au aceeași culoare. În continuare, considerăm că rețeaua N (pe care o extindem la ) este o rețea SM1WF stabilă și presupunem că rețeaua extinsă nu este stabilă. Atunci există o secvență de tranziții și un marcaj ce poate fi atins din locația inițială i , și marcajul nu poate ajunge în starea finală f, . Luăm suficiente resurse care sunt permise/accesibile tranzițiilor , atunci marcajul este accesibil/atins în dar nu este atins în , (nu are loc relația) ceea ce contrazice ipoteza stabilității rețelei SM1WF, deci rețeaua este stabilă.

Paleta extinsă de modelare și de instrumente de analiză oferită de rețelele Petri și derivatele lor a permis

să modelăm procesul, fluxul de prelucrarre

să evidențiem particularitățile

să dezvoltăm modelul cu extensii pentru analiza și prelucrarea defectelor.

Condițiile esențiale ale funcționării corecte a unui sistem sunt în esență: derularea normală, stabilitatea și acolo unde este posibil tratarea erorilor. Pentru rețelele Petri imbricate am dezvoltat treptat și demonstrat prin particularizare proprietățile legate de stabilitate. Sistemele reale utilizează resurse care sunt partajate în comun de componentele lor. Componentele concurează între ele pentru accesul la resurse și aceasta necesită eleborarea unor modele adecvate.

CONCLUZII

Sistemele complexe necesita instrumente adecvate pentru proiectarea lor, iar Retelele Petri si deritavele lor sunt astfel de instrumente. Evidentierea concurentei, a conflictelor si confuziilor impreuna cu existenta unor instrumente formale de analiza, fac din retelele Petri un instrument eficace. Retelele Petri de tip workflow prin existenta proprietatii de stabilitate asigura dezvoltatorilor de sisteme construirea de fluxuri de prelucrare (workflow) care sa garanteze derularea corecta a proceselor.

Aparitia cerintelor de evedientiere a exceptiilor si erorilor precum si tratarea lor este o cerinta normala pentru cei care proiecteaza sisteme complexe.

Lucrarea prezinta conceptele de baza, proprietatile si tehnicile de analiza pentru retelele Petri clasice. Prin utilizarea retelelor Petri de fluxuri extinse si a celor imbricate am construit un model de tratare a exceptiilor pentru un proces de fabricatie.

Intre posibiltiatile de dezvoltare ulterioara a modelului abordat, le consider pe urmatoarele:

detalierea tuturor exceptiilor si erorilor precum si a modalitatilor lor de solutionare;

conceperea unuor subretele care sa trateze exceptiile si erorile;

integrarea lor intr-un sistem unitar.

O alta posibilitate este conceperea unei aplicatii care sa permita generarea retelelor imbricate cu asigurarea conservarii proprietatilor de stabilitate si marginire.

BIBLIOGRAFIE

1. Aalst, W. M. P., (1996)- ”Structural Characterizations of Sound Workflow.ets”, Computing Science Reports 96/23, Eindhoven University of Technology,Eindhoven.

2. Aalst, W. M. P., (1997)- ”Verification of Workflow .eds”, In P. Zema and G. Balbo, editors, Application and Theory of Petri Nets 1997, volume 11248 of Lecture Notes in Computer Science, Springer – Verlag, Berlin, 407-426.

3. Ackoff, R. L., Sasieni, M. W., – ”Bazele Cercetării Operaționale”, Editura Tehnică, Bucuresti, 1979.

4. Boldea, C. R., (2006) – ”Rețele Petri. Modelare si Analiză”, Editura Mirton, Timisoara.

5. Hee, K., Sidorova, N., Voorhoeve, M., (2005)– ”Resource-Constrained Workflow .ets”, Fundamenta InformaticaeXX, (1-15) IOS Press.

6. Hee, K., Lomazova, I. A., Oanea, O., Serebrenik, A., Sidorova, N., Voorhoeve, M., (2006)- ”Nested nets for adaptive systems”, Lecture Notes in Computer Science, Springer Berlin/Heidelberg.

7. Hee, K., Serebrenik, A., Sidorova, N., Voorhoeve, M., (2005)- “Soundness of Resource-Constrained Workflow .ets”; Lecture Notes in Computer Science, Springer Berlin/Heidelberg.

8. Jensen, K., (1992) – ”Coloured Petri nets. Basic Concepts, Analysis Methods and Practical Use”, Vol 1Basic Concepts, EATCS Monographs on Theoretical Computer SCience, Springer.

9. Jucan, T., Țiplea, F. L., (1999) – ”Rețele Petri, teorie si practică”, Editura Academiei Române.

10. Lomazova, A. I., Schnoebelen, Ph., (1999) – ”Some decidability results for tested Petri.ets”, Ershov Memorial Conference, Novosibirsk.132

11. Lomazova, A. I., (2008) – ”Nested Petri Nets for Adaptive Process Modelling”, Pillars of Computer Science, Springer, 460-474.

12. Lomazova, A. I., (1999) – ”Modelling of multi-agent dynamic systems by tested Petri nets”, In Programmnye Sistemy: Teoreticheskie Osnovy i Prilozheniya Moskow: Nauka, 1999, 143-156.

13. Mateia, N. A., (2009)- ”Petri nets a powerfull tool for analysis of manufacturing systems”, DAAAM International Viena, 2009(în curs de apariție).

14. Mateia, N.A. Modele si algoritmi pentru programarea operativa a productiei, ASE Bucuresti, 2009.

15. Prisecaru, O.O., (2009) – ”Petri nets-based Approaches for the Modelling and Verification of Workflow Process”, PhD Thesis, Department of Computer Science, “Al. I. Cuza” University of Iasi, Iasi, Romania, March 2009.

16. Reisig, W., (1985) – ”Petri .ets. An Introduction”, Vol 4 of EATCS Monographs on Theoretical Computer SCience, Springer.

17. Riascos, L. A. M., Moscato, L. A., Miyagi, P. E., (2004)– ”Detection and Treatmeant of Faults in Manufacturing Systems Based on Petri nets”, Journal of the Brazilian society of mechanical Sciences and Engineering, no 3.

18. Siegeris, J., Zimmermann A., (2006) – “Workflow Model Compositions Preserving Relaxed Soundness”, Business Process Management, 177-192.

19. Spur, K., Mertins, K., Wieneke-Toutaoui, B., Rabe, M., (1989)– “MOSYSa planning system for manufacturing and assembly planning”, Simulation in Manufacturing 5, Bedford,, IFS.

20. Valk, R., (1998) – ”Petri nets as token objects: An Introduction to elementary objects nets”. In Proc. 19th International Conference Application and Theory of Petri Nets, Lisbon.

21. Villaroel, J. L., Martinez, J., Silva, M., (1989) – ”GRAMA.: A graphic system for manufacturing system design”, Symposium on System Modelling and Simulation, Elsevier SciencePubl, , 311-316.

22. Vittorini, V., Basile, F., Chiacchio, P., Mazzocca, N., (2004) – ”Modeling and logic controller specification of flexible manufacturing systems using behavioral traces and Petri net building blocks”, Journal of Intelligent Manufacturing, Springer Netherlands, 351-371.

23. http://www.ac.tuiasi.ro/pntool/