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

LUCRARE DE DIZERTATIE

Coordonator stiintific: Profesor Dr.ALEXANDRU CICORTAS

Candidat:

Timisoara 2009

UNIVERSITATEA DE VEST TIMISOARA FACULTATEA DE MATEMATICA INFORMATICA MASTER: SPECIALIZAREA INFORMATICA APLICATA IN STIINTA,TEHNOLOGIE SI ECONOMIE

Retele petri Instrument de modelare

Coordonator stiintific: Profesor dr. Alexandru Cicortas

Candidat:

2

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 3

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

IntroducereRar vom gasi o ramificatie a Informaticii n care cercetarea sa stagneze sau sa se desfasoare anevoios. Retelele Petri [16], [13] nu fac exceptiedovada 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, avnd 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, diviznd sistemul n anumite elemente care ar caracteriza st rile locale ale sistemului modelat i caracteriznd 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. Simulnd 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 6

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 ct 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. Considernd 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. Utiliznd 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 t j la o colectie de locatii I (t j ) care poarta numele de locatii de intrare ale tranzitiei. Functia de iesire O este o functie de la o tranzitie t j la o colectie de locatii O (t j ) 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 mnt 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= { p1 ,..., pn } este o multime finita de locatii, n 0; - T= { t1 ,..., tm } este o multime finita de tranzitii, m 0; Multimea locatiilor si multimea tranzitiilor sunt disjuncte P T= * . g - I:T p P este functia de intrare, o functie de la multimea tranzitiilor la colectia de locatii. g - O:T p P 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: g g I:T p P , O : T p P unde: # (t j , I ( pi )) ! # ( pi , O (t j )) #(t j , O ( p i )) ! # ( pi , I (t j )) Definitia 3: Un graf de retea Petri este un multigraf orientat bipartit G= (V,A) unde V= {v1 ,.., vs } este o multime de varfuri si A={ a1 ,...,a r } este un multiset de arce directionate ai ! (v j , vk ), cu v j , vk V . Reteua V poate fi partitionata in doua retele disjuncte P si T astfel incat T , P T ! * si pentru fiecare arc distinct ai A daca ai ! (v j , vk ) atunci fie V= Pv j P , vk T , v j T , vk P .

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 ={ p1 ,..., p5 } - T ={ t1 ,...,t 4 } I ( t 1 ) ! { p 1 }, I ( t 2 ) ! { p 2 , p 3 , p 5 }, I ( t 3 ) ! { p 3 }, I ( t 4 ) ! { p 4 } O(t1 ) ! { p2 , p3 , p5 }, O(t 2 ) ! { p5 }, I (t3 ) ! { p4 }, I (t 4 ) ! { p2 , p4 }

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 Q al unei retele Petri C = (P, T, I, O) este o functie de la multimea locatiilor P la multimea numerelor naturale N, si anume Q : P p 2 . Marcajul Q poate fi, de asemenea, definit ca un vector n-dimensional Q ! (Q1 ,..., Q n ) unde n= card(P), i ! 1,..., n, Q i 2 Definitiile apartenente uni marcaj ca o functie si ca un vector se bazeaza, in mod evident, pe relatia Q ( pi ) ! Q i .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 n din 2 . Aceasta multime infinita este bineinteles nenumarabila.

10

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 t j T dintr-o retea Petri marcata C= (P, T, I, O) cu marcajul Q este permisa daca pentru toate pi P , Q ( pi ) u # ( pi , I (t j )) . 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 t j intr-o retea Petri marcata cu marcajul Q se poate declansa de fiecare data cand este posibila. Declansarea unei tranzitii t j posibile produce un nou marcaj ' Q ' definit de relatia: Q ( pi ) ! Q ( pi ) # ( pi , I (t j )) # ( pi , O (t j ))

# ( pi , I (t j )) ! 0 # ( pi , I (t j )) ! 1 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

