Retele Petri Algebrice. Modele de Sincronizare a Proceselor Paralele

INTRODUCERE

Posibilitățile de modelare ale rețelelor Petri și eficiența lor în aplicații se explică, înainte de toate, prin aceea că, rețeaua Petri este o integrare de graf și de sistem dinamic , ea poate servi, în felul acesta, și ca model static și ca model dinamic al unui obiect reprezentat cu ajutorul ei. Totodată, absența unei ordini analitice, fixate strict la determinarea – ieșirii rețelei, face acest sistem nedeterminat algoritmic în același sens ca și pentru modelele de imitare. Rețelele Petri joacă un rol deosebit la modelarea proceselor paralele, aici acesta reprezentând aproape cel mai comod și promițător instrument de cercetare . O nu mai mică importanță are cunoscutul avantaj al acestor rețele – comoditatea programării lor pe calculator.

Aplicarea rețelelor Petri nu se limitează, însă, la modelarea proceselor și sistemelor dinamice. Ele se folosesc cu succes în programarea teoretică , la soluționarea problemelor de specificare funcțională și verificarea asigurării de programe , organizarea proceselor de calcul , comandă .

Este esențial să se evidențieze patru obiective de cercetare a obiectivelor cu ajutorul rețelelor Petri:

1) interpretarea (programarea obiectului), legată de o reprezentare adecvată a obiectului ce se modelează cu rețelele Petri;

2) programarea modelului într-un mediu operațional concret;

3) cercetarea modelului;

4) trecerea din limbajul rețelelor Petri în limbajele de programare, acest obiectiv a apărut relativ recent legat de realizarea sistemelor de comandă pe baza modelelor de rețele.

Dezvoltarea teoriei rețelelor Petri în planul soluționării problemelor arătate, și în special al obiectivului , duce la apariția unor diverse modificări ale acestora. La nivel verbal procesul generalizării descrierii rețelelor Petri poate fi reprezentat în felul următor. Cele mai limitate rețele automate și grafurile marcate, care permit o intrare și o ieșire pentru tranziții și respectiv locații. Întotdeauna nu examinarea multiplicativității arcelor sau numai a jetoanelor in locații permite deja modelarea nu numai a funcționării sistemelor paralele, ci și a dinamicii resurselor.

Complicarea respectivă a rețelelor extinde în mod esențial posibilitățile descrierii sistemelor fizice, totuși obligă la a se recurge la diferite construcții artificiale, la descrierea proceselor ce interacționează, ce se desfășoară în aceleași subsisteme funcționale indivizibile. Ieșirea din această situație s-a dovedit a fi permisiunea existenței unor jetoane și arce colorate. Dezvoltarea acestei idei a dus la apariția cîtorva variante de descriere a rețelelor Petri colorate, care, însă, nu au deosebiri de principiu și pot fi transformate în mod izomorf una în alta.

Necesitatea cercetării dinamicii fluxurilor de resurse în sisteme a obligat la căutarea căilor de includere în rețelele Petri a parametrilor de timp într-o formă evidentă. Totuși, în rețelele Petri în reprezentarea lor actuală nu se deosebește ordinea intrării jetoanelor în locatii, ceea ce nu permite întotdeauna ordinii lineare pe multimea de jetoane în locații și, ca atare, ordonarea evenimentelor în timp printr-o cale naturală, în cadrul porpriu-zis al rețelelor. De exemplu, se recurge la informația din afară. De exemplu, în lucrările timpul este introdus prin întârzierea jetoanelor în locatii, există și alte căi similare.

Generalizarea ulterioară a rețelelor Petri examinată în lucrare se reduce ușor la toate modelele arătate mai sus. Ideea de bază constă în însemnarea arcelor și a conținutului locatiilor prin cuvintele unui monoid liber pe un alfabet final (terminal). Generalizarea rețelelor, propusă prin program, se realizează sub forma algoritmilor exprimați cu folosirea calculului simbolic, adică a mijloacelor algebrei de computer. De aici rezultă că, analogul de program al sistemului (sau procesului) modelat poate fi în principiu, cercetat prin metode algebrice.

În prezenta lucrare sunt descrise câteva abordări ale analizei unor asemenea rețele, denumite rețele Petri algebrice ce se bazează pe proprietățile monoidului liber asupra alfabetului final. După cum au arătat cercetările efectuate, rețelele algebrice sunt un complex și interesant obiect matematic. Ele se formulează în codul propriei categorii , închisă față de produsul și coprodusul de categorie, au o serie de proprietăți interesante.

Prin intermediul rețelelor algebrice se pot formula o serie de proprietati clasice de analiză a sistemelor cu utilizarea metodelor de comparare. Totodată, rețelele algebrice sunt și un mijloc de descriere nemijlocită a sistemelor și proceselor fizice reale. Pe de o parte acest lucru dă posibilitatea obținerii unor rezultate utile în practică, iar pe de altă parte, dă posibilitatea stimulării dezvoltării teoriei înseși a rețelelor algebrice prin idei noi, ce-și au izvoarele în lumea reală.

În practică se utilizează pe larg extinderile orientate – e problemă ale rețelelor Petri, între care cele mai cunoscute sunt rețelele E, rețelele-combi, rețelele FIFO, rețelele M, rețelele de vocabular ș. a. Alegerea unui limbaj concret al rețelelor Petri se determină prin conținutul obiectivelor utilizării modelelor de rețele. Totodată, unul dintre domeniile cele mai importante ale aplicărilor rețelelor Petri îl reprezintă comanda obiectelor discrete. Aici aparatul rețelelor Petri se utilizează atât în stadiul proiectării sistemului de comandă, cât și la crearea bazei algoritmice de comandă, de exemplu pentru reprezentarea modelului etalon al obiectului de comandă.

Un domeniu important al utilizării practice a rețelelor Petri îl reprezintă sistemele flexibile de producție.

În acest domeniu progresul nu este posibil fără atragerea unor noi mijloace algoritmice și de program de perspectivă, rețelele Petri joacă aici un rol important la soluționarea problemelor formalizării domeniului ca obiecte, modelări și comenzi.

Capitolul 1

REȚELE PETRI ALGEBRICE

1.1. Obiectivele modelării proceselor paralele

Modelarea sistemelor descrise de totalitatea componentelor ce interacționează, a parcurs o serie întreagă de etape în dezvoltarea sa, iar complicarea modelelor s-a dovedit legată nu de intensificarea detaliilor descrierii ci a “schematicității”: s-a demonstrat că măcar în plan principial, este mai complicată modelarea unei structuri complexe. Interacțiunea componentelor sistemului în timp, se poate descrie într-un timp continuu (de ex., prin ecuații diferențiale), în timp discret (prin ecuații cu diferențe finite) și în timp neregulat (așa numitul timp al evenimentelor), la acesta din urmă timpul se citește doar în momentele, cînd în sistem au loc evenimente ce modifică starea sa.

Ultima modalitate, fără îndoială, e cea mai economicoasă, dar și cea mai complicată, aproape că nu se pretează descrierii analitice. Aici cele mai puternice instrumente sunt modelele imitative și rețelele Petri, acestea din urmă avînd posibilitatea să servească în anumite cazuri drept bază pentru modelele imitative.

La nivel generalizat sistemul de modelat se prezintă ca o totalitate de componente ce au o dinamică proprie, comasată. Se are în vedere faptul că starea componentelor corespunde doar unor anume stări separate mai importante, ale obiectului de modelat. Într-o anume terminologie universală această stare este “activ”, “așteaptă” ș. a.m.d.

Schimbarea stărilor se realizează sub acțiunea unei serii de factori interni pentru sistem, legați de unele situații prescrise, care la rîndul lor sînt legate de starea însăși a acestor componente cît și a celor adiacente cu ele. În felul acesta, din punct de vedere al interacțiunii elementelor între ele, nu toate stările lor sînt de aceeași valoare. Este util să se evidențieze între ele următoarele clase, care la general se intersectează:

stări sistemice,

stări conjugate,

stări interne.

Stările primei clase sînt esențiale pentru planificarea mișcărilor întregului sistem. Este vorba despre o oarecare totalitate de stări conjugate și stări aflate sub acțiunea factorilor externi.

Prin stări conjugate se înțeleg stările adiacente ale elementelor, prin care se realizează interacțiunea lor. Analizînd separat elementul, fiecare asemenea stare o vom denumi marcată (înregistrată), iar toate stările sale le vom numi interne. Modificarea stărilor interne nu se reflectă nemijlocit asupra funcționării altor elemente, aceste stări fiind importante doar din punct de vedere al cercetării dinamicii elementului însăși.

Sistemele cercetate adesea reprezintă totalitatea proceselor, care în termenii modelării dinamice pot fi descrise sub forma succesiunilor interacțiunii cu elementele unor obiecte. Avînd în vedere aplicațiile, importante penru tehnica zilelor noastre, – sistemele de calcul și sistemele flexibile de producție (SFP) , vom considera aceste obiecte în mod corespunzător probleme prelucrate de sistemul de calcul, sau repere ce trec prin SFP.

Des.1.1. Interacțiunea elementelor sistemului prin stări conjugate.

Să reprezentăm prin , elementele sistemului cercetat, ele însele fiind sisteme dinamice elementare. Stările interioare ale sistemelor , să le notăm cu . Un anume cortegiu de elemente modelează realizarea mișcării corespunzătoare; este normal să se numească traiectoria elementului , considerînd, de exemplu că punctele se dispun pe o oarecare suprafață sau plan în R3. Pe des. 1.1 este reprezentată interacțiunea sistemelor , …, , stările marcate fiind figurate prin cercuri neîntrerupte. Starea a sistemului inițiază lansarea sistemului , starea căruia este , și de asemenea starea a sistemului inițiază demararea sistemului . Întregul tablou al interacțiunii poate fi reprezentat printr-un graf ilustrat în des. 1.2. Într-un anume sens se poate vorbi despre dinamizarea modelului static de graf al sistemului, prin sistemele dinamice SI (mai amănunțit vezi ).

Des.1.2. Graful sistemelor ce interacționează

Cel mai simplu model al sistemului dat se poate obține ușor prin mijloacele unui oarecare limbaj de programare. Totuși, dacă condițiile interacțiunii sînt complicate prin oarecare factori suplimentari, atunci descrierea prin astfel de modalitate poate fi puternic îngreunată, iar ce este mai important, această cale nu duce la obținerea caracteristicilor de calculare a sistemului și nu se caracterizează printr-o oarecare flexibilitate esențială. Utilizarea limbajului LISP sau a altui limbaj corespunzător inteligenței artificial, de ex. PROLOG, îmbunătățește situația, însă alcătuirea construcțiilor complexe, în special a celor temporare se poate dovedi a fi un lucru dificil. În esență problema constă în aceea, că nu se umple, într-o oarecare măsură, breșa între mijloacele de calcul și cele de limbaj ale descrierii proceselor paralele.

Noțiunea de bază în definirea procesului o reprezintă ordinea. Metodele de realizare în model a procesului acestei ordini pot fi diferite:

incrementală,

recursivă,

declarativă (există un metaproces, ordinea se stabilește),

cu utilizarea proceselor-sincronizatoare.

Mecanismele 1), 2) se realizează prin intermediul calcului stării curente după cea anterioară, sau, indirect, prin intermediul variabilei tampon, care are, de regulă, sens de timp, fie nemijlocit, cu ajutorul determinării regulii interacțiunii evenimentelor. Mecanismele exterioare se construiesc pe seama întroducerii unei suprastructuri asupra totalității proceselor.

Modalitatea declarativă cea mai simplă de realizare a proceselor o constituie sistematizarea stărilor după regula dată. Modelarea proceselor se poate realiza atribuind fiecărei stări un parametru de ordine special , adică analizînd o stare extinsă (, k=1,…,ni, și ordonînd parametrii . Exemplu de ordonare – prescrierea ordinii după în conformitate cu succesiunea dată a prelucrării problemelor în sisteme de calcul și cu sistemul priorităților.

Dacă întroducem sincronizatori în analiza sistemului de raporturi asupra mulțimii i=1,…,r; k =1, …,ni, ce determină ordinea înfăptuirii evenimentelor în sistem, atunci vom obține încă ice pot fi descrise sub forma succesiunilor interacțiunii cu elementele unor obiecte. Avînd în vedere aplicațiile, importante penru tehnica zilelor noastre, – sistemele de calcul și sistemele flexibile de producție (SFP) , vom considera aceste obiecte în mod corespunzător probleme prelucrate de sistemul de calcul, sau repere ce trec prin SFP.

Des.1.1. Interacțiunea elementelor sistemului prin stări conjugate.

Să reprezentăm prin , elementele sistemului cercetat, ele însele fiind sisteme dinamice elementare. Stările interioare ale sistemelor , să le notăm cu . Un anume cortegiu de elemente modelează realizarea mișcării corespunzătoare; este normal să se numească traiectoria elementului , considerînd, de exemplu că punctele se dispun pe o oarecare suprafață sau plan în R3. Pe des. 1.1 este reprezentată interacțiunea sistemelor , …, , stările marcate fiind figurate prin cercuri neîntrerupte. Starea a sistemului inițiază lansarea sistemului , starea căruia este , și de asemenea starea a sistemului inițiază demararea sistemului . Întregul tablou al interacțiunii poate fi reprezentat printr-un graf ilustrat în des. 1.2. Într-un anume sens se poate vorbi despre dinamizarea modelului static de graf al sistemului, prin sistemele dinamice SI (mai amănunțit vezi ).

Des.1.2. Graful sistemelor ce interacționează

Cel mai simplu model al sistemului dat se poate obține ușor prin mijloacele unui oarecare limbaj de programare. Totuși, dacă condițiile interacțiunii sînt complicate prin oarecare factori suplimentari, atunci descrierea prin astfel de modalitate poate fi puternic îngreunată, iar ce este mai important, această cale nu duce la obținerea caracteristicilor de calculare a sistemului și nu se caracterizează printr-o oarecare flexibilitate esențială. Utilizarea limbajului LISP sau a altui limbaj corespunzător inteligenței artificial, de ex. PROLOG, îmbunătățește situația, însă alcătuirea construcțiilor complexe, în special a celor temporare se poate dovedi a fi un lucru dificil. În esență problema constă în aceea, că nu se umple, într-o oarecare măsură, breșa între mijloacele de calcul și cele de limbaj ale descrierii proceselor paralele.

Noțiunea de bază în definirea procesului o reprezintă ordinea. Metodele de realizare în model a procesului acestei ordini pot fi diferite:

incrementală,

recursivă,

declarativă (există un metaproces, ordinea se stabilește),

cu utilizarea proceselor-sincronizatoare.

Mecanismele 1), 2) se realizează prin intermediul calcului stării curente după cea anterioară, sau, indirect, prin intermediul variabilei tampon, care are, de regulă, sens de timp, fie nemijlocit, cu ajutorul determinării regulii interacțiunii evenimentelor. Mecanismele exterioare se construiesc pe seama întroducerii unei suprastructuri asupra totalității proceselor.

Modalitatea declarativă cea mai simplă de realizare a proceselor o constituie sistematizarea stărilor după regula dată. Modelarea proceselor se poate realiza atribuind fiecărei stări un parametru de ordine special , adică analizînd o stare extinsă (, k=1,…,ni, și ordonînd parametrii . Exemplu de ordonare – prescrierea ordinii după în conformitate cu succesiunea dată a prelucrării problemelor în sisteme de calcul și cu sistemul priorităților.

Dacă întroducem sincronizatori în analiza sistemului de raporturi asupra mulțimii i=1,…,r; k =1, …,ni, ce determină ordinea înfăptuirii evenimentelor în sistem, atunci vom obține încă o modalitate de generare a stărilor. În acest caz, este evident, se pot lua în considerație atît construcțiile exterioare, cît și cele interioare ale mecanismului de realizare a dinamicii.

Construcțiile interioare pot fi alcătuite pe baza transformatorului F de tipul F: L→L, unde L – este mulțimea stărilor conjugate ale sistemului. Exemple de asemenea transformator – semaforul Dijkstra, mecanismul Rendezvous în limbajul Ada, monitorul . Construcțiile exterioare se determină cu ajutorul metasistemului.

Semaforul este mijlocul cel mai simplu, ca realizare, de ordonare a interacțiunii proceselor. În același timp, fiind niște primitive, semafoarele pot fi utilizate incorect, ceea ce duce la obținerea unor descrieri neclare ale proceselor. Responsabilitatea pentru accesul corect la rețeaua comună în cazul utilizării semafoarelor o are procesul, care realizează acest acces, ceea ce vine în contradicție cu principiul modularitații.

Mecanismul rendez-vous este, se pare, modalitatea cu cea mai mare putere de rezolvare a problemelor interacțiunii proceselor paralele. Avantajele sale principale se consideră a fi ușurința relativă de înțelegere a funcționării sistemelor paralele complexe și probele corectitudinii lor, întrucît sincronizarea apare drept condiție a interacțiunii. Totuși o sincronizare prea strictă a proceselor, caracteristică pentru rendez-vous, necesită construirea unor procese paralele suplimentare, iar pentru procesele asincrone complexitatea realizării mecanismului rendez-vous este mai mare decît pentru soluțiile care utilizează alte mecanisme.

Monitoarele posedă o serie întreagă de avantaje, legate de specificul construirii lor. Unul dintre avantajele principale constă într-aceea, că elaborarea monitorului se poate desfășura independent de proiectarea celorlalte procese. Dezavantajele principale ale monitorului sunt legate de absența în el tocmai a mecanismelor de sincronizare ceea ce nu este principial, în întregime, pentru sistemele construite din procese independente.

Tipurile de stări stabilite mai sus permit să se utilizeze diferite feluri de modele de procese, ce asigură, într-un fel sau altul, posibilitatea de calculare a caracteristicilor lor . Să ilustrăm folosirea cîtorva dintre ele pe exemplul obiectivului modelării proceselor de prelucrare a rețelelor în SFP (similar se descriu procesele prelucrării subprogramelor în calculatoare). Una din primele metode de modelare a asemenea procese este metoda bazată pe diagramele lui Gantt. Pentru reperul de prelucrat se consideră cunoscute ordinea succesivă a operațiilor ui (des.1.3) și durata a fiecărei operații j pe unitatea ide utilaj.

Des.1.3. Schema ordinii succesive a operațiilor .

Des.1.4. Diagrama lui Gantt.

Totalitatea vectorilor pe planul (t, i) (t – timpul) pentru j fixat, formează diagrama lui Gantt (des.1.4).

Diagrama Gantt – este portretul static al dinamicii SFP. Ea ne dă o imagine concretă despre raporturile de timp și interdependența dintre procesele prelucrării. Și mai important este faptul că utilizînd diagrama Gantt, se poate determina timpul de oprire și timpul încheierii ciclului de prelucrare în condiții ideale. Aceste valori joacă un rol esențial la evaluarea organizării proceselor tehnologice și informaționale în SFP, a corectitudinii alegerii și dispunerii utilajelor, precum și la soluționarea sarcinilor de planificare a producției.

Pentru procesele multireper (corespunzător pentru cele cu mai multe obiective) este normal să se întroducă diagramele polimetrice ale lui Gantt G (DPG), care reprezintă lotul de vectori plasat în spațiul tridimensional al lui Euclid R3 (cu axele i, j, t), vectori coliniari la axa t, determinați cu schema prelucrării reperului (des.1.5.). Diagrama Gantt pentru reperul j (diagrama lui Gantt pentru j) se află în planul paralel la planul (t, i). Secțiunea spațiului R3 cu planul , ce trece prin punctul l de pe axa i și paralel la planul (t, j), este esența diagramei obiectivului unității de utilaj l (des.1.6.). În continuare vom identifica proiecția diagramei polimetrice a lui Gantt pe plan cu însuși acest plan. Proiecțiile vectorilor pe axa t nu se intersectează: pe o unitate de utilaj nu pot fi simultan în prelucrare mai mult de un reper, un obiect nu poate să se afle simultan pe două unități de utilaj diferite.

Să notăm diagrama j a lui Gantt în proiecții pe axa t sub forma unei recursii (întroducînd noi variabile ):

Aici este un parametru, ce are sensul timpului de întrerupere înaintea prelucrării pe unitatea i de utilaj (des.1.7,1.8).. DPG se descrie în acest caz prin sistemul:

(1.1)

unde inegalitatea – produs este întrodusă pentru realizarea condiției neintersectării.

DPG este prin esență un model geometric, ce reprezintă statica funcționării SFP. Să analizăm utilizarea sa pentru rezolvarea analitică a problemei planificării optime, adică pentru determinarea succesiunii optime a prelucrării reperelor în SFP. Problema întocmirii ordinii optime pentru SFP se reduce la minimizarea funcției speciale

,

unde

.

DPG, evident, asigură de asemenea posibilitatea vizualizării proceselor de prelucrare a reperelor în SFP. Cînd, pentru aceasta, se utilizează calculatoare personale, de exemplu calculatoare PC XT de ordinul 16 ale firmei IBM, este bine să se folosească unul din pachetele de prelucrare integrată a datelor, pachete elaborate pînă în prezent cu utilizarea tabelelor electronice de format mare TEFM și a bazelor de date [22]. Aceasta dă utilizatorului posibilitatea de a asigura interacțiunea TEFM și SUBD, așa că modificarea datelor în bază se realizează și în TEFM, iar acest lucru se reflectă de asemenea simultan pe graficele corespunzătoare sau , ce apar la ecran. Totodată apare posibilitatea vizualizării a întreg procesului de optimizare a sistemului. La fiecare pas al vizualizării putem observa deformarea carcaselor, legate de fiecare diagramă : întinderea – comprimarea lor după precum și modificarea pozițiilor lor reciproce.

Să analizăm, pe baza DPG, modelul descrierii analitice a proceselor paralele. Să întroducem noțiunea de diagramă Gantt discretă . Pentru aceasta să efectuăm discretizarea timpului, în care se analizează lucrul la prelucrarea reperului j, considerînd O așa discretizare este normal să fie denumită pe detalii. Să determinăm pasul ca fiind divizorul comun cel mai mare (CMMDC) al numerelor întregi , unde rj – numărul unităților de utilaj, pe care se prelucrează reperul j,

.

Atunci, evident, – timpul de prelucrare a reperului j pe unitatea i de utilaj, exprimat în unități ,

.

Pentru legarea dimensiunilor temporare determinăm pasul discretizării , comun pentru toate reperele r:

.

Respectiv

reprezintă durata prelucrării reperului j pe unitatea i de utilaj, exprimată în timpul real al sistemului. În fiecare moment de timp k SFP (în raport cu reperul j) se află într-o oarecare stare . Această stare este esența tuturor stărilor în momentul k de timp a tuturor unităților de utilaj a sistemului, ce participă la proces,

Problema noastră este să alcătuim algoritmul calculării stărilor în timp real. Pentru aceasta este necesar să se construiască un model, care reprezintă un analog analitic sau electronic (în calculator) care să fie analog cu SFP ca pentru un sistem dinamic. Cu alte cuvinte, este necesar să se efectuieze “desfășurarea“ în timp a vectorilor cu ajutorul sistemelor dinamice corespunzătoare, utilizînd în calitate de stări interioare ale sistemului.

Pentru generarea succesiunii stărilor, vom folosi modele dinamice ciclice . Să prezentăm starea elementului sistemului în momentul de timp n sub forma

unde .

Ținînd seama de acțiunea rapidă a elementului i la prelucrarea reperului j cu ajutorul numărului întrodus mai sus și a timpului de așteptare starea se poate prezenta sub forma

În virtutea proprietății de rotație a planului complex, punctele se deplasează pe circumferința de rază cu centrul . Stările conjugate sînt numerele egale două cîte două Circumferințele – orbitele acțiunii grupelor de substituiri de pe mulțimile stărilor interioare – se lipesc două cîte două în aceste puncte. (des.1.9.)

Penru structurarea și vizualizarea orbitelor, să le dispunem pe suprafețe bidimensionale compacte închise fără margini în spațiul R3. Totodată vom obține spațiile configurative ale elementelor utilajului ca sisteme dinamice de tipul totalității circumferințelor pe suprafața ce reprezintă o sumă logică a unui oarecare număr de torri (des.1.10).

Pentru sincronizarea mișcărilor elementelor se poate utiliza un monitor –funcție analitic , ce se determină prin durata așteptării și prelucrării la transmiterea reperului de pe un element pe altul, – ce se întroduce în expresie pentru . Metoda întrodusă de modelare a proceselor paralele se racordează la aparatul rețelelor Petri.

Des.1.9. Traiectoriile ciclice ale elementelor sistemului de producție.

Des.1.10. Spații configuraționale ale elementelor sistemului de producție.

Să reamintim definiția rețelei Petri . Rețeaua Petri П se reprezintă prin următoarele obiecte:

– mulțime finită de locații;

– mulțime finită de tranziții;

– funcția de intrare, unde – este o mulțime compusă din elementele mulțimii X, posibil cu intrări repetate ale acestora.

– funcția de ieșire;

– marcarea rețelei Petri, unde N este mulțimea numerelor naturale.

Cînd se lucrează cu rețelele Petri, se utilizează următoarele însemnări convenționale. Locația se reprezintă printr-un cerc, tranziția – printr-o bara, marcarea – prin puncte (jetoane în cerculețe), fiecărei locație corespunzîndu-i un anumit număr de jetoane. Cînd rețeaua Petri funcționează, se schimbă numărul de jetoane din locații – are loc redistribuirea lor în salturi în coformitate cu anumite reguli.

Permisiunea pentru realizarea tranziției se determină prin condiția

#

pentru toate valorile unde #(- reprezintă divizibilitatea locației de intrare xi pentru tranziția yj, adică numărul de intrări ale locației xi în mulțimea de intrare a tranziției yj.

Rezultatul efectuării tranziției permise este o nouă marcare ce se determină prin relația

##.

Exemple de schimbare a marcării sint aduse în des.1.11.

Modelarea proceselor cu ajutorul rețelelor Petri se bazează pe interacțiunea evenimentelor și condițiilor. Evenimentul este o acțiune, ce are loc în sistem, condiția este descrierea logică a stării sistemului (variabilă binară adevăr – fals). Condițiile se împart în precondițiile evenimentului, care determină realizarea evenimentelor, și postcondiții, care sînt urmările evenimentului petrecut. Evenimentele în rețelele Petri se reprezintă prin tranziții, condițiile – prin locații, intrările tranziției reprezentînd precondițiile; ieșirile tranziției – postcondițiile evenimentului corespunzător.

Să analizăm procesul complex (cu exactitatea de pînă la procedura încărcării – descărcării) de modelare a funcționării instalației (des.1.12).

Des.1.11 Modificarea marcării rețelei Petri.

Des.1.12. Rețeaua Petri ce modelează lucrul unei instalații.

Evenimentele sînt aici următoarele: 1 – piesa a sosit pe stocator; 2 – piesa așteaptă începutul prelucrării; 3 – instalația începe prelucrarea piesei; 4 – piesa se prelucrează; 5 – piesa este prelucrată; 6 – instalația este liberă; 7 – piesa este depusă în stocator. Precondițiile evenimentului 2 (piesa așteaptă pe stocator) – instalația este liberă și poate să înceapă prelucrarea. Postcondițiile acestui eveniment – instalația prelucrează piesa. Celelalte pre – și postcondiții sînt de asemenea evidente.

Metoda de modelare analizată a itinerariilor este legată de utilizarea rețelelor Petri de aspect particular, al așa numitelor grafuri marcate. Graful marcat este o rețea Petri, care satisface condițiile

unde – este mulțimea tranzițiilor, pentru care xi este ieșirea; – este mulțimea tranzițiilor, pentru care xi este intrare. Cu alte cuvinte, graful marcat este o rețea Petri, in fiecare locație are o intrare și o ieșire.

Rețeaua Petri analizată pe des.1.12 este un graf marcat. Un alt exemplu de model de algoritm de funcționare a celulei automate de prelucrare, ce constă din instalațiile c1, c2 și robotul P, se află pe des. 1.13. Aici pozițiile reprezintă stările robotului (luarea piesei, transportarea piesei s.a.m.d.), – stările instalației c1 (x5 – instalația este liberă, x6 – instalația este în starea de așteptare a piesei, x7 – instalația prelucrează piesa), x8, x9 – stările instalației c2. Tranzițiile reflectă condițiile corespunzătoare, care predetermină schimbarea stărilor.

Numărul stărilor, ce corespund algoritmului de funcționare al unităților corespunzătoare de utilaj, se determină în rețelele Petri doar prin necesitatea descrierii logicii funcționării lor și nu este legat în nici un fel de înfățișarea acestor procese în timp. Problema acordării algoritmilor cu evidența raporturilor temporare, ce caracterizează realizarea lor în sistem, se poate rezolva cu ajutorul întroducerii stărilor intermediare ale utilajelor, durata tranzițiilor între care este una și aceeași valoare pentru toate elementele SFP.

Cînd se presupune ciclicitatea funcționării elementelor, macroreprezentarea funcționării elementului SFP în timp, se poate obține în principiu, doar dînd două stări “marginale” ale elementului, ce corespund începutului și sfîrșitului operației îndeplinite de acesta. Funcționarea elementului răspunde în acest caz, tranziției de la o stare marginală la alta (des.1.14).

Des.1.13. Rețea Petri – model de celulă automată de prelucrare.

Întroducerea stărilor intermediare, prin care trece elementul la intervale egale de timp, permite punerea în concordanță a timpului sistemului cu cel real.

Să analizăm mai întîi cazul, cînd intervalele timpului de mișcare a elementului real SFP înainte (de la xinit spre xfin) și înapoi (de la xfin spre xin) coincid și sînt egale cu T/2. Să întroducem stările intermediare (des.1.15), ce trec, se presupune, la intervale egale de timp astfel, încît timpului T îi corespund m timpi. Drept model de asemenea element servește cascada a cărei orbită de acțiune pe circumferință constă din puncte de felul

Un caz mai complex de mișcare neuniformă a elementului înainte și înapoi poate fi descris prin formula

Funcția m=m(n) poate primi, de exemplu, următorul aspect

Des.1.16. Ciclul pe un plan complex.

Evident, în timpul sistemic, cînd pentru toate elementele SFP unui timp i se rezervă unul și același interval de timp, numărul m este caracteristica acțiunii rapide a elementului: .

Starea de început a elementului se ia în considerare prin întroducerea unui oarecare parametru de numere întregi, așa încît în cele din urmă, pentru mișcarea uniformă avem:

Orbita deplasată a acțiunii cascadei pe circumferință se descrie cu polinomul

(1.2)

unde q – este parametrul, ce ia în considerare starea de început a elementului.

Să ilustrăm folosirea formulei (1.2) pe exemplul modelării schimbului stărilor robotului. Să codificăm stările robotului prin numere complexe:

.

Atunci, la n = 0, 1, 2, 3, 4, punctul parcurge (aleargă) pe circumferința razei unitare, deplasîndu-se discret la fiecare tact pe un sfert de circumferință (des.1.16)

Limbajul rețelelor Petri oferă multe avantaje la modelarea sistemelor de tip general: modularitatea prezentă în mod normal la subsisteme, oferă posibilitatea de calcul a unei serii de caracteristici foarte importante ale sistemului, posibilitatea analizei proprietăților globale ale sistemului prin metode matematice ș.a. Mai jos se analizează modificările rețelelor Petri, care extind în mod radical posibilitățile lor în obiectivele cercetării proceselor paralele.

1.2. Rețelele Petri algebrice.

1.2.1. Noțiuni de bază și definiții.

Înainte de a începe definirea nemijlocită a rețelei Petri algebrice, trebuie să analizăm cîteva noțiuni și definiții ajutătoare, care se folosesc în procesul descrierii rețelelor. Astfel, fie A={a,b,c,d,…} – alfabetul finit, – monoidul liber generat de alfabetul A, a cărei mulțime de elemente este mulțimea secvențelor finite ale elementelor din A, numite cuvinte, iar prin operație – concatenarea cuvintelor. Element neutru al monoidului liber este un cuvînt vid, adică o secvență vidă de simboluri din A. În continuare vom simboliza monoizii sub forma unui grup de trei

,

unde A* – mulțimea de cuvinte; . – operația de concatenare; – elementul neutru.

Definiția 1.1. Mulțimea finită nevidă se numește cod, dacă toate cuvintele din X* permit descompunere unică în cuvinte din X, cu alte cuvinte, X* este un monoid liber.

Formal faptul că X* este un monoid liber, înseamnă justețea implicației

unde.

Definiția 1.2. Codul X îl vom interpreta în termenul finit egal cu d, dacă

cu alte cuvinte, o descompunere inexactă se va depista nu mai tîrziu de cuvîntul d al codului X.

Exemplul 1.1. Codul A, se va descifra în timp finit, egal cu 0, întrucît elementele alfabetului A sînt unice și se identifică unic. X={cd, cs, c} – este cod ce se descifrează în timpul egal cu 1, întrucît după simbolul c este necesar să se citească următoarea literă pentru a determina descompunerea cd, cs sau ccs. X={c,cd,d} nu este un cod, întrucît c·d=cd.

Definiția 1.3. Rețea Petri algebrică se numește sistemul

N=(P, T, A, V, M0),

unde – este mulțimea finită de locații de tipul p; – este mulțimea finită a locațiilor de tipul f; – mulțimea finită a tranzițiilor; A – alfabet finit;

este o aplicație, care marchează arcele, ce unesc locații cu tranziții și tranziții cu locații; – este marcarea inițială a locațiilor.

Des.1.17. Exemple de rețea Petri algebrică.

Prezența arcelor între locații și tranzitii se determină în felul următor. Dacă – este cuvînt vid, atunci nu există arc între a și b, sau Dacă V(a,b) =S, atunci există arc din a în b, însemnat cu cuvîntul S, sau

Să definim pentru fiecare element :

mulțimea ieșirilor a;

mulțimea intrărilor a;

Pentru aplicația V se aplică următoarea condiție: totalitatea cuvintelor monoidului liber A, care marchează ieșirile ale locațiilor tipurilor p și f, constituie un cod ce se descifrează în termenul final, . În cazul imposibilității descifrării cuvîntului ce se află în poziția , după codul

trecerile vor fi blocate pe tot timpul de funcționare a rețelei.

Fie . Cuvîntul definește cuvîntul oglindit în raportul cu a: .

Exemplul 1.2. Să analizăm următoarea rețea Petri algebrică (des.1.17):

ș.a

Să descriem algoritmul funcționării rețelei Petri algebrice. Starea globală a rețelei se determină cu cuvinte în locații de tipul p și f. La declanșarea unei oarecare tranziții t, cuvintele, aflate în locațiile se modifică. Regulile declanșării tranzițiilor asigură dinamica pentru rețelele Petri algebrice și precizează condițiile modificării stării rețelei.

Din punct de vedere formal starea rețelei se determină cu marcare, adică cu aplicație

,

unde . Cuvîntul marchează locația a. Marcarea rețelei se reprezintă prin vectorul

unde pe primele locuri m se găsesc marcările locațiilor de tip f și pe locurile de la la – marcările locațiilor de tip p.

Marcarea de început a locațiilor se descrie în mod similar:

Acum să ne oprim asupra problemei necesității introducerii locațiilor de cele două tipuri, p și f, care pare la prima vedere artificială și neîntemeiată. Cauza principală, care a determinat o asemenea împărțire, constă în dorința de a modela procesele funcționării tipului (first in, first out) – FIFO, adică “primul sosit – primul plecat” și a tipului (last in, first out) – LIFO, adică “ultimul sosit – primul plecat”. Acest lucru este ușor de realizat, dacă se prezintă cuvintele din locație de tipul f și p ca șiruri de simboluri ale alfabetului A, iar șirurile ce ies din locații, ca drepte și cuvinte în oglindă corespunzător. În felul acesta, locațiile f modelează funcționarea procesului de tipul FIFO iar locațiile p pe aceea a procesului de tip LIFO.

Să descriem condiția declanșării tranziției t, .

Definiția 1.4. Tranziția t este permisă pentru marcarea M, dacă pentru toate locațiile f, acelea, unde este factor stîng al , și pentru toate locațiile de tip p, acelea, unde este factor stîng al . În cazul, cînd tranziția t este permisă pentru marcarea M, se reprezintă

Condițiile declanșării tranziției , care asigură modelarea proceselor FIFO și LIFO, se descriu formal sub forma următoare.

Definiția 1.5. Declanșarea tranziției t, permise pentru marcarea M, duce la o nouă marcare , dacă

unde și .

Altfel spus, în cuvintele locațiilor de tip f, ce au arce la tranziția t, marcate cu cuvinte , are loc absorbirea factorului stîng în cuvintele și adăugate în dreapta, ca urmare a concatenării factorului . La rîndul lor în cuvintele locațiilor de tipul p, ce au arce la tranziția t, marcate cu cuvintele are loc absorbția factorului drept și adăugarea în dreapta în urma concatenării factorului .

Să ne întoarcem la exemplul 1.2. La marcarea de început este permisă doar tranziția . Declanșarea tranziției duce la o nouă marcare , adică , unde . Marcarea permite declanșarea tranziției .S-o pornim:

Marcarea permite declanșarea tranziției ,. Să le lansăm pe rînd:

Acum sunt permise tranzițiile ,:

Marcarea permite doar tranziția :

La marcarea este posibilă de asemenea declanșarea doar a unei tranziții :

Ajungînd la marcarea rețeaua oprește activitatea deoarece sunt interzise acțiunile tuturor tranzițiilor. În mod definitiv rezultatul funcționării rețelei se prezintă sub forma următoare:

Să relevăm un moment foarte important , care se referă la funcționarea rețelei , pe care am analizat-o mai sus. La marcările și a fost permisă declanșarea simultană a două tranziții, , și , respectiv. Totodată alegerea succesiunii declanșării tranzițiilor n-a avut nici o importanță, întrucît în mod definitiv se ajungea la una și aceeași marcare :

și

Pe baza celor spuse mai sus se poate trage concluzia, că în cazul dat succesiunile declanșării tranzițiilor și sînt independente, iar tranzițiile care intră în aceste șiruri nu se află în stare de conflict. Acest lucru permite, la rîndul său, să se modeleze funcționarea rețelei în mod paralel. Mai jos această problemă se va explica mai în amănunt.

Des. 1.18. Rețeaua ce modelează pe rînd consumul resursei.

Exemplul 1.3. Să analizăm cîteva exemple de rețele algebrice, ce realizează modelarea proceselor date.

Avem două procese, care consumă una și aceeași resursă. Este exlus consumul simultan al resursei prin două procese deodată. Este necesar să se construiască o rețea care descrie consumul pe rînd al resursei. Construcția prezentată pe des. 1.18 permite descrierea situației date.

Marcarea inițială

permite declanșarea doar a tranziției , . În noua marcare este permisă dencalnșarea doar a tranziției :

În felul acesta, resursa aflată în poziția , este consumată de procesele reprezentate de tranzițiile și pe rînd. Marcarea inițială stabilește ordinea consumului de resursă: dacă , atunci prima se va declanșa tranziția , dacă , atunci mai întîi se va declanșa tranziția .

Să analizăm rețeaua algebrică ce modelează funcționarea automatului finit, ce transformă numărul binar reprezentat de sunccesiune începînd cu ordinul mai mic, în completare pînă la doi. Alfabetul de intrare și de ieșire al automatului constă din trei simboluri: 0; 1; R. Simbolul R reprezintă sfîrșitul sau începutul numărului și aduce automatul în starea inițială.Rețeau Petri obișnuită, ce modulează un asemenea aparat, este descrisa în lucrarea. Rețeaua algebrică, care modelează acest automat, este prezentată pe des. 1.19.

Des. 1.19. Rețea Petri algebrică, ce modelează automatul finit.

Marcarea inițială a rețelei are aspectul unde – șirul finit din 0 și 1, ce reprezintă numărul binar începînd cu ordinul mai mic. De exemplu, pentru numărul marcarea finită în locatia va fi egală cu . Succesiunea declanșării tranzițiilor, la care se realizează această marcare finită, are aspectul

.

Să analizăm acum rețeaua algebrică, ce modelează funcționarea automatului finit și determină paritatea numărului unităților în șirul de intrare. Intrările acestui automat sînt similare cu intrările automatului analizat mai sus, iar ieșirea va fi simbolul 0 în cazul unui număr impar al unităților și simbolul 1 în cazul unui număr par al unităților. Rețeaua algebrică are aspectul prezentat în des. 1.20.

Des. 1.20.Rețea, ce modelează automatul finit în obiectivul determinării parității numărului unităților în șirul de intrare.

Marcarea inițială a rețelei este egală cu unde – șirul finit din 0 și 1, ce reprezintă numărul binar. Fie . Atunci șirul declanșării tranzițiilor pentru realizarea marcării finite are aspectul

.

În mod definitiv rezultatul funcționării rețelei se prezintă sub forma următoare:

.

1.2.2. Proprietățile rețelelor Petri algebrice.

Să introducem noțiunea mulțimii marcărilor ce se pot realiza pentru rețeaua Petri algebrică. Pentru aceasta, la început, să determinăm șirurile permise pentru o marcare fixată.

Definiția 1.6. Șirul -mulțimea cuvintelor finite pe alfabetul T) se numește permis pentru marcarea M și dă marcarea , dacă sînt îndeplinite următoarele condiții:

a) ;

b) ,

– atunci există marcarea , o astfel de marcare încît și . La rîndul său marcarea se numește accesibilă din marcarea M, dacă există un șir finit , astfel încît .

Definiția 1.7. Mulțimea marcărilor accesibile, ale rețelei Petri algebrice, începînd cu marcarea M, se numește mulțimea

Mulțimea marcărilor accesibile, ale rețelei N, începînd cu marcarea inițială a locațiilor , se notează prin .

Mulțimea marcărilor accesibile permit să se conexeze cu rețeaua Petri algebrică N trei limbaje [2]:

1)

2)

este factorul stîng în șirul t cu lungimea egală cu n;

3)

Limbajele și se dovedesc ulterior utile la determinarea proprietăților caracteristice rețelelor.

Definiția 1.8. Locație de tipul „f”fi__sau de tipul „p”pi se numește marginită, dacă , încît pentru are loc sau , unde prin este notată lungimea cuvîntului k.

La rîndul său rețeaua N se numește marginită, dacă fiecare locație a ei este limitată.

Teorema 1.1. Rețeaua N este marginită atunci și numai atunci, cînd este finită.

Demonstrare.

Necesitate. Fie rețeaua N marginită, atunci există finite, astfel, încît

.

Să notăm prin . Prin urmare, cardinalul mulțimii marcărilor ce se realizează, ale rețelei este marginită superior de numărul , unde – cardinalul alfabetului A. Necesitatea este demonstrată.

Suficiența. Fie mulțimea finită. Prin urmare pentru orice locație există o mulțime de cuvinte permise. În fiecare vom alege cuvîntul de lungime maximă . Dacă presupunem, că în locația la marcarea permisă se află un cuvînt de lungime infinită, acest lucru semnifică:

i)

ii) tranzițiile se declanșează de un număr infinit de ori.

Însă , unde este mulțimea tuturor șirurilor finite, adică . Cazul ii) este echivalent cu faptul, că mulțimea este nemarginită, iar acest lucru vine în contradicție cu condițiile inițiale. Prin urmare, lungimea cuvintelor este finită. Teorema este demonstrată.

Următoarea proprietate a rețelei Petri algebrice este legată de posibilitatea potențială a tranzițiilor de a fi permise la o marcare oarecare.

Definiția 1.9. Tranziția a rețelei N se numește activă, dacă pentru orice marcare există marcarea , astfel, încît .

Proprietatea caracterului activ garantează, că tranziția t nu va fi blocată în procesul funcționării rețelei. Extinderea proprietății caracterului activ asupra tuturor tranzițiilor rețelei N duce la noțiunea de rețea activă, adică N este activă, dacă este activ.

Proprietatea caracterului activ a fost formulată pe baza utilizării mulțimii marcărilor accesibile. Caracterizarea tranzițiilor cu ajutorul limbajului introduce un nou aspect în noțiunea de funcționare a rețelei. Să-l analizăm.

Definiția 1.10. Rețeaua N se numește rețea fără blocare, dacă pentru orice există tranziția , astfel încît .

Acest lucru este echivalent cu faptul că pentru orice marcare există tranziția , care este permisă la această marcare, adică . Echivalența aratată decurge din izomorfismul mulțimilor și .

1.2.3. Timpul în rețelele algebrice Petri.

Una dintre ideile fundamentale ce stau la baza creării rețelei Petri, este renunțarea de la legăturile temporale dintre elemente la modelarea sistemelor și înlocuirea lor cu legături de tip cauză-efect. Modelele asincrone realizate în acest mod au permis rezolvarea unui complex întreg de probleme, ce se referă la analiza locală a sistemelor și la punerea în evidență a legăturilor lor de tip cauză-efect. Un moment negativ l-au reprezentat dispariția parametrilor temporali în stare pură și înlocuirea parțială a lor cu evenimente legate de momente sau intervale de timp separate. După cum s-a arătat deja mai sus, absența mijloacelor pentru fixarea ordinii intrării jetoanelor nu permite stabilirea ordinii lineare la o mulțime de jetoane, ce se află în locație. Aceasta înseamnă în fond, că informația locală despre succesiunea declanșării tranzițiilor în locațiile înseși se pierde. În rețelele Petri algebrice această informație este prezentă în succesiunile simbolurilor , . În felul acesta, a apărut posibilitatea de a se obține șiruri de simboluri ordonate liniar, confruntate reciproc uniform cu șirul discret temporar (0, 1, 2, … , n, …), a cărui unitate este tactul timpului, care la rîndul său este legat de scara reală a timpului.

Să analizăm una din variantele posibile de includere a timpului în rețea. Să luăm rețeaua Petri algebrică de tipul N0, arătat pe des. 1. 21.

Cea mai simplă construcție dată poate fi interpretată ca pendul în ore. Fiecare declanșare a tranziției provoacă o marcare identică cu cea anterioară și tranziția t este permisă, prin urmare, întotdeauna.

Adăugarea locației duce la o nouă construcție a rețelei (des.1.22).

Locația joacă rolul stocatorului de tacturi de timp, de aceea întreaga rețea se poate interpreta ca un ceas. Să arătăm pe un exemplu concret varianta utilizării construcției „ceas”. Fie că avem o oarecare rețea Petri algebrică, care include locațiile și (pentru noi în exemplul acesta tipul locației nu are rol), separate de tranziția . Să presupunem, că tranziția este permisă pentru marcarea , totuși este necesar, plecînd de la logica funcționării sistemului real, modelat de rețeaua dată, ca tranziția să se declanșeze în momentul k al timpului discret de funcționare a rețelei. Soluționarea acestei probleme se prezintă pe des. 1.23.

Nu este greu de observat, că în construcția ceasului încă nu a fost folosită proprietatea ordonării liniare a elementelor în cuvintele locațiilor, prin urmare, construcția respectivă poate fi realizată prin mijloacele obișnuitelor rețele Petri. Totuși, în exemplul prezentat se cerea nu memorarea timpului declanșării tranziției, ci, la realizarea unui anumit timp, permiterea declanșării sale. Să schimbăm exemplul analizat mai sus. Fie că acum să se ceară memorarea timpului de declanșare a tranziției , atunci rețeaua are aspectul prezentat de des. 1.24.

Șirul simbolurilor acumulat în locația va avea aspectul

unde sînt intervale de timp între declanșarea tranziției .

Este evident, că pentru orice rețea Petri algebrică sînt necesare două ceasuri, unul dintre ele este destinat pentru deschiderea tranzițiilor, celălalt pentru fixarea timpului de declanșare a tranzițiilor.

Exemplele prezentate arată doar în linii generale direcția rezolvării problemei introducerii timpului în rețeaua Petri pe cale naturală, fără a ieși din cadrul rețelelor înseși.

1.2.4. Conflicte în rețelele Petri algebrice.

Să introducem o serie de definiții auxiliare.

Definiția 1.11. Fie – tranziții, . Se spune că tranzițiile se află în pre-conflict dacă

.

Se spune că tranzițiile se află în post-conflict, dacă

.

În definiția citată conflictele sînt legate de mulțimile de precondiții și postcondiții ale tranzițiilor . Astfel, dacă mulțimile precondițiilor și tranzițiilor și au o intersecție nevidă, atunci are loc un conflict anterior. Procedînd în mod similar față de mulțimea postcondițiilor și , ajungem la noțiunea de post-conflict.

În obișnuitele rețele Petri (cu excepția grafurilor marcate) se descriu pre-conflictele, care influențează succesiunea declanșării tranzițiilor. Post-conflictele nu prezintă aici interes, întrucît în locații procesul stocării (acumulării) jetoanelor nu se deosebește de succesiunea intrării jetoanelor, ci se fixează doar numărul lor.

La rîndul lor în rețelele Petri algebrice succesiunea cuvintelor, ce intră din tranziții pe locații, are o semnificație de principiu, astfel, de exemplu, dacă , atunci

unde este operația de concatenare. Aceasta, de fapt, înseamnă că două procese paralel independente, și se descriu în poziție a două cuvinte neegale între ele ale monoidului liber . Ieșirea din situația creată o reprezintă introducerea comutativității parțiale în cuvintele .

Definiția 1.12. Cuvintele se numesc parțial comutative în locația ,

și

unde

.

Proprietatea comutativității parțiale modifică într-o oarecare măsură condiția permisiunii declanșării tranzițiilor.

Definiția 1.13. Tranziția este permisă pentru marcarea M, dacă pentru toate locațiile „f”fi este factorul stîng al unuia din cuvintele , echivalent, prin comutativitatea parțială, cu cuvintul , și pentru toate locațiile de tipul p, este factorul stîng al unuia din cuvintele , echivalent, prin comutativitatea parțială, cu cuvîntul .

Altfel spus, în fiecare locație b se analizează nu numai cuvîntul , ci mulțimea cuvintelor echivalente , care pot fi obținute la rezolvarea pre-conflictelor. La rîndul lor, conflictele anterioare în rețelele Petri algebrice se descriu prin metode devenite deja tradiționale, cu ajutorul priorităților sau cu utilizarea unor oarecare comunicații erustice.

1.2.5. Reducerea rețelelor Petri algebrice la rețelele obișnuite.

Să analizăm constructiv reducerea respectivă, adică să construim o rețea Petri obișnuită, a cărei comportare este echivalentă cu a unei oarecare rețele algebrice Petri. Pentru aceasta să luăm alfabetul A, ce constă dintr-un simbol . Aplicația

confruntă fiecare pereche cu cuvîntul a din monoidul liber , . Lungimea cuvîntului a – card (a) va corespunde numărului de arce ale rețele Petri obișnuite ce se construiește, ce unesc tranziția și locațiile analizate. Întrucît cuvintele, aflate în P și F, se prezintă ca șiruri ale unuia și aceluiași simbol k de diferită multiplicitate, atunci algoritmul funcționării locațiilor P și F pentru permiterea tranzițiilor va fi același. Formal acest lucru poate fi determinat în felul următor:

adică cuvintele și sînt echivalente cu oglinditele cuvintelor lor . Altfel spus, locațiile de tipul p și f nu se deosebesc între ele și unificarea lor dă o mulțime de locații a rețelei Petri obișnuite,

.

În acest caz marcarea inițială din rețeaua algebrică trece fără modificare în rețeaua obișnuită,

.

Propoziția 1.1. Rețeaua Petri algebrică cu este izomorfă cu rețeaua Petri obișnuită cu

Demonstrația acestei propoziții se bazează pe verificarea nemijlocită a echivalenței funcționării rețelei Petri algebrice și a rețelei construite.

Se poate face și construirea inversă, la oricare rețea Petri dată să se construiască analogul său algebric. Acest lucru oferă motiv să se susțină includerea clasei rețelelor Petri obișnuite în cele algebrice.

1.3. Factorizarea cuvintelor în locațiile rețelei algebrice

1.3.1. Coduri.

Să analizăm problemele legate de proprietățile codului, a cărui definiție s-a dat în 1.2.1 Pe lîngă proprietățile de bază, care trebuie să fie satisfăcute de cod, se fac operații asupra elementelor codului. În încheiere se descrie algoritmul factorizării cuvintelor în locațiile rețelei algebrice. Așadar, să analizăm condițiile în care mulțimea de cuvinte este un cod.

Teorema 1.2. Mulțimea este un cod dacă și numai dacă intersecția oricăror doi monoizi liberi, dați de generatoarele și , , , nu conține cuvinte , încît

?

Corolar 1.1. Dacă mulțimea este un cod, atunci intersecția oricăror doi monoizi liberi, dați de generatoarele și , corespunzător , , ce au proprietatea , este egală cu șirul vid, adică .

Corolar 1.2. Toate elementele codului determinat pe monoidul liber cu alfabetul finit A au proprietatea

,

unde și totodată se admite că .

Observația 1.1. La obținem condiția cea mai simplă a verificării, că mulțimea este un cod: nici un element nu poate fi compus din alte elemente ale mulțimii . Această condiție este necesară pentru ca să fie cod, însă, bineînțeles, insuficientă.

Demonstrația teoremei 1.2. Necesitatea

Fie . După definiția codului , toate cuvintele admit o unică factorizare în cuvintele . Atunci

totodată este posibil ca

Să reprezentăm . Este evident, că și cu atît mai mult . Întrucît a a fost ales arbitrar, atunci este șirul vid. Deci am demonstrat, că pentru oricare doi monoizi liberi dați pe descompunerea mulțimii , intersectarea lor este egală cu șirul vid, adică am demonstrat corolarul 1.1. De aici decurge că, dacă cuvîntul și cuvîntul , atunci include în sine monoidul liber , ale cărui toate elemente se descompun univoc. Acest lucru înseamnă că

.

Necesitate este demonstrată.

Suficiența. Fie și sînt îndeplinite condițiile teoremei. Să presupunem, că un cuvint oarecare se poate factoriza prin două modalități

, ()

. Să presupunem că . În egalitatea () sînt posibile două situații.

1. Toatele elementele din partea stîngă și partea dreaptă () sînt diferite, adică mulțimea se divizează în două submulțimi ce nu se intersectează și ,. Dar atunci și , ceea ce contravine condițiilor teoremei.

2. Printre elementele și , , există elemente egale. Dacă asemenea elemente sînt factorii din stînga și dreapta (), atunci, simplificînd prin ele, obținem

Aceasta înseamnă că

.

Însă în conformitate cu condiția teoremei,

.

Altfel spus, în () și , adică descompunerea a este univocă. Teorema este demonstrată.

Exemplul 1.4. Să analizăm cîteva submulțimi ale monoidului liber, dat pe alfabet.

1. Mulțimea nu este cod întrucît nu satisface corolarul 1.2 al teoremei 1.2. Într-adevăr, cuvîntul și permite factorizarea prin două modalități:

.

2. Mulțimea nu este cod, deși satisface condițiile corolarului 1.2 al teoremei 1.2. Totuși, admite factorizarea prin două modalități și nu satisface condițiile corolarului 1.2, altfel, cuvîntul și .

3. Mulțimea nu este cod, chiar satisfăcînd condițiile corolariilor 1.1 și 1.2 ai teoremei 1.2, întrucît cuvîntul și .

Să analizăm operațiile cu elementele codurilor. Introducerea acestor operații ne va fi necesară ulterior pentru construirea și analiza noilor coduri, întocmite pe baza unuia inițial. Astfel, fie – un cod determinat pe monoidul liber , , dat pe alfabetul finit A.

1. Operația de grupare. Fie . Rezultatul operației de grupare a elementelor codului este elementul

,

adică operația de grupare este operația de concatenare.

2. Operația de descompunere. Fie . Rezultatul operației de descompunere a elementului este mulțimea elementelor , astfel încît .Să observăm că operația de grupare și operația de descompunere sînt necomutative.

Afirmația 1.1. Aplicarea operației de grupare la elementele codului , duce la formarea unui nou cod, , determinat pe același monoid liber .

Afirmația 1.2. Aplicarea operației de descompunere la elementele codului , nu duce în mod obligatoriu la formarea unui nou cod. Mulțimea obținută , pare să nu satisfacă condițiile teoremei 1.1.

Afirmația 1.3. Dacă codul este obținut din codul ca urmare a folosirii la elementele sale a operației de grupare, atunci cuvintele, ce se factorizează conform codului , pot să nu se factorizeze conform codului .

Afirmația 1.4. Dacă aplicarea operației de descompunere la elementele codului a dus la crearea unui nou cod , atunci toate cuvintele ce se factorizează conform codului , se vor factoriza după codul .

Demonstrația afirmațiilor 1.1-1.4 este bazată pe utilizarea directă a teoremei 1.2.

După cum s-a arătat mai sus, problema determinării apartenenței la mulțimea codurilor este destul de laborioasă. De aceea, o tendință firească va fi încercarea de a simplifica această problemă și de a diminua volumul total al calculelor legate de verificarea condițților teoremei. Referitor la aceasta aici apar o serie de obiective de optimizare, care pot fi realizate în funcție de restricțiile impuse procesului de modelare prin natura domeniului de obiecte cercetat. Primul obiectiv este legat de alegerea alfabetului minim permis la limitarea pe lungime a cuvintelor codului, adică se cere să se găsească la , unde este cod; . Dimensiunea codului însuși se determină prin valoarea

Al doilea obiectiv este într-un fel opus celui dintîi. Aici se cere să se găsească lungimea minimă a cuvintelor codului la alfabetul fixat, adică să se afle

dacă ; – este cod. Se poate arăta că primul obiectiv este o generalizare a obiectivului de colorare a vîrfurilor grafului.

Să analizăm acum ce aduce nou în rezolvarea problemei conflictelor din rețelele Petri, abordarea algebrică. Anterior am definit noțiunile de pre- și postconflicte, plecînd de la intrările și ieșirile tranzițiilor mulțimii T. Un fapt perfect evident este acela, că premisa apariției pre-conflictului, o constituie prezența la locațiile mulțimii a mai mult de o ieșire adică de așa fel, încît . În mod similar se poate arăta, că premisa apariției post-conflictului o constituie existența în locațiile mulțimii a mai mult de o intrare, adică sînt de așa fel , încît .

Mai sus s-a arătat, că introducerea noțiunii de comutativitate parțială a cuvintelor în locații permite într-o destul de mare măsură rezolvarea a problemei post-conflictului. Acum ne vom folosi de proprietățile codurilor și vom analiza pre-conflictul de pe niște locații un pic diferite. Ideea de bază, de care ne vom folosi, constă în următoarele. Întrucît pre-conflictul apare ca urmare a imposibilității satisfacerii simultan, cu conținutul locației , a condițiilor permiterii declanșării tuturor acelor tranziții , pentru care , atunci este necesar să se excludă complet asemenea situații. În rețelele Petri obișnuite această sarcină se soluționează fie prin aplicarea condiției

,

fie prin darea priorităților pentru declanșarea tranzițiilor. Prima cale reduce în mod esențial posibilitățile modelatoare ale rețelelor, iar a doua aduce dezacord în algoritmul funcționării rețelei, întrucît iese propriu-zis din cadrul descrierii. Rețelele Petri algebrice au posibilitatea de a rezolva această problemă în alt mod.

Să aplicăm pe mulțimea

,

următoarea condiție este cod, definit pe monoidul liber , . Aceasta înseamnă, de fapt că toate cuvintele , trebuie să se factorizeze univoc în cuvintele . La rîndul lor, dacă cuvintele se pot descompune univoc în părți componente, atunci ordinea declanșării tranzițiilor se determină prin această descompunere: prima se va declanșa acea tranziție , pentru care este factorul stîng (sau pentru pozițiile de tipul p).

