Imbricarea retelelor Petri

Imbricarea retelelor Petri

Pentru a construi un sistem mai flexibil al managementului fluxului de producție se poate utiliza rețelelor Petri imbricate. Pentru gasirea unei soluții este necesar sa se cunoasca toate etapele, situațiile de excepție și orice combinație a acestora, folosind abilitatea, modificarea structurala a proceselor, chiar inlocuirea subproceselor sau extinderea lor. Presupunem data o colecție (biblioteca) a protocoalelor care vor fi utilizate ca blocuri de baza pentru construcția unor protocoale mai complexe [18].

Rețelele Petri imbricate sunt rețele Petri in care jetoanele pot fi rețele Petri insași, numite rețele jeton ( TN-Token Nets). Capacitatea de modificare a rețelelor jeton TN  are urmatoarele avantaje:

acutalizarea colecției de protocoale;

Modificarea proceselor continue;

Capacitatea de modelare a deciziilor luate ca parți diferite.

Pentru a introduce rețele Petri imbricate consideram un tip special de rețele colorate. Presupunem ca mulțimea U conține valoarea negru, corespunzatoare obiectelor ce nu conțin informații.

Intr-o rețea colorata, fiecare locație este mapata cu un tip, care este o submulțime a lui U. Mai presupunem ca L este mulțimea etichetelor pentru tranziții astfel incat τ L. Fiecarei etichete ii este asociat un numar natural unic, denumit rangul etichetei. Atunci definim mulțimea etichetelor de tranziție . Eticheta τ este o eticheta "silențioasa"/fara efect.

Definiție 1: O rețea colorata peste universul U este un 6-uplu (P,T,F,ʋ,ρ, ), unde

P, T sunt doua multimi nevide (reprezentand multimea locatiilor si respectiv multimea tranzitiilor), PT = ;

este mulțimea arcelor

ʋ este o locație data ca o funcție cu dom(ʋ)=P, astfel incat ʋ(p)U, pentru orice p;

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

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

Definitia 2: Fiind data o rețea colorata N=(P,T,F,ʋ,ρ, ) peste universul U, un marcaj pentru N este o funcție MN, astfel incat pentru orice pși orice u, M(p,u)˃0 implica . Mulțimea tuturor marcajelor a rețelei colorate este data de .

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

O rețea colorata definește un sistem de tranziție care furnizeaza starile observabile ale rețelei.

Definiția 3. O relație ternara este definita ca cea mai mica relație astfel incat pentru orice (N;M) , și Mai putem scrie și numai daca exista un marcaj astfel incat In final, inseamna ca exista o secvența astfel incat . In acest caz putem spune ca este accesibila in (N,M).

4. Rețele fluxuri de lucru extinse

Rețelele fluxuri de lucru ( rețea WF) au o locație inițiala și una finala, și orice locație sau tranziție este o cale direcționata din locația inițiala spre cea finala. Extindem noțiunea rețea WF la un model special/excepție astfel incat tranzițiile trebuie sa termine execuția rețelei curente [43],[58].

Definiția 4: O rețea colorata N=(P,T,F,ʋ,ρ, ) peste universul U este o rețea fluxuri de lucru extinsa cu locația inițiala i, și locația finala f și mulțimea tranzițiilor de excepție daca:

1. Ø;

2. ;

3. pentru oricedaca și numai daca daca și numai daca Ø;

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

5. pentru orice nod exista o cale de la n la un nod in .

Rețele EWF confera un numar de avantaje din mai multe puncte de vedere ale modelarii intre care menționam faptul ca acestea fac o distincție clara intre o terminare normala și o terminare generata de o excepție. Spre deosebire de rețelele tradiționale fluxuri de lucru WF, o atenție speciala se acorda mutarii tuturor jetoanelor prezente in sistem cand era intalnita o situație de exceptie, in rețelele EWF aceasta cerința nu se utilizeaza[18].

Definiția 5: Fie N o rețea extinsa de fluxuri de lucru (EWF) cu o locație inițiala i și una finala f, și fie . Marcajul rețelei (N,M) este denumit inițial, respectiv final, daca și numai daca , respectiv . Inițializarea init(N) lui N este rețeaua marcata .

2. Stabilitatea rețelelor EWF