Q ( pi ) ! Q ( pi )

Q ( pi ) ! 1 Q ( pi )

Q ( pi ) ! Q ( pi ) 1

Q ( pi ) ! Q ( pi ) 1 1

Exemplu: avem urmatoarea figura:

FIG 4: Retea Petri marcata pentru a arata regulile de declansare. Tranzitiile t1 , t3 , t4 sunt posibile. Deci, consideram reteaua Petri marcata, ca in figura 4 . Cu acest marcaj, trei tranzitii sunt posibile si anume t1 , t3 , t4 , tranzitia t 2 nefiind posibila deoarece nu se afla nici un jeton in nici una din locatiile aferente si anume p2 , p3 care sunt amandoua intrari ale tranzitiei t 2 . Putem observa ca declansarea lui t4 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 n spatiul starilor unei retele Petri este multimea tuturor marcajelor, adica 2 , schimbarea de stare cauzata de declansarea unei tranzitii este definita de o functie de schimbare numita functie de tranzitie. n n Definitia 7: functia de tranzitie : 2 v T p 2 pentru o retea Petri C = (P, T, I, O) cu marcajul Q si tranzitiile t j T este definita daca si numai daca Q ( pi ) u # ( pi , I (t j )), pi P .0 Data fiind o retea Petri C = (P, T, I, O) cu marcajul initial Q , putem executa reteaua Petri prin declansari succesive de tranzitii. Declansarea unei tranzitii posibile t j T in marcajul 1 0 initial produce un nou marcaj Q ! H ( Q , t j ) . In marcajul nou, putem declansa orice tranzitie 2 1 posibila, si anume tk , ceea ce determina aparitia unui nou marcaj Q ! H ( Q , tk ) . 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

-

12

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 Q , un marcaj Q este direct accesibildin Q daca exista o tranzitie t j T astfel incat H ( Q , t j ) ! Q . Definitia 9: Multimea de accesibilitate R(C , Q ) pentru o retea Petri C = (P, T, I, O) cu marcajul Q este cea mai mica multime de marcaje definita dupa cum urameaza: - Q R(C , Q )' '' '' - daca Q R (C , Q ), Q ! H ( Q ' , t j ), t j T Q R (C , Q ) 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.

13

Solu ie: 1. Aplicnd 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) . 14

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

15

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: a) atelierul este in asteptare b) a sosit un ordin si este in asteptare c) atelierul prelucreaza ordinul d) prelucrarea ordinului sa incheiat Evenimentele pot fi: 1. sosirea unui ordin 2. 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 1 2 3 4 Preconditii Nici una a, b c d Postconditii b c d, a Nici una

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 16

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 M 1 , M 2 , M 3 si doi operatori F1 si F2 . Operatorul F1 poate opera masinile M 1 , M 2 , iar operatorul F2 poate opera masinile M 1 , M 3 . Lucrarile necesita doua stagii de prelucrare, mai intai acestea trebuie prelucrate de masina M 1 , apoi de oricare dintre celelalte doua masini. Deci avem sistemul cu urmatoarele conditii: a) A sosit o lucrare si asteapta sa fie prelucrata de M 1 b) O lucrare a fost prelucrata de M 1 si asteapta sa fie prelucrata si de celelalte masini c) Prelucrarea lucrarii s-a terminat d) Masina M 1 este libera e) Masina M 2 este libera f) Masina M 3 este libera g) Operatorul F1 este liber h) Operatorul F2 este liber i) Masina M 1 este operata de F1 j) Masina M 1 este operata de F2 k) Masina M 2 este opearata de F1 l) Masina M 3 este operata de F2 Aici pot aparea urmatoarele evenimente: 1) Soseste un ordin 2) Operatorul F1 porneste prelucrarea lucrarii pe masina M 1 3) Operatorul F1 termina prelucrarea lucrarii pe masina M 1 17