Totuși aici trebuie notată o împrejurare importantă: Pentru ca tranzițiile să nu fie blocat din cauza imposibilității factorizării cuvîntului în cuvintele , trebuie să se ia în considerare structura codului , unde

.

Totodată codul poate fi construit doar din codul cu ajutorul operațiilor de grupare și descompunere a elementelor . Particularitățile folosirii acestor operații sînt formulate de afirmațiile 1.1-1.4.

Astfel, se poate trage o concluzie: rețelele Petri algebrice includ o subclasă, în care pre-conflictele nu au loc. Limitarea – cod, diminuează, bineînțeles, posibilitățile modelatoare ale rețelelor, dar într-o măsură considerabil mai mică, decît în rețelele Petri obișnuite, în care un asemenea efect se atinge doar în grafurile marcate.

1.3.2. Algoritmul factorizării cuvintelor în locații.

Să analizăm algoritmul factorizării cuvintelor din locațiile în cuvintele codului . Algoritmul include următorii pași.

1. Construim lista lexicografică S a cuvintelor codului .

2. Alegem prima literă din stînga a cuvîntului ce se factorizează .

3. Din lista lexicografică S alegem toate cuvintele ce încep cu litera , reprezentăm această mulțime .

4. Dacă atunci atribuim și trecem la p. 7, în caz contrar alegem litera , următoarea după .

5. Din mulțimea îndepărtăm toate cuvintele, cu excepția acelora la care factorul stîng este cuvîntul .

6. Dacă , atunci și trecem la p.7, în caz contrar alegem următoarea literă de după adică . Mai deprate repetăm procedura descrisă la p.5, 6 tinînd cont de noul factor , și așa pînă cînd nu se va determina elementul codului .

7. Din cuvîntul înlăturăm factorul stîng , și obținem un cuvînt nou , de așa fel, încît

8. Alegem prima literă din stînga cuvîntului .

9. Alegem din lista lexicografică S toate cuvintele care încep cu litera , reprezentăm din nou această mulțime cu simbolul . Dacă , atunci atribuim și trecem la p.11. În caz contrar sînt posibile două situații:

a) , în caz contrar trasăm acțiunile analoage p.4-6;

b) mulțimea , adică nu conține nici un element, aceasta înseamnă, că pasul precedent al factorizării nu este exact și este necesar să ne întoarcem; adăugăm la cuvîntul , în dreapta, litera ce îi urmează din cuvîntul , .

10. Alegem în lista lexicografică S toate cuvintele, care încep cu cuvîntul și trasăm acțiunile analog p.4-6. Primul cuvînt aflat, ce aparține , îl marcăm și ne întoarcem la p.7, înlocuind în el cu .

11. Pe baza cuvintelor și (indicii arată numărul iterației) determinăm cuvîntul astfel, încît

și trasăm acțiunile analoge p.8-10.

Algoritmul termină lucrul la obținerea șirului de cuvinte

de așa fel, încît

.

Întrucît toate cuvintele, permit o unică factorizare în cuvintele și , atunci procesul factorizării are un caracter finit și nu admite ciclării.

Funcționarea algoritmului poate fi reprezentată concret sub forma unui șir de arbori cu rădăcini în vîrfuri, notate cu cuvintele . Soluția o constituie calea din ultimul arbore al acestui șir de la rădăcina pînă la vîrful suspendat notat cu cuvîntul .

Exemplul 1.5. Este dat codul . Se cere să se factorizeze cuvîntul în cuvintele codului X.

Soluția este prezentată sub forma grafurilor, în care vîrfurile suspendate șterse semnifică o factorizare inexactă (des. 1.25). În felul acesta, soluția are aspectul

Factorizarea prezentată este univocă.

1.4. Aritmetica numerelor întregi în rețelele Petri algebrice

Spre deosebire de cele obișnuite, rețelele algebrice Petri permit să se realizeze toate operațiile structurii numerelor întregi – adunarea, scăderea, înmulțirea și împărțirea cu rest [divizarea inexactă], ceea ce permite să se compare posibitățile modelatoare ale unor astfel de rețele cu calcularea predicatelor de ordinul întîi. Calitățile practice se determină totodată, în special, prin posibilitatea modelării polinomilor de variabile, precum și a operațiilor cu funcții prezentate sub forma tabelară.

1.4.1. Operația de adunare.

Rețeaua Petri algebrică, ce realizează operația de însumare, este prezentată pe des. 1.26. Rețeaua permite să se însumeze numerele întregi pozitive. Datele inițiale și rezultatul se prezintă sub forma șirului de simboluri s, lungimea acestui șir este egală cu valoarea numărului; simbolul n semnifică sfîrșitul șirului

Exemplul 1.6. Numărul pozitiv 7 sub forma șirului S are aspectul

.

Pentru concizie în continuare șirurile simbolurilor identice se vor prezenta sub forma de putere .

Marcarea inițială a rețelei, ce realizează operația de adunare a numerelor întregi, are aspectul ; se permite declanșarea tranzițiilor și , care transcriu șirurile indicate în poziția . La terminarea reînregistrării din ambele locații, și , se îndeplinesc condițiile pentru declanșarea tranziției , iar cuvîntul din locația se completează cu subcuvîntul n, care semnifică sfîrșitul șirului (vezi des. 1.26).

1.4.2. Operația înmulțirii.

Rețeaua Petri algebrică N, ce efectuează înmulțirea numerelor întregi pozitive, este prezentată pe des. 1.27. Toate locațiile din rețea sînt de tipul f. În locațiile și se află datele (numerele) inițiale, ce urmează a fi înmulțite, care sînt descrise în șirul de simboluri s, lungimea acestui șir este egală cu valoarea numărului. În locația va fi plasat rezultatul înmulțirii.

Marcarea inițială a rețelei

unde sînt numerele a și b ce urmează a fi reînmulțite;

.

În marcarea inițială condiția permisiunii pentru declanșare o are doar tranziția .

Des. 1.27. Model de rețea a operației de înmulțire a numerelor întregi pozitive.

Declanșarea tranziției duce la absorbirea cuvîntului s din cuvîntul , care era factorul său stîng, și la absorbirea cuvîntului n din cuvîntul , însă adică în noua marcare , unde , . Astfel, la primul pas se obține marcarea , unde

În marcarea este permisă pentru declanșare doar tranziția . Declanșarea sa duce la marcarea , , în care, spre deosebire de marcarea anterioară, se vor modifica cuvintele din locațiile și :

.

Nu este greu de observat, că tranziția va fi permisă pentru declanșare pînă în momentul cînd marcarea din locația nu va egală cu cuvîntul . În același timp conținutul locației va fi egală cu , adică partea semnificativă a numărului b va fi dublată în locația . În marcarea este permisă pentru declanșare, doar tranziția , . Ca urmare a declanșării sale obținem modificarea în conținutul locațiilor și :

.

Factorizarea cuvîntului , după codul , duce la îndeplinirea condiției declanșării tranziției . Declanșarea tuturor celorlalte tranziții este interzisă. Marcarea următoare , se deosebește de cea anterioară în locațiile ,:

.

În marcarea este permisă pentru declanșare tranziția , obținem:

.

Astfel este îndeplinit un ciclu în operația de înmulțire. Drept rezultat în locația a avut loc micșorarea lungimii cuvîntului cu o unitate, iar în locația s-a adăugat cuvîntul .

Repetarea ciclului respectiv de ori va duce la marcarea :

În marcarea este permisă pentru declanșare doar tranziția , . Avem în final:

Marcarea este o marcare terminală, , adică funcționarea ulteioară a rețelei N este imposibilă din cauza neîndeplinirii condițiilor de permisiune a declanșării pentru toate tranzițiile.

Dezvoltarea ulterioară a construcției rețelei N, ce efectuează operația de înmulțire a numerelor pozitive întregi, duce la rețea ce efectuează înmulțirea numerelor întregi arbitrare, atît a celor pozitive, cît și a celor negative. Totodată prezentarea numerelor sub forma șirurilor se modifică într-o oarecare măsură: la stînga șirului i se adaugă simbolul p, dacă numărul este pozitiv (plus), sau simbolul m, dacă numărul este negativ (minus).

Exemplul 1.7. Să notăm numerele și :

.

Pe des. 1.28 este prezentată rețeaua care se deosebește de rețeaua N din des. 1.27 prin patru tranziții suplimentare .

Des. 1.28. Înmulțirea cu luarea în considerație a semnului.

Des. 1.29. Model de rețea a operației de scădere.

Ordinea de lucru a rețelei se deosebește de funcționarea rețelei doar la primul pas, întrucît fiecare factor din locațiile și în calitate de prim simbol are fie p, fie cuvîntul m, ultimul va corespunde semnului produsului. Ulterior ordinea de lucru a releței corespunde în întregime ordinii de lucru a rețelei .

În încheiere se poate nota, că rețeaua Petri algebrică analizată, permite multiplicarea numerelor arbitrare întregi fără modificarea structurii sale proprii.

Mai mult decît atît, universalitatea rețelei prezentate nu se limitează la aceasta. Se pot construi rețele compuse din subrețele de tipul , care permit să se efectueze înmulțirea cîtorva factori.

1.4.3. Operația de scădere.

Să analizăm rețeaua algebrică , ce efectuează operația de scădere a unui număr întreg pozitiv dintr-un altul. Cazul în care în calitate de descăzut sau de scăzător avem numere negative, se reduce fie la operația de adunare a numerelor pozitive, fie la situația analizată de noi. Avînd în vedere că semnul rezultatului se determină cu delimitarea introdusă prin relațiile sau între descăzut și scăzător, datele inițiale se vor reprezenta prin șiruri fără simbolurile inițiale p sau m (vezi operația de înmulțire), iar diferența – cu simbolurile corespunzătoare p sau m.

Rețeaua Petri algebrică, ce realizează operația de scădere, este reprezentată pe des. 1.29. Marcarea inițială a rețelei este următoarea:

Rezultatul operației va fi plasat în poziția . Să presupunem

.

Marcarea admite doar declanșarea tranziției , , modificările vor avea loc în conținutul locațiilor . Marcarea atinsă nu modifică condițiile permisiunii pentru declanșarea tranzițiilor, adică din nou este permisă doar tranziția . O asemenea situație se va păstra pînă cînd într-una din locațiile sau , nu va fi absorbit ultimul subcuvînt s. Totodată sînt posibile trei cazuri.

1. . La atingerea marcării condițiile permisiunii vor fi satisfăcute de tranziția . Declanșarea acesteia va duce la golirea locațiilor și , precum și la înregistrarea în locația a cuvîntului n, . Aceasta va duce la posibilitatea declanșării tranziției și înscierea în locația a cuvîntului n, adică diferența este egală cu zero.

2. . După absorbirea ultimului subcuvînt s în locația se realizează condițiile permisiunii pentru declanșarea tranziției . În urma declanșării tranziției în locația se înscrie cuvîntul k și devine posibilă declanșarea tranziției . Tranziția va dubla conținutul locației în locația pînă la atingerea marcării .

În marcarea este permisă declanșarea tranziției , declanșarea acesteia va completa cuvîntul cu cuvîntul . Subcuvîntul complementar s este necesar pentru compensare de cuvînt în locația , care s-a simplificat cu subcuvîntul s după declanșarea tranziției și nu a fost transcris în locația . În felul acesta, în locația este înscrisă diferența , însă fără semnul p, întrucît . Marcarea permite declanșărea mai întîi a tranziției de -ori, iar apoi a tranziției . Acest lucru va duce la apariția în locația a cuvîntului . Declanșarea tranzițiilor , , va transcrie diferența .

3. . Aici situația este simetrică cu situația anterioară, cu excepția înregistrării în fața diferenței a cuvîntului m, ce semnifică valoarea negativă. Înregistrarea m se atinge datorită conținutului locației (în cazul anterior acest rol îl avea locația ). Diferența se va înscrie iarăși în locația .

1.4.4. Operația de împărțire.

Ea poate fi realizată cu ajutorul construcției utilizate mai sus pentru scădere. Pentru aceasta este suficient să se organizeze un proces de iterație, în care are loc scăderea din divizorul deîmpărțit. La atingerea valorii negative se organizează formarea rezultatului operației de împărțire sub forma unei părți întregi și unui rest.

Capitolul 2

ANALIZA REȚELELOR PETRI ALGEBRICE

2.1. Obiectivul analizei rețelelor algebrice

La modelarea sistemelor paralele arbitrare o importanță de principiu o are prezența mijloacelor ce permit să se interpreteze comportamentul proceselor independente în condițiile aplicării ordinelor lineare pe șirul subproceselor. De fapt, aplicat la rețelele algebrice, acest lucru înseamnă posibilitatea analizei locale a modificării stării pozițiilor evidențiate cu luarea în considerație a coordonării funcționării întregii rețele. Una dintre căile posibile de creare a asemenea mijloace de analiză o constituie utilizarea proprietăților algebrice ale monoidului liber asupra alfabetului finit. Totodată aici se pot evidenția două abordări. Prima este legată de proprietățile de structură ale monoidului și se realizează în planul calculării prin diferite construcții combinatoriale. A doua se bazează pe reprezentarea prin grafuri a proceselor asincrone și permite utilizarea pentru rezolvarea sarcinilor concrete a unui aparat dezvoltat al teoriei grafurilor.

Teoria prezentată mai jos este destinată în principal pentru analiza paralelismului în rețelele algebrice și verificarea posibilității de realizare locală în diferite locații ale proceselor globale ale rețelei. Totodată, problemele analizei clasice a rețelelor Petri, astfel ca marginirea, activitatea, accesibilitatea (caracterul realizabil), declanșarea și echivalența pentru rețelele algebrice, nu necesită explicări suplimentare, iar rezultatele de bază, obținute în clasa rețelelor Petri, obișnuite, sînt aplicabile și la rețelele algebrice. Situația dată se bazează pe acel fapt că, după cum s-a dovedit deja, orice rețea Petri poate fi reprezentată sub forma unei rețele algebrice.

Totuși, particularitățile specifice rețelelor algebrice aduc o serie de noi aspecte în analiza comportării sistemelor și proceselor modelate de rețele. Acest lucru se referă la posibilitatea reproducerii proceselor la un anume interval pe baza stării atinse în locații: marcarea locațiilor, reprezentată prin cuvinte ale monoidului liber pe alfabetul finit, în urma proprietăților codului permite determinarea tranzițiilor declanșate în intervalul anterior. Trecerea de la descrierea locală pe locații a procesului la descrierea globală în întreaga rețea are loc pe baza unui oarecare raport de ordin parțial, determinat de structura rețelei. Bineînțeles procesul va fi în genere reprodus în mod neunivoc din pricina prezenței preconflictelor pe tranziții. Însă toate variantele comportării rețelei sau, dacă este să spunem mai plastic „ale traiectoriei” sistemului în spațiu stărilor, se vor determina deplin.

În lucrarea prezentă sînt făcuți doar primii pași în cercetarea comportării sistemelor și proceselor modelate de rețele algebrice. Totuși, rezultatele obținute au arătat deja perspectiva abordării propuse.

2.2. Analiza de structură a mulțimii proceselor

După cum s-a arătat deja în cap.1, următoarele trei limbaje pot fi asociate cu rețeua N:

L1(N)t* 0t;

L2(N)t* n , tn;

L3(N,M)t* 0tM.

În toate limbajele prezentate cuvintele sînt secvențe ale elementelor din T. Fiecare limbaj descrie succesiunea declanșării tranzițiilor în rețeaua N pentru atingerea unei marcări concrete. Totuși, în descrierea respectivă nu sînt prezentate sub o formă evidentă subprocesele care pot să se desfășoare independent unul față de altul. Să încercăm să evidențiem aceste subprocese. Să introducem o serie de simboluri. Fie R1, R2 relații date pe produsul cartezian a două mulțimi finite E E . Compunerea relațiilor R1 și R2 este relații R1R2 :

xR1R2y z: x R1zR2y; x,y,z, E.

Pentru oricare relație R vom simboliza cu R* închiderea sa tranzitivă și reflexivă.

Dacă f : EE – funcție, atunci fR și Rf sunt relații de așa fel încît

xfSyf(x)Ry; x,y E;

xRfy z:xRz & f(z)y; x,y,z E.

Să analizăm șirul finit arbitrar . Perechea , unde 1jm o vom denumi evenimentul al nj în t. De exemplu, pentru șirul t (t1, t2, t1 ,t3, t2, t3, t1) șirul perechilor va arăta (t1,1), (t2,1), (t1,2), (t3,1), (t2, 2), (t3,2), (t1,3).

Să determinăm pe șirul t relația ordonării naturale

Ord (t) , nj, , nk j k, 1j , km.

Relația arătată poate fi prezentată sub forma unei matrice S, la care rîndurile și coloanele sînt notate cu elementele șirului t, totodată la intersecția rîndului (t1, nj) cu coloana , nk se află 1, în cazul cînd aceste elemente sînt ordonate unul față de altul, și în caz contrar, astfel, pentru șirul t mai sus prezentat:

(t1,1) (t2,1) (t1,2) (t3,1) (t2, 2) (t3,2) (t1,3)

Să analizăm o rețea oarecare N și să fixăm în ea submulțimea tranzițiilor T1T și mulțimea legată de ea, a precondițiilor PPF. Mulțimile intrărilor (x) și ale ieșilor (y), xT, yP, determină relația RP T . Întrucît în sistemele paralele tranzițiile sînt legate nu de toate precondițiile, vom evidenția în rețeaua N pentru fiecare locație p mulțimea Tpp și pentru fiecare tranziție t mulțimea Pt(t), denumindu-le corespunzător amplitudinea locației și diapazonul tranziției.

Dacă în rețeaua algebrică N cuvîntul din locația p, adică marcarea M(p), nu are proprietatea comutativității parțiale, atunci tranzițiile din amplitudinea locației sale pot să se declanșeze doar în mod consecvent, cu alte cuvinte, aceste tranziții sînt interdependente. La rîndul lor tranzițiile ce nu aparțin simultan aceleiași amplitudini a locațiilor, pot să se declașeze independent una de cealaltă.

Să admitem

DR-1R, (2.1)

ITTD. (2.2)

Relația D determină relația dependenței pe mulțimea tranzițiilor T, iar relația I – relația nedependenței pe mulțimea tranzițiilor T. Să admitem mai departe, pentru simplitate, TT, PPF. Este evident, că relația dependenței este simetrică și reflexivă, iar relația nedependenței – simetrică și nereflexivă.

Să determinăm monoidul linear asupra alfabetului T, T,, , unde T este mulțimea șirurilor finite de tot felul al elementelor din T ; – operația de concatenare; este șirul vid. Să introducem pe mulțimea T congruența , de așa fel, încît t t t t t t, adică congruența se determină prin comutativitatea elementelor T. Monoidul factor T/ este, de asemenea, un monoid, iar elementele sale – clase de echivalență – se numesc urme .

Des. 2.1. Exemplu de rețea.

Este necesar să remarcăm că sorgintea apariției comutativității pe T se determină prin independența tranzițiilor, descrisă de relația I. La rîndul său comutativitatea elementelor T naște o comutativitate parțială în subcuvintele cuvintelor T. Pentru fiecare cuvînt t T simbolizăm t urma reprezentată de t. Cuvîntul t T arată succesiunea declanșării tranzițiilor în rețea. Tranzițiile independente, după cum s-a remarcat deja, au proprietatea comutativității. De aceea urma t este o mulțime în care intră toate variantele posibile ale descrierii declanșării tranzițiilor la tema fixată, adică după succesiunea dată a declanșării se construiește mulțimea variantelor posibile de descriere a declanșării tranzițiilor, variante ce nu contravin cu această succesiune.

Exemplu 2.1. Să analizăm rețeaua N (des. 2.1.), deocamdată nu ne interesează marcarea arcelor. Avem:

P p1, p2; T t1, t2, t3;

Rp1, t1, p1, t2, p2, t2, p2, t3;

Dt1, t1, t2, t2, t3, t3, t1, t2, t2, t1, t2, t3, t3, t2) relația dependenței);

I( t1, t3 ); ( t2, t3 ) (relația independenței);

t1, t2; t2, t3 (amplitutdinea locației);

p1; p1, p2; p2 (gama tranziției).

Pentru șirul t t2t1t1t3t2 urma t t2t1t1t3t2 , t2t1t3t1t2 , t2t3t1t1t2. Nu există ordonare între declanșările tranzițiiilor t1 și t3 , adică ele sînt independente.

Să analizăm relația

(t)Ord(t) tt.

Să raportăm la urma t mulțimea:

={(, nj) | t, tt ,

njcard k kj, , , t, t t .

Propoziția 2.1. (t) este o relație de ordine parțială pe mulțimea pentru fiecare urmă t din T/.

Pentru elementele urmei t din exemplu 2.1. matricele raporturilor Ord (t), t t arată astfel:

(t2 , 1) (t1 , 1) (t1 , 2) (t3 , 1) (t2 , 2)

(t2 , 1) (t1 , 1) (t3 , 1) (t1 , 2) (t2 , 2)

(t2 , 1) (t3 , 1) (t1 , 1) (t1 , 2) (t2 , 2)

Să schimbăm în matricele S2 și S3 rîndurilor și coloanelor între ele cu locurile în așa fel, încît să corespundă ordinii de parcurs a rîndurilor și coloanelor din matricea S1, obținem:

(t2 , 1) (t1 , 1) (t1 , 2) (t3 , 1) (t2 , 2)

(t2 , 1) (t1 , 1) (t1 , 2) (t3 , 1) (t2 , 2)

Matricea relației (t) este egală cu matricea , ale cărei elemente sînt egale cu produsul boolean al elementelor corespunzătoare ale matricelor S1, S2, S3, S1) (S2)(S3):

(t2 , 1) (t1 , 1) (t1 , 2) (t3 , 1) (t2 , 2)

Elementele șirului t, pentru care , vor fi independente. În exemplul analizat acestea sînt tranzițiile t1 și t3.

Astfel, am evidențiat suprocesele independente în succesiunea declanșării tranzițiilor, utilizînd noțiunea de urmă a clasei de echivalență a monoidului factor T/. Să analizăm acum succesiunea declanșării tranzițiilor dintr-un alt punct de vedere. Fiecare locație creează succesiv precondițile pentru declanșarea tranzițiilor ce intră în mulțimea amplitudinii sale. Prin urmare, totalitatea istoriilor individuale de modificare a stărilor tuturor locațiilor creează o imagine generală a descrierii funcționării rețelei. Să descriem acest lucru formal.

Fie . Elementele sînt funcții din p în , adică , . Să definim operația de concatenare în în felul următor:

Să admitem , și astfel este monoid. Să determinăm pentru fiecare element elementul :

Submonoidul H al monoidului , format de mulțimea se numește monoid de istorii globale asupra lui T. Introducerea submoidului H este condiționată de dorința de a elimina astfel de elemente ale monoidului , care nu sînt realizabile cu o structură concretă a rețelei. De exemplu elementul nu este istoria rețelei N, întrucît tranziția t2 poate să se declanșeze doar în cazul îndeplinim precondițiilor din p1 și p2.

Dacă este istoria, atunci este istoria individuală pentru fiecare pP în .

Exemplu 2.2. Pentru datele inițiale din exemplul 2.1. este istorie. se poate reprezenta sub aspectul concatenării elementelor din în felul următor:

Exemplul dat mai sus arată, că pentru descrierea procesului în rețea se pot utiliza elemente diferite ale monoidului , concatenarea cărora dă unul și același rezultat căutat – una și aceeași istorie a întregului proces. Totodată limita superioară a agregării istoriilor este evidentă – aceasta este istoria . Astfel stau lucrurile cu limita inferioară a descompunerii istoriei în istorii componente Deplin firească este întrebarea: care este lungimea maximă a șirului ce constituie , adică valoarea maximă n. Vom formula răspunsul sub forma unei propoziții.

Propoziția 2.2. Fie istorie asupra T . Lungimea maximă a șirului de elemente , ce reprezintă este egală cu numărul de elemente din mulțimea ce reprezintă. În felul acesta, în descompunerea celei mai mari lungimi

Să stabilim acum legătura între noțiunile de urmă și istorie. Să luăm un element arbitrar t al monoidul factor T/ , să fixăm un t t, arbitrar să admitem pentru precizie . Să raportăm la fiecare elementul său din și să notăm:

Formația obținută este istoria procesului descris de urma t în rețea. Demonstrația aceste afirmații se bazează pe propoziția 2.2. și pe proprietățile urmei t.

Exemplu 2.3. Să folosim datele inițiale ale exemplului 2.1. și să luăm urma

Alegem și determinăm :

Efectuînd operația de concatenare în , obținem

Să observăm, că același rezultat s-ar fi obținut dacă în locul elementului t am fi ales oricare alt element Astfel, s-a arătat, că trecerea de la urma t la istoria nu prezintă practic nici un fel de greutăți. Pentru a realiza acum trecerea inversă de la la t trebuie introduse o serie de noțiuni.

Să admitem

Să determinăm mulțimea de tipul următor:

Propoziția 2.3. este o relație de ordine parțială pe mulțime pentru fiecare istorie .

Propoziția 2.4. Relațiile de ordine parțială și sînt izomorfe.

Să determinăm matricea , corespunzătoare relației . Pentru aceasta, la început este necesar să scaotem mulțimea perechilor de tipul din relațiile pentru toate locațiile pP, iar apoi să le ordonăm sub forma unui tabel. Pentru datele inițiale din exemplul 2.3. avem:

Ca rezultat

Pe baza vom construi matricea , numerotînd rîndurile și coloanele în aceeași ordine, ca în matricea:

(t2 , 1) (t1 , 1) (t1 , 2) (t3 , 1) (t2 , 2)

Izomorfismul relațiilor de ordine parțială și se demonstrează prin egalitatea matricelor și .

Din propoziția 2.4. decurge mecanismul transformării în . În acest scop trebuie să se construiască relație și matricea corespunzătoare . Ulterior elementele mulțimii se ordonează sub forma șirului , totodată acele elemente și , care sînt independente, se pot dispune unul față de celălalt într-o ordine arbitrară. Mulțimea tuturor șirurilor permise formează t.

Să analizăm acum relația , definită pe produsul cartezian al mulțimii tranzițiilor și al mulțimii locațiilor în rețeaua N : (ti , pj) , dacă . Să evidențiem pentru fiecare locație p mulțimea tranzițiilor și pentru fiecare tranziție mulțimea locațiilor , vom denumi aceste mulțimi gama locației și amplitudinea tranziției corespunzătoare. Relația este dual ralației R și stabilește căile înmagazinării cuvintelor în locațiile rețelei.

Să raportăm la fiecare tranziție un vector, ale cărui elemente sînt notate cu mulțimea locațiilor P:

unde

Să notăm prin următorul vector:

Să determinăm pe mulțimea a celor mai diferite șiruri finite ale elementelor din operația de compoziție sub forma unei operații obișnuite de concatenare, ce se efectuează pe componente:

Să extindem operația dată prin inducție asupra șirului arbitrar finit al elementelor din .

Propoziția 2.5. este monoid. Să notăm prin , unde este mulțimea tuturor cuvintelor finite peste alfabetul , calitatea căruia o are gama locației p. Atunci este submonoidul monoidului , care în continuare va fi numit monoidul locațiilor. Elementele monoidului locațiilor sînt funcții din mulțimea locațiilor P în mulțimea cuvintelor , adică .

Necesitatea introducerii monoidului posibilităților este determinată de următoarele. Fie e dat un șir oareacare al declanșării tranzițiilor în rețeaua N, . Trebuie să se stabilească influența procesului t asupra stării locațiilor. Pentru aceasta fiecărui i se raportează un element din și se determină pentru șirul t elementul corespunzător al monoidului , egal cu. Fiecare proiecție este un cuvînt din , ea arată succesiunea tranzițiilor ce modifică marcarea în locația P. Astfel spus, se poate stabili pentru orice proces t influența lui asupra stării proceselor

.

Des.2.2 Rețea cu locații de tipul f și p.

Să tragem o concluzie la rezultatele obținute. Noțiunile introduse de urmă a istorii și de postistorie permit să se descrie modificările stării locației la modelarea proceselor asincrone din punctul de vedere al creării precondițiilor pentru tranzițiile corespunzătoare și al modoficării post condițiilor în locații. Acest lucru dă posibilitatea efectuării unei analize locale a stării locațiilor pentru oricare proces fixat, modelat de rețeaua algebrică. Pentru a răspunde la întrebarea asupra permisiunii procesului dat tT în rețea, este suficient să găsim istoria ce îi corespunde

și postistoria ce îi corespunde

pentru fiecare locație .

Dacă a este locația tipului f, căreia îi corespund istoria și postistoria , atunci pentru toate cuvîntul ar trebui să fie factor stîng al cuvîntului , unde M(a) este marcarea inițială a rețelei pînă la realizarea procesului t. sunt elementele procesului t, ce determină o parte a postistoriei , care va fi realizată la momentul încheierii istoriei

Dacă a este locația de tipul P, atunci cuvîntul S trebuie să fie factor drept al cuvîntului .

Exemplu 2.4. Să analizăm rețeaua N de tipul următor (des. 2.2) unde p1 este locația de tip f, p2 este locația de tip p.

Pentru procesul descris de șirul

istoria și postistoria ce îi corespunde

Șirul t poate fi realizat de rețeaua N cu marcarea inițială M, dacă

va fi factor stîng al

iar

va fi factor drept al

2.3. Modele de grafuri ale interacțiunii proceselor

În 2.2. s-a analizat abordarea structurală a analizei paralelismului în rețele. Indiferent de toate avantajele legate de simplitatea realizării sale în plan algoritmic datorită proprietăților combinatoariale, ea are un dezavantaj, care într-o serie de cazuri influențează negativ rezultatele cercetărilor practice, – absența caracterului intuitiv al imaginii. Ieșirea din această situație o constituie elaborarea interpretării de graf a abordării structurale, care ar avea proprietățile combinatoariale ale abordării structurale și ar reprezenta clasa grafurilor orientate, ceea ce ar permite, în afară de toate celelalte, utilizarea pentru analiza rețelelor a unui aparat dezvoltat al teoriei grafurilor.

Să analizăm reprezentarea de graf a urmelor și istoriilor. Reprezentarea de graf a urmelor o constituie așa numitele grafuri ale dependențelor cu o mulțime de vîrfuri notate cu elementele și arcele ce leagă vîrfurile depedente. Vîrfurile se numesc dependente, dacă ele sînt notate cu tranziții interdependente.

Definiția 2.1.Tripletul se numește graful dependențelor asupra lui t, unde V este mulțimea de noduri; este mulțimea arcelor; este aplicație ce asociază fiecare vîrf cu o tranziției oarecare , totodată

unde idV este aplicația identică în V; D este relația depdendenței în rețeaua N.

Condiția (2.3) asigură absența ciclurilor în graful G. Condiția (2.4) înseamnă, că două vîrfuri diferite sînt legate printr-un arc atunci și numai atunci, cînd ele sînt depedente. Să analizăm expresia (2.4). Vîrful x1 este legat de vîrful x2 dacă

Des.2.3. Graful dependențelor.

Exemplul 2.5. Pentru urma t din exemplul 2.1. graful dependențelor are aspectul arătat pe des. 2.3.

Definiția 2.2.Graful dependențelor este compunerea grafurilor dependențelor și dacă

a) ;

b)

c)

Condiția a) vorbește despre faptul că graful ce rezultă are în calitate de mulțime a vîrfurilor sale reuniunea mulțimilor ce nu se intersectează ale vîrfurilor grafurilor G1 și G2.

Condiția b) indică necomutativitatea operației de compunere și stabilește legăturile în graful G, în care sînt incluse toate arcele din G1 și G2, și sînt adăugate arcele din mulțimea vîrfurilor V1 în mulțimea vîrfurilor V2, ce satisfac condiția . Vîrful este legat de vîrful , dacă

;

întrucît

În acest fel relație dependenței apare în rolul „filtrului”, ce permite să se stabilească legătura din V1 în V2 doar pentru elementele dependente din T. Plecînd de la univocitatea funcțiilor în T, se poate trage concluzia asupra univocității operației de compunere a grafurilor arbitrare ale funcțiilor.

Condiția c) semnifică faptul că .

Să reprezentăm graful vid al funcțiilor și G – mulțimea tuturor grafurilor funcțiilor în T. Atunci va fi monoid, unde este operația de compunere asupra elementelor mulțimii G.

Operația de compunere pe grafuri este de fapt similară cu operația de concatenare a șirurilor în T. Într-adevăr legătura de la vîrfurile V1 ale grafului G1 la vîrfuri V2 ale grafului G2 duce la un nou graf G, care corespunde șirului obținut în urma concatenării. Totuși, o importanță de principiu o are aici faptul, că graful G descrie întreaga clasă de echivalență t din monoidul factor T/.

Să introducem funcția h, definită pe mulțimea vîrfurilor grafului funcțiilor G, astfel încît

unde

Funcția raportează la fiecare vîrf al grafului G tranziția și un număr de vîrfuri notate cu aceeași tranziție ti, dintre care vîrful respectiv este posibil de atins. Atunci relația ordonează parțial mulțimea vîrfurilor grafului G.

Să determinăm pe mulțimea T funcția F cu mulțimea de valori din G:

Propoziția 2.6. Relația de ordine parțială pe mulțimea grafului G se determină în felul următor:

Propoziția 2.7. Relațiile de ordine parțială , , sînt izomorfe.

Reprezentarea grafică a istoriilor nu se deosebește de reprezentarea grafică a urmelor, totuși, procesul construirii graficului are loc diferit. În calitate de date inițiale la determinarea grafului istoriei (să-l denumim în continuare graful evenimentelor) avem mulțimea și relației .

Definiția 2.3. Graf al evenimentelor se numește perechea , unde este mulțimea vîrfurilor grafului Г; este mulțimea arcelor grafului Г.

Să reprezentăm Г mulțimea tuturor grafurilor evenimentelor, date pe mulțimea . Operația compunerii grafurilor evenimentelor se poate determina astfel:

Definiția dată a operației de compunere este corectă, întrucît operația de concatenare în monoidul este determinată univoc.

Pe mulțimea Г se poate determina monoidul unde este operația de compunere a grafurilor evenimentelor; este graful vid .

Ce noutate a conferit analizei proceselor introducerea grafurilor dependenței și evenimentelor? În primul rînd, asincronismul desfășurării proceselor în rețeaua algebrică a devenit evident. Din graful dependențelor se extrag ușor componentelele independente ale procesului. În al doilea rînd, graful depedențelor permite să se stabilească conflictele anterioare și cele posterioare ale tranzițiilor pe baza analizei mulțimilor arcelor de intrare și de ieșire în vîrfurile grafului. În al treilea rînd, se poate determina istoria locală a lungimii maxime (minime) din graful dependențelor care este egală cu calea maximă (minimă) din vîrful inițial (calitate căreia, avînd-o pentru fiecare locație, vîrful însemnat de prima tranziție ce intră în istoria acestei locații) în vîrful finit, însemnat de ultima tranziție tot din istoria acestei locații.

Astfel, se poate trage concluzia, că toate obiectivele analizei rețelelor algebrice, care se rezolvă prin metode de structură se pot rezolva prin metodele teoriei grafurilor, cu alte cuvinte există o reducere a obiectivelor analizei proceselor în realizare combinatoariale la obiective ale analizei proceselor în cadrul teoriei grafurilor și invers.

Capitolul 3

MODELE DE SINCRONIZARE A PROCESELOR PARALELE

3.1. Categoria rețelelor Petri algebrice

Să analizăm abordarea ce permite crearea unor construcții de categorie pe rețelele Petri algebrice și cercetarea pe baza lor a comportamentului unor sisteme complexe, reprezentate de rețele, după rezultatele analizei componentelor lor. Noțiunea cheie la construirea categoriei o constituie morfismul pe rețele, care păstrează caracteristicile comportamentului lor dinamic.

Înainte de a începe expunerea noțiunilor fundamentale, să introducem o serie de simboluri. Fie R1, R2 – relații date pe produsul cartezian al mulțimilor finite: . Compunerea relațiilor R1 și R2 o constituie relație

Dacă relația satisface proprietatea

atunci relația R este funcție parțială. Funcția parțială R va fi completă, dacă pentru oricare există b, de așa fel, încît are loc . În continuare vom simboliza cu nedeterminarea valorii funcției parțiale R la argumentul a: dacă , atunci pentru argumentul a nu există funcția parțială R. Relația inversă pentru R are aspectul

.

Fie și – rețele Petri algebrice. Să admitem la început, că mulțimile locațiilor în rețelele N0 și N1 sînt doar de tip f, adică . În continuare vom renunța la această ipoteză. Morfismul din rețeaua N0 duce în rețeaua N1 informația despre faptul, cum comportamentul dinamic al rețelei N0 induce un comportament dinamic în rețeaua N1 . Morfismul include patru componente . Prima componentă, , este o funcție parțială, determinată pe produsul cartezian al mulțimilor tranzițiilor rețelelor Totodată relația semnifică faptul că declanșarea tranziției atrage simultan după sine declanșarea tranziției . Această împrejurare impune la rîndul său anumite condiții corespondentei între mulțimile pre- și postcondițiilor tranzițiilor și .

Condițiile indicate sînt realizate de a doua componentă a morfismului – de relația . Relația înseamnă, că cuvîntul, conținut în poziția se raportează la cuvîntul conținut în locația . Se presupune, că există o unică locație în N0 , care se raportează la locația în N1. Această cerință permite să se transfere în mod univoc marcarea inițială a locațiilor din N0 în N1 cu cea de-a treia componență a morfismului – cu relația .

Cea de-a patra componentă a morfismului este relația dată pe produsul cartezian al mulțimilor finite

Relația înseamnă că marcarea arcului se transferă din N0 în marcarea arcului în N1. Condițiile concordanței cu , și se analizează mai jos.

Din structura dată a morfismului rezultă o serie de proprietăți ce îl compun. Să le definim formal.

Definiția 3.1. Fie – rețele Petri algebrice. Morfismul din N0 în N1 este sistemul , care satisface următoarele condiții:

1) Dacă ,

atunci este funcția completă

și este funcția completă ;

2) dacă și , atunci

și

3) dacă ,

atunci este funcția completă

și este funcția completă

4) este astfel, încît ;

aceasta înseamnă că adică ;

5) dacă , , atunci și , unde este codul de intrare al locației din rețeaua N1;

6) dacă , și ,

atunci și este cod;

dacă , și ,

atunci și este cod.

Să analizăm mai amănunțit partea de conținut a fiecăreia dintre proprietățile prezentate mai sus al morfismului din N0 în N1. Prima proprietate înseamnă că, dacă tranziția se reflectă în tranziția , atunci toate precondițiile tranziției sînt legate de precondițiile tranziției , cu alte cuvinte, modificarea conținutului locațiilor mulțimii precondițiilor tranziției se determină prin modificarea conținutului locațiilor mulțimii de precondiții ale tranziției , dar nu obligatoriu cu toată mulțimea de precondiții ale tranziției , adică . În mod analog este adevărat pentru mulțimea postcondițiilor tranzițiilor și :

.

A doua proprietate vorbește despre faptul, că, dacă două tranziții, și , din rețeaua N0 se reflectă într-una și aceeași tranziție a rețelei N1, atunci tranzițiile și se găsesc în stare de conflict de tranziție, adică intersectarea mulțimilor precondițiilor lor nu este vidă și conținutul ei determină conținutul mulțimii precondițiilor tranziției . În afară de aceasta, pe baza primei proprietăți a definiției, tranzițiile și se găsesc în stare de conflict posterior, adică intersectarea mulțimilor postcondițiilor lor nu este vidă și conținutul ei determină conținutul mulțimii postcondițiilor tranziției .

Următoarea proprietate se referă la relației dintre mulțimile locațiilor. Dacă locația din N0 se raportează la locația din N1, atunci mulțimea tranzițiilor, ce au legătură la intrare cu locația și căreia îi modifică conținutul, se reflectă în mulțimea tranzițiilor ce au legătură la intrare cu locația și căreia îi modifică conținutul. O afirmație similară este adevărată pentru mulțimile tranzițiilor, ce au legătură la ieșire cu locațiile și . Prezența unor asemenea legături între mulțimile tranzițiilor semnifică faptul, că fiecare modificare în conținutul locației duce la o modificare corespunzătoare în conținutul locației .

A patra proprietate a morfismului necesită ca marcarea inițială nenulă a rețelei N1 să fie legată total de marcarea inițială nenulă a rețelei N0 și fiecare locație a rețelei N1 cu marcare inițială nenulă să fie legată de unica locație a rețelei N0 cu marcare inițială nenulă. Să analizăm exemplul ce ilustrează condițiile impuse morfismului.

Des. 3.1. Exemplu, ce ilustrează condițiile suprapuse morfismului.

Exemplul 3.1. Pe des. 3.1 este reprezentat morfismul din rețeaua N0 în rețeaua N1. Marcarea locațiilor și arcelor lipsește pe des. 3.1., întrucît în exemplu se studiază doar dependențele de structură. Mulțimile pre- și postcondițiile tranziției a rețelei N1 sînt legate total de mulțimile pre- și postcondițiile tranzițiilor și , care se reflectă în tranziția . În afară de aceasta, tranzițiile și se află în stare de conflict anterior și conflict posterior și conținutul locațiilor ,, determină conținutul locațiilor ,,,. Este evident, de asemenea, îndeplinirea celei de-a treia condiții, care cere, ca tranzițiile legate la intrare și ieșire de poziția reflectată, să fie legate cu tranzițiile corespunzătoare ale rețelei N1, cu care are legătură imaginea locației. Astfel, locația este legată de locațiileși , de aceea este necesar, ca ambele tranziții și să se reflecte în tranziția , care este legată de locațiile și . Pentru respectivul morfism marcarea inițială poate fi doar în locațiile și (sau într-una din aceste locații).

Toate proprietățile morfismului analizate mai sus se refereau la relațiile dintre locații și tranziții și se realizau cu componentele și ale morfismului. Următoarele proprietăți sînt legate de conținutul locațiilor, adică de cuvinte în locații și de marcarea arcelor. A cincea proprietate a morfismului semnifică faptul că, dacă locația cu marcarea inițială nenulă se raportează la locația , atunci conținutul locațiilor și satisface relația , totodată marcarea este factorizabilă univoc după ciclul de intrare al locației . Condiția respectivă asigură lipsa blocării în rețeaua N1 la marcarea inițială indusă.

Ultima proprietate a morfismului se referă la relația dintre mulțimile cuvintelor ce notează arcele în rețelele N0 și N1. Ea semnifică faptul, că dacă locația (tranziția ) este legată de tranziția ( locația ), totodată (), adică arcul este notat cu un cuvînt nevid, iar locația din N0 este raportată la locația din N1, tranziția la tranziția , atunci cuvintele, care notează arcele între ele, satisfac relația și mulțimea cuvintelor ce notează mulțimea arcelor de intrare (ieșire) ale locației și induse de relația , formează un cod.

Să indicăm acum posibilitatea refuzului limitării ce se referă la prezența în rețelele N0, N1 a locațiilor de același tip. Dacă în N0 și N1 sînt prezente locațiile ambelor tipuri, atunci relația se determină în felul următor :

Este evident că completarea adusă nu aduce dificultăți de principiu la construirea morfismului, totuși pentru a evita ulterior necesitatea de a înfrunta o serie de dificultăți tehnice, ce îngrădesc esența problemei, vom admite iarăși, că în rețele sînt prezente locațiile unui tip. Înainte de a da exemple de morfisme concrete, să definim noțiunea de subrețea.

Definiția 3.2. Fie – rețele Petri algebrice. Atunci N0 este subrețea N1 dacă

pentru orice este adevărat:

1)

2)

Cu alte cuvinte, mulțimea locațiilor rețelei N0 este submulțimea mulțimii locațiilor rețelei N1, însă totodată ea include toate locațiile cu marcare inițială, conținutul cărora este egal cu marcarea inițială a rețelei N1. La rîndul său mulțimea tranzițiilor T0 aparține mulțimii T1 și satisface condiția

sau

adică oricare element al rețelei este incident măcar la un alt element al rețelei.

Cel mai simplu exemplu de subrețea îl reprezintă limitarea rețelei N după mulțimea de tranziții. Astfel, dacă – rețea, atunci – subrețea, unde .

Să analizăm două exemple de morfisme obținute cu ajutorul operației de limitare Rs. Fie – limitarea rețelei N după mulțimea tranzițiilor T0. Aici nu se cere îndeplinirea condițiilor adică N0 nu este obligatoriu subrețea N. Atunci morfismul

,

unde sînt aplicați firești, iar – sînt relații de egalitate, se numește aplicație.

Proiecție se numește morfismul

unde . Limitarea funcției parțiale după mulțimea tranzițiilor T0, este injecție naturală. Pentru oricare sînt definite aplicațiile surjective

aici

și

, unde

relațiile f, f sînt relații de egalitate.

Rezultatele obținute permit construirea categoriei de rețele Petri algebrice, în care în calitate de obiecte vom vea rețelele algebrice, iar morfisme vor fi morfismele de rețea analizate mai sus.

Definiția 3.3. Categoria rețelelor algebrice se determină în felul următor:

1) mulțimea obiectelor Ob AN , calitatea cărora avîndu-le rețelele algebrice;

2) pentru fiecare pereche de obiecte (N0, N1) se determină mulțimea morfismelor de rețea Mor (N0, N1).

pentru fiecare triplet de obiecte (N0, N1, N2) se dă reprezentarea

totodată compunerea morfismelor de rețea se determină pe componente, adică

compunerea morfismelor de rețea satisface axioma asociativității;

4) pentru fiecare obiect există un morfism identic 1N de așa fel, încît pentru oricare morfisme se îndeplinesc egalitățile

Astfel, am construit categoria de rețele algebrice. Pasul următor pe această cale îl reprezintă cercetarea proprietăților respectivei categorii și aplicarea lor pentru analiza sistemelor.

3.2. Categoria de produs

Să analizăm unele construcții de categorie. Aici va fi necesară utilizarea categoriei de mulțimi Set . Să determinăm în categoria Set produsul și coprodusul.

Definiția 3.4. Produsul în Set a două mulțimi, A1 și A2 se numește obiectul Set, notat prin

, cu două morfisme-proiecții ,

astfel încît pentru obiectul arbitrar și perechea de morfisme

există un morfism unic ,

pentru care

Definiția 3.5. Coprodus în Set a două mulțimi, A1 și A2 se numește obiectul Set, notat prin

, cu două morfisme-injecții,

astfel încît pentru obiectul arbitrar și perechea de morfisme

există un unic morfism ,

pentru care

Produsul de categorie al rețelelor algebrice se poate determina plecînd de la următoarele considerații. În definiția rețelei algebrice figurează două mulțimi: mulțimea locațiilor și mulțimea tranzițiilor. În categoria Set sînt determinate, cu o precizie de pînă la izomorfism, produsele mulțimilor locațiilor și mulțimilor tranzițiilor ale două rețele algebrice arbitrare. Pe baza lor se pot crea noi rețele, care vor avea drept mulțime a locațiilor fie produsul de categorie al mulțimilor locațiilor rețelelor inițiale, fie asocierea lor disjunctă, iar ca mulțime a tranzițiilor – fie produsul de categorie al mulțimilor tranzițiilor rețelelor inițiale, fie asocierea lor disjunctă. În felul acesta se definesc trei tipuri de produse.

Definiția 3.6. Produs P de categorie al rețelelor algebrice

se numește rețeaua cu mulțimea de locații , mulțimea de tranziții , alfabetul , marcarea inițială , ponderea V, care notează arcele după regulă:

dacă sau

dacă ;

dacă sau

dacă ; proiecțiile și sînt morfisme-proiecții definite anterior.

Definirea produsului P de categorie necesită cîteva explicații. Prima se referă la necesitatea introducerii în produsul de categorie a mulțimilor vide ale mulțimii locațiilor rețelelor. O extindere asemănătoare include în rețeaua locații de felul și , ceea ce la rîndul său asigură obținerea rețelelor inițiale prin operația de limitare pe locații, similară cu operațiile de limitare Rs pe tranziții. A doua explicați se referă la marcarea inițială a locațiilor. Astfel, dacă , atunci locația de felul are marcarea inițială . O afirmație simetrică se referă la locațiile de felul . Pentru locațiile de felul marcarea inițială se determină după regula

adică cuvintele S0, S1 sînt parțial comutative în locația . Echivalența produsului P de categorie se garantează prin produsul de categorie în Set.

Definiția 3.7. Produs T de categorie al rețelelor algebrice

se numește rețeaua , cu alfabetul , marcarea inițială , ponderea V, care notează arcele după regulă cu mulțimea de locații , mulțimea de tranziții:

dacă sau

dacă ;

dacă sau

dacă ; proiecțiile și sînt morfisme-proiecții definite mai devreme.

În definițiile produsului P și, respectiv, a produsului T de categorie se întrevede ușor simetria. În produsul P, în esență, este făcută o asociere disjunctă a mulțimilor tranzițiilor, care este legată într-un întreg cu mulțimea locațiilor de felul , ce au legături cu mulțimile tranzițiilor uneia și celeilalte rețele. În produsul T sînt asociate disjunct mulțimile locațiilor legate prin tranzițiile de felul . Cele spuse mai sus schițează hotarele utilizării utile a noțiunilor de produs P și produs T. În produsul P sînt cuprinse compunerile paralele ale rețelelor pe mulțimea de pre- și postcondiții, compuneri ce sînt modelate ca limitări pe mulțimea locațiilor corespunzătoare. În produsul T sînt cuprinse compunerile paralele ale rețelelor pe mulțimile de tranziții, modelate ca limitări pe mulțimile tranzițiilor dependente și ale tranzițiilor nedependente , . Următoarea definiție reunește ambele tipuri de produse.

Definiția 3.8. Produs P-T de categorie al rețelelor algebrice

se numește rețeaua cu mulțimea de locații , mulțimea de tranziții , cu alfabetul ,

marcarea inițială , ponderea V, care notează arcele după regula:

dacă sau

dacă ; sau

dacă , , , , – sînt parțial comutative;

dacă sau

dacă ; sau

dacă , , , , – sînt parțial comutative;

proiecțiile și sînt morfisme-proiecții.

Să menționăm încă o dată, că produsul de categorie P-T include simultan și produsul P, și produsul T. Prin urmare, în el sînt cuprinse compunerile paralele atît după mulțimea locațiilor, cît și pe mulțimea tranzițiilor, care devin proiecții după elemente corespunzătoare. Definițiile produselor de categorie pot fi adaptate pentru produsele familiei de rețele algebrice. Este ușor de dovedit, că fiecare dintre produsele de categore analizate mai sus este unică cu o precizie de pînă la izomorfism.

Definiția coprodusului în categoria AN a rețelelor algebrice este duală la produs. Coprodusul în categoria rețelelor algebrice reprezintă o asociere fără legătură a rețelelor și nu prezintă interes din punct de vedere teoretic.

Exemplul 3.2. Pe des. 3.2. sînt reprezentate două rețele algebrice N0 și N1 . Pentru o mai mare concretețe mulțimile locațiilor și tranzițiilor la o rețea sînt notate cu litere latine, iar la cealaltă cu cifre. Pe des. 3.3. este prezentat produsul P al rețelelor algebrice N0 și N1 , pe des .3.4 – produsul T, iar pe des. 3.5. – produsul P-T.

Des. 3.2. Rețele N0 și N1.

Des. 3.3. Produs P al rețelelor N0, N1.

Des. 3.4. Produs T al rețelelor N0, N1.

Des. 3.5. Produs P-T al rețelelor N0, N1.

3.3. Obiectivele sincronizării proceselor paralele

Întregul complex al obiectivelor sincronizării proceselor paralele se poate împărți în două clase. În prima clasă, intră obiectivelor legate de sincronizarea indusă, la care un sistem determină comportamentul altui sistem prin intermediul influențării mulțimii sale de pre- și postcondiții. A doua clasă de obiective este legată de sincronizarea reciprocă a sistemelor. În acest caz este necesar să se coordoneze funcționarea comună a celor două sisteme în interesul atingerii aceluiași scop. Să analizăm pe rînd ambele clase de obiective.

Pentru început este bine să se evidențieze cîteva grupe de morfisme de rețea în funcție de proprietăților relațíilor și . Prima este grupa de morfisme la care este funcție completă. În acest caz rețeaua care este domeniul de definire a morfismului, sincronizează parțial comportamentul dinamic al rețelei care este domeniul semnificației morfismului. Mai departe vom numi astfel de morfisme-sincrone. Dacă însă va fi o funcție surjectivă completă, atunci comporatmentul dinamic al rețelei – domeniului semnificației morfismului – se descrie univoc de rețeaua ce este domeniul definirii morfismului. Vom denumi aceste morfisme – morfisme puternic sincrone.

Următoarea grupă de morfisme sînt morfisme la care este funcție surjectivă completă. Asemenea morfisme le vom denumi de cuprindere, plecînd de la faptul că modificarea conținutului tuturor locațiilor rețelei – domeniului semnificației morfismului – se determină prin modificarea conținutului tuturor locațiilor rețelei-domeniului definirii morfismului.

Propoziția 3.1. Dacă reprezintă un morfism sincron, atunci :

1)

2)

Demonstrația propoziției se bazeză pe proprietățile morfismului din definiția 3.1., în special pe caracterul complet al funcției . Dezvoltarea părții de conținut a propoziției 3.1. permite să se formuleze o proprietate a morfismelor, foarte utilă la analiza rețelelor.

Propoziția 3.2. Fie – morfismul rețelelor, – modificarea marcării în rețeaua N0 datorită declanșării mulțimii tranzițiilor . Atunci

Cu alte cuvinte, pentru determinarea marcării, ce se realizează în rețea în urma declanșării mulțimii tranzițiilor din marcarea inițială , este suficient să se determine marcarea din rețeaua N0 la declanșarea mulțimii tranzițiilor E0 din marcarea inițială M0 și să se folosească relația .

Una din posibilele direcții ale clasificării ulterioarea a morfismelor este legată de scoaterea în evidență a mulțimii Np a rețelelor algebrice cu una și aceeași mulțime a locațiilor și mulțimi diferite ale tranzițiilor și a mulțimii NE de rețele algebrice cu una și aceeași mulțime de tranziții și mulțimi diferite ale locațiilor. Definirea pe mulțimea Np a morfismelor cu funcție identică și funcție surectivă duce la noțiunea de morfism de compresiune pe tranziții, care pe o mulțime de pre- și postcondiții micșorează mulțimea tranzițiilor. Definirea pe mulțimea NE a morfismelor cu funcție identică și funcție surjectivă duce la noțiunea de morfism de compresiune pe locații care pe o mulțime de tranziții, păstrînd dinamica comportării, micșorează numărul de pre- și postcondiții.

Toate grupele de morfisme determinate mai sus permit să se formuleze scopul sincronizării induse sub forma obiectivului căutării morfismului corespunzător. Pozitiv, aici, apare faptul că spectrul larg al obiectivelor se analizează în poziții metodologice unitare.

Să trecem acum la problema sincronizării reciproce. Noțiunea, anterior formulată, de produs de categoie dă posibiltatea de a determina diverse compuneri paralele ale rețelelor alegebrice, în care mulțimile tranzițiilor și locațiilor pot fi, fie o asociație disjunctă, fie un produs cartezian. Produsul P de fapt sincronizează comportamentul rețelelor algebrice la îndeplinirea precondițiilor. Doar în cazul realizării precondițiilor cerute în toate rețelele ce se sincronizează, va avea loc dezvoltarea ulterioară a procesului. Produsul T include compunerile paralele, ce permit pentru fiecare rețea o funcționare independentă, dar totodată posedă tranzițiile ce fixează declanșarea sincronă. Produsul P-T este unificarea a două tipuri de compunere paralelă.

Produsele de categorie, dacă ne putem exprima astfel, realizează sincronizarea reciprocă de-odată în întregime, ceea ce într-o serie de cazuri nu este admis. De aceea obiectivul sincronizării reciproce trebuie să se soluționeze în genere în două etape. În prima etapă se construiește produsul de categorie corespunzător, care, în afară de condiții cerute pentru sincronizare, va include și elemente „nedorite”. În a doua etapă se determină morfismul de tipul proiecției, care evidențiază rețeaua căutată, ce are toate proprietățile cerute.

Dezvoltarea ulterioară a abordărilor rezolvării obiectivelor sincronizării este legată de astfel de construcții de categorie ca egalizatorul și coegalizatorul. Să analizăm construcția egalizatorului în categoria ANP , în care obiecte sînt rețelele algebrice cu una și aceeași mulțime de locații. În general egalizator i în categoria arbitrară R pentru morfismele f, g: se numește morfismul , care este astfel, încît:

1)

2) pentru oricare morfism , ce satisface egalitatea există un unic morfism , care este astfel, încît

Categoria rețelelor algebrice

G0 G1

Des. 3.6. Informații ale cercetării interacțiunii rețelelor N0 și N1 pentru cercetarea imaginilor grafurilor dependențelor

În categoria ANP construcția egalizătorului se transformă în felul următor:

Definiția 3.9. Morfismul în categoria ANP se numește egalizatorul perechii de morfisme , dacă:

1) , adică oricare marcare inițială M0 în rețeaua N0 , raportată la rețeaua N2, va duce unul și același comportament dinamic, independent de morfismul ce raportează sau ;

2) Pentru orice morfism care satisface există un unic morfism h0, care este astfel încît , adică morfismul h0 va fi aplicație.

Din punct de vedere practic noțiunea de egalizator permite să se cerceteze comportamentul dinamic al rețelei algebrice la diferite marcări inițiale pe baza analizei proprietăților morfismelor concrete din rețeaua fixată. Aici se distinge destul de clar analogia cu metoda comparării în teoria sistemelor care oferă posibilitatea de a deduce concluziii asupra sistemului complex după caracteristici separate, obținute pe baza analizei modelului simplificat.

Noțiunea duală la egalizator o reprezintă noțiunea de coegalizator.

Definiția 3.10. Morfismul în categoria ANP se numește coegalizatorul perechii de morfisme , dacă:

1) , adică oricare marcare inițială M1 în rețeaua N1, raportată la rețeaua N2, prin intermediul a două morfisme diferite, g și f, readresat în rețeaua N0 din N2 prin morfismul Q, în ambele cazuri va duce la unul și același comportament dinamic al rețelei N0;

2) Pentru orice morfism care satisface există un unic morfism h0, care este astfel încît , adică morfismul h0 va fi aplicație.

Să analizăm acum pe scurt legătura între caegoria de rețele algebrice și categoria de grafuri ale depenedențelor. Grafurile dependențelor au fost introduse pentru reprezentarea mulțimii tuturor variantelor admise ale descrierii declanșării tranzițiilor în rețeaua algebrică la o temă fixată. Mulțimea indicată [t], numită urmă, este clasa de echivalență a monoidul factor , unde este monoidul liber dat pe mulțimea de tranziții T ale rețelei algebrice; este congruența determinată de nedependența tranzițiilor.

Fiecărui comportament dinamic al rețelei algebrice îi corespunde o oarecare urmă [t], legat univoc de graful depedențelor. Prin urmare, dacă în categoria AN se fixează două obiecte, N0, N1, iar morfismele de cuprindere , atunci pentru toate perechile de grafuri ale dependențelor urmelor [t0] și [t1], care descriu comportamentl dinamic al rețelei N0 și comportamentul dinamic al rețelei N1, indus de morfismul r, se poate stabili morfismul corespunzător. Construirea categoriei corespunzătoare de grafuri ale dependențelor, în care asemenea morfisme s-ar determina univoc, se poate realiza în cadrul categoriei de grafuri, propusă de B.V. Stepanov.

Ce apare nou la realizarea acestei construcții referitor la obiectivele sincronizării și în întregime pentru analiza comportamentului sistemelor modelate de rețele? Din des. 3.6. se vede că studierea influenței rețelei N0 asupra N1 se poate realiza prin cercetarea homomorfismului corespunzător în categoria grafurilor dependențelor cu transformarea ulterioară a rezultatelor obținute în categoria rețelelor algebrice.

Capitolul 4

RETELE PETRI STOCHASTICE SI FUZZY

4.1. Modele de prognozare a comportamentului proceselor

în condiții de nedeterminare

Una dintre problemele actuale ale teoriei generale a sistemelor o constituie elaborarea metodelor de cercetare a dinamicii funcționării sistemelor complexe în condiții de nedeterminare. Greutățile legate de soluționarea acestei probleme sînt condiționate de o serie întreagă de factori, între care trebuie să evidențiem:

prezența unui număr mare de subsisteme (elemente) interconexate cu raporturi de structurale și funcționale complexe între ele;

vitalitatea diferitelor subsisteme nu are caracter de sine stătător și este condiționată de locul ei în sistem;

funcționarea unor subsisteme (elemente) se face asincron, regulile interacțiunii lor se descriu cu condiții logice complexe;

nedeterminarea comportamentului unor subsisteme (elemente) poate avea atît caracter probabil, cît și neclar.

Condițiile indicate au necesitat elaborarea unei abordări calitativ noi a modelării comportamentului sistemelor și proceselor în condiții de nedeterminare. Baza pentru o asemenea abordare au consituit-o construcțiile rețelelor Petri și dezvoltarea ulterioară a rețelelor algebrice, care permit să se descrie cu precizie dată procesle asincrone ce interacționează. Totuși, aducerea, ca element nou, a nedeterminării în construcții de rețele, necesită cercetarea căilor de generalizare a rețelelor Petri.

Una din posibilele generalizări ale rețelelor Petri este legată de realizarea în ele a proprietăților complementare, care permit să se descrie nedeterminarea comportamentului sistemelor în procesul funcționării lor. Aici pot fi propuse două abordări. Prima este legată de descrierea nedeterminăriii declanșării tranzițiilor aflate în stare de conflict. Totodată mulțimea șirurilor permise ale tranzițiilor de felul este numărul tranziției declanșabile, se consideră ca grup complet de evenimente și fiecărui element al mulțimii i se atribuie o oarecare probabilitate. Construcția obținută se cercetează mai apoi cu ajutorul metodelor teoriei automatelor probabile. Neajunsul principal al acestei abordări este legat de necesitatea analizei unui număr mare de elemente ale mulțimii șirurilor permise ale tranzițiilor și creșterea lor bruscă la extinderea rețelei.

A doua abordare are în vedere nedeterminarea numărului de jetoane în locațiile rețelei. Și deoarece locațiile rețelei modelează stările diferitelor elemente ale sistemului, numărul jetoanelor în toate locațiile determină starea globală a sistemului. Totodată este important de subliniat că nedeterminarea jetoanelor în locații poate fi descrisă atît de pe locații probabile, cît și de pe locațiile teoriei mulțimilor fuzzy. Împrejurarea dată permite ca în procesul modelării funcționării sistemelor să se utilizeze mai deplin informația obținută pe cale expertă.

4.2. Analiza proceselor prin intermediul rețelelor Petri stochastice

Să definim rețeaua Petri stochastică. În definirea rețelei Petri marcate este prezentă aplicația , care atribuie fiecărei locații un anumit număr de jetoane . Să înlocuim această aplicație, lucru pentru care introducem mulțimea vectorilor cu componente, ale căror valori aparțin intervalului [0, 1], și suma componentelor fiecărui vector este egală cu unitatea, adică

Elementele mulțimii vor determina repartizarea probabilităților prezenței jetoanelor în locațiile rețelei, totodată numărul componentei corespunde cu numărul de jetoane, iar valoarea însăși a componentei este egală cu probabilitatea aflării acestui număr de jetoane în locație.

Definiția 4.1. Rețea Petri stohastică se numește perechea , unde descrie structura rețelei, iar aplicația atribuie fiecărei locații vectorul repartizării probabilităților prezenței jetoanelor .

Ca și în rețelele Petri obișnuite, în rețelele stochastice la declanșarea tranzițiilor are loc procesul redistribuirii jetoanelor, care se reflectă în modificarea vectorilor distribuirii probabilităților prezenței jetoanelor în locații. Pentru simplitatea expunerii, vectorii indicați vor fi denumiți în continuare vectori ai probabilităților. Să determinăm regula permiterii tranziției.

Definiția 4.2. Tranziția în rețeaua stohastică este permisă, dacă vectorul probabilităților fiecărei locații de intrare a acestei tranziții are o componentă, care nu este egală cu zero, cu un număr egal sau mai mare decît numărul arcelor ce leagă locația respectivă cu tranziția, adică

(4.1)

Înainte de a determina regula modificării marcării la declanșarea tranziției, să introducem noțiunea de vector al diagonalei reduse al matricei lui Gram a doi vectori. Fie dați doi vectori,

unde indicele este semnul de transpunere. Matricea lui Gram a vectorilor a și b se numește matricea de următoarea formă:

.

Diagonala redusă a matricei lui Gram a vectorilor a și b se numește vectorul al cărui componente sînt egale cu suma elementelor dispuse pe o line simetrică față de diagonala principală, adică

Vectorul diagonalei reduse are următoarele proprietăți:

1) – comutativitate;

2) – asociativitate;

3) dacă atunci – normalitate.

Să analizăm regula modificării marcării la declanșarea tranziției. Valoarea – simbolizează marcarea locației pînă la declanșarea tranziției , iar – după declanșarea tranziției . La declanșarea tranziției dimensiunea vectorului probabilităților în fiecare locație de intrare se micșorează cu valoarea . Totodată componenta zero a vectorului este egală cu suma componentelor vectorului cu componenta zero pînă la numărul , iar valorile celorlalte componente ale vectorului se egalează cu componentele cu un număr mai mare cu aceiași valoare,

(4.2)

Desen 4.1. Exemplu de rețea.

La rîndul său vectorul probabilităților în fiecare locație de ieșire după declanșarea tranziției este egal cu vectorul diagonalei reduse a vectorului inițial și a vectorului r,

(4.3)

Expresia (4.3) este obținută cu condiția . Cazul se va analiza mai jos.

Exemplul 4.1. Să analizăm acțiunea regulei modificării marcării la declanșarea tranziției pe exemplul rețelei prezentate pe des. 4.1.

Des. 4.2. Rețea cu două locații de intrare.

Marcarea inițială arată, că tranziția este permisă, întrucît componentele a doua și a treia ale vectorului sînt mai mari decît zero,

.

După declanșarea tranziției obținem o nouă marcare , la care

.

Însumarea are loc pînă la a doua componentă, întrucît . Mai departe

.

În felul acesta vectorul are aspectul

.

Marcarea locației de ieșire a tranziției este egală cu vectorul diagonalei reduse a vectorului și a vectorului , unde

În mod definitiv: . Să determinăm matricea lui Gram a vectorului și r.

Să găsim vectorul diagonalei reduse a matricei :

În felul acesta, marcarea locației după declanșarea tranziției

Să analizăm acum cazul, cînd mulțimea locațiilor de intrare al tranziției constă din mai mult de un element. Fără a diminua unitatea raționamentului, se poate admite, că (des. 4.2.). Aici totul rămîne consecvent celor expuse anterior, cu excepția regulei calculării componentei a vectorului r, în cazul dat

, (4.4)

unde

Regula indicată are următoarea interpretare fizică. Întrucît cantitatea necesară de jetoane pentru declanșarea tranziției vine din locația cu probabilitatea egală cu suma componentelor vectorului cu numere mai mari decît valoarea , iar din locația – cu o probabilitate egală cu suma componentelor vectorului cu numerele mai mari decît valoarea , atunci probabilitatea declanșării tranziției și a distribuirii jetoanelor în locația este egală cu produsul acestor probabilități.

Exemplul 4.2. Structura rețelei este prezentată în des. 4.2. Marcarea inițială

Tranziția este permisă, întrucît

După declanșarea tranziției marcarea locațiilor și are aspectul

Să determinăm vectorul r:

Aflăm matricea lui Gram a vectorului și r:

Marcarea locației după declanșarea tranzițiilor va fi

.

În felul acesta regulile prezentate de pregătire și declanșare a tranzițiilor descriu complet procesul funcționării rețelelor Petri stochastice. Ca urmare este obținut pentru fiecare locație a rețelei un vector de distribuire a probabilităților prezenței jetoanelor, care deja la rîndul lor se trasează în conformitate cu interpretarea rețelei concrete.

4.3. Rețele fuzzy în scopul descrierii proceselor

Să definim rețelele Petri fuzzy bazîndu-ne pe rezultatele existente la rețelele stochastice. Fie – submulțimi ale numerelor pozitive întregi (admitem, că ). Determinăm pe R mulțimea fuzzy , iar funcția de apartenență . Valoarea se numește grad de apartenență a elementului r la mulțimea fuzzy v [16]. Dacă R reprezintă mulțimea numerelor succesive începînd de la zero, atunci v se poate compune sub forma vectorului:

.

Să introducem mulțimea vectorilor , elementele căreia reprezintă vectorul de fond de tipul v analizat mai sus. Dacă acum se presupune, că elementele mulțimii determină distribuirea gradelor de apartenență a jetoanelor la locațiile rețelei Petri, atunci următoarea definiție este firească.

Definiția 4.3. Rețea Petri fuzzy se numește perechea , unde descrie structura rețelei, în aplicația atribuie structurei fiecărei locații vectorul distribuirii gradelor de apartenență a jetoanelor la locația .

Trebuie remarcat că deosebirea de principiu a marcării în rețelele fuzzy față de marcarea din rețelele stochastice constă într-aceea, că suma componentelor oricărui vector de distribuție a gradelor de apartenență a jetoanelor poate fi diferită de unitate. Totodată, din punct de vedere al structurii, marcarea este de același tip în ambele clase. Aceasta dă motiv să considerăm că regula permiterii tranzițiilor în rețelele fuzzy este analoagă cu regula din rețelele stochastice (vezi (4.1.)),

Anterior, la determinarea vectorului diagonalei reduse a matricei lui Gram a doi vectori, s-a arătat că componentele vectorilor (matricei) aparțin cîmpului numerelor reale, iar obișnuitele operații de înmulțire și adunare sînt legi de compoziții pe ele. La determinarea însă a matricei lui Grama vectorilor de distribuire a gradelor de apartenență și a vectorului ei de diagonală redusă, componentele vectorilor, ca și mai înainte, aparțin cîmpului de numere reale, însă legile compunerii sînt altele: înmulțirea este înlocuită prin operația minimului a două numere, iar operația de adunare – prin operația maximului a două numere, Dacă reprezentăm operația maximului prin semnul , iar cea a minimului prin , atunci matricea lui Gram a vectorilor a și b și vectorul ei de diagonală redusă dobîndește aspectul:

,

Totodată, proprietățile de asociativitate și comutative a vectorului diagonalei reduse se păstrează.

Să trecem acum la analiza regulei de declanșare. La pdeclanșarea tranziției dimensiunea vectorului de distribuție a gradelor în fiecare locație de intrare se micșorează cu valoarea . Componenta zero a vectorului este egală cu valoarea maximă între componentele vectorului cu numere de la zero la , iar valorile celorlalte componente se consideră egale cu componentele vectorului cu un număr mai mare cu valoarea ,

(4.5)

Vectorul distribuirii gradelor de apartenență a jetoanelor la locația de ieșire a tranziției este egal, după declanșarea ei, cu vectorul diagonalei reduse a vectorului inițial , și vectorul , unde . La determinarea analizăm două cazuri:

a)

(4.6)

b)

(4.7)

Să explicăm sensul expresiei (4.7). Componenta cu valoarea cea mai mare după indicele la i fixat caracterizează nedeterminarea prezenței cantității de jetoane în locația de intrare necesar pentru declanșarea tranziției . Alegerea valorii celei mai mici după indicele i între gradele cele mai mare de apartenență după indexul caracterizează nedeterminarea declanșării tranziției și eliberarea jetoanelor în locațiile de ieșire.

Exemplul 4.3 Să analizăm rețeaua Petri fuzzy cu datele inițiale ale exemplului 4.1., considerînd că valorile numerice aparțin vectorilor și .

Întrucît regula permiterii tranziției în rețeaua fuzzy este similară cu (4.1), atunci tranziția este gata de declanșare. După declanșarea tranziției obținem o nouă marcare la care

Numărul componentelor în vectorul s-a micșorat pînă la două, întrucît ,

Numărul componentelor în vectorul este egal cu vectorul diagonalei reduse a matricei lui Gram a vectorului și a vectorului , unde ; Locația de intrare pentru tranziția t este unică, de aceea operația luării minimului lipsește. În final vectorul are aspectul: .

Să determinăm matricea lui Gram a vectorilor și :

Să aflăm vectorul diagonalei reduse a matricei :

care este egal cu vectorul .

Exemplul 4.4 Structura rețelei Petri fuzzy este prezentată pe des. 4.2., datele inițiale pentru vectorii , și după valorile numerice sînt luate din exemplul 4.2.

Tranziția este permisă. După declanșarea tranziției marcarea locațiilor și

Să determinăm vectorul :

Să determinăm matricea lui Grama a vectorilor și :

Marcarea locației după declanșarea tranziției va fi

.

Astfel s-a analizat una din căile posibile de construire a rețelelor Petri fuzzy și stochastice. Trebuie subliniat îndeosebi faptul că alegerea unui model sau a altuia de rețele pentru descrirea unui sistem concret real trebuie să se bazeze pe o analiză strictă a întregii informații existente, întrucît chiar valorile numerice identice în datele inițiale duc la diverse rezultate în modelul stochastic și cel fuzzy, lucru ilustrat de exemplele 4.1 – 4.4, astfel

4.4. Stochastica și neexactitatea în rețelele algebrice

Toate noțiunile și simbolurile date mai jos, ale rețelelor Petri algebrice corespund deplin noțiunilor și simbolurilor prezentate în cap.1. La construirea rețelelor Petri stohastice algebrice, ca și anterior, este aleasă o abordare ce constă din suprapunerea structurii de probabilitate pe marcarea rețelei. În rețelele algebrice marcarea se prezintă ca vector de dimensiunea

unde pe primele locuri m se găsesc marcările locațiilor de tip f și pe locurile de la la – marcările locațiilor de tipul p. Pentru a evita blocarea în rețea vom considera, că pentru fiecare locație mulțimea cuvintelor, ce marchează arcele ei de ieșire, formează codul

.

Factorizăm cuvintele după elementele codului ,

,

și raportăm fiecărui valoarea din partea [0,1], care este egală cu probabilitatea pătrunderii subcuvîntului în cuvîntul; să notăm această probabilitate .

Definiția 4.4. Rețea Petri algebrică stochastică se numește sistemul

unde este mulțimea finită a locațiilor de tip p; este mulțimea finită a locațiilor de tipul f; este mulțimea finită a tranzițiilor; A este alfabetul finit;

este aplicația ce marchează arcele care leagă tranzițiile de locații și pozițiile de tranziții, A este monoidul liber asupra lui A;

este marcarea inițială a locațiilor cu cuvinte din A ,

În felul acesta marcarea inițială pentru fiecare locație și (bineînțeles, marcările ulterioare) se prezintă prin perechea

(4.8)

Regula permiterii tranzițiilor și a declanșării tranzițiilor în rețelele Petri algebrice stochastice este similară regulei din rețelele algebrice simple și se determină prin primul element al perechea (4.8). Declanșarea tranziției t, permisă pentru marcarea va duce la o nouă marcare, , totodată primul element al perechea se determină într-un mod obișnuit pentru rețelele algebrice, iar al doilea se calculează după formula

, (4.9)

adică la declanșarea tranziției t, la cuvîntul din dreapta se adaugă factorul și probabilitatea ce îi corespunde . Procesul de funcționare a rețelei, arătat mai sus, va fi determinat univoc doar în cazul, cînd codul de ieșire pentru fiecare locație constă din elemente ale codului de intrare. De aceea, este necesar să se finalizeze determinarea regulei calculării probabilității la prezența în codul a elementelor ce nu aparțin codului . Din cap.2 se știe, că, codul se poate obține din codul doar cu ajutorul operațiilor de combinare și descompunere a elementelor sale. Să analizăm succesiv variantele posibile ale obținerii codului .

1. Codul este obținut din codul doar cu ajutorul operației de descompunere, adică

În acest caz, în absența unei informații suplimentare asupra parametrilor probabili este bine să considerăm că (4.10)

2. Codul este obținut din codul doar cu ajutorul operației de combinare, adică

În acest caz este evident, că

. (4.11)

Combinînd prima și a doua variantă, epuizăm întreaga mulțime de coduri admise, care se pot obține din codul .

Astfel, la valorile date ale probabilității pentru fiecare subcuvînt din , expresiile (4.10), (4.11) permit să se determine valorile , la declanșarea oricărei tranziții .

Exemplul 4.5. Să analizăm rețeaua algebrică stochastică prezentată pe des. 4.3.

Tranziția este permisă. După declanșarea ei obținem

.

Valoarea este determinată dacă utilizăm expresia (4.9).

Exemplul 4.6. Să analizăm rețeaua mai complexă reprezentată pe des. 4.4.

Să descriem marcarea inițială a locațiilor

.

La marcarea este permisă doar tranziția , declanșarea ei duce la modificarea în conținut a locațiilor și :

Marcarea permite tranziția , declanșarea ei modifică conținutul locațiilor și :

Calcularea și s-a realizat după formula (4.10).

Marcarea permite tranziția , declanșarea ei modifică conținutul locațiilor și :

întrucît conform expresiei (4.11),

conform expresiilor (4.9) și (4.10).

În felul acesta s-a construit una din posibilele variante ale rețelelor Petri algebrice stochatice. Indiferent de simplitatea concepțiilor propuse, rețelele algebrice stochastice dețin puternice posibilități modelatoare.

Observație. În mod similar se pot determina rețelele algebrice fuzzy. După structura descrierii ele corespund total rețelelor algebrice stochastice. Asemănarea în descriere se explică aici prin suprapunerea nedeterminării probabile sau neexacte pe structura cuvintelor în locații, care sînt legate rigid și univoc de structura monoidului liber ce marchează arcele și conținutul locațiilor. De aceea din punct de vedere formal deosebirea constă în modificarea formulelor (4.9) și (4.11), care în conformitate cu legile neprecise ale compoziției iau aspectul:

(4.12)

. (4.13)

În expresiile (4.12), (4.13) definește gradul de apartenență a cuvîntului M. Algoritmul funcționării rețelelor algebrice fuzzy nu se deosebește de algoritmul rețelelor algebrice stochastice, de aceea nu se descrie.

Capitolul 5

REȚELELE PETRI ÎN OBIECTIVELE CONDUCERII PROCESELOR TEHNOLOGICE ALE SISTEMELOR FLEXIBILE DE PRODUCȚIE

5.1. Particularitățile proceselor de conducere a SFP

Sistemele flexibile de producție (SFP) sînt complexe ce includ utilaje tehnologice comandate prin program, mijloace moderne ale tehnicii de calcul pentru comandă, precum și mijloace de automatizare a lucrărilor de proiectare-construcții, tehnologice și de producție planificată. Sistemul ce unește aceste resurse într-un întreg și care determină prin aceasta caracterul și calitatea întregului SFP, este sistemul său de comandă (SC).

În cel mai general aspect funcționarea SC a SFP corespunde schemei sistemului clasic de comandă. Pe baza informației de intrare în conformitate cu tema de producție, a informației apriorice despre starea inițială a complexului comenzii, precum și a informației despre starea curentă a complexului se elaborează acțiunile de comandă sub forma comenzilor către toate elementele complexului tehnologic SFP. Comenzile inițiază îndeplinirea operațiilor tehnologice de bază și auxiliare, și ca urmare se modifică starea complexului: componentele fluxului material în SFP se amestecă după complexul tehnologic automatizat (CTA), piesele cerute se transformă în semifabricate, iar semifabricatele – în piese finite. Datele despre starea elementelor CTA (statutele elementelor CTA) reprezintă o informație de legătură imensă, destinată controlului și corectării operative a stării obiectului comenzii.

Experiența creării arată utilitatea prezentării ierarhice pe trei nivele a structurii SC a SFP, ce reflectă structura funcțională a întregului sistem de producție. Totodată se evidențiază următoarele nivele ale ierarhiei SC a SFP: nivelul de comandă a unui utilaj tehnologic separat SFP, a sistemelor sale de execuție, agregatelor și a totalității acestora; nivelul de comandă a grupurilor de utilaje tehnologice, a celulelor specializate automate SFP; nivelul conducerii operative SFP (a unui sector sau atelier). Fiecărui nivel SC a SFP îi corespunde o anumită mulțime de obiective, iar selectarea lor și conținutul de bază sînt automatizate de comandă a proceselor tehnologice, SC a SFP fiind o subclasă a lor, rămîn practic fără modificări 10-15 ani.

Indiferent de simplitatea și tradiționalismul analizei generale a proceselor în SC a SFP, elaborarea concretă a acestor sisteme se lovește de o serie întreagă de greutăți esențiale, condiționate de următoarele particularitți SFP:

structura CTA a SFP se concretizează printr-o mare diversitate de elemente, utilaje tehnologice și legături, care sînt determinate de mulțimea proceselor tehnologice ce se îndeplinesc;

există un număr mare de variante alternative de utilaje, operații tehnologice și itinerarii de prelucrae a pieselor, ce servesc ca bază a flexibilității sistemului de producție;

proceselor de comandă în SFP le sînt proprii repartizarea, paralelismul, asincronismul și o dinamică înaltă, ce se determină prin proprietățile corespunzătoare CTA a SFP;

comanda SFP este legată de prelucrarea unor volume considerabile de informație, ce vine de la obiectul de comandă și de la sistemele de automatizare, exterioare în raport cu SC a SFP.

Aceste particularități își pun amprenta în mod inevitabil asupra conținutului sarcinilor de conducere SFP. Să ne oprim mai amănunțit la analiza lor. Primul nivel, cel mai de jos al sistemului, strîns legat de componentele CTA a SFP, este nivelul conducerii locale a utilajului tehnologic. La acest nivel se realizează conducerea utilajului CTA cu ajutorul sistemelor incorporate ale conducerii de program la o gamă fixată de funcții realizabile ale conducerii diferitelor mecanisme ale utilajului. Problemele realizării acestui nivel de comandă au început să fie analizate în anii ’60 iar la ora actuală sînt cele mai studiate. Într-o literatură vastă, dedicată sistemelor locale de conducere a utilajelor, se descrie un număr mare de sisteme, produse industriale, ale acestei clase.

Specific pentru SC a SFP este complexarea diferitelor sisteme locale de conducere pe baza unei rețele informaționale unice, care la rîndul ei este o subrețea a rețelei locale de calcul SFP. Cu ajutorul acestei rețele dispozitivele de conducere a utilajelor tehnologice și nivelele mai înalte ale SC a SFP fac schimb de informații funcționale (programe de prelucrare, date despre deplasarea mijloacelor de transport, a roboților, statute al utilajelor și altele) și de informații de conducere, legate de pornirea și oprirea utilajului, schimbul regimurilor îndeplinirii operațiilor ș.a.

Următorul nivel al SC a SFP, al doilea, este destinat pentru translația temelor, pentru îndeplinirea operațiilor tehnologice imediate, în comenzi de conducere pentru unități concrete CTA din grupe de utilaje asemănătoare din punct de vedere funcțional sau în succesiunea comenzilor de conducere a utilajelor de celule automate specializate. La acest nivel problemele de bază sînt acelea ale repartizării ordinii de succesiune a comenzilor tehnologice. În cazul prelucrării mecanice se evidențiază trei clase de operații ce se analizează: principale, operații de prelucrare; ajutătoare, în principal operații de transport; operații de control-măsurare. Numărul limitat de elemente în grupele utilajelor interschimbabile sau în celulele SFP, ce constau din cîteva unități de utilaj, precum și tema rigidă și determinarea totală a sarcinilor ce se rezolvă, dau posibilitatea unei realizări relativ simple a conducerii la acest nivel SC a SFP.

În sfîrșit, al treilea nivel al SC a SFP servește pentru rezolvarea sarcinilor planificării operative (calendaristice) și pentru dispecerizarea SFP. Acest nivel determină în mare măsură calitatea conducerii în sistemele de producție. Astfel, pierderile de timp la funcționarea SFP, legate de greșeli logice, aduse la rezolvarea sarcinilor acestui nivel, constituie 75% din pierderile totale, ceea ce crește cu un ordin pierderile de timp legate de alte cauze. Informația inițială pentru rezolvarea sarcinilor acestui nivel vine pe rețeaua SC a SFP și include informația despre planul de volum, procesele tehnologice, datele nomenclatorului, include comenzi despre începutul sau schimbul regimurilor de funcționare SC a SFP, precum și date ce vin de la nivelele de jos ale sistemului de comandă, despre starea CTA a SFP, operațiile tehnologice ce se îndeplinesc și despre resursele existente. Rezolvări generale pentru asemenea sarcini, datorită importanței lor practice și posibilității formulării matematice precise, îi este dedicat un număr mare de cercetări, însă influența esențială a specificului SFP asupra modelelor și procedurilor planificării operative face practic imposibilă transferarea nemijlocită în domeniul SFP a experienței înmagazinate despre rezolvarea unor asemenea obiective. Itinerarele obținute prin metode tradiționale, de regulă, necesită ipoteze esențiale, ce reduc precizia rezultatelor planificării. În caz contrar întocmirea lor necesită rezolvarea unei oarecare obiective combinatoare de timp sau resurse de calcul.

Greutățile de principiu ale elaborării apriorice a logicii funcționării SFP în regim off-line cresc importanța pentru conducerea SFP a rezolvării sarcinii de conducere de dispecer, ce constă în organizarea în timp real (on-line), pe baza doar a informației curente necesare despre CTA a SFP, a îndeplinirii temei de producție. Totodată se rezolvă problemele destinației operațiilor tehnologice la utilajele CTA a SFP ale verificării condițiilor începerii rezolvării operațiilor, elaborării comenzilor pentru pornirea operațiilor, a urmăririi procesului realizării lor.

Pe baza scurtei analize efectuate se pot evidenția trăsăturile de bază SC a SFP, ce determină particularitățile conducerii în astfel de producții flexibile. Aceste trăsături constau în următoarele:

structura SC a SFP se prezintă sub forma unui sistem ierarhic pe trei nivele, ce include nivele conducerii operative, de grup și locale;

rezolvarea sarcinilor conducerii operative, comune pentru sistemele automatizate de conducere a proceselor tehnologice, în condițiile SFP se ciocnește cu o serie de greutăți de principiu, condiționate de complexitatea funcțională și de structură CTA a SFP, distribuția, paralelismul, asincronismul și dinamismul proceselor de conducere;

un rol esențial în conducerea SFP o au sistemele conducerii de dispecerat (SCD) SFP, care realizează concordanța și coordonarea funcționării grupelor de utilaje.

5.2. Conducerea situțională de dispecerat SFP

Obiectivul conducerii de dispecer, după cum s-a arătat la 5.1., este importantă și caracteristică pentru conducerea SFP. Să ne oprim mai în amănunt asupra analizei proceselor în sistemele conducerii de dispecer, ale căror complexitate de structură și funcțională condiționează necesitatea utilizării unor modele și metode de conducere specifice. Obiectul analizei îl constituie sistemul de producție, care este o producție discretă, a cărei funcționare este împărțită în operații separate, ce se îndeplinesc de către anumite utilaje în succesiunile date de procesele tehnologice. Tipurile de procese tehnologice, realizate în răstimpul planificat, și numărul lor se determină prin tema de producție, a cărei îndeplinire, prin mijloacele utilajelor de bază și auxiliare, constituie scopul global al funcționării SFP.

SFP include un oarecare număr de module flexibile de producție (MFP), unite într-un întreg cu ajutorul sistemului automatizat de transport-depozitare (SATD) și care reprezintă unitatea de producție atomică, destinată pentru îndeplinirea diferitelor operații asupra reperului [piesei]. După tipurile operațiilor îndeplinite MFP, de regulă, se subîmpart în module de prelucrare, de măsurare și de poziționare. În componența MFP de prelucrare pot intra una sau mai multe mașini [unelte] cu comandă numerică de program (CMP) sau centre de prelucrare și unul sau mai mulți roboți industriali. MFP utilizat pentru control și măsurări, include utilajul necesar, care este de asemenea dotat cu dispozitive CNP. MFP de poziționare realizează poziționarea rezervelor de repere, piese brute și scule necesare pentru începerea operațiilor de prelucrare și control-măsurare. Fiecare modul de producție are un oarecare complet de stocare tampon de intrare, de la care vin resursele pentru îndeplinirea operațiilor, și de ieșire, unde se transmit rezultatele efectuării lor.

SATD servește pentru păstrarea și transportarea obiectelor fluxului material (OFM), în care, în SFP, intră piesele brute, semifabricatele, sculele, accesoriile, completele de scule, paletele cu piese brute etc. SATD include unul sau mai multe depozite și stocatoare automate, numărul necesar de roboți industriali și transportul automat. Toate MFP și SATD au sistemele lor de conducere, care realizează coordonarea și sincronizarea funcționării utilajelor ce intră în ele. Aceste sisteme de conducere corespund sistemelor conducerii de grup (SCG) a SFP.

Vom considera, că SCG a SFP asigură conducerea utilajelor MFP, suficientă pentru efectuarea unei piese-operație. Prin piesă-operație vom înțelege totalitatea operațiilor de prelucrare, care se efectuaează asupra unui anumit obiect al fluxului material (piesă brută sau semifabricat) sub comanda unui program de lucru CNP. Totodată, pentru realizarea unei piese-operație SCG a MFP trebuie să aibă un program CNP de lucru ce îi corespunde, pe stocatoarele de intrare ale modului ce trebuie să găsească OFM necesare, iar stocatoarele de ieșire trebuie să fie libere.

În ceea ce privește sistemul conducerii de grup SATD, acesta trebuie să asigure coordonarea și sincronizarea funcționării depozitelor automatizate (DA) și a transportului automatizat (TA), necesare pentru deplasarea OFM de la stocatoarele de intrare pînă la cele de ieșire MFP și între acestea și celulele DA. Este posibilă și o organizare SFP oarecum deschisă, la care nu se creează SCG a SATD, iar sarcinile coordonării activității utilajelor ajutătoare ale sectorulului (DA, TA) sînt atribuite SCD a SFP.

Scopul global al funcționării SFP, după cum s-a arătat deja, este legat de îndeplinirea într-un anume răstimp a setului dat de procese tehnologice, care sînt o mulțime parțial ordonată de piese-operație de bază (PO). Efectuarea PO de bază este inevitabil legată de realizarea operațiilor tehnologice ajutătoare, destinate pentru furnizarea resurselor necesare către PO de bază, controlul calității efectuării principalelor PO, pregătirea obiectelor fluxului materiale ș.a.

Operațiile ajutătoare este bine să se împartă în două clase. În prima clasă intră operațiile ajutătoare, efectuate asupra unor anume OFM sub conducerea SCG MFP corespunzătoare după programe de lucru CNP (de control-măsurare, pregătitoare). Din punct de vedere SCD ele sînt în totalitate analize cu TO principale, și în legătură cu acest lucru vom considera, că informația despre acestei clase de TO ajutătoare este conținută, alături de informația despre TO principale, în descrierile temei de producție pentru îndeplinirea TO.

A doua clasă de operații ajutătoare sînt constituite din operațiile legate de deplasarea OFM. Ele se efectuează prin utliaje de transport sub conducerea SCG, de regulă, cu programe universale, ce nu depind de tipul OFM. În legătură cu aceasta este utilă o analiză separată a respectivelor operații ajutătoare și scoaterea lor într-o clasă separată de operații – al operațiilor de transport (OT).

Toate unitățile sau grupele de utilaj, ce au sisteme proprii de comandă, ce interacționează cu SCD SFP și destinate îndeplinirii temei de producție, le vom denumi obiecte ale complexului tehnologic (OCT). Exemple OCT SFP sînt MFP, sistemul de transport-depozitare complet automatizat și (sau) DA ce îl compun, cărucioare automate de transport, roboți industriali.

Toate locurile din complexul de prelucrare mecanică, unde, cu ajutorul SATD sau al utilajelor ajutătoare, se pot instala sau de unde se pot retrage obiectele, le vom denumi poziții de transport (PT). Exemple de PT sînt stocatoarele MFP de intrare și ieșire, celulele depozitatelor, stațiile de încărcare și descărcare DA și TA. În unele cazuri noțiunea de PT poate fi extinsă și, în acest caz, pozițiilor le vor corespunde secțiunile magistralelor transportării OFM, evidențiate din punct de vedere al procesului de dispecerizare (PT ale instalației, evidenței OFM ș.a.).

Să introducem simbolizările: – mulțimea piesăoperațiilor de bază și ajutătoare; – mulțimea OT; – mulțimea OCT; – mulțimea OFM; – mulțimea PT; – numărul elementelor mulțimilor. Grupul acestor mulțimi , după cum urmează din analiza efectuată, reprezintă un model SFP, analizat drept obiect de dispecerizare.

Activitatea SCD SFP se construiește pe baza informației apriorice și curente despre SFP. Această informație conține date despre repartizarea obiectelor în toate PT, despre lista PO, efectuate de către fiecare obiect al complexului tehnologic, precum și condițiile efectuării și lista OCT pentru OT SFP. Pe baza ei SCD trebuie să elaboreze comunicările informaționale de comandă (influențe de comandă) către toate OCT. Comunicările informaționale SCD inițiază efectuarea cu obiecte a operațiilor de bază și ajutătoare, și drept urmare se modifică starea complexului tehnologic: obiectele se deplasează pe poziții, piesele brute se transformă în semifabricate, iar semifabricatele – în piese finite, ceea ce se reflectă în informația de lucru despre procesul dispecerizării. Un rol determinativ îl joacă în activitatea SCD conținutul temei de producție, transmisă de la nivelele de sus ale planificării producției.

Conducerea SFP, ce se referă după cum s-a arătat anterior, la producțiile de tip discret, este legată de necesitatea evidenței unui număr mare de limitări și criterii de conducere, a varietății tipurlor de utilaje, itinerariilor prelucrării și nomenclatorului pieselor produse. În afară de aceasta, funcționarea SFP se desfășoară în condiții de pierderi și refuzuri ale utilajelor, avateri de la valorile cerute ale proprietăților OFM, rămîneri în urmă în timp de la graficul funcționării SFP, pierturbări ale succesiunilor de plan pentru prelucrarea reperelor. Toate acestea fac necesară analiza conducerii SFP pe mulțimea discretă a situațiilor, în genere nedependente, cu utilizarea obligatorie a modelelor și metodelor speciale, ce permit reducerea complexității procesului prelucrării situațiilor. O asemenea analiză este caracteristică mai mult pentru sistemele de producție la luări de decizii, decît pentru sistemele de conducere, deși în ultimul timp ea și-a găsit aplicarea și la conducerea sistemelor complexe, între care și tehnice.

Înainte de a analiza modelele concrete și algoritmice dispecerizării, să analizăm specificul procesului conducerii situaționale de dispecer SFP și să evidențiem succesiunea sarcinilor necesare pentru funcționarea eficientă a sistemului. Folosind terminologia abordării situaționale, se poate considera, că starea concretă a obiectelor CTA SFP, prezența și repartizarea obiectelor pe poziții, precum și reflectarea tuturor acestor lucruri în date corespunzătoare determină prezența în SCD SFP a unei oarecare situații. Stările tuturor obiectelor CTA, prevăzute la elaborarea sistemului și admise din punct de vedere al mersului normal al proiectului de producție, precum și reflectarea adecvată a lor în date ce condiționează prezența situației de ștat în CTA. Vom considera toate celelalte situații critice (de criză).

Cauzele principale ale apariției situațiilor critice pot fi refuzurile utilajelor de bază și ajutătoare tehnologice, deranjamentele în funcționarea sistemului de calcul, erori în informația de intrare și cea apriorică, precum și acțiuni eronate ale operatorului. Particularitatea CTA, ca a unui obiect de comandă, constă într-aceea, că diversitatea situațiilor de ștat este destul de limitată, iar numărul posibilităților situații critice este mare. Aceasta condiționează utilizarea în SCD SFP a procedurilor a două clase. Procedurile primei clase lucrează doar în cazul prezenței pe sector a situației de ștat. La apariția situației critice SCD se adresează procedurilor clasei a doua, a cărei sarcină este prelucrarea situațiilor critice.

La abordarea situațională a conducerii SFP apare o serie întreagă de avantaje, care permit:

să se conducă doar în momentele caracteristice, necesare din punct de vedere al efectuării procesului discret de producție;

folosind independența analizării situațiilor, dinamic, cu precizia de pînă la situație să se modifice sau să se corecteze cursul procesului de producție, precum, și să se construiască sisteme de comandă eficiente în sensul capacității de dezvoltare, modulații, capacității de modificare;

să se analizeze, de pe aceleași poziții, conducerea la efectuarea normală a temei de producție și în cazul situațiilor neprevăzute:

să se elaboreze sistemele de conducere, orientate pe efectuarea paralelă a proceselor.

Procesul conducerii SFP situaționale de dispecer poate fi prezentat în mod generalizat ca un proces de prelucrare a situațiilor (de ștat și critice), care include următoarea succesiune de sarcini de bază:

determinarea discordanței stărilor curente și dorită ale obiectului conducerii (diagnosticarea situațiilor);

aflarea evaluărilor situațiilor;

prognozarea (extrapolarea) urmărilor situațiilor apărute.

elaborarea influențelor de conducere.

Sarcina recunoașterii situațiilor este legată de urmărirea efectuării PO și OT. În cazul apariției discordanței între stările curente și cele necesare, provocate de necesitatea realizării stadiului ordinar al temei de producție și (sau) de perturbările în procesul tehnologic al fabricării pieselor și (sau) de deranjamentele în refuzurile obiectelor CTA SFP, se fixează apariția situației de producție.

Evaluarea situației necesare pentru optimizarea ulterioară a procesului de conducere, se face pe baza caracteristicilor stării CTA, ce depind de criteriile și limitările conducerii. Cele mai răspîndite dintre ele pentru SCD SFP sînt durata îndeplinirii temei de producție sau a părților ei, cheltuielile pentru producerea unei anume cantități și a nomenclatorului pieselor, timpul de întrerupere sau de funcționare OCT, cantitatea de piese produse, cantitatea de rebut ș.a. Cea mai importantă parte a evaluării situațiilor o constituie prognozarea urmărilor apariției sale doar cu evidența mulțimii evaluărilor situație, evaluări ce se prognozează, este posibilă obținerea valorilor optime ale influențelor de comandă.

În sfîrșit, elaborarea influențelor de comandă constă în formarea unei asemenea comenzi, care să asigure valoarea extremală a criteriului conducerii pe baza evaluărilor situației cu condiția îndeplinirii limitărilor. Drept criterii utilizate în mod tradițional pentru optimizarea conducerii sistemelor de producție, sînt analizate de asemenea cheltuielile sumare de producție, durata ciclului de producție ș.a. Totodată sarcina alegerii criteriului este complicată și conjugată cu cercetarea faptului, cum sînt legați parametrii evaluați de situațiile de producție care apar. În calitate de limitări ale sarcinii, în principal vor fi ordinele de succesiune tehnologice ale executării PO, caracterul limitat al resurselor SFP pentru OCT, OFM și PT, respectarea termenelor de pornire-producere piese, posibilitățile OCT pentru executarea PO și OT ș.a. De fapt conducerea, determinată în urma rezolvării sarcinii analizate, se reduce în capul SFP, înainte de toate la destinația, pornirea și încheierea prelucrării PO și OT ordinare în OCT alese, precum și la corectarea modelului CTA în capul apariției deranjamentelor și căderilor OCT SFP.

5.3. Modelarea complexului tehnologic SFP cu rețelele Petri

Rezolvarea sarcinilor conducerii situaționale dispeceriale SFP, analizate anterior, este bazată pe utilizarea modelului obiectului conduceri, care dă starea etalon cerută CTA SFP. Importanța acestui model pentru conducerea SFP subliniază actualitatea construirii ei eficiente. Necesitatea unei prezentări adecvate a caracterului multinomenclatorial al producției, evidența flexibilității tehnologiei, a interschimbabilității utilajelor CTA, a complexității structurii fluxurilor materiale duce la crearea mijloacelor specifice ale descrierii modelului CTA. Unul dintre aceste mijloace îl reprezintă rețelele Petri și extinderile lor orientate pe problemă.

În genere vîrfurile și arcele unor asemenea rețele dau raporturi de structură între elementele SFP. Pe mulțimea vîrfurilor se dă o funcție care determină prezența la fiecare vîrf a unor proprietăți, de exemplu a aflării reperului de tip dat în elementul corespunzător SFP. În afară de aceasta, există o oarecare regulă de conducere, ce dă în timp modificarea prorietăților vîrfurilor rețelei și modificarea reflectată prin aceasta a stării curente SFP. Să analizăm mai amănunțit aceste modele, folosind pentru prezentarea lor limbajul rețelelor Petri.

Formal rețeaua Petri generalizată este dată de sistemul

,

unde este digraful orientat, în care este mulțimea finită a vîrfurilor, numite tranziții; este mulțimea finită a vîrfurilor, numite locații; – funcția de parcurs; – funcția de precedență. Locațiilor rețelei li se atribuie jetoane ce caracterizează starea curentă a rețelei. Să adoptăm: – mulțimea jetoanelor; -jetonul lui s al rețelei. Fiecare jeton îl confruntăm cu vectorul proprietăților , care dă atributele ale jetonului s al rețelei; – mulțimea proprietăților jetoanelor. Starea rețelei se dă prin marcarea m, care confruntă fiecare din locații cu mulțimea jetoanelor din E, iar fiecare din jeton cu descriptorul cu valorile formate ale proprietăților atributelor jetoanelor rețelei, totodată marcarea inițială se dă prin aplicația m0: . Conducerea proceselor pe rețea se realizează prin darea funcțiilor și , unde dă condițiile declanșării tranziției j, determină operațiile asupra particularităților discriptorilor ai jetoanelor, trimiși prin tranziția j după declanșarea lui, totodată . Aceste funcții dau aplicația de încărcare . Timpul între momentele permisiunii tranzițiilor și momentele declanșării lor se dă prin aplicația – mulțimea numerelor raționale nenegative, ce dau reținerile jetoanelor în tranziții.

Modelul de rețea (MR) CTA SFP trebuie:

să descrie schemelor tehnologice ale prelucrării pieselor și itinerariile concrete ale efectuării operațiilor de bază și ajutătoare cu obiectele CTA SFP;

să reflecte caracterul alternativ al efectuării operațiilor tehnologice de bază și ajutătoare (scheme alternative de prelucrare a pieselor, itinerarii tehnologice, tipuri de utilaje SFP);

să prezinte afectiv în timp real logica funcționării proceselor asincronice paralele în SFP;

să prezinte structura fluxurilor materiale în SFP cu evidența diversității nomenclatorului pieselor brute, semifabricatelor, tipurilor de scule și accesoriilor;

să dea posibilitatea efectuării eficiente a evidențierii și analizei situațiilor de producție apărute în SFP, să calculeze valoarea lor și să realizeze căutarea soluțiilor optime de conducere și a corectării necesare a modelului CTA SFP.

Să analizăm la MR CTA prezența proprietăților cerute, construite prin mijloacele rețelelor Petri lărgite. Prima cerință este satisfăcută cu MR CTA cu interpretare modificabilă a sensului semantic al tranzițiilor, iar acest lucru este adevărat pentru rețelele Petri lărgite în legătură cu faptul că interpretarea este separată de descrierea rețelei. Legînd tranzițiile rețelei de obiectele CTA și dînd imaginea ce determină destinația la utilajele operațiilor tehnologice, vom obține rețeaua ce modelează procesele tehnologice atît la nivelul operațiilor, cît și la nivelul utilajelor SFP. Totodată locațiile corespund PT CTA, fie cîtorva stări evidențiate ale efectuării procesullui tehnologic în SFP.

Caracterul alternativ al îndeplirii operațiilor tehnologice se are în vedere prin introducerea surplusului necesar în structura rețelei Petri CTA, precum și prin darea regulilor speciale de conducere pe rețea.

Evenimentele permise, ce nu interacționează, din rețele, legate de modificarea marcării și determinate de aplicația f, se pot petrece în model independent unul de altul; în legătură cu acest fapt rețelele generalizate sînt, la fel ca și rețelele ordinare Petri, un mijloc comod de modelare a proceselor tehnologice asincrone paralele în SFP. În afară de aceasta legarea valorilor de raporturile de timp reale dă posibilitatea obținerii modelului etalon SFP, în care evenimentele sînt sincronizate cu evenimentele în SFP.

Cerința prezentării structurii complexe a fluxurilor materiale în SFP se satisface cu ajutorul imaginii reciproc univoce a tipurilor separate de obiecte ale fluxului material în anumite atribute ale jetoanelor MR. Jetoanele în acest caz se colorează în funcție de tipurile OFM.

Necesitatea rezolvării efective în model a sarcinilor conducerii situaționale de dispecer condiționează de asemenea cerințele specifice pentru limbajul modelării. Astfel, mijloacele descrierii modelului SFP trebuie, pe de o parte, să reflecte doar faptul prezenței jetoanelor în locație pentru determinarea discordanței stărilor ideală și reală ale SFP, iar pe de altă parte pentru formarea influențelor de conducere să reflecte seria completă a atributelor jetonului la toate OFM. Similar, la conducerea SFP după orarul de funcționare a utilajelor tehnologice, conducerea pe rețea se determină prin logica disjunctivă simplă. Funcționarea SCD SFP fără un orar întocmit din timp, poate să necesite calcularea de procedură a fiecărei noi stări a rețelei. Aceste cerințe sînt de asemenea satisfăcute de MR analizate, a căror descriere nu depinde de darea concretă a proprietăților jetoanelor și de logica conducerii rețelei.

Cerințele evidențiate permit să se determine mai concret clasa MR CTA SFP și să se treacă apoi la descrierea procedurilor de conducere SFP bazate pe aceste modele.

MR CTA poate fi prezentat sub forma sistemului

aici B este digraf orientat, dat, ca și anterior, sub forma , unde T este mulțimea OCT; iar P – mulțimea operațiilor; K – mulțimea imaginilor legate de destinația PO pe OCT SFP și date ca ; – aplicația ce determină aspectul concret al aplicației ki, ce acționează pe un oarecare pas i al acțiunii rețelei ; D este mulțimea atributelor jetoanelor MR; f – aplicația de încărcare, ce dă conducerea pe rețea unde dă condițiile pornirii pentru efectuarea operației tehnologice i, determină operațiile de rețea asupra atributelor jetoanelor după efectuarea operației i. Timpul de lucru al tranzițiilor rețelei se dă prin aplicația ; m0 dă marcarea inițială a rețelei.

Pentru rețelele introduse se determină în mod natural toate proprietățile de bază, necesare pentru rețelele ordinare Petri. Să ne oprim mai în amănunt asupra analizei acestor proprietăți, iar mai întîi vom analiza rețelele vopsite fără evidența timpului, iar apoi să cercetăm proprietățile MR complet.

Analiza proprietăților modelelor de rețea CTA se poate realiza prin construirea și cercetarea mulțimii stărilor realizabile ale modelului, ceea ce în cazul SFP provoacă dificultăți esențiale din cauza numărului mare de stări posibile. O altă modalitate este bazată pe cercetarea reprezentării matriceale a rețelei. Analiza se face prin rezolvarea ecuației recurente, ce dă dinamica rețelei pe baza matricelor de parcurs și de precedență, precum și prin darea marcării inițiale. Această ecuație are în genere următorul aspect:

Aici Mk este marcarea rețelei, următoarea după marcarea Mk-1 în urma acțiunii Uk; M0 este marcarea inițială a rețelei; W este matricea care determină proprietățile de structură ale rețelei; Uk este vectorul de conducere cu componentele ujk0,1. Dacă ujk 1, atunci la pasul k (k- întreg, pozitiv) are loc declanșarea tranziției ti, dacă ujk 0, atunci declanșarea nu se produce.

Condițiile permiterii tranziției se prezintă prin ecuația logică

unde este mulțimea predecesorilor tranziției tj, adică

este vectorul de conducere. Aceste condiții vorbesc despre posibilitatea producerii tranziției. În caz contrar .

Tranzițiile încep să se declanșeze, jetoanele ce le produc în conformitate cu aplicația f1 pleacă din locațiile de intrare ale tranziției și apar în cele de ieșire în conformitate cu aplicația f2.

Vom reprezenta marcarea rețelei sub forma vectorului este operația de transpunere; ei este jetonul i al rețelei; este valoarea atributului r al jetonului. Aflăm expresia pentru matricea W. Pentru aceasta să reprezentăm sub formă de matrice aplicațile k și f. Aplicația k va fi prezentată sub forma matricei K de dimensiunea m n , unde m este numărul de operații, iar n este numărul tranzițiilor SFP. kij 1 vorbește despre repartizarea pe utilajul j a operației i.

Aplicația f1 poate fi prezentată cu matricea diagonală F1 de dimensiunea k k , unde k este numărul de operații. Elementele diagonale ale matricei corespund elementelor ej, pentru care , adică jetoanelor, ale căror atribute satisfac condițiile producerii tranziției j a operației. Corespunzător F2 este matricea diagonală k k, ale cărei elemente diagonale corespund jetoanelor dispuse în locațiile de ieșire ale tranzițiilor după declanșarea acestora.

Trebuie remarcat faptul că în procesul de conducere, după cum s-a arătat deja, se realizează modificarea tipului de imagini K prin influența asupra lor a aplicației . Felul aplicației , într-o măsură considerabilă, depinde de regiunile de comandă alese, care vor fi analizate mai tîrziu. În legătură cu aceasta la analiza proprietăților modelelor de rețea vom considera temporar aplicațiile K modificabile.

Ca urmare prin analogie cu rețelele Petri ordinare vom descrie dinamica modelului de rețea SFP prin următoarea ecuație a stării rețelei:

aici W este matricea legăturii tranzițiilor utilajelor cu locațiile de ieșire corespunzătoare, iar elementul acestei matrice wij 1, dacă există legătura tranziției i cu locația de ieșire j, wij 0 la absența legăturii; este matricea legăturii tranzițiilor utilajelor cu locațiile de intrare corespunzătoare.

În ecuația stării produsele KW și descriu structura rețelei operațiilor. Produsulcaracterizează deplasarea jetoanelor în locațiile de ieșire ale tranzițiilor rețelei operațiilor, – deplasarea jetoanelor din locațiile de intrare ale tranzițiilor. Produsul este vectorul de comandă al tranzițiilor declanșate ale operațiilor ( – vectorul-coloană de conducere pe tranziții).

Analizarea proprietăților MR o vom lega de noțiunea de invariant în mod analog. Vom înțelege prin p – invariant vectorul coloană numeric întreg , fiind soluția sistemului linear

unde – numărul atributelor.

După cum se știe, marcarea arbitrară realizabilă a rețelei poate fi obținută prin vectorul apariției tranzițiilor S(), unde este succesiunea pornirilor tranzițiilor, iar Sj() – numărul apariției tranziției tj în succesiunea . De aici.

Prin urmare, folosind definiția p- invariantului , avem ecuația ce descrie invariabilitatea marcărilor MR. De aici

Dacă toate componentele p -invariantului MR sunt pozitive, atunci rețeaua este marginită întrucît suma semnelor rețelei din proprietățile invariantului, ponderată cu valorile componentelor p-invariantului este marginită. Această proprietate este legată de caracterul realizabil al modelului pe CTA SFP cu PT de capacitate redusă.

t-invariant MR vom numi vectorul de numere întregi , ce este soluția sistemului linear

iar Dacă în ecuația stării se substituie valoarea t-invariantului, atunci obținem condiția stabilității rețelei sau a funcționării ciclice a acesteia după un oarecare OFM, întrucît dacă , rețeaua se va întoarce în starea inițială, dată de marcarea M. Dacă toate componentele t-invariantului sînt pozitive, atunci MR este viabil la orice marcare inițială, întrucît în de la M0 la se declanșează toate tranzițiile (OCT).

Pe des. 5.1. se dă un exemplu de model de rețea CTA SFP, ce include șase OCT cu PT tampon și depozitul de obiecte ale fluxului de material. Pentru această rețea pe des. 5.2. se dau p si t-invarianții, ce dovedesc marginirea, stabilitatea și viabilitatea rețelei. Să dăm de asemenea matricea incidențelor:

La introducerea operatorului , ce dă destinația la utilajele operațiilor tehnologice curente, analiza proprietăților MR în cazul SFP se face pentru valorile discrete k, iar analizarea pentru fiecare valoare concretă k este în întregime analogă celei descrise anterior.

Des. 5.1. Rețea Petri a complexului flexibil de prelucrare mecanică.

p0 – locația de transport a depozitului; , – mulțimea locațiilor de transport tampon; – mulțimea obiectelor de transport și de prelucrare ale complexului tehnologic.

Des. 5.2. p si t – invarianții rețelei, arătate pe des. 5.1.

Dacă de tranzițiile MR se leagă intervalele de timp între evenimentele permiterii și declanșărilor, atunci obținem un model de rețea complet CTA SFP, ce permite cercetarea în timp a proceselor în SFP. Totodată dacă timpii declanșării tranzițiilor sînt identici sau multipli, atunci toate proprietățile MR rămîn neschimbabile, iar schimbarea marcărilor se face cu un ritm egal fie cu durata declanșării tranzițiilor, fie cu multiplul comun cel mai mic al acestor durate. În cazul intervalelor arbitrare ale tranzițiilor, rămîn nemodificate toate proprietățile de structură ale MR, întrucît introducerea timpului se răsfrînge doar asupra regulilor declanșării tranzițiilor care dau dinamica rețelei. Aceste reguli pentru MR temporar vor fi prezentate sub forma următoare:

unde t – timpul ce a trecut de la începutul funcționării MR; t momentul permiterii tranziției; timpul opririi jetoanelor în tranziția rețelei.

Mijloacele analizate ale prezentării modelului CTA SFP, fiind o extindere orientată pe probleme a rețelelor Petri, permit să se treacă la construirea procedurilor conducerii situționale de dispecer SFP, care utlizează modelul CTA SFP în calitate de model etalon.

5.4. Algoritmul conducerii situaționale de dispecer în conformitate cu modelul etalon de rețea

Să analizăm utilizarea rețelelor Petri lărgite introduse în diferite etape ale conducerii SFP. Pentru aceasta să descriem algoritmul conducerii de dispecer în succesiunea, în care acestea apar la prelucrarea situațiilor de producție în SFP. Procedura generală a conducerii SFP situaționale de dispecer începe, după cum s-a arătat în 5.2., de la recunoașterea situațiilor de producție, ce apar în procesul funcționării SFP. Sarcina etapei o constituie evidențierea dezacordului dintre starea CTA SFP etalon, dat după model, și cea reală, curentă. În cazul prezenței dezacordului în această etapă are loc identificarea situației apărute. Totodată se presupune, că în SCD de la sistemele de comandă ale nivelului inferior se transmite toată informația despre CTA SFP, necesară pentru evidențierea situației.

Modelul etalon de rețea se prezintă în această etapă în felul următor. Tranzițiile rețelei corespund unui utilaj în stare bună, utilizat pentru îndeplinirea temei de producție. Locațiile rețelei corespund PT SFP. Legăturile locațiilor și tranzițiilor se determină prin posibilitățile realizării PO și OP asupra OFM pe utilajele determinate de tranzițiile rețelei. Semnele rețelei determină prezența sau absența OFM în locațiile corespunzătoare. Pentru identificarea diferitelor tipuri OFM fiecare jeton este dat de mulțimea atributelor.

În felul acesta, formal modelului de rețea în această etapă îi corespunde seria unde B este bigraful PT și al obiectelor CTA; D este mulțimea atributelor jetoanelor rețelei; f este aplicație, ce dă valorile etalon ale atributelor jetoanelor în locații; m determină marcarea curentă a rețelei.

Logica generală a algoritmului evidențierii și analizei situațiilor de producție este următoarea.

Pasul 1. Compararea stării etalon curente a rețelei, date de digraful B și de marcarea m, și a stării corespunzătoare CTA, de asemenea prezentate în termeni de rețea.

Pasul 2. Dacă nu există dezacord al stării, atunci ieșirea din procedură.

Pasul 3. Identificarea dezacordului obținut. Dacă abaterile necesită modificarea structurii rețelei sau a programului funcționării sale (situație de criză), atunci se merge spre pasul 4. Dacă însă abaterile pot fi lichidate fără schimbarea etalonului, se formează o situație de ștat și se face apelul către procedura elaborării comenzilor de conducere.

Pasul 4. Pentru situațiile de criză se calculează intervalul de timp necesar pentru prelucrarea situației apărute. Acest interval limitează complexitatea prelucrării situațiilor critice după algoritmul corespunzător. Durata de timp pentru prelucrarea situației depinde într-o măsură considerabilă de dinamismul obiectului de conducere și de acea eficiență dată de activitatea optimă CTA față de funcționarea după orare aproximative. În condițiile cele mai critice acest timp reprezintă cîteva zeci de minute.

Situațiile de ștat formate servesc drept bază pentru comenzile de conducere elaborate de SCD. Aceste comenzi se formează în urma transformării informației despre abaterile în marcările curente reale și etalon ale rețelei din situațiile de ștat în comenzi pentru utilajele tehnologice SFP pentru prelucrarea sau transportarea obiectelor corespunzătoare atributelor rețelei.

Următoarea etapă o reprezintă elaborarea stării următoare etalon a rețelei. Lucrul se face cu modelul de rețea complet, dat de următoarea serie:, unde B este digraful rețelei; K este matricea de destinație, ce leagă utilajul și operațiile executate pe acesta; este aplicația care determină valoarea curentă a matricei K, valorile pot fi calculate dinainte și păstrate sub forma orarului – mutarea j a utilajului, – operația tehnologică k, poate de asemenea să aibă o temă de procedură și să servească pentru calcularea în fiecare tact i al lucrului SFP a elementelor matricei K; D – mulțimea atributelor jetoanelor; f – aplicație, ce dă regulile declanșării tranzițiilor, acești timpi depind atît de tipurile utilajelor CTA SFP, cît și de PO executate pe ele; m0 – marcarea inițială a rețelei.

Pentru comoditatea descoperirii logicii procedurilor independente, vom prezenta în forma următoare ecuația stării rețelei pe tactul i:

unde și – sînt corespunzător matricele de destinație și simultan de pornire a perechilor (tranziție, operație) pentru locațiile de ieșire și intrare ale locațiilor. vorbește despre pornirea tranziției j după operația i. vorbește despre terminarea efectuării operației i în tranziția j. F2 , F1 sînt reprezentarea vectorială a operatorului f. F2 este vectorul-coloană al transformărilor atributelor (culorilor) jetoanelor la ieșirea operației, F1 – la intrare.

Ca urmare logica funcționării sistemului în această etapă se prezintă sub forma următorului algoritm.

Pasul 1. Pe baza B, K, K, , se caută tranzițiile ce declanșează pe tactul respectiv al funcționării sistemului. Dacă nu există asemenea tranziții, atunci ieșire din procedură.

Pasul 2. Pentru tranzițiile aflate în conformitate cu B, K, K, D, F1, F2 se găsește marcarea obținută după declanșarea lor:

Pasul 3. Pentru întreaga rețea pe baza marcării obținute se găsește marcare curentă a rețelei, ce este rezultatul declanșării tuturor tranzițiilor posibile:

Ultima procedură ce intră îm ciclul prelucrării situațiilor, este procedura prognozării, extrapolării comportamentului rețelei (a calculării orarului funcționării SFP) în cazul apariției situațiilor de criză. Sarcina ce se soluționează este asemănătoare în multe privințe cu sarcina clasică a planificării operative. Totuși există o serie de trăsături specifice, ce o evidențiază și dintre sarcinile planificării operative pentru tipurile tradiționale ale producțiilor automatizate, și din sarcinile planificării operative SFP. Acest specific este legat de următoarele momente:

descrierea CTA SFP are o înaltă complexitate de structură și funcțională;

mulțimea obiectelor fluxului material în SFP are o mare diversitate de elemente și, într-o oarecare măsură are capacitate de spălare;

se ridică cerințe stricte față de complexitatea temporară a algoritmului procedurii, cerințe determinate de timpul consumat pentru prelucrarea situațiilor de producție de criză;

necesitatea analizei complexe a tuturor procedurilor conducerii situaționale pe baza unui model mic de rețea CTA.

Particularitățile arătate își pun inevitabil pecetea asupra metodelor rezolvării sarcinii, cărora în plan general le este dedicată o literatură vastă. În ultimul timp în legătură cu dezvoltarea impetuoasă a modelării de imitație se fac încercări de construire a orarelor în urma efectuării experimentelor de imitație cu model al obiectului de conducere.

Avantajele unei asemenea abordări sînt legate înainte de toate de posibilitatea reducerii complexității modelării întregului sistem pe baza formalizării proceselor de funcționare și a schemelor de îmbinare a diferitelor elemente ale sistemului. Totodată devine neobligatorie formalizarea situațiilor sistematice generale, ce constituie dificultatea principală a utilizării modelelor analitice pentru sistemele complexe. În afară de aceasta, similitudinea de structură a obiectului și modelului la modelarea de imitație dă posibilitatea să se construiască și să se modifice ușor modelul, și de asemenea să se interpreteze concret și simplu rezultatele modelării.

Totuși optimizarea conducerii pe baza modelelor de imitație este o procedură extrem de îndelungată, în legătură cu faptul că astfel de modele permit să se analizeze doar urmările modificărilor, ce au loc în obiectul conducerii. De aceea în practică se tinde să se unifice modelarea de imitație cu cea analitică într-o unică procedură de imitație. Exemplu de asemenea abordare o constituie procedura analizată mai departe, a extrapolării, ce utilizează modelarea matematică (de exemplu algebrică) pentru evaluarea rapidă, dar aproximativă a situațiilor în CTA SFP, iar modelarea de imitare pe baza modelelor de rețea CTA introduse – pentru formlizarea detaliată a comportamentului sistemului.

Să ne întoarcem la analiza procedurii extrapolării la apariția situației critice. Să introducem în analiză următoarele matrice: L – matricea, conținînd informația despre tranzițiile ce lucrează în momentul dat (tranziții declanșate), , i – numărul tranziției, j – numărul operației, ; V – vectorul tranzițiilor declanșate, care arată cît timp a rămas pînă la producerii fiecărei tranziții, , i – numărul tranziției; G – matricea generală a destinației operațiilor pe utilaj, ce oferă posibilitatea efectuării de către tranziții a operațiilor corespunzătoare, , i – numărul tranziției, j – numărul operației; T – matricea duratei efectuării operațiilor în tranziții, , i, j – numerele tranzițiilor și a operațiilor.

Ca urmare modelul de rețea CTA se reprezintă în această etapă sub forma

Să analizăm algoritmul procedurii care realizează schema „ ramurilor și hotarelor”.

Pasul 1. Se aleg pe matricea L și vectorul V tranzițiile ce se declanșează pe tactul i. Se modifică timpii celorlalte tranziții. Dacă nu există pretendenți la declanșare, atunci trecem la pe pasul 3.

Pasul 2. Se află marcarea obținută după declanșarea tranzițiilor găsite

Pasul 3. Se generalizează toți pașii posibili din marcarea Mi, Totodată vom numi pas al rețelei totalitatea tranzițiilor, care pe tactul respectiv pot să se declanșeze din marcarea curentă Mi.

Pasul 4. Se calculează evaluările pașilor rețelei pentru toate destinațiile posibile pe tranzițiile operațiilor (după matricele G și T).

Pasul 5. Se alege cel mai bun pas al rețelei după toate tacturile analizate (organizarea revenirilor). Se construiesc L, V, noi. Se află

Dacă nu se îndeplinesc condițiile finalizării, se trece la pasul 1.

Pasul 6. Succesiunea cea mai bună a pașilor se consideră orarul funcționării rețelei.

Să analizăm procedura mai amănunțit. Înainte de toate să observăm, că condițiile generării pașilor rețelei din marcarea Mi pe pasul 3 al procedurii sînt:

1) – condiția declanșării tranziției;

2) în momentul respectiv tranzițiile nu sunt declanșate.

Aceste condiții sînt necesare pentru conectarea tranzițiilor în pasul următor al rețelei. În același timp pas este și totalitatea tranzițiilor, unele dintre ele, deși posibile, nu sînt pornite. Totodată se au în vedere situațiile, cînd este necesar să se întîrzie pornirea piesei pe un oarecare utilaj liber pentru ca, peste un timp oarecare să pornească pe o altă unitate de utilaj, cu mai bune caracteristici ale efectuării operațiilor tehnologice. O asemenea admitere permite să se ia în considerație preistoria declanșării tranzițiior și prin aceasta să se construiască orarul optim.

Baza procedurii descrise o constituie pașii 4, 5. Ei sînt destinați pentru alegerea unui asemenea pas al rețelei care, în stadiul respectiv al lucrului, să aibă cea mai mare prioritate pentru cuplarea în orarul optim. Alegerea acestui pas al rețelei se realizează cu ajutorul diferitelor evaluări ale hotarelor inferioare ale criteriului de minimizare al eficienței SFP. Este evident că, cea mai bună va fi aprecierea egală cu valoarea optimă a criteriului însuși de întocmire a orarului pe pasul respectiv al rețelei, dau totodată rezolvarea sarcinii, prin metoda „ramurilor și hotarelor” devine extrem de neeficientă, întrucît necesită mari cheltuieli de calcul, legate de determinarea evaluării deși procedura nu are întoarceri. O altă situație extremă este cazul evaluării pasului rețelei fără evidența influenței urmărilor alegerii sale pe precizia orarului. Totodată cheltuielile de calcul de bază sînt legate de întoarcerea pe pașii anteriori ai rețelei, cu valori mai mici ale evaluărilor.

Din cele spuse decurge faptul că este utilă construirea evaluării, în primul rînd, a celei ale cărei valori ar fi mai mici sau egale cu marginea inferioară al valorilor criteriului compunerii orarului și, în al doilea rînd, a cărei calculare ar fi legată cu dificultăți esențiale mai mici decît calcularea valorii optime a citeriului. Totodată trebuie remarcat, că alegerea criteriului, după cum s-a arătat deja, este deosebit de complicată și se realizează individual pentru fiecare SFP concret. Unul dintre cele mai universale și des folosite este criteriul minimizării cheltuielilor de producție S. Cheltuielile pot conține cheltuielile de timp pentru efectuarea operațiilor tehnologice, noua reglare, instalarea pieselor, consumurile resurselor energetice, consumurile de cost ș.a. Să construim evaluarea acestui criteriu și să analizăm pentru el funcționarea procedurii, însă scoatem limitarea la succesiunea declanșării tranzițiilor modelului de rețea SFP. Din punct de vedere al procesului de producție o asemenea ipoteză este legată de anularea succesiunii în executarea PO. La această condiție este evident că, cheltuielile de producție vor fi mai mici, iar în capul prezenței proceselor tehnologice care constau doar dintr-o operație, egale cu consumurile în SFP real. De aici evaluarea consumurilor, după un model de rețea simplificat fără limitări la succesiunea declanșării tranzițiilor, va satisface prima cerință pentru evaluarea pentru procedura extrapolării.

Să analizăm problema calculării evaluării pașilor pe o asemenea rețea simplificată. Să ponderăm tranzițiile rețelei cu valorile Si, unde i este numărul tranziției, iar SiR corespunde consumurilor tranziției la toate operațiile. În legătură cu faptul că, la calcularea evaluării nu există necesitatea de a împărți momentele pornirii și opririi lucrului tranzițiilor și întrucît timpii declanșării tranzițiilor sînt incluși în Si, pentru rețeaua simplificată. Folosindu-ne de dependența obținută anterior

unde este vectorul apariției tranzițiilor la toate operațiile, avem că corespunde consumurilor sumare ce revin pe tranziția i la declanșarea rețelei din marcare inițială în cea k. De aici pentru evaluarea pasului, înainte de toate, este necesară calcularea consumurilor pentru toate tranzițiile rețelei obținute la trecerea de la marcarea ce corespunde pasului analizat (Mш) la marcarea de linie moartă (de impas) ce corespunde închierii ciclului de producție (MТ). Aceste consumuri se găsesc cu ajutorul ecuației

MТ MшX

unde X este vectorul căutat care determină numărul declanșărilor tranzițiilor rețelei. Vom considera că rețeaua analizată este fără bucle și cicluri [1], iar acest lucru se poate realiza printr-o nouă simbolizare a operațiilor și atributelor jetoanelor rețelei. Acum, dacă se înmulțesc [multiplică] vectorii XiSi și se însumează cheltuielile la toate operațiile tranziției i, iar pentru cheltuielile legate de succesiunea efectuării operațiilor, de exemplu cheltuielile pentru o nouă reglare, se iau valorile lor cele mai mici. Dacă acum însumăm cheltuielile la toate tranzițiile declanșate, atunci obținem evaluarea căutată, iar alegerea pasului următor în procedura extrapolării se reduce la căutarea pasului, pentru care această evaluare ia valoarea minimă.

Momentul principial următor la prelucrarea situațiilor de criză este cerința calculului orarului cu evidența timpului repartizat pentru funcționarea procedurii. Acest timp, după cum s-a arătat deja, dă complexitatea realizării pașilor ei 4, 5, legată de cheltuielile pentru soluționarea sarcinii aflării evaluărilor, precum și pentru realizarea întoarecerilor [revenirilor] în schema „ramurilor și ghotarelor” la obținerea valorilor evaluărilor finite, mai mari, decît evaluarea pașilor mai recenți ai rețelei. Acest lucru este în mod special esențial în acele cazuri, cînd timpul acordat calcului, este insuficient pentru aflarea orarului optim pentru algoritmul descris. În asemenea cazuri este necesar să se renunțe la obținerea orarului optim și să se construiască diferite aproximații pentru el.

Să analizăm variantele posibile ale modificării procedurii extrapolării pentru obținerea rapidă a orarelor apropiate cvazioptime, ce păstrează în același timp logica generală anterior descrisă a procedurii extrapolării exacte. Primele simplificări sînt posibile pe pasul 3. Dacă nu se ia în considerație anteistoria declanșării tranzițiilor și se prescriu operațiile pe toate tranzițiile libere, atunci se reduce în mod esențial numărul pașilor analizați. Astfel, la n tranziții gata pentru pornire și la o singură operație prescrisă [destinată] pe fiecare tranziție, se va analiza doar un singur pas în loc de 2n posibili.

La alegerea celui mai bun pas există două variante de simplificare principale. Prima variantă este legată de alegerea pasului pe baza evaluării, însă fără reveniri sau, în general, cu reveniri doar la depășirea evaluării cu o oarecare valoare nenegativă, ce determină precizia orarului aproximativ. În afară de aceasta este posibilă obținerea evaluării nu pînă la marcarea de impas, ci pînă la marcarea, ce rămîne în urmă de la cea curentă cu un oarecare numări fixat de pași, iar numărul se poate modifica în funcție de situația creată și de timpul consumat pentru elaborarea soluțiilor. A doua variantă de simplificare este legată de excluderea din procedură a evaluării și de organizarea alegerii pasului cu ajutorul metodelor statistice și euristice de obținere a orarelor aproximative.

La baza aplicării metodelor statistice de optimizare se află următoarea legitate stabilită experimental. Numărul tuturor orarelor realizabile, adică a unor astfel de orare, pentru care nu este posibilă abaterea stînga a nici unei operații este considerabil mai mic decît numărul [cantitatea] tuturor orarelor și, de regulă, numărul orarelor optime este mai mare de unul. În legătură cu aceasta la construirea orarelor prin alegerea întîmplătoare a pașilor rețelei cu mărirea numărului realizărilor alegerii, orarul cel mai probabil se află mai aproape de cel optim. Complexitatea obținerii variantei orarului se determină doar prin complexitatea realizării pașilor rețelei de la marcarea inițială pînă la cea de impas, deși pentru obținerea orarului optim este necesar să se calculeze nu mai puțin de V variante de orare:

,

unde p este probabilitatea obținerii orarului optim la prima variantă de alegere a pasului rețelei.

Metodele euristice de optimizare se bazează nu pe alegerea pasului din mulțimea celor posibili, ci pe construirea singurului [unicului] pas pe fiecare tact de lucru a rețelei, iar construirea lui trebuie să se facă pe baza funcțiilor și regulilor preferinței. Funcțiile de preferință reflectă caracteristicile operației din punct de vedere al funcționării rețelei și caracterizează starea operației, apărută fie în urma pașilor precedenți ai construirii orarului (funcții poziționale de preferință), fie doar pe un pas al rețelei (funcții lineare de preferință). Regulile preferinței sînt niște reguli speciale; conform cărora, pe baza funcțiilor preferențiale, se realizează includerea unui element sau altuia în pasul corepsunzător al rețelei. Cele mai cunoscute sînt: regula la care se dă preferință operației cu durată mai mică de executare în tranziție; regula acordării preferinței operației care este prima gata pentru deservire; regula deservirii celei mai rare operații ș.a.

Precizia orarelor obținute depinde într-o măsură considerabilă de faptul, cît de corelate sînt regulile folosite de regulile „ideale” ale alegerii, legate nemijlocit de criteriul optimizării orarului. Îmbunătățirea regulilor este legată în principal de complicarea lor și poate să se reducă în extremis la calcularea valorilor criteriului de optimizare și, prin urmare, la obținerea unor orare exacte. Abordările descrise, ale construirii procedurii permit, în funcție de timpul acordat întocmirii orarului, se realizeze alegerea metodei corespunzătoare și să obțină orarele funcționării rețelei pe baza unei logici unitare a întregii proceduri.

Descrierea în detaliu a modelelor și algoritmilor propuși, ce permit efectuarea analizei situațiilor de producție și elaborarea acțiunilor de comandă, se dă în următorul capitol, cu specificarea mijloacelor de program SCD SFP.

Capitolul 6

SISTEMUL CONDUCERII DISPECERIALE

DUPĂ MODELUL ETALON DE REȚEA

AL COMPLEXULUI FLEXIBIL DE PRODUCȚIE

6.1. Organizarea sistemului conducerii dispeceriale

Modelele și algoritmii introduși în capitolul anterior dau posibilitatea începerii realzării SCD SFP, în particular, elaborării asigurării sale de program. Dificultăți esențiale vor fi, totodată, legate de necesitatea reprezentării corecte a macroprocesului conducerii dispeceriale, constă în interacțiunea proceselor asincrone paralele SCD SFP. Erorile apărute la construirea sistemului pot duce ulterior la deformări esențiale ale funcționării sale, legate de blocări reciproce, ciclări ale proceselor sau accesul nesancționat la datele SCD. De aceea este bine să se elaboreze o metodă specială (schemă) de organizare SCD, a cărei aplicare va permite efectuarea construirii schemei, protejată de erori în organizarea interacțiunii proceselor și datelor sale.

La baza metodei se găsește noțiunea de proces. Prin proces P vom înțelege sistemul {A, B, C, D, F}, unde A, B, C sînt, corespunzător, mulțimi ale datelor de intrare, de ieșire și intermediare; D este mulțimea acțiunilor succesive asupra datelor; F este funcția activării acestei acțiuni. Vom considera, că efectuarea unui proces separat în sistem decurge paralel și independent de alte procese. În legătură cu aceasta diferite procese nu pot să activeze în mod direct acțiunile unul celuilalt, cu alte cuvinte, funcția de activare Fi a procesului i este inaccesibilă pentru procesul al i-lea P. Legătura între procesele unificate într-un singur sistem, se realizează prin structurile generale ale datelor (des. 6.1.).

SCD SFP, care reprezintă sistemul proceselor cu proprietățile arătate, are o serie întreagă de avantaje atît în etapa de sinteză cît și la funcționarea sistemului. Astfel, procedura proiectării întregului SCD SFP în această etapă se descompune în proiectarea părților (diferite procese) autonome legate doar prin intermediul datelor comune. Logica interacțiunii diferitor procese se determină concomitent pentru întregul sistem și nu depinde de realizarea concretă a proceselor.

Înlocuirea structurii logice sau a mijloacelor realizării diferitelor procese la deformarea lucrului întregului sistem și se poate realiza în timp real în funcție de situația concretă de producție. În afară de aceasta, în legătură cu faptul că logica sistemului este cuprinsă în datele generale pentru procese, există o posibilitate eficientă de control și modificare a procesului conducerii dispeceriale SFP. Acest lucru, în particular, permite să se obțină în oricare moment al timpului, indiferent de starea diferitelor procese, informația completă despre starea curentă CTA SFP, să se introducă, într-un moment arbitrar al timpului, o nouă informație pentru conducerea SFP, fără să se deformeze funcționarea întregului sistem. Există posibilitatea redresării rapide a funcționării SCD după deranjarea dispozitivului de conducere, este necesar doar să se redreseze conținutul structurilor generale ale datelor.

Construirea schemei de procese paralele, independente după comandă permite realizarea eficientă SCD prin mijloacele sistemelor distribuite – multiprogram de conducere informațională, iar realizarea schemei descrise în sistemele monoprogram nu provoacă, de asemenea, complicații și este eficientă la utilizarea mecanismelor acoperirilor.

Alături de avantajele arătate există o serie de dezavantaje, pentru înlăturarea cărora este necesară o oarecare corectare a organizării descrise a sistemului. Dezavantajul principal al schemei îl reprezintă posibilitatea accesului nesancționat al diferitelor procese la date și, prin urmare, deformarea întregii logici a funcționării sistemului. În afară de aceasta, funcționarea eronată a unui proces separat se reflectă de asemenea asupra lucrului întregului sistem, iar fără o analiză suplimentară nu este posibilă evidențierea procesului defect. Proiectarea independentă a diferitelor procese, la rîndul ei, poate duce la dublarea diferitelor succesiuni ale acțiunilor lor.

Des. 6.1. Schema generală a interacțiunii proceselor.

Înlăturarea dezavantajelor aratate necesită, înainte de toate, creșterea calității și a facilității proiectării, ceea ce este legat de folosirea metodelor de sistem ale elaborării SCD SFP. Alături de aceasta, problemele provocate de accesul simultan al proceselor la resursele generale se rezolvă cu ajutorul introducerii în schema SCD SFP a mijloacelor accesului de exludere reciprocă la resurse. Să ne oprim mai în amănunt asupra analizei lor. Cele mai răspîndite dintre asemenea mijloace sînt trei tipuri de construcții de interacțiune interproces-semafor, rendes-vous, monitor .

Semaforul este alternativa dublă s, care înregistrează dacă resursa pe care o protejează este sau nu accesibilă. Pentru semaforul dat resursa este accesibilă, cînd ; în caz contrar resursa nu este accesibilă și procesul care are intenția să i se adreseze, va trebui să aștepte. Verificarea cu semaforul se realizează cu ajutorul adresării către două proceduri de sistem:

Pentru susținerea integrității semaforului aceste proceduri sînt de excludere reciprocă.

Rendes-vous este un mecanism ce analizează legătura interprocese din punct de vedere al transmiterii datelor și al sincronizării, care la rîndul lor sînt analizate ca o singură activitate neîntreruptă. Modelul rendes-vous necesită ca, în cazul procesului Pj are intenția de a transmite datele unui alt proces Pi , ambele procese să exprime disponibilitatea lor de a stabili legătura, trimițînd comenzi corespunzător pentru transmitere și recepție. Dacă se întîmplă astfel, încît procesul Pj va trimite primul cerere pentru transmitere, atunci îndeplinirea lui se oprește pînă atunci cînd, un alt proces nu va trimite cerere pentru primire. Cînd ambele procese se sincronizează astfel are loc transmiterea datelor și fiecare dintre procese își reînnoiește activitatea. O asemenea sincronizare a proceselor se numește rendes-vous.

Monitorul, al treilea mijloc al interacțiunii interproce, este un proces special în care datele generale pentru o oarecare grupă de procese, sînt unificate cu mulțimea acțiunilor care realizează accesul la aceste date. Acțiunile monitorului au o proprietate specifică: de fiecare dată doar un singur proces poate efectua activ acțiunile monitorului. Cu alte cuvinte monitoarele sînt construcții de nivel înalt care permit să se realizeze accesul de excludere reciprocă al proceselor la resursele partajate. Compararea construcțiilor descrise, efectuată la 1.1. face necesară alegerea monitorului în calitate de construcție de bază a realizării mecanismelor schimbului interproces în organizarea propusă SCD SFP.

Un moment esențial îl reprezintă de asemenea luarea în considerație a specificului modelelor și algoritmilor dispecerizării SFP. Conducerea dispecerială SFP se construiește pe baza aparatului rețelelor Petri modificate, iar procesele conducerii operează cu noțiunile și reprezentările limbajului lor formal. În același timp informația cu care face schimb SCD cu sistemele exterioare în raport cu el, are un caracter pur tehnologic, determinat de structura fluxurilor informaționale în SFP. În legătură cu aceasta, pentru a nu perturba abordarea generală a construirii SCD SFP, ce constă din sistemul proceselor independente, structura sistemului se completează cu procesul service-interpretatorul, care realizează reprezentarea informației tehnologice în structurile modelelor de rețea CTA respective.

Des. 6.2. Schema generală a interacțiunii proceselor SCD SFP.

Ca urmare structura generală SCD SFP este sistemul proceselor împărțite în două grupe. În prima grupă intră procesele funcționale care de fapt realizează comanda dispecerială SFP. Aceste procese care realizează diferite obiective ale conducerii SFP sînt indepdendente unul de celălalt în ceea ce privește comanda și sînt legate doar prin date generale. În a doua grupă intră două procese ajutătoare: interpretatorul și monitorul. Interpretatorul realizează reprezentarea informației exterioare în termenii limbajului SCD și invers. Monitorul asigură accesul corect al celorlalte procese la datele SCD SFP (des. 6.2.).

6.2. Specificul mijloacelor de program ale sistemului

Gradul scăzut de formalizare a cerințelor, precum și influența considerabilă a erorilor admise asupra calității SCD SFP creat condiționează necesitate a atragerii unor mijloace speciale ale specificării asigurării de program, a căror utilizare este tradițională pentru SCD SFP analoge ale sistemelor tehnice-organizaționale complexe. La o asemenea abordare se asigură formalizarea și simplificarea procedurilor introducerii corecturilor și a modificării descrierilor sistemului, și se ușurează evidențierea și analiza cauzelor abaterilor calității sistemului proiectat de la cel dorit. Alegerea mijloacelor specificării este legată de alegerea sistemului algoritmizării, bazat fie pe limbajul algoritmic, în care se pot determina noile tipuri de date, acțiuni ș.a.m.d., fie pe un oarecare sistem lărgit de programare.

Să alegem ca mijloc de specificare limbajul orientat pe sintaxa limbajului Pascal. O asemenea alegere se explică printr-o serie întreagă de motive. În primul rînd, specificațiile algoritmice obținute dobîndesc concretețe și claritate, întrucît Pascal a devenit în ultima vreme în esență un limbaj al publicațiilor. În al doilea rînd, Pascal este limbajul lărgit datorită prezenței în el a mijloacelor introducerii noilor tipuri. În al treilea rînd, se ușurează posibilitatea realizării SCD după specificații algoritmice, întrucît practic pe toate calculatoarele există translatori din limbajul Pascal, iar notarea sa se află la baza majorității limbajelor utilizate ale timpului real (Pascal Paralel, Ada, Modula ș.a.).

Specificarea cerințelor se face pe un limbaj oarecum deosebit de limbajul standard Pascal, dar aceste extinderi evidente nu au caracter principial, ci sînt direcționate pentru obținerea unui grad mai mare de înțelegere și naturalețe a descrierilor. Destinația lor va fi fie descrisă, fie clară din contextul general al specificației.

Să trecem la elaborarea specificației asigurării de program SCD SFP. Specificăm mai întîi tipurile generale de date ale sistemului, a căror bază o constituie structurile informaționale utilizate în algoritmii descriși anterior ai conducerii dispeceriale. Necesitatea introducerii de noi tipuri va deveni limpede la descrierea funcționării diferitelor procese de dispecerizare. Dăm specificațiile tipurilor de date:

Type

timp, evaluare număr real;

tact__crt, numărul__culorii, numărul__tranziției,

numărul__poziției, numărul operației număr întreg;

culoare Array numărul__culorii of număr întreg;

pas Array numărul__operației, numărul__tranziției of (0,1);

eveniment (lipsește, a avut loc);

orar Array tact__crt of Array numărul__operației; numărul__ tranziției of (0,1);

rețea__ Petri__a utilajului Record

W, W: Array numărul__tranziției, numărul__poziției of (0,1);

F1, F2: Array numărul__operației of culoare;

L,G,K, K+: Array numărul__operației, numărul__tranziției of (0,1);

M: Array numărul__poziției of culoare;

V: Array numărul__tranziției of timp;

T: Array numărul__operației, numărul tranziției of timp;

Tact__crt: tact__crt;

End;

starea__ rețelei Record

W: Array numărul__tranziției, numărul__poziției of (0,1);

L: Array numărul__operației, numărul__tranziției of (0,1);

M: Array numărul__poziției of culoare;

End;

situația de rețea Record

Tact__crt: tact__crt;

case: indicele_situației: (de stat, de criză) of

de criză: (timp_pentru_adoptarea_soluției: timp)

de stat: case indecele (oprire, pornire) of

oprire: (numrul_tranziției_defecte: numărul_tranziției)

pornire: (numărul_poziției_defecte: numărul_poziției;

numărul culorii_defecte: numărul_culorii)

End

End

End

comanda Record

numărul_tranziției_ce se pornește: numărul_tranziției;

numărul_operației : numărul_operației;

numărul_culorii_prelucrat : numărul_culorii

End;

portretul_utilajului;

portretul_poziției_de transport;

portretul_comenzii_pentru_utilaj;

Descrierile ulterioare se construiesc pe baza acestor structuri care reflectă, după cum s-a spus mai devreme, logica și rezultatele funcționării tuturor proceselor sistemului conducerii situaționale dispeceriale.

Trebuie remarcat, că tipurile de date, nelegate de modelele specificabile și de procedurile de conducere, sînt prezentate sub forma numerelor de tipuri abstracte, fără dezvăluirea structurii lor interne. De aceste date se leagă doar faptul că ele conțin toată informația necesară pentru SCD. O asemenea reprezentare dă posibilitatea ca la un nivel fizic de proiectare să se formeze structura acestor date, asigurînd accesul cel mai eficient și păstrarea.

Lucrul cu datele, în conformitate cu metoda propusă de organizare a proceselor paralele, are loc cu ajutorul procesului MONITOR, care realizează accesul concret al celorlalte procese la date. Caracteristica procedurilor o constituie faptul că doar un singur proces le poate îndeplini activ. Vom reprezenta aceste proceduri Procedure entry, iar apelul lor îl vom realiza cu operatorul „monitor.numele procedurii (parametri)”. Dăm specificația generală a procesului MONITOR (necesitatea introducerii în MONITOR a operatorilor ce impun limitări ale succesiunii pornirii proceselor va fi clară din analiza ulterioară):

Process MONITOR

{comment Procesul este destinat pentru conducerea accesului la datele generale ale proceselor și întocmirea calendarului evenimentelor în sistem}

Var

D: date;

Procedure entry să se citească (x: date);

Begin

să se aleagă (x)

End;

Procedure entry să se introducă (x: date);

Begin

să se noteze (x)

End;

Procedure entry să se distrugă (x: date);

Begin

să se șteargă (x)

End;

Begin

să se aleagă (evenimentul);

să se aleagă (timpul);

să se aleagă (rețeaua_Petri_a utilajului);

For toate tranzițiile care ard ale rețelei do să se afle tranzițiile la care

(Vi -timp)0;

If tranzițiile sînt aflate then

Begin

interzicerea ANALIZATORULUI să aibă acces la date înaintea EXTRAPOLATORULUI;

tactul_crt: reprezentare întreagă (timp);

înregistrare (tact_crt)

End;

Else

If (evenimentul a avut loc) then

Begin

interzicerearea către EXTRAPOLATOR de a avea acces la date înaintea ANALIZATORULUI;

tactul_crt: reprezentare întreagă (timp);

înregistrare (tact_crt)

End;

inițializarea datelor D ale sistemului

