1.1. Sisteme dinamice cu stri discrete, pilotate de evenimenteAceast sectiune are drept scop introducerea conceptului de sistem dinamic cu evenimente discrete, plecnd de la notiuni si tipuri de comportri care se presupun cunoscute cititorului familiarizat cu domeniile de studiu traditionale ale automaticii. Aspectele fundamentale sunt legate de structura discret a spatiului strilor si de evolutia pilotat de evenimente. Aceste aspecte sunt inital comentate cu referire la anumite procese fizice, concrete, iar ulterior sunt formalizate printr-o definitie cu caracter general. Un accent deosebit se pune pe evitarea, de la bun nceput, a posibilelor confuzii dintre sistemele dinamice cu evenimente discrete si sistemele dinamice discrete n timp. Prezentri ale problematicii introductive ce face obiectul de studiu al sectiunii curente pot fi gsite si n studiile monografice (Cassandras, 1993) si (Cassandras et al, 1995).Index si dictionar romn-englez1.1.1. Sisteme dinamice cu stri continue si sisteme dinamice cu stri discrete1.1.2. Sisteme dinamice pilotate de timp si sisteme dinamice pilotate de evenimente1.1.3. Conceptul de sistem dinamic cu evenimente discrete 1.1.1. Sisteme dinamice cu stri continue si sisteme dinamice cu stri discreten automatica clasic, formalizarea matematic este orientat asupra modelelor cu stri continue, pentru care spatiul strilor este o submultime a lui n. Reprezentrile de stare liniare sau neliniare, continue n timp, sau discrete n timp, constituie binecunoscute exemple de astfel de modele, utilizate n studierea fenomenelor fizico-tehnice (si nu numai).Totusi, acest mod de a privi si ntelege modelarea proceselor nu este unic, ntruct nenumratele aplicatii practice pun n evident sisteme pentru care spatiul strilor este o multime discret, numrabil (finita sau nu).Exemplul 1.1.1.Considerm functionarea recipientului din fig. 1.1.1 (a), caracterizat prin evolutia nivelului de fluid x(t). Variabila de stare x ia valori n multimea s0, xmaxt, iar n fig. 1.1.1 (b) este reprezentat o posibil evolutie (traiectorie) a lui x.Fig. 1.1.1. Functionarea recipientului din Exemplul 1.1.1Nu ntotdeauna, ns, prezint interes cunoasterea efectiv a valorii luate de x n intervalul s0, xmaxt. De pild, ne-ar putea interesa numai urmtoarele aspecte privind functionarea rezervorului:dac recipientul este gol;dac recipientul contine fluid sub cota xmax;dac fluidul a atins cota xmax.n acest caz, putem considera o variabil de stare discret y {0,1,2}, unde valorile 0, 1 si 2 sunt asociate, n ordine, situatiilor mentionate mai sus. n fig. 1.1.1 (c) este prezentat evolutia lui y(t), corespunztoare evolutiei lui x(t) din fig. 1.1.1 (b).Conform diagramei din fig. 1.1.1 (c), se constat c tranzitiile dintr-o stare discret n alta corespund unor evenimente care se produc ntr-o manier asincron:tranzitia din 0 n 1 - n rezervorul complet gol tocmai a nceput s se acumuleze fluid;tranzitia din 1 n 0 - rezervorul tocmai s-a golit complet;tranzitia din 1 n 2 - fluidul tocmai a atins cota maxim admisibil xmax;tranzitia din 2 n 1 - nivelul de fluid tocmai a sczut sub cota maxim admisibil xmax. 1.1.2. Sisteme dinamice pilotate de timp si sisteme dinamicepilotate de evenimenteModelele matematice de tip intrare-iesire sau intrare-stare-iesire, continue sau discrete n timp sunt guvernate de o variabil independent, cu semnificatie temporal. Astfel evolutia acestor modele se raporteaz la timpul continuu sau discret care se scurge ntr-o manier uniform.Sistemele cu stri discrete pot pune ns n evident o comportare guvernat de evenimente asincrone, care se petrec la momente de timp repartizate neuniform.Exemplul 1.1.2.Considerm functionarea magaziei automate din fig. 1.1.2 (a), caracterizat prin evolutia numrului de piese depozitate x(t).Se presupune c n magazie se introduce sau se extrage cte o singur pies si c durata unei operatiuni de introducere sau extragere este neglijabil. Se mai presupune c magazia are o capacitate suficient de mare astfel nct s nu se ajung la ocuparea complet a spatiului de depozitare. Sa considera m drept mrimi de intrare functiile:pentru a preciza momentele de introducere a pieselor s ipentru a preciza momentele de extragere.Se considera c introducerea si extragerea nu pot avea loc simultan, adic:Cu aceste ipoteze, o ecuatie de stare ar putea fi scris sub forma:unde t+ > t noteaz momentul de timp imediat urmtor lui t.n fig. 1.1.2 (b) se prezint evolutia numrului de piese din magazie (traiectoria lui x(t)) pentru urmtorul caz:momente de introducere (u1(t) 1):momente de extragere (u2(t) 1):unde tk < tk+1, k ? 1,..., 12.Fig. 1.1.2. Functionarea magaziei automate din Exemplul 1.1.2 Se constat c tranzitiile sistemului dintr-o stare n alta sunt dictate de ctre fluxul de evenimente tip introducere s i respectiv fluxul de evenimente tip extragere. Se observ c alura diagramei din fig. 1.1.2 (b) rmne neschimbat dac valorile numerice tk , k?1,...,13, se modifica , atta vreme ct succesiunea acestor momente rmne aceeasi. Multimea evenimentelor este o multime discret, numrabil (finita sau nu). 1.1.3. Conceptul de sistem dinamic cu evenimente discreten baza discutiilor din paragrafele precedente, formulm urmtoarea definitie pentru a ne referi la clasa sistemelor dinamice cu stri discrete, pilotate de evenimente. Se numeste sistem dinamic cu evenimente discrete (eng. discrete event dynamic system) un sistem dinamic care posed urmtoarele dou proprietti:Spatiul strilor este o multime discret.Mecanismul de tranzitie a strilor este pilotat de evenimente cu aparitie asincron.Conform acestei definitii, construirea unui model de tip sistem cu evenimente discrete necesit identificarea a dou multimi discrete (finite sau nu):X - spatiul strilor,E - multimea evenimentelor,precum si formularea unei descrieri matematice a legittilor prin care aparitia evenimentelor din multimea E determin tranzitionarea n spatiul strilor X.n spiritul acestei definitii se observ imediat c magazia automat din Exemplul 1.1.2 ar nceta s mai constituie un sistem cu evenimente discrete n cazul cnd introducerea si extragerea din magazie s-ar realiza sincron cu un ceas de perioad T > 0, apriori cunoscut. ntr-o atare situatie, am avea de a face cu un sistem cu stri discrete pilotat de timp, tranzitiile neputnd avea loc dect la momentele t ? kT, k . n realitate, functionarea unei magazii automate este conditionat de ritmul n care se produc piesele (adic intrarea n magazie) si de cerinta de distribuire a pieselor (adic iesirea din magazie). ntruct, n general, aceste fenomene nu pot fi privite (n sensul de modelate matematic) ca sincrone cu un anumit ceas de perioad cunoscut aprioric, necesitatea utiliza rii, n modelare, a conceptului de sistem cu evenimente discrete apare evident.Mai remarcm faptul c evenimentele din multimea E pot fi privite ca realiznd o structur de ceas asincron (neperiodic) care piloteaz desfsurarea tranzitiilor n X. Aceast structur de ceas asincron trebuie nteleas ca un corespondent al ceasului periodic din cazul sistemelor pilotate de timp. Totusi, ca si problematic a comportrii, deosebirile sunt fundamentale, ntruct ceasul asincron elimin tocmai conditia de periodicitate necesar studierii dinamicii sistemelor discrete n timp. 1.2. Modele si tehnici utilizate n studierea sistemelor cu evenimente discreteSpecificul dinamicii sistemelor cu evenimente discrete necesit un suport matematic adecvat pentru modelare, analiz si sintez. Explorarea dinamicii se poate realiza sub raport calitativ (viznd comportarea logic, independent de timp) si/sau sub raport cantitativ (viznd comportarea dependent de timp). Pn n prezent nu exist o teorie unificat a sistemelor dinamice cu evenimente discrete, modelele si tehnicile utilizate aflndu-si sorgintea n diferite domenii ale matematicii cum ar fi: teoria retelelor Petri, teoria automatelor, teoria sistemelor de asteptare, teoria proceselor Markov etc.Treceri n revist ale diverselor maniere de abordare a studierii sistemelor cu evenimente discrete pot fi gsite n (Cao and Ho, 1990), (Cassandras, 1993) si (Cassandras, et al, 1995).Index si dictionar romn-englez1.2.1. Sistemele cu evenimente discrete - parte integrant a teoriei sistemelor 1.2.2. Aspecte calitative si cantitative n explorarea dinamicii sistemelor cu evenimente discrete1.2.1. Sistemele cu evenimente discrete - parte integrant a teoriei sistemelorCunostintele prezentate n sectiunea anterioar ne permit s extindem viziunea asupra comportrii sistemelor dinamice, constatnd c sistemele cu evenimente discrete constituie o clas de sisteme neliniare, dup cum reiese din diagrama prezentat n fig. 1.2.1.ncorporarea sistemelor cu evenimente discrete n diagrama din fig. 1.2.1 este absolut fireasc, ntruct aceast clas de sisteme descrie un anumit tip de dinamic (comportare), care nu este acoperit, la nivel conceptual, de celelalte clase de sisteme cu care se opereaz curent n diferite domenii ale automaticii. Constata m, asadar, c sistemele cu evenimente discrete constituie o parte integrant a Teoriei Sistemelor, ca disciplin general ce ofer suportul matematic riguros, necesar modelrii si investigrii comportamentului proceselor fizico-tehnice. Fig. 1.2.1. Specificul comportrii sistemelor cu evenimente discrete, raportat la o clasificare de ansamblu a sistemelor dinamice Ceea ce difer ns de la o clas de sisteme dinamice la alta este tipul de instrument matematic la care se face apel pentru descrierea ct mai precis a specificului dinamicii. Astfel este de asteptat faptul c pentru modelarea, analiza si sinteza sistemelor cu evenimente discrete s utiliza m un suport teoretic propriu studierii acestei clase de sisteme. 1.2.2. Aspecte calitative si cantitative n explorarea dinamicii sistemelor cu evenimente discreten definitia formulat n paragraful 1.1.3 nu s-a fcut nici o precizare asupra momentelor de timp cnd apar evenimentele din multimea E, cu exceptia faptului c producerea lor este asincron. (Subliniem, nc o dat, c prin aceast producere asincron a evenimentelor, sistemele cu evenimente discrete se delimiteaz strict de sistemele a cror evolutie este pilotat de o variabil temporal uniform).n cazul n care modelul matematic nu contine nici o informatie asupra momentelor de timp cnd se produc evenimentele e1, e2,..., en,... E, avem de a face cu un model logic sau netemporizat (eng. untimed model). Astfel de modele pot pune n evidnt numai propriettile de tip calitativ ale comportrii sistemelor. Explorarea propriettilor calitative se bazeaz pe tehnici calitative, ce utilizeaz drept formalism matematic fie teoria retelelor Petri, fie teoria automatelor.n schimb, n cazul cnd evenimentele din E sunt prezentate sub forma unor perechi (e1, t1), (e2, t2),..., (en, tn)... n care t1, t2,..., tn,... noteaz momentele de aparitie a evenimentelor respective, avem de a face cu un model temporizat (eng. timed model). Astfel de modele pot pune n evident proprietti de tip cantitativ ale comportrii sistemelor. Cunoasterea momentelor de timp t1, t2,..., tn,... poate fi de factur determinist sau probabilistic, modelele temporizate divizndu-se n modele deterministe si modele stocastice, dup cum reiese si din diagrama de clasificare prezentat n fig. 1.2.1. Explorarea propriettilor cantitative se bazeaz pe tehnici cantitative. Initial, tehnicile cantitative au fcut apel la aparatul matematic specific teoriei proceselor Markov sau teoriei sistemelor de asteptare. Ulterior au fost realizate extinderi ale teoriei retelelor Petri si teoriei automatelor, capabile s nglobeze si aspectul temporal, demonstrndu-se totodat c aceste extinderi devin compatibile cu tehnicile cantitative amintite anterior.Este evident c propriettile de natur calitativ posed un grad mult mai mare de generalitate dect cele cantitative, n sensul c un numr de sisteme ce au o comportare identic sub raport calitativ, pot diferi mult ntre ele atunci cnd sunt luate n discutie si aspecte cantitative.Dup cum reiese din aceast discutie sumar, teoria sistemelor cu evenimente discrete poate fi abordat prin intermediul a mai multor formalisme. n expunerea noastr, ne vom axa pe formalismul retelelor Petri, ntruct reprezenta rile de acest tip sunt dublate de un suport grafic cu impact deosebit de eficient asupra ntelegerii la nivel intuitiv a dinamicii sistemelor cu evenimente discrete. Pe parcursul primului volum ne vom opri la studierea tehnicilor calitative, urmnd ca n cel de-al doilea, s ne ocupm de tehnicile cantitative. n msura n care economia expunerii o va cere, vom face si unele referiri la celelalte formalisme matematice utilizate n teoria sistemelor cu evenimente discrete. 1.3. Proprietti calitative puse n evident de comportarea unor sisteme cu evenimente discrete, tipicen scopul dezvoltrii unui fundament intuitiv ct mai solid pentru studierea aspectelor de factura calitativa (logica ) ce caracterizeaza dinamica sistemelor cu evenimente discrete, apelm la investigarea comportrii unor procese concrete, frecvent ntlnite n practica tehnico-inginereasc. Rolul investigatiilor const n a identifica, n functionarea proceselor respective, elementele specifice dinamicii pilotate de evenimente (care au fost discutate n sectiunile anterioare ale capitolului curent).Pentru a parcurge s i alte exemple, formulate la nivelul elementar al acestei introduceri n studiul sistemelor cu evenimente discrete, cititorul poate consulta referint ele bibliografice recomandate pentru sectiunea 1.2.Index si dictionar romn-englez1.3.1. Servirea clientilor ntr-un sistem de asteptare 1.3.2. Procesarea joburilor ntr-un sistem de calcul 1.3.3. Prelucrarea pieselor ntr-un sistem de fabricatie 1.3.1. Servirea clientilor ntr-un sistem de asteptareUn sistem de asteptare (eng. queueing system) se compune din 3 elemente definitorii, puse n evident si de reprezentarea schematizat din fig. 1.3.1:clientiiresursele (serverele)firul (coada) de asteptareCaracterizarea complet a sistemului de asteptare presupune furnizarea urmtoarelor informatii:numrul de serverecapacitarea firului de asteptare (ca numr de clienti acceptati);disciplina de servire a clientilor (n ordinea venirii, aleatorie, dup anumite prioritti). Fig. 1.3.1. Reprezentarea schematizat a unui sistem de asteptare Descrierea ca sistem cu evenimente discrete se bazeaz pe o multime de evenimente E ce cuprinde evenimente de dou tipuri: s (sosire) si p (plecare). Starea sistemului x(t) este dat de numrul total de clienti care se gsesc la un moment arbitrar de timp t n sistem (client i care as teapta n fir, plus client i care sunt servit i), adic spatiul strilor este multimea X {0,1,2,...}.Sistemul de asteptare trebuie privit drept o structur (configuratie) tipic ce poate fi ntlnit n functionarea multor procese fizico-tehnice, ca de pild:asteptarea joburilor sau taskurilor ntr-un sistem de calcul pentru a beneficia de o anumit resurs (procesor sau periferic);asteptarea pieselor ntr-un sistem de fabricatie pentru a fi prelucrate pe o anumit masin;asteptarea mesajelor ntr-un sistem de comunicatii pentru a fi transmise.Dou sau mai multe sisteme de asteptare pot fi interconectate, dnd nastere la o retea de asteptare. 1.3.2. Procesarea joburilor ntr-un sistem de calculFunctionarea sistemelor de calcul se bazeaz pe organizarea firelor de asteptare pentru diferite resurse, cum ar fi procesoarele, perifericele etc. Clientii sunt joburile sau taskurile prezentate n sistemul de calcul. De exemplu, n fig. 1.3.2 se prezint schematizat, modul de prelucrare a unui lot de joburi de ctre un sistem de calcul, n care orice job solicit accesul la UC si, eventual, la discurile D1, D2. Modelarea ca sistem cu evenimente discrete se bazeaz pe identificarea urmtoarelor tipuri de evenimente ce pot tranzitiona sistemul dintr-o stare n alta:s - sosirea unui job n lotul de intrare (din universul exterior)p - plecarea unui job din UC (ctre universul exterior)r1 - rutarea unui job pentru utilizarea discului D1r2 - rutarea unui job pentru utilizarea discului D2d1 - rutarea unui job de la D1 ctre UCd2 - rutarea unui job de la D2 ctre UCVectorul de stare este un triplet de forma (xUC, x1, x2)T, unde fiecare component este un numr natural, limitat superior de capacitatea fiecruia din sistemele de asteptare ce intr n structura reprezentat n fig. 1.3.2. n consecint, spatiul strilor este o multime de forma X{(xUC, x1, x2)T}. n functie de situatia real pe care o modelm, capacitatea sistemelor de asteptare va fi precizat n clar sau nu. Dac se consider c, n orice conditii de functionare, aceast capacitate nu poate fi atins, variabilele de stare xUC, x1, x2 iau valori n multimea {0,1,2,..., n,...}, fr a impune mrginirea superioar. Fig. 1.3.2. Reprezentarea schematizat a prelucrrii unui lot de joburi ntr-un sistem de calcul 1.3.3. Prelucrarea pieselor ntr-un sistem de fabricatien functionarea sistemelor de fabricatie, se utilizeaz frecvent fire de asteptare sub forma unor depozite (eng. buffer) care permit stocarea pieselor ce trebuie prelucrate pe o anumit masin. n fig. 1.3.3 se reprezint schematizat configuratia unui sistem de fabricatie alctuit din dou masini (M1) si (M2), ambele prevzute cu depozite de intrare. Se presupune c depozitul ce precede M1 are capacitate nelimitat (practic, nu se poate ajunge la situatia umplerii complete), n timp ce n depozitul ce precede M2 se pot stoca numai dou piese.Multimea evenimentelor E se compune din evenimente de tipul:s - sosirea unei piese brute n sistemul de fabricatie;p - plecarea unei piese prelucrate complet din sistemul de fabricatie;c1 - terminarea prelucrrii unei piese pe masina M1.Pentru a identifica variabilele de stare, pornim de la observatia c fiecare din cele dou masini reprezint serverul unei structuri de tipul sistem de asteptare. n consecint, procesul de prelucrare a pieselor poate fi privit ca o conexiune a celor dou sisteme de asteptare, ale cror stri se descriu n conformitate cu cele discutate n paragraful 1.3.1. Astfel vectorul de stare al modelului ntregului sistem de fabricatie are forma (x1, x2)T unde x1 {0,1,2,...}, iar x2 {0,1,2,3}, adic spatiul strilor este multimea:Examinnd cu atentie functionarea sistemului de fabricatie, se observ c modelarea bazat pe X1 definit mai sus, nu poate surprinde urmtorul aspect privind utilizarea masinii M1. n cazul cnd M2 prelucreaz o pies si alte dou piese asteapt n depozitul ce precede M2, piesa de pe masina M1 poate fi n curs de prelucrare, sau prelucrat complet, dar rmas pe masin din lips de spatiu pentru depozitarea ei, situatie care este cunoscut sub numele de blocaj (eng. blocking). Astfel, dac prin variabilele de stare x1 si x2, identificm strile celor dou masini (fr a mai fi interesati de numrul de piese din fiecare sistem de asteptare), putem utiliza drept spatiu al strilor multimea:unde simbolurile N, L, B noteaz urmtoarele stri posibile:N - masina este neutilizat (eng. iddle)L - masina lucreazB - masina este blocat.Se observ c prin utilizarea spatiului strilor X2, modelul poate face distinctie ntre starea B sau L a masinii M1, pentru situatia semnalat anterior. Totusi, de data aceasta, nu mai avem informatii privind numrul de piese din fiecare sistem de asteptare. Putem incorpora si aceste informatii n model, revenind la spatiul strilor X1 si observnd c blocajul lui M1 nu poate aprea dect pentru x23. Cu alte cuvinte, x23 poate corespunde la dou stri distincte ale sistemului de fabricatie (care difer prin situatia n care se afl M1):x23L - masina M1 lucreaz;x23B - masina M1 este blocat.Astfel, spatiul strilor definit prin multimea:permite includerea n model att a strilor individuale a masinilor, ct si a numrului de piese aflate n fiecare din sistemele de asteptare. Fig. 1.3.3. Reprezentarea schematizat a prelucrrii unui lot de piese ntr-un sistem de fabricatie