O alta proprietate naturala a rețelelor EWF este stabilitatea. Rețelele clasice WF. sunt stabile daca de la orice marcaj intermediar se ajunge la marcajul final. Proprietatea de soliditate/stabilitatea mai este uneori denumita terminare normala.

Definiția 6: O rețea EWF N=(P,T,F,ʋ,ρ, ) cu o locație inițiala i și una finala f peste universul U se numește stabila daca și numai daca pentru orice

fiecare sau exista a.i. pentru un ;

implica m=Ø pentru orice .

Din noțiunea de stabilitate formalizata in definiția 6, reiese faptul ca pentru orice stare posibila intotdeauna exista o posibilitate de a completa execuția pana intr-o stare finala, sau de a raporta o excepție. O a doua cerința a stabilitații este faptul ca nu se ajunge la o stare finala fara o execuție completa. In cazul rețelelor WF clasice, a doua condiție a stabilitații este redundanta.

Definiția 7. O rețea WF este stabila daca și numai daca:

pentru orice stare M accesibila din starea inițiala i, exista o secvența de tranziții ce permite starii M sa ajunga in starea finala f:

starea f este numai starea accesibila din starea i cu cel puțin un jeton in locația f:

nu exista tranziții moarte, adicaastfel incat .

Proprietatea de stabilitate reda dinamica rețelelor WF. Din prima cerința a definiției 7. reiese faptul ca dintr-o stare intermediara (posibila din starea inițiala) intotdeauna se poate ajunge intr-o stare finala. A doua cerința specifica faptul ca in momentul in care avem un jeton in starea finala, toate celelalte locații trebuie sa fie goale/vide. In majoritatea cazurilor, noțiunea de terminare proprie/normala este asociata primelor doua cerințe ale definiției anterioare. A treia cerința a definiției, afirma faptul ca din starea inițiala prin intermediul unei tranziții se poate ajunge la o noua locație (stare).

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

și

, pentru și și pentru orice .

Atunci rețeaua este o rețea stabila EWF peste U.

Remarcam ca t este o tranziție de excepție avand , pentru orice .

Lema 1 permite folosirea unei aproximari incrementale pentru a modela in primul rand cu o execuție normala evenimentul apoi adaugarea excepției.

Operații cu rețele EWF

Una dintre cele mai importante facilitați oferite de modelarea cu rețele Petri este evidențiera concurenței (paralelismului), sincronizarii și a conflictelor. Deoarece sistemele reale sunt complexe și este necesara o modularizare a lor se impune asigurarea unor facilitați de compunere.

Vom considera orice rețea ca fiind rețea EWF. Mulțimea tuturor rețelelor EWF marcate, sunt notate N^w (M^W). Consideram numarul predicatelor și operațiilor pe rețele și rețele cu marcaj. Utilizam definiția 5 pentru a converti o rețea intr-o rețea cu marcaj, adaugand un marcaj inițial corespunzator și pentru orice rețea cu marcaj, putem verifica daca este un marcaj inițial și unul final.

Doua rețele pot fi combinate pentru a construi o noua rețea utilizind compunere secvențiala, paralela și alegere. Mai mult, compunerea paralela poate fi aplicata rețelelor marcate și compunerea secvențiala rețelelor și rețelelor marcate. Operații similare sunt definite și pentru rețelele fluxuri de lucru.

Fig. 4. Compunerea rețelelor

Lema 3: Pentru orice N₁,N₂N^W ,. Mai mult și + este asociativa, iar și + sunt comutative. Daca sunt stabile atunci sunt de asemenea stabile.

Rolul compunerii secvențiale este de a extinde procesul de rulare cu o noua funcționalitate. Astfel definim compunerea secvențiala ca o operație pe rețele cu marcaj și rețele (simple) dupa cum urmeaza , iar compunerea paralela: , unde sunt rețele EWF cu marcaj.

Operațiile rețelelor cu marcaj satisfac urmatoarea lema:

Lemma 4 Pentru orice {N₁,M₁),(N₂,M₂) M^w și N N^w, (N₁, M₁) ·N M^w, și (N₁, M₁) || (N₂, M₂) M^w. mai mult, · este asociativa și || este comutativa.

