Rețele Petri - instrument de modelare

Introducere

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

S-a urmarit:

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

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

3. Definirea reţelelor Petri temporizate cu salturi şi a structurilor de acoperire respective.

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

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

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

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

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

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

CAPITOLUL 1

DEFINITII FUNDAMENTALE

1.1. Structura unei retele Petri

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

- o multime da tranzitii T;

- o functie de intrare I;

- o functie de iesire O;

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

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

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

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