End {Process}.

Din considerații legate de o descriere mai rațională a structurii procesului în MONITOR, sînt utilizate tip-date, reprezentînd generalizarea tuturor tipurilor de date, utilizate de celelalte procese. Pentru efectuarea descrierii celorlalte procese fără legarea de realizarea concretă a accesului la date, procedurile „să se citească”, „să se includă”, „să se distrugă” sînt făcute independent de realizare. Totodată se consideră că lucrul cu elementele datelor se face cu procedurile „să se aleagă”, „să se noteze”, „să se șteargă”. Celelalte procese le vom descrie în aceea ordine în care ele se utilizează la prelucrarea situațiilor de rețea SCD SFP.

Primul din procesele indicate, INTERPRETATORUL, servește pentru transformarea informației tehnologice exterioare față de SCD în informație internă, de rețea, și invers. El formează informația despre starea curentă reală a utilajului. Tot acest proces încheie ciclul prelucrăii situației, formînd informația de comandă pe utilajul CTA. Să prezentăm specificația procesului INTERPRETATOR:

Process INTERPRETATOR

{comment Procesul este destinat pentru prezentarea informației tehnologice în termeni de rețea și invers}

Var

util_stat: portreul_utilajului;

st_p_de trasnp: portretul_poziției_de transport;

st_crt_a rețelei: starea _rețelei;

com: comanda;

com_util: portretul_comenzii_către_utilaj;

even_crt: eveniment;

Begin

monitor.să se citească (stat_util);

monitor. să se citească (st_p_de transport);

If (a avut loc defectarea util.CTA) OR (s-a încheiat oper.tehn) Then

Begin

monitor.să se citească (st_crt_a rețelei);

With st_crt_a rețelei do

să se corecteze W, L, M;

monitor. să se includă (st_crt_a rețelei);

even_crt: a avut loc;

monitor. să se includă (even_crt)

End

End;

monitor. să se citească (com);

While sînt comenzi de conducere do

Begin

com_util: com;

monitor.să se includă (com_util);

monitor.să se distrugă (com)

End

End {Process}.

Aici și în continuare se consideră, că toate informația necesară vine din sistemele de conducere a unităților de utilaj CTA și se transmite lor fără deformări.

Următorul proces SCD, ANALIZATORUL, servește pentru evidențierea și clasificarea situațiilor ce apar. Cauzele situațiilor sînt evenimentele din sistem, provocate fie de schimbarea stării SCD SFP, fie de schimbarea stării etalon a rețelei utilajului. ANALIZATORUL face clasificarea situațiilor în situații de ștat, ce nu necestită recalcularea orarului, și în situații critice, legate de modificarea modelului etalon de rețea CTA. Specificația procesului ANALIZATOR:

Process ANALIZATOR

{comment Procesul este destinat pentru evidențierea și clasificarea situațiilor de rețea apărute}

Label 1;

Var

RPUEtal: rețea_Petri_a utilajului;

SR: starea_rețelei;

OR: orar;

even: eveniment;

TC: tact_crt;

even_crt: eveniment;

sit: situație_de rețea;

Procedure csituație

Begin

să se calculeze timpul-pentru_luarea_hotărîrii sit;

indiciu_situație.sit: de criză;

monitor.să se includă (sit)

End;

Begin

monitor.să se citească (TC);

monitor.să se citească (SR);

If (t_crt sit TC) Then

Begin

monitor.să se citească (RPUEtal);

monotur.să se citească (SR);

While nu a părut dezacord do

să se compare elementele corespunzătoare RPUEtal și SR;

If (există dezacord) Then

Begin

If (nu sînt abateri în structura rețelei ) Then

Begin

For toate pozițile, ce dau dezacord do

Begin

If (abatere în M. RPUEtal sînt provocate de reținerea opririi tranziției) Then

Begin

indiciul_situației.sit: de ștat;

indiciu.sit: oprire;

numărul_tranzi_defecte.sit: numărul tranziției ce nu s-a oprit;

t_crt.sit: TC;

monitor. să se includă (sit);

End;

Else

csituația;

If (abateri în M.RPUEtal sînt provocate de reținerea pornirii tranziției) Then

If (prezența obiectului în poziție nu este legată de imposibilitatea pornirii tranziței) Then

Begin

indiciu_situației.sit: de ștat;

indiciu_sit: pornire;

numărul_poziției_defecte.sit: numărul poz;

numărul_culorii-defecte.sit: numărul culorii;

t_crt.sit: TC;

monitor. să se includă (sit);

End

Else

csituație;

End

End

Else

{comment abatere în structura rețelei}

Begin

monitor.să se citească (timp_crt);

monitor.să se citească (OR);

să se afle în OR TC, cînd prima oară se utilizează elementul defect al rețelei;

If TC este aflat Then

Begin

vr_luării_hot.sit: TCTC;

t_crt.sit: TC;

indiciul_situației.sit:de criză;

monitor. să se distrugă (OR);

monitor. să se includă (sit);

End

Else

{comment Nu este abatere în structura rețelei}

GOTO 1

End

End

End {Process}.

Primele acțiuni ale procesului sînt cheia pornirii sale. Dacă pentru tactul curent al lucrului sistemului elaborat cu MONITORUL, proces ANALIZATOR a lucrat deja, ultimul nu se pornește. În caz contrar se face inițializarea aleatoare o singură dată a procesului. Logica generală a procesului corespunde algoritmului evidențierii situațiilor de producție.

Următorul proces, EXTRAPOLATORUL, servește simultan pentru obținerea orarului în cazul apariției situației critice și schimbării stării etalon a rețelei utilajului. O asmenea cumulare este determinată de posibilitatea evitării dublării acțiunilor pentru schimbarea situației rețelei. Logica generală și datele de bază ale procesului au fost descrise anterior și corespund des. 6.3. Suplimentar la tipurile descrise se introduc variabilele de lucru:

PK – vectorul pașilor rețelei utilajului pentru numărul k al tactului timpului;

PE – vectorul evaluărilor pașilor după tactul curent;

R – vectorul numerelor pașilor;

timpul de model – timpul repartizat pentru efectuarea procesului

În descrirea procesului sînt introduse funcțiile de transpunere a matricelor și de transformare a timpului curent . Pornirea procesului EXTRAPOLATOR, la fel ca și a procesului ANALIZATOR, se face pentru tactul curent al sistemului doar o dată specificația procesului EXTRAPOLATOR:

Process EXTRAPOLATOR

{comment Procesul este destinat pentru obținerea stării ordinare următoare a rețelei după orarul stabilit dinainte sau prin întocmirea unui nou orar}

Label 1,2,3;

Var

SR: starea_rețelei;

RPICrt, RPULucru: rețea_petri_utilaj;

R: pas

PK: Array [tact_crt, numărul_pasului] of pas;

PE: Array [tact_crt, numărul_pasului] of evaluare;

R: Array [tact_crt, numărul_pasului] of (0, 1);

sit: situație_de_rețea;

OR: orar;

timp_de model; timp_crt: timp;

TC: tact_crt;

Function

transp (x: Array [întreg, întreg] of (0, 1): Array [întreg, întreg] of (0, 1);

Function

propoziție întreagă (x: număr real): întreg;

Begin

monitor.să se citească (sit);

monitor. să se citească (TC);

monitor. să se citească (RPUCrt);

If (tact_crt. RPUCrt TC) or (indiciu_situației, sit_de criză) and (t_crt.sitTC)

Then

Begin

monitor. să se citească (vr_crt);

RPULucru:RPUcrt;

timp_de model: vr_crt;

If (indiciul_situației.sitde criză) and (t_crt.sitTC) Then

Begin

monitor. să se citească (SR);

End;

1: With RPULucru do

For toate tranzițiile declanșate do

Begin

If (V[i] – timp de model 0 Then

Begin

să se amplaseze 1 în pozițiile corepunzătoare K; V[i]:

End

V[i]: V[i] – timp_de model

End

If (nu sînt tranziții care s-au declanșat) Then GOTO 2;

M:M+ transp ((KW+)F2);

să se exludă tranzițiile stinse din L, V;

2: If (indiciu_situaței.sit de criză) Then

Begin

{comment Generarea pașilor rețelei}

For toate tranzițiile nearzînde ale rețelei do

For toate destinațiile permise din G do

If M transp (KW)F2) Then pe baza timpului_pentru_luarea_hotărîrii. sit să se formeze vectorul PK pentru tactul curent;

{comment Alegerea celui mai bun pas}

For toate elementele PK do

pe baza timpului_pentru_luarea_deciziei.sit să se construiască PK conjugat vectorul evaluării PE;

să se includă în P și K – pasul cu cea mai bună evaluare;

End

Else

Begin

monitor. să se citească (OR);

să se formeze K din OR pentru tactul curent

End

If este aflat K pentru tactul curent Then

Begin

M:M+ transp ((KW+)F1);

să se includă tranzițiile aprinse în L; după matricea duratelor operației să se formeze V;

tact_crt.RPULucru:TC;

End

{comment Modificarea tactului de timp}

If indiciul_situației.sitde criză Then

Begin

For toate tranzițiile rețelei do

să se afle tranziția i cu timpul cel mai mic de declanș;

timp_de model :V[i];

TC:propoziție întreagă (timp_de model);

End

Else GOTO3;

{comment Verificarea condiției terminării}

If (este obținută marcare de neimpas) Then

GOTO 1;

indiciul_situației.sit:de ștat;

numărul_tacturilor:propoziție întreagă (timp_de model) – propoziție întreagă (timp_crt)

For numărul de tacturi do

OR [TC] :PK[TC, R(TC)];

monitor.să se includă (OR)

End

With RPUCrt do

M:M+transp ((PK[TC, R(TC)]W)F1);

RPULucru:RPUCrt;

3: monitor să se includă (RPULucru)

End

End {Process}.

Des. 6.3. Schema extrapolării situațiilor critice de produse.

1, …, k – tacturile de timp de lucru al modelului de rețea a obiectului (MRO). I – situație curentă de producție (SP); II – calcularea evaluărilor , a urmărilor SP după modelul etalon de matrice a obiectului ; III – alegerea pasului j ordin MRO după regula ; IV – oragnizarea revenirilor de pe tactul i pe cel (i-p) la ; V – imitarea pașilor posibili ai MRO complet pentru următorul tact; VI – evidențierea succesiunii optime a pașilor MRO (opt); VII – extrapolarea SP terminală sau limitată de orizont.

Trebuie observat, că operațiile generării pașilor rețelei și alegerii celui mai bun dintre ei, corespunzători pașilor 3-5 ai algoritmului extrapolării, după cum s-a arătat anterior, depind în mod esențial de timpul acordat îndeplinirii procesullui. Acțiunile corepunzătoare se aleg pe baza timpului cheltuit pentru efectuarea procesului după o metodă sau alta.

Ultimul în ciclul prelucrării situațiilor de rețea este procesul FORMATOR, destinat elaborării comenzilor conducerii în scopul lichidării situațiilor de ștat apărute:

Process FORMATOR;

{comment Procesul este destinat pentru formarea comenzilor de lichidare a situațiilor de ștat}

Var

sit: situație;

com: comanda;

RPUEtal: rețea_Petri_a utilajului;

Begin

While sînt situții de ștat do

Begin

monitor.să se citească (sit);

If indiciu.sit oprire Then să se elaboreze averismentul;

If indiciu.sit pornire Then

Begin

monitor.să se citească (RPUEtal);

monitoru_culorii_prelucr_com: numărul_culorii_defecte.sit;

să se formeze numărul_tranziției _ce se pornește.com;

numărul_operației.com după numărul_poziției_defecte.sit și matricele W, K RPUEtal;

monitor.să se includă (com);

monitor.să se distrugă (sit);

End

End;

End

End {Process}.

Comenzile de conducere se împart totodată în două tipuri – active și pasive. Comenzile active necesită efectuarea anumitor acțiuni în CTA pentru lichidarea situațiilor de producție. Comenzile pasive servesc pentru elaborarea avertismentelor despre abaterile apărute, ce nu provoacă situații critice pe tactul respectiv de lucru al sistemului. Aceste situații sînt legate de abaterile de la etalonul duratelor efectuării operațiilor, abateri permise [admise] pe tactul respectiv. Stocarea reținerilor la efectuarea operațiilor, provocate de abaterile de un asemenea fel, poate ulterior să servească drept cauză a unei situații critice, și în legătură cu aceasta avertismentele despre aceste abateri trebuie să fie legate de corectarea valorilor etalon ale duratelor efectuării operațiilor.

Să analizăm mai atent particularitățile funcționării multiptogram a proceselor specificate. Pentru aceasta să analizăm stările caracteristice ale sistemului. Asemenea sînt stările determinate cu momentele următoare:

au absența dezacordului între stările obiectului conducerii și modelul său de rețea etalon;

cu prezența dezacordurilor, provocate de modificarea modelului etalon al rețelei;

cu prezența dezacordurilor provocate de modificările (evenimentele) în obiectul conducerii;

cu prezența dezacordurilor provocate de modificări atît în obiectul conducerii, cît și în modelul său.

Să analizăm funcționarea MONITOR-ului în cele patru stări caracteristice. În prima stare procesele funcționează asincron și independent unul de altul, adresindu-se prin MONITOR către datele generale. Procesele ANALIZATOR și EXTRAPOLATOR așteaptă apariția evenimentului curent în sistem, eveniment generat de MONITOR (vezi specificația procesului MONITOR). INTERPRETATORUL chestionează starea CTA și formează comenzile pentru utilaj. FORMATORUL transformă mulțimea situațiilor de ștat în comenzi pentru lichidarea lor.

În a doua stare a sistemului, cu MONITOR-ul se evidențiază apariția evenimentului curent, legată de schimbarea marcării modelului etalon de rețea. În urma acestui eveniment, fixat în valoarea tactului curent al timpului de sistem, sînt posibile diferite variante ale pornirii proceselor. Succesiunea de lucru a proceselor INTERPRETATOR și FORMATOR nu influențează asupra rezultatelor funcționării întegului sistem cu precizia pînă la timpul unui ciclu de chemări ale celorlalte procese. Ordinea pornirilor proceselor ANALIZATOR și EXTRAPOLATOR are un caracter principial, întrucît dacă EXTRAPOLATOR-ul nu va realiza schema necesară a stării rețelei etalon, ANALIZATOR-ul nu va elabora situațiile de rețea corespunzătoare tactului de timp analizat. EXTRAPOLATOR-ul la rîndul său nu va efectua prelucrarea, posibil a situațiilor critice de rețea ce au loc. În legătură cu posibilitatea apariției unei asemenea incorectitudinii devine de înțeles introducerea în MONITOR a interdicției pornirii procesului ANALIZATOR înaintea procesullui EXTRAPOLATOR.

În starea a treia, la pornirea procesului EXTRAPOLATOR înaintea procesului ANALIZATOR, este posibilă reținerea cu un tact întreg a prelucrării situațiilor critice, în legătură cu care fapt în MONITOR sînt de asemenea introduse acțiuni corespunzătoare de conducere. Starea a patra corespunde în esență celei de a doua. Diferența constă doar în faptul, că se modifică de asemenea starea obiectului conducerii, iar dezacordul între noua stare reală a rețelei formată de procesul FORMATOR, și noua stare etalon a rețelei, obținută cu ajutorul procesului EXTRAPOLATOR, se va determina cu procesul ANALIZATOR.

În încheiere mai trebuie atrasă atenția asupra următoarelor. Logica analizată a lucrului sistemului este proprie obiectelor CTA, ale căror durate de executare a operațiilor, corespunzătoare tactului de lucru SCD, depășesc ciclul prelucrării situațiilor. În caz contrar sistemul dispecerizării va forma situații de rețea, ce nu corespund stării curente a obiectului conducerii și succesiunii etalon a efectuării operațiilor. În legătură cu aceasta parametrul cel mai important al SCD situațional este durata ciclului de prelucrare a situațiilor de rețea. Specificul construirii sistemului și procedurilor conducerii situaționale dispeceriale SCD permite, în funcție de abordarea aleasă pentru realizarea SCD la nivelul fizic al proiectării, să se modifice în limite largi această durată. Totodată diminuarea sa esențială poate fi atinsă pe complexul informațional-de conducere multiprocesor de înaltă productivitate, cînd, în particular fiecărui proces la comadă îi este repartizat un proces separat.

6.3. Machetă program a sistemului conducerii dispecerale

Elaborarea sistemelor, ale căror dificultăți de descriere formală și analiză sînt comensurabile cu complexitatea întregului poces al elaborării lor, a condiționat necesitatea creării unor metode și mijloace speciale de automatizare a proiectării lor.

Una dintre aceste metode relativ noi este machetarea de program, care a fost propusă la începutul anilor 80 în legătură cu apariția unei noi tehnologii de programare-tehnologia autoformalizării cunoștințelor profesionale.

Macheta de program (MP) a sistemului este un model al sistemului, creat pe calea descrierii sale de program. Elaborarea MP se numește scopul creării unor sisteme calitative, trainice din punct de vedere al realizării, scopul ei principal este de a da descrirea și mijlocul cercetării structurii și a funcțiilor realizate de sistem doar pe baza cerințelor exterioare, nelegate de caracteristicile concrete ale mijloacelor realizării sistemului. Totodată baza aplicării MP o constituie realizarea de program și cercetarea automatizată a proceselor și datelor SC SFP. O asemenea utilizare MP dă posibilitatea concretizării cerințelor către sistem, verificării corectitudinii modelelor întregului sistem, diferitelor sale procese și structuri de date. Se simplifică în mod esențial realizarea ulterioară SCD după macheta sa de program, care la anumite limitări este o variantă a asigurării de program a sistemului.

Mijlocul preferat al realizării MP îl reprezintă calculatoarele personale (CP), a căror utilizare pentru machetarea SCD SFP are o serie întreagă de avantaje. Mijloacele bazate ale introducerii/scoaterii de text color și grafic a informației, permit în acest caz să se efectuieze simplu și concret deschiderea SCD SFP și să se realizeze comanda procesului cercetării lor. Prezența la CP a mijloacelor dezvoltate de bază de program, ce includ translatori practic din toate limbajele algoritmice, între care și din limbajele timpului real, precum și a sistemelor de program specializate de modelare și proiectare dă mari posibilități pentru alegerea celor mai eficiente mijloace de construire a SCD SFP. CP se înzestrează cu mijloace de schimb intermașini și de susținere a întreruperilor, în legătură cu care fapt există posibilitatea construirii MP SCD SFP, realizată sub forma unui sistem distribuit ce include, în special, mijloace reale de program SC SFP. În sfîrșit, utilizarea CP în sistemele automatizrii și în SC SFP a devenit destul de tradițională, cea ce permite folosirea efectivă a MP SCD SFP, realizată pe clasa analizată de calculator, la crearea asigurării de program a sistemelor de comandă SFP.

Să trecem la analiza machetei de program SCD SFP, elaborată în conformitate cu abordarea propusă a organizării sistemului la Institutul de informatică și automatizări din Leningrad al Acad. de Științe a URSS. MP a sistemului dispecerizării automatizate (DISA) funcționează sub conducerea sistemelor operaționale MS DOS și UCSD pe CP corespunzătoare cu caracteristicile necesare pentru lucrul machetei. Toate modulele de program MP sînt scrise în limbajul algoritmic Pascal cu utilizarea pachetelor Turbo Pascal și Turbo Grafix și sînt autodocumentabile. Macheta de program DISA este destinată pentru efectuarea următoarelor acțiuni tip:

cercetarea în diferite regimuri a funcționării SCD SFP, ce lucrează cu CTA diferite ca structură și discipline de conducere dispecerială;

controlul procesului de conducere dispecerială SFP;

culegere a informației statistice despre funcționarea machetei în scopul evaluării calității sistemului proiectat,

Elaborarea MP DISA s-a efectuat pe baza specificațiilor proceselor și datelor SCD SFP, precum și a abordării propuse de organizare a sistemului. În legătură cu aceasta MP DISA constă din setul de module independente de program, ce corespund diferitelor procese SCD SFP și interacționează prin adresarea către datele generale ale sistemului. Modulele machetei sînt destinate pentru:

conducerea dispecerială automată SFP la nivelul sectorului;

modelarea lucrului complexului tehnologic SFP în conformitate cu duratele efectuării operației prin OCT SFP separate;

ferestre interactive de introducerea/ afișare și modificarea informației despre SCD SFP;

conducerea prin mijloace de menu cu regimuri de machetare;

emiterea informației despre evenimentele petrecute la funcționarea machetei;

culegerea statisticii și afișarea informației generalizate despre funcționarea complexului tehnologic SFP după modelul său.

Structura machetei include următoarele tipuri de module de program:

proceduri funcționale determinate prin destinația machetei;

proceduri service destinate introducerii/ afișării și modificării informației despre SCD SFP, controlul intrevalelor de timp în funcționarea sistemului, formarea statisticii ș.a.;

monitor care realizează pornirea, oprirea, schimbul regimurilor de lucru ale machetei SCD SFP.

Des. 6.4. Structura generală a machetei DISA.

Structura generală a machetei DISA se reprezintă pe des. 6.4, unde se dau modulele de bază ale machetei, legăturile informaționale și de comandă dintre ele, precum și structurile generale ale datelor MP. Meritele machetei DISA se determină în principal prin abordarea organizării SCD SFP. Se remarcă specificul utilizării modelului algoritmic SCD în macheta DISA. Apelul consecutiv al procedurilor MP DISA, care, după cum s-a arătat anterior, sînt independente după comandă una de cealaltă, a condiționat utilitatea și caracterul normal al amplasării acestor proceduri în memoria calculatorului cu utilizarea overlayer-erilor ceea ce a permis să se reducă considerabil volumul modulului de încărcare al machetei. Legătura procedurilor doar prin date asigură susținerea simultana a cîtorva versiuni ale machetei cu proceduri de conducere dispecerială diferite ca complexitate și structură. Tot această particularitate a machetei simplifică considerabil cercetarea SCD în diferite modele CTA SFP.

În machetă s-au utilizat fișiere structurate de date, ceea ce a permis să se simplifice considerabil și să se accelereze schimbul informațional în procesul machetării SCD spre deosebire de fișierile de text. În același timp s-a complicat procedura schimbului de informație între proiectant și machetă. De aceea s-a elaborat o procedură specială de overlay, care transformă informația din fișierile de lucru ale machetei spre un tip comod pentru operator. În machetă sînt incluse de asemenea mijloace care permit realizarea cercetării în timp real, cu utilizarea întreruperii de la timer-ul autonom CP. În afară de aceasta, există o procedură pentru culegerea și emiterea informației statistice despre funcționarea machetei. Funcționarea machetei se realizează sub comanda monitorului, ce dă următoarele regimuri de lucru MP:

regim1 – trasarea procesului dispecerizării SFP după pașii prelucrăii operațiilor tehnologice (regim de dispecerizare manuală);

regim 2 – dispecerizare automată SFP;

regim 3 – introducere/ afișare, modificare a datelor;

regim 4 – terminarea procesului de machetare.

Regimul 1 provoacă acțiunile corespunzătoare pentru prelucrarea situațiilor de producție de ștat și critice, legate de destinația operațiilor pe OCT, generarea operațiilor de transport, modelarea efectuării operațiilor de transport, modelarea efectuării operațiilor cu obiectele complexului tehnologic SFP, prelucrarea deranjamentelor și refuzurilor OCT SFP. Fiecare nouă acțiune începe după o comanda de pe tastatura CP.

Regimul 2 este legat de apelul ciclic automat al procedurilor conducerii dispeceriale și al modelului CTA SFP. Încheierea regimului 2 se face fie la comanda operatorului, fie la încheierea efecturării temei de producție.

În regimul 3 se realizează următoarele acțiuni cu fișierele machetei:

înregistrarea inițială a informației;

emiterea informației pe ecranul display-ului;

modificarea diferitelor înregistrări ale fișierilor;

tipărirea informației;

copierea și distrugerea fișierilor.

Regimul 4 este legat de înregistrarea statisticii despre funcționarea SFP, de închiderea tuturor fișierilor machetei și de adresarea către sistemul operațional.

Lucrul machetei în toate regimurile este însoțit de formarea și emiterea informației corespunzătoare despre starea curentă și evenimentele petrecute în sistemul cercetat.

Des. 6.5. Exemple de ferestre (windows) de dialog al sistemului DISA.

Cercetarea machetei cu diferite modele CTA, între care la crearea sistemelor de conducere SFP în întreprinderile industriale, a confirmat corectitudinea modelelor propuse în lucrare precum și caracterul complet al specificațiilor SCD SFP obținute și al diferitelor sale procese și date.

După cum s-a arătat deja, utilizarea MP DISA la crearea sistemelor reale de conducere dispecerială este realizabilă la următoarele limitări:

la durata operației de elaborare a influențelor de comandă;

la volumele informației permanente și modificabile despre procesul dispecerizării la realizarea pe CP concret.

După cum se vede, metodele de rețea elaborate și mijlocele dispecerizării sînt aplicabile nu numai la conducerea producției. Proceduri analogice pot fi utilizate la dispecerizarea mișcării trenurilor pe calea ferată, a lucrului executanților la efectuarea de către ei a unei oarecare mulțimi de teme, a proceselor în sistemele de calcul ș.a. În particular, pe aceleași principii a fost realizat sistemul dispecerizării organizaționale (DISO). Funcțiile principale ale sistemului DISO sînt –

formarea informației despre începutul și încheierea efectuării temei următoare de către grupul de executanți;

controlul stării curente a temelor ce se îndeplinesc;

culegerea și emiterea informației statistice despre lucrul executanților.

Structura sistemului DISO include proceduri ale machetei DISA cu modificarea evidentă a tehnologiei: PO în DISO corespund datelor problemei, OCT – executanți ș.a.m.d. Fișierile generale ale sistemului conțin informația despre teme, executanți și documente în momentul de timp respectiv. Pe des. 6.5 se dau ferestrele de dialog ale sistemului DISO. Limitarea de bază la utilizarea sistemului DISO au devenit volumele mari de informație introdusă, păstrată și transmisă. În același timp utilizarea unor codări speciale ale informației organizaționale, precum și orientarea spre CP cu harduri mari, de ordinul 100 Gbytes, ai informației permit practic să se scoată această limitare.

ÎNCHEIERE

Formalismele analizate mai sus, bazate pe rețele Petri, se dovedesc un instrument puternic de modelare a sistemelor dinamice, totodată în fiecare caz concret este utilă folosirea uneia dintre modificațiile lor, ce constă, pentru aplicațiile tradiționale, în introducerea limitărilor impuse funcționării elementelor rețelei. Una dintre aplicații este modelarea conducerii sistemelor discrete, și în special a unei atît de importante subclase a lor din punct de vedere al practicii, ca SFP. Complexitatea de structură și funcțională a unor asemenea sisteme face necesară utilizarea modelelor specifice la formarea conducerii SFP pe mulțimea discretă a situațiilor de producție, care în general sînt independente și se determină prin raporturile stărilor curentă (reale) și ideală (dată după model) ale subiectului. Crearea unor asemenea modele necesită elaborarea unei modificații corespunzătoare problemo-orientate a rețelelor Petri, descrierea și utilizarea unei asemenea modificații pentru cazul sistemului conducerii dispeceriale SFP se dă în lucrare. Dezvoltarea pe această bază a metodelor proiectării algoritmilor fiabili de optimizare, crearea translatorilor în limbajele utilizate în conducere (C, Modulla 2 ș.a.), precum și a interfeței utilizatorului pentru sistemele de program de acest tip vor necesita, se pare, eforturi mari ale specialiștilor.

Un interes deosebit îl prezintă problemele construirii și cercetării modelelor în sistemele inteligenței artificiale, pentru care este necesară crearea unei suprastrucuturi intelectuale speciale, orientate spre aparat (mai) universal și flexibil decît în rețelele Petri ordinare. În această calitate poate să se utilizeze formalismul introdus al rețelelor Petri algebrice. În această direcție sînt multe probleme nerezolvate și, ce este mai important, abia urmează să se elaboreze modalitatea cea mai economică și flexibilă de programare a rețelelor algebrice. În întregime rețelele Petri sînt un domeniu folositor și de perspectivă al cercetărilor, în care se unifică, îmbogățîndu-se una pe cealaltă, eforturile specialiștilor din cele mai diverse orientări.

Bibliografie

1.V. Kotov. Seti Petri . Moscova. : Nauka. 1984.

2.Reisig. W. Rețele Petri. Springer-Verlag. 1982.

3.Peterson Dj. Teoria setei Petri i modelirovanie sistem. Moscova. Mir. 1984.

4. Janicki R. A caracteriyation of concurrency-lika relations//LNCS. 1979.

5.Nielsen M. Petri Nets.: Event structures and domains/ M. Nielsen, G. Plolkin, G. Winskel//

Teor. Computer Sci. 1981.

6. Mazurkiewicz A. Traces, histories, grahs; Instances of a process monoid// LNCS. 1984.

7. Bar R. Programarea in limbajul Ada. Moscova. Mir. 1983.

8. Dijkstra E. W. Co-operating siquential process in programing languages/ Ed. F. Genuys.

New-York; Acad. Press, 1968.

9. Proceeding of the 2hd International Conference of FMS. London. IFS Ltd a North-Holland publ.co

1983.

10. Petri C. A. Concurrency// LNCS. 1980.

11. Gestaltungsloesungen intergrierter Fertigungen/ Hrsg. S. Wirth, K. Rudolph. Berlin: Verlag

Technik, 1986.

12. Goolahan J. Timing riguirement for time-driven system using augment Petri Nets// IEEE

Trans. SE. 1983.

13. M. Popa. Concurrently firing in PrT-Petri Nets, Anuarul Univ. București., 1993.

14. A. A. Leskin, P. A. Malțev, A. M. Apiridonov. Seti Petri v modelirovanie i upravlenii,

Leningrad, 1989.