Compunerea paralela și alegerea sunt congruente in raport cu EWF-bisimilaritea și compunerea secvențiala este congruenta daca primul operator este stabil [17], [18].

Teorema 1: Fie rețele EWF, astfel incat . Atunci . Fie rețele EWF cu . Atunci și .

4. Imbricarea rețelelor

Consideram un univers inițial U ce conține valori de baza, cum ar fi valori intregi, valori compuse cum ar fi perechile/cuplu, liste și mulțimi ale valorilor compuse. Universul urmator și mulțimile rețelelor sunt definite recursiv prin urmatoarea definiție:

Definiția 8 Mulțimile N₀, M₀ ale rețelelor și marcajul rețelei de adancime zero este definit ca mulțimile rețelelor colorate și rețelelor marcate colorate cu peste universul U₀.. Pentru fiecare n > 0 valoarea universului U_n mulțimile N_n, M_n ale rețelelor și rețelelor marcate ale adancimii n sunt definite recursiv: U_n= U_n-1 M_n-1 și N_n și M_n ca mulțimea rețelelor colorate și a rețelelor cu marcaj color peste universul U_n. mulțimea Nw U_n≥0 N_n,Mw = U_n≥0 M_n și Uw = U₀ Mw.

Observam ca definiția recursiva a noțiunii de rețea imbricata marcata de adancime n permite jetoanelor sa fie colorate de rețele imbricate de adancime n-1.

Exemplu: consideram ca mulțimea U₀ conține doar numere naturale. In figura 1 se folosește N₁ ca jeton in rețeaua N₀.

Fig. 4. Rețea Petri imbricata

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: Consideram rețeaua Petri imbricata pentru doua operații/activitați desfașurate in cadrul Autoliv Lugoj. (producția de airbag-uri)[37].

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

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

Materialul trebuie aliniat astfel incat marginea materialului sa fie perpendicular pe senzor. Senzorul are rolul de aliniere automata a marginii materialului.

La incarcarea materialului in mașina. acesta va fi introdus minim pana la jumatatea mașinii dupa care se va realiza selectarea Datum-pointului pentru primele piese.

Taie perna cu punctul de referinta indicat folosind markerul.

Verificarea vizuala unor eventuale defecte:- defecte de țesatura șı a ınvelısuluı de sılıcon referıtoare la catalogul de standarde acceptate vor fı separate ın cutıa de rebuturı

Ia elementul decupat și deschide gatul.

Introdu bara pentru a te asigura ca nu este lipit.

Pune perna in zona de așteptare a urmatoarei operații de la stația alaturata.

Operația de impachetare:

1. Inainte de a pune in cutie, pentru fiecare bucata se apasa pe butonul numaratorului pentru a urmari exact numarul de piese in cutie.
2. In cutia de plastic se așeaza o punga de plastic albastra in care se vor impatura produsele, scopul acesteia este sa protejeze airbagurile.
3. Se introduc 16 cortine in cutie, toate fiind orientate cu gatul intr-o singura parte.
4. Se pune un sul de carton in partea dreapta a cutiei
5. Aceași parte se impatura de 2 ori in cutie
6. Se pune un sul de carton in partea stanga a cutiei
7. Aceași parte se impatura de 2 ori in cutie
8. Dupa ce s-au pus in cutie 16 OPW-uri cu h-sock-urile introduse, se scoate eticheta de cutie,se ștampileaza și se pune deasupra OPW-urilor.
9. Ultima operație este reprezentata de impaturarea pungii deasupra produselor. Fiecare cutie se va pune pe palet

Modelarea celor doua operații cu rețele Petri este cea din figura 2.

a) b)

Fig. 2. Modelarea operației de taiere și ambalare cu rețele Petri.

In figura 2. a) este prezentata o rețea imbricata, adica jetonul Rețea2 este rețeaua din figura 2. b).

Verificarea fluxului de lucru conține trei componente principale:

- verificarea structurii (are ca scop studierea consistenței fluxului de lucru, adica determinarea ,daca este cazul, a blocajelor, ciclarii sau/și lipsa sincronizarii);

- verificare temporara ( restricțiilor temporare le sunt atribuite importante specificații ale fluxului de lucru);

