Universitatea De Vest Timisoara Facultatea De Matematica Si InformaticaMaster:Informatica Aplicata In Stiinta, Tehnologie Si Economie

LUCRARE DE DIZERTATIE

Coordonator stiintific: Candidat:Profesor Dr.ALEXANDRU CICORTAS

Timisoara2009

UNIVERSITATEA DE VEST TIMISOARA

FACULTATEA DE MATEMATICA INFORMATICAMASTER: SPECIALIZAREA INFORMATICA APLICATA IN STIINTA,TEHNOLOGIE SI ECONOMIE

Retele petriInstrument de modelare

Coordonator stiintific: Candidat:

2

Profesor dr. Alexandru Cicortas

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.

3

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.

4

Cuprins

Introducere .........................................................................................................................pag 6Capitolul 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 12Capitolul 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 35Capitolul 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 46Concluzii ...........................................................................................................................pag 48

5

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.

6

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.

7

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:

#(tDefinitia 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

.

8

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

9

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

10

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.

11

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 t nefiind 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.

12

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 precizezecare dintre tranziţii sunt validate şi marcajul ce rezultă după executarea fiecăreia din acestetranziţ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.

13

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 ajungedin M0 la marcajul 1 M = (1,2,0) ; • tranziţia t2 este validată deoarece M0( p2) =W( p2 ,t2) ; prin executarea lui t2 seajunge 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) ; prinexecutarea 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 ajungedin M0 la marcajul 1 M = (1,2,0) ; • tranziţia t2 este validată deoarece M0( p2) =W( p2 ,t2 ) ; prin executarea lui t2 seajunge 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) ; prinexecutarea 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 simplea tranziţiei conduce la: • tranziţia t1 este validată deoarece M0 (p1) >W (p1,t1) ; prin executarea lui t1 se ajungedin M0 la marcajul 1 M = (0,3,0,2) ; • tranziţia t5 este validată deoarece M0 (p4) =W(p4 ,t5) ; prin executarea lui t2 seajunge din M0 la marcajul 2 M =( 4,0,0,0) .

14

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 reguliistricte 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) ; prinexecutarea 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 ajungedin M0 la marcajul 2 M = (3,0,0) ; • tranziţia t3 deoarece M0 (p1) >W( p1,t3) , M0 (p2 )=W( p2 ,t3) şiK (p3) = M0( p3) +W(t3, p3) ; prin executarea lui t3 se ajunge din M0 lamarcajul 3 M = (1,0,1) ;(iii) pentru reţeaua din fig.29.(c) nici una dintre tranziţii nu este validată.

15

CAPITOLUL 2MODELAREA CU AJUTORUL RETELELOR PETRI

16

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:

a) atelierul este in asteptareb) a sosit un ordin si este in asteptare c) atelierul prelucreaza ordinul d) prelucrarea ordinului sa incheiat

Evenimentele pot fi:1. sosirea unui ordin2. atelierul incepe prelucrarea ordinului 3. atelirul termina prelucrarea ordinului 4. 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:

Eveniment Preconditii Postconditii1 Nici una b2 a, b c3 c d, a4 d Nici una

17

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) A sosit o lucrare si asteapta sa fie prelucrata de b) O lucrare a fost prelucrata de si asteapta sa fie prelucrata si de celelalte masinic) Prelucrarea lucrarii s-a terminatd) Masina este liberae) Masina este liberaf) Masina este liberag) Operatorul este liberh) Operatorul este liberi) Masina este operata de j) Masina este operata de k) Masina este opearata de l) Masina este operata de

Aici pot aparea urmatoarele evenimente:

1) Soseste un ordin

18

2) Operatorul porneste prelucrarea lucrarii pe masina 3) Operatorul termina prelucrarea lucrarii pe masina 4) Operatorul porneste prelucrarea lucrarii pe masina 5) Operatorul termina prelucrarea lucrarii pe masina 6) Operatorul porneste prelucrarea lucrarii pe masina 7) Operatorul termina prelucrarea lucrarii pe masina 8) Operatorul porneste prelucrarea lucrarii pe masina 9) Operatorul termina prelucrarea lucrarii pe masina 10) Ordinul de livrare este trimis

Preconditiile si postconditiile fiecarui eveniment sunt urmatoarele:Eveniment Preconditii Postconditii1 Nici una A2 a, g, d I3 i g, d, b4 a, h, d J5 f b, h, d6 b, g, e K7 k c, g, e8 b, f, h L9 l c, f, h10 c Nici una

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

19

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

20

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 p va 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.

21

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

22

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.

23

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.

24

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.

25

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.

26

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

27

CAPITOLUL 3Analiza 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.

28

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.

29

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.

30

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.

31

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

32

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.

33

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:

34

1. 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.

2. Daca nici o tranzitie nu este posibila pentru marcajul μ[x], atunci x este nod terminal.3. 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: a) daca b) daca exista un nod y pe drumul de la radacina la nodul x cu

.c) 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

35

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.

36

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)

37

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 5Imbricarea reţelelor Petri

Dispozitiv comandăDispozitiv

monitorizare

supervizor

Dispozitiv control

senzor actuator

Obiect de control

Extragere date

reparare

proiectant

eroare

mainti ner

38

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), P T = ;- 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 M N, 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.

39

Definiția 18. O relație ternară este definită ca cea mai mică relație

astfel încât pentru orice (N;M) , Tt ș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 orice dacă ș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

1. fiecare sau există a.î. pentru

un ;

2. implică m=Ø pentru orice .

40

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ă:1. 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: 2. starea f este numai starea accesibilă din starea i cu cel puțin un jeton în locația f:

3. 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 N

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

41

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,N2 NW , . 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 N Nw, (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

42

ș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-1 Mn-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:

43

1. 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.

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

3. 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.

4. Taie perna cu punctul de referinta indicat folosind markerul.5. 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.

6. Ia elementul decupat și deschide gâtul.7. Introdu bara pentru a te asigura că nu este lipit.8. Pune perna în zona de așteptare a următoarei operații de la stația alăturată.

Operația de împachetare:

1. 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.

2. 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.

3. Se introduc 16 cortine în cutie, toate fiind orientate cu gâtul intr-o singură parte.4. Se pune un sul de carton în partea dreaptă a cutiei5. Aceași parte se impătura de 2 ori in cutie6. Se pune un sul de carton in partea stangă a cutiei7. Aceași parte se impătura de 2 ori în cutie8. 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.9. Ultima operație este reprezentată de împăturarea pungii deasupra produselor. Fiecare

cutie se va pune pe paletModelarea celor două operații cu rețele Petri este cea din figura 27.

44

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).

45

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;

Categorie Cauză AcțiuneMetodă Operatorul nu a primit informații

despre metodele de selectare Datum și a poziției critice.

Poziționarea corectă a senzorului P2.

Persoană Operatorul nu a verificat termenii standard ai cortinei

Poziționarea senzorului P2 arată operatorilor punctele de focalizare

Mașină Eroare software pe durata operației de tăiere

Este necesar suport tehnic pentru determinarea originii cauzei

Persoană   Stabilirea originii cauzei în ansamblu, analiza acesteia și luarea deciziilor detaliate necesare

B: Operația de capsare a eșuat

Categorie Cauză AcțiunePersoană Operatia a fost comandată de

operatorDetectarea manuală a metalului în celulă

Persoană Operatorul nu efectuat inspecția Detectarea manuală a metalului în celulă

Persoană Operatorul nu efectuat inspecția Operatorul trebuie să aplice ștampila mai aproape de ambele capse

Persoană Operatorul nu efectuat inspecția Instalarea sistemului de senzor în detectarea prezenței capsei

C:Tăiere prea aproape de linia neagră

46

Categorie Cauză AcțiuneMașină Aliniere incorectă a materialului Plasarea senzorilor care

detectează alinierea incorectă a materialului

Persoană  Operatorul nu a aliniat normal materialul

Plasarea senzorilor care detectează alinierea incorectă a materialului

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:

47

- 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.

48

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.

49

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.13211. 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.

50

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/

51