4) Operatorul F2 porneste prelucrarea lucrarii pe masina M 1 5) Operatorul F2 termina prelucrarea lucrarii pe masina M 1 6) Operatorul F1 porneste prelucrarea lucrarii pe masina M 2 7) Operatorul F1 termina prelucrarea lucrarii pe masina M 2 8) Operatorul F2 porneste prelucrarea lucrarii pe masina M 3 9) Operatorul F2 termina prelucrarea lucrarii pe masina M 3 10) Ordinul de livrare este trimis Preconditiile si postconditiile fiecarui eveniment sunt urmatoarele: Eveniment Preconditii Postconditii 1 Nici una A 2 a, g, d I 3 i g, d, b 4 a, h, d J 5 f b, h, d 6 b, g, e K 7 k c, g, e 8 b, f, h L 9 l c, f, h 10 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

18

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.

19

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 Cele doua tranzitii se pot declansa in orice ordine

FIG 9: Conflict Aici tranzitiile sunt in conflict deoarece declansarea oricareia jetonul din p i 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 20

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 vech ea 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 21

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 p1sau p2 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 t1si t2 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.

22

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.

23

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.

24

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.

25

E3

M3

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

26

c2

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 pi a unei retele Petri C=(P,T,I,O) cu marcajul initial Q este sigura daca pentru toate Q R (C , Q ), Q e 1 , 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 pi ca intrare sai iesire, se modifica dupa cum urmeaza: ' - daca pi I (t j ), pi O (t j ) atunci se adauga pi laO (t j ) .' daca pi O (t j ), pi I (t j ) atunci se adauga pi laI (t j ) ' Scopul acestei noi locatii pi este acela de a reprezenta conditia pi este goala , de aceea ' cele doua sunt complementare, adica pi are un jeton numai daca pi nu are nici unul, si invers.

-

' Orice tranzitie care muta un jeton din pi trebuie sa depoziteze unul in pi 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.

27

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 pi P a unei retele petri C=(P,T,I,O) cu un marcaj initial Q este k' ' sigura daca pentru fiecare Q R(C , Q ), Q e k . 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.

28

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.

29

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 Q este strict conservativa daca Q ' R (C , Q ), Q ' ( pi ) ! Q ( pi ) pentru toate . piP piP 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 Q este conservativa cu respectarea [ , [ ! ([1 ,..., [ n ), n ! P , [ i u 0 daca unui vector de ponderi pentru toateQ ' R(C , Q ), [ i Q ' ( pi ) ! [i Q ( pi )i i

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

30

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 Q si un marcaj Q ' , Q ' R (C , Q ) .' Definitia 15. Problema acoperirii- o retea Petri C cu marcajul initial Q exista un marcaj '' '' ' accesibil Q R (C , Q ), a.i.Q u Q . 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.

31

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.

32

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 Q ! Q ( Q Q ), Q Q " 0 , deoarece decansarile tranzitiilor nu sunt afectate de jetoanele suplimentare, secventa poate fi declansata din nou, incepand din Q ' si terminand in Q '' . Deoarece efectul secventei de tranzitii a fost sa adauge Q ' Q '' jetoane la marcajul , la aceasta noua declansare va mai aduga inca Q Q jetoane la'' ' ' ' marcajul Q , astfel incat Q ! Q ( Q Q ) . 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 [ a ! [; [ a ! [; a [; [ e [ , 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.

t1

(1 2 0)

33

t1

t2

Fie x un nod de frontiera ce urmeaza sa fie procesat atunci: 1. Daca exista un alt nod y in arbore care nu este nod de frontiera si are acelasi marcaj asociat adica Q ( x) ! Q ( y ) 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 Q [ x ] j ! [ , atunci, Q[ z ]i ! [ b) daca exista un nod y pe drumul de la radacina la nodul x cu Q [ y ] H ( Q [ x ], t j ) siQ [ y ]i H ( Q [ x ], t j ) i , atunci Q [ z ]i ! [ . c) Altfel, Q [ z ]i H ( Q [ x ], t j )i . 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. -

34

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 Q daca un marcaj Q u Q este accesibil, dat fiind un marcaj initial , construim arborele de accesibilitate, apoi cautam orice nod x, cu Q [ x] u Q ' , daca nu se gaseste un astfel de nod, marcajul Q ' 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 ct mai facil . Metodologiile elaborate pn n prezent, consider detectarea erorilor numai la nivelul echipamentelor, att timp ct 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]: y bazate pe model/model-based: starea actual i viitoare (dintr-un model matematic) sunt comparate pentru determinarea erorii; y bazate pe cunoa tere/knowledge-based: modele calitative sunt asociate cu modele euristice pentru determinarea cauzei erorii;

35

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: y detectare; y culegerea datelor parametrilor opera ionali date de senzori; y identificarea st rii opera ionale (normale sau anormale); y determinarea cauzei erorii; y tratare. 4.3.1.Detectarea erorilory

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;

36

-

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.

Dispozitiv comand

Dispozitiv monitorizare

supervizorproie ctant Dispozitiv control reparare

senzor

actuatormainti ner

Obiect de control Extragere dateeroare

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, pn cnd echipamentul respectiv ajunge operativ. La nivelul produc iei, tratamentul erorilor este efectuat de reprogramarea rutelor fluxului de material n celule. 37

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: y actualizarea colec iei de protocoale; y Modificarea proceselor continue; y 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 nct L. Fiec rei etichete i este asociat un num r natural unic, denumit rangul etichetei. Atunci definim mul imea etichetelor de tranzi ie X a ! _ a _ ( x1 ,..., xn ), a L, n ! rang (a ), x1 ,..., xn U a. 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, , , N), unde P, T sunt dou mul imi nevide (reprezentnd mul imea loca iilor i respectiv mul imea tranzi iilor), P T = J ; F PxT este mul imea arcelor TxP este o loca ie dat ca o func ie cu dom( )=P, astfel nct (p) U, pentru orice p P ; este o func ie de tranzi ie cu dom( )=T, astfel nct V (t ) (N t ) v ] t ,

t T , pentru orice p ] t ! _ p Y ( p ) (t , p ) F a;

unde

p N t ! _ p Y ( p ) ( p, t ) F a

i

-

Neste o func ie de etichetare cu dom( N _t , K , H ) t T (K , H ) V (t )a i )= ( ran( N . )

38

Definitia 17: Fiind dat o re ea colorat N=(P,T,F, , , N) peste universul U, un marcaj pentru N este o func ie M : P v U p N, astfel nct pentru orice p P i orice u U , M(p,u) 0 implic u Y ( p ) . Mul imea tuturor marcajelor a re elei colorate este dat de Q (N ) . O re ea cu marcaj colorat peste U este o pereche (N,M), unde N este o re ea colorat peste U i M Q (N ) 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 p M v v M este definit ca cea mai micNt ,K ,H ( i rela ie astfel nct ( N , M K ) p(n, M H pentru orice (N;M) 1 , t T (K , H ) V (t ). Mai putem scrie ( N , M ) H pentru H i numai dac exist un marcaj p M d Q (N ) astfel nct ( N , M ) H ( N , M d n final, ( N , M ) * ( N , M d p ). p ) nseamn c (W 1 ,..., W n ) astfel exist o secven nct

H2 Hn ( N , M ) ! ( N , M 1) H 1 ( N , M 2) p ... p( N , M n 1) ! ( N , M d n acest caz putem ). p ) este spune c ( N , M d 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 nct tranzi iile trebuie sa termine execu ia re elei curente [43],[58]. Defini ia 19: O re ea colorat N=(P,T,F, , , N) peste universul U este o re ea fluxuri de lucru extins cu loca ia ini ial i P , i loca ia final f P i mul imea tranzi iilor de excep ie T d T dac : t t 1. _ (t , i ) F a! _ ( f , t ) F a! ;negru a; 2. Y (i ) ! Y ( f ) ! _ dac 3. pentru orice t T , (K , H ) V (t ), t T d ( i numai dac Nt , K , H ) e

dac

i

numai dac 4. pentru orice nod n ( P T ) exist o cale/drum de la i la n; 5. pentru orice nod n ( P T ) exist o cale de la n la un nod n T d _f a. 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 n o terminare tre 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 cnd era ntlnit 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 M Q (N ) . Marcajul re elei (N,M) este denumit ini ial, respectiv i final, dac i numai dac M ! ?A, respectiv M ! ?f A. Ini ializarea init(N) lui N este i re eaua marcat N, ?A. 5.2. Stabilitatea re elelor EWF 39

_p (t , p) F a! ;

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, , , N cu o loca ie ini ial i i una final f ) i) peste universul U se nume te stabil dac i numai dac pentru orice ( N , M ) R( N , ?A * ( N , M d R N , M ) ( N , M ) ( N , ?f A sau p ) exist a.. 1. fiecare( N , M d p pentru un H ) H* e

;

( N , M ) ( N , m ?f A implic m= pentru orice m Q (N ) . p ) 2. 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 pn 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 * * p p f ) ce permite st rii M s ajung n starea final f: M , (i M ) (M 2. starea f este numai starea accesibil din starea i cu cel pu in un jeton n loca ia f: M , (i * M M u 0) (M ! 0) p T * p p 3. nu exist tranzi ii moarte, adic t T , M , M d astfel nct i M M d . 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 , , , N o re ea stabil EWF peste universul U. Fie Q P _f a,e

t T

i

h:

pQ

(Y ( p )) p

e

.

Fie

Nd

( P, T _a F _ p, t ) p QaY , V d d unde t, ( , ,N ), V d ) ! V (u ) pentru u T i V d) ! N (t )) v _ a (u (t y d Nu ,Y , H ) ! N ,Y , H ) , ( (u u T, i pentru y d Nt , K , ) ! h(K ) pentru orice K (N t ) . ( Atunci re eaua N d o re ea stabil EWF peste U. este

(K , H ) V (u ), i

(t Remarcam c t este o tranzi ie de excep ie avnd H ! , pentru orice (K , H ) V d) . Lema 2: permite folosirea unei aproxim ri incrementale pentru a modela n primul rnd cu o execu ie normal evenimentul apoi ad ugarea excep iei.

5.3. Opera ii cu re ele EWF

40

Una dintre cele mai importante facilit i oferite de modelarea cu re ele Petr este i 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 ugnd 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 utiliznd 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,N2 NW , N 1 N 2 , N 1 N 2, N 1 N 2 N1 , N 2 asociativ , iar i + sunt comutative. Dac

W

. Mai mult stabile

i + este atunci

sunt

N 1 N 2 , N 1 N 2, N 1 N 2 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 ( N 1 , M ) N 2 ! ( N 1 N 2 , M ) , iar compunerea paralel : ( N 1 , M 1)) ( N 2 , M 2) ! ( N 1 N 2, M 1 M 2) , unde ( N 1 , M 1), ( N 2 , M 2 ) 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 . 41

, , Teorema 1: Fie N 1 , N 2 , N 1dN 2 d ele EWF, astfel nct N 1 !e N 1dN 2 !e N 2 dAtunci re . d d , ), , ), N 1U N 2 !e N 1 U N 2 ,U _ , ,a Fie ( N 3 , M 3), ( N 3 dM 3d ( N 4 , M 4 ), ( N 4 dM 4 d re ele EWF . ( N 3 , M 3) !e ( N 3dM 3 d ( N 4 , M 4 ) !e ( N 4 dM 4 d.Atunci , ), , ) cu ( N 3 , M 3) ( N 4 , M 4 ) !e ( N 3dM 3d( N 4 dM 4 d i ( N 3 , M 3) N 2 !e ( N 3dM 3d N 2 d , ) , ) , ) .

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 adncime 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 adncimii 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 = Un0 Nn,Mw = Un0 Mn i Uw = U0 Mw. Observ m c defini ia recursiv a no iunii de re ea imbricat marcat de adncime n permite jetoanelor s fie colorate de re ele imbricate de adncime 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.

w Teorema 2. Fie L N [ 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.

desf

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

i

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: 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 nct 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 pn 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 gtul. 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 gtul intr-o singur parte. 4. Se pune un sul de carton n partea dreapt a cutiei 5. Acea i parte se imp tura de 2 ori in cutie 6. Se pune un sul de carton in partea stang a cutiei 7. Acea i parte se imp tura de 2 ori n cutie 8. 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 palet Modelarea celor dou opera ii cu re ele Petri este cea din figura 27.

43

a) Fig. 27. Modelarea opera iei de t iere

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

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 ct 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 Metod Persoan Ma in Persoan Cauz Operatorul nu a primit informa ii despre metodele de selectare Datum i a pozi iei critice. Operatorul nu a verificat termenii standard ai cortinei Eroare software opera iei de t iere pe Ac iune Pozi ionarea corect a senzorului P2. Pozi ionarea senzorului P2 arat operatorilor punctele de focalizare

durata Este necesar suport tehnic pentru determinarea originii cauzei Stabilirea originii cauzei n ansamblu, analiza acesteia i luarea deciziilor detaliate necesare

B: Opera ia de capsare a e uat Categorie Persoan Persoan Persoan Persoan Cauz Operatia a fost comandat operator Ac iune de Detectarea manual a metalului n celul Detectarea manual a metalului n celul Operatorul trebuie s aplice tampila mai aproape de ambele capse Instalarea sistemului de senzor n detectarea prezen ei capsei

Operatorul nu efectuat inspec ia Operatorul nu efectuat inspec ia Operatorul nu efectuat inspec ia

45

C:T iere prea aproape de linia neagr Categorie Ma in Persoan Cauz Aliniere incorect a materialului Ac iune Plasarea senzorilor care detecteaz alinierea incorect a materialului Operatorul nu a aliniat normal Plasarea senzorilor care materialul 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.

46

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 ( d i ) ntr-o anumit loca ie din re eaua tranzi ia t j care genereaz eroarea, plaseaz n loca ia p k un jeton de culoare col d i . Re elei originale i conect m de tip imbricare cte o subre ea pentru fiecare tip de eroare. Tranzi ia poate genera un num r de erori simultan. n acest caz Id-jeton reprezint col d i . Defini ie: Numim re ea extins N e , o re ea SM1WF n care pentru fiecare defect d i tranzi iei t j care genereaz eroarea i se ata eaz o loca ie de ie ire p d i , n care la momentul apari iei eroriii prin ac iunea tranzi iei t j se plaseaz un jeton cu culoarea col d i Teorem : Re eaua N e 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 N e ) este o re ea SM1WF stabil i presupunem c re eaua extins N e nu este stabil . Atunci exist o i un marcaj m p ce poate fi atins din loca ia ini ial i secven de tranzi ii W W p ?A m p , i marcajul m p nu poate ajunge n starea final f, m p * ?f A. Lu m i p suficiente resurse m0 care sunt permise/accesibile tranzi iilor t j , atunci marcajul m p mr * p i este accesibil/atins n ( N , i m0 ) m p mr ?A mo dar nu este atins n ( N , f m0 ) , (nu* p are loc rela ia m p mr ?f A mo ) ceea ce contrazice ipoteza stabilit SM1WF, deci re eaua N e este stabil .

ii re elei

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.

47

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.

BIBLIOGRAFIE48

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 ResourceConstrained 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 Romne. 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. 49

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/

50