- verificarea resurselor/ analiza performanțelor (verificarea resurselor are ca scop stabilirea starii resurselor pentru a nu aparea conflicte intre activitați).

Din paragrafele anterioare, stabilitatea rețelei Petri implica o terminare normala, adica activitațile/operațiile sunt finalizate fara probleme.

In cazul in care nu exista stabilitate, avem o terminare anormala. Aceasta terminare anormala se datoreaza aparițiilor unor erori. Pentru remedierea acestora este necesara o detectare/determinare intr-un timp cat mai scurt, pentru ca activitațile care urmeaza sa poata fi duse la final (terminare proprie).

Analiza operației de taiere, duce la apariția urmatoarelor defecte:

A: Perna taiata cu caracteristici greșite

B: Operația de capsare a eșuat

C:Taiere prea aproape de linia neagra

Tratarea erorilor

In derularea unui proces/activitate de producție se produce o stare de excepție. In acel moment, se introduce intr-o locație un jeton cu un anumit atribut (culoare) și locația respectiva este intrare intr-o subrețea care trateaza excepția/eroarea respectiva (rețele imbricate).

Tranziția care declanșeaza excepția acționeaza daca atributul in cauza are o anumita culoare. Tranziția face verificarea culorii cu ajutorul funcției de etichetare.

In teoria clasica a rețelelor Petri, jetonul este la un moment dat un parametru al starii. In modelele construite și derivatele rețelelor Petri, in funcție de context, jetoanele primesc semnificații particulare, cum ar fi:

identificator, care identifica un obiect real;

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

In funcție de context, prin Id-jeton vom ințelege un atribut(culoare), și unde va fi cazul vom specifica faptul ca Id-jeton identifica un obiect, iar acolo unde va fi cazul vom preciza ca jetonul va avea anumite atribute (culori).

Extensie pentru tratarea erorilor

Definim o rețea SM1WF in care pentru o roare specifica () intr-o anumita locație din rețeaua tranziția care genereaza eroarea, plaseaza in locația un jeton de culoare .

Rețelei originale ii conectam de tip imbricare cate o subrețea pentru fiecare tip de eroare. Tranziția poate genera un numar de erori simultan. In acest caz Id-jeton reprezinta .

Definiție: Numim rețea extinsa , o rețea SM1WF in care pentru fiecare defect

tranziției care genereaza eroarea i se atașeaza o locație de ieșire , in care la momentul apariției eroriii prin acțiunea tranziției se plaseaza un jeton cu culoarea

Definiție

Teorema: Rețeaua construita in definiția anterioara este stabila.

Dem: Pentru a demonstra stabilitatea rețelei, consideram ca toate jetoanele au aceeași culoare. In continuare, consideram ca rețeaua N (pe care o extindem la ) este o rețea SM1WF stabila și presupunem ca rețeaua extinsa nu este stabila. Atunci exista o secvența de tranziții și un marcaj ce poate fi atins din locația inițiala i , și marcajul nu poate ajunge in starea finala f, . Luam suficiente resurse care sunt permise/accesibile tranzițiilor , atunci marcajul este accesibil/atins in dar nu este atins in , (nu are loc relația) ceea ce contrazice ipoteza stabilitații rețelei SM1WF, deci rețeaua este stabila.

Paleta extinsa de modelare și de instrumente de analiza oferita de rețelele Petri și derivatele lor a permis

sa modelam procesul, fluxul de prelucrarre

sa evidențiem particularitațile

sa dezvoltam modelul cu extensii pentru analiza și prelucrarea defectelor.

Condițiile esențiale ale funcționarii corecte a unui sistem sunt in esența: derularea normala, stabilitatea și acolo unde este posibil tratarea erorilor. Pentru rețelele Petri imbricate am dezvoltat treptat și demonstrat prin particularizare proprietațile legate de stabilitate. Sistemele reale utilizeaza resurse care sunt partajate in comun de componentele lor. Componentele concureaza intre ele pentru accesul la resurse și aceasta necesita eleborarea unor modele adecvate. In acest sens, pornind de la rețele Petri clasice s-au dezvoltat treptat derivate ale lor care conserva proprietațile fundamentale: marginire, viabilitate, stabilitate. Pentru toate acestea unde a fost necesar am dat teoreme și le-am demonstrat.