Modelarea Sistemelor Dinamice cu Evenimente Discrete Utilizând Algebra

CAPITOLUL 3

MODELAREA SISTEMELOR DINAMICE CU EVENIMENTE DISCRETE UTILIZÂND ALGEBRA (max, +)

3.1 Introducere

În acest capitol vom prezenta elemente ale teoriei sistemelor cu evenimente discrete dezvoltate în algebra (max, +).

Sistemele dinamice cu evenimente discrete sunt sisteme al căror comportament este complet determinat prin cunoaşterea momentelor de început şi de sfîrşit ale activităţilor executate în cadrul acestora. Structura mulţimii de activităţi poate fi descrisă, în general printr-un graf de evenimente temporizat. Aceste sisteme se bucură de o anumită "linearitate" în sensul algebrei (max, +), algebră ce permite o abordare a analizei şi sintezei acestora foarte asemănătoare cu cele din teoria clasică a sistemelor lineare. Se regăseşte o reprezentare de stare ce permite introducerea conceptelor de reacţie şi de sistem în buclă închisă, ai cărei parametrii sunt resursele materiale ale procesului modelat.

Multe procese de producţie pot fi modelate ca sisteme dinamice cu evenimente discrete. Ca un exemplu de aplicare a abordării prezentate, vom trata modelarea sistemelor de producţie, în particular sistemele de asamblare. Ea ne va permite tratarea atât a sistemelor de fabricaţie de tip "flow-shop", cât şi a celor de tip "job-shop".

3.2 SDED deterministe şi finite

Un SDED determinist şi finit este caracterizat de o mulţime de activităţi A şi de o mulţime de resurse R partajate de activităţi (activităţile intră în concurenţă pentru a li se aloca resurse). Ordinea în care activităţile sunt executate poate fi descrisă printr-un graf orientat aciclic (A, U). Pentru două activităţi ai şi aj, apartenenţa (ai, aj) U semnifică faptul că activitatea ai precede activitatea aj. Graful este numit de obicei graf de precedenţă şi corespunde unei relaţii de ordine parţială (relaţia de precedenţă). Se presupune că graful (A, U) este conex ca în fig.3.1. În cele ce urmează vom nota arcele (ai, aj) prin (i, j).

Fiecărei resurse r R i se asociază un drum Pr în graf, adică o secvenţă de activităţi consecutive în graf. Drumul Pr corespunde unei ordonanţări a activităţilor asociate resursei r. Întrucât fiecare activitate utilizează cel puţin o resursă, considerăm că mulţimea acestor drumuri

P = {Pr / r R}

este o acoperire a grafului (A, U), adică

(i, j) U , r a.î. (i, j) Pr

Există două motive posibile pentru care o activitate ai precede o altă activitate aj:

- cele două activităţi partajează aceeaşi resursă şi deci nu o vor putea utiliza în acelaşi timp;

- există o restricţie de precedenţă impusă de procesul descris de (A, U)

Cînd există două activităţi care necesită aceeaşi resursă şi nu ştim care dintre cele două activităţi va fi executată prima, graful de evenimente este disjunctiv. Spunem în acest caz, că SDED nu este determinist (trebuie facută o alegere de obicei la un nivel de comanda). Pentru a evita acest lucru facem ipoteza că sistemul nostru poate fi descris printr-un graf de evenimente. Astfel un SDED este un cvartet (A, U, R, P) în care mulţimile ce intervin sunt definite mai sus.

De exemplu, un proces de fabricaţie (proces de asamblare sau proces de uzinare) poate fi descris prin transformări de stare aduse la n produse

(pj, j=1,...,n) de către m echipamente (ei, i=1,...,m). Fiecărui produs i se asociază o secvenţă formată dintr-un număr finit de echipamente, cu semnificaţia că produsul respectiv va trece pe rând pe la echipamentele din secvenţă pentru a suferi transformări de stare specifice. Această secvenţă este numită uneori "rutaj". În aceste condiţii semnificaţia mulţimilor definite mai sus este următoarea:

A = mulţimea de activităţi necesare pentru producerea celor n produse; le putem nota prin perechi (i, j) unde i este indicele echipamentului ei, iar j este indicele produsului pj;

R = mulţimea de produse şi de maşini (adică de resurse);

U = mulţimea de restricţii de precedenţă între activităţi, restricţii cuprinse în secvenţele asociate produselor, sau în secvenţele operatorii asociate maşinilor;

P = mulţimea de secvenţe asociate produselor şi de secvenţe operatorii asociate maşinilor.

Fiecare drum Pr conţine o activitate iniţială şi o activitate finală, notate a1(r) şi respectiv akr(r). Se definesc mulţimile

I = {a1(r)/r R}

F = {akr(r)/r R}

unde I conţine toate acţiunile fără predecesor, iar F conţine toate acţiunile fără succesor. Pentru exemplul din fig.3.1 se poate scrie:

P1 = a1 a3 a5 a6, P2 = a1 a4 a5, P3 = a2 a4 a6

I = {a1, a2}, F = {a5, a6}

Fiecare arc (i, j) din U are drept pondere un număr real tij care este suma între durata activităţii ti şi timpul de trecere ("setup time") dij de la activitatea i la activitatea j . Ponderea unui drum din graful (A, U) este egală cu suma ponderilor tuturor arcelor. Lungimea unui drum este egală cu numărul său de arce.

Introducem următoarele variabile:

-xi este momentul cel mai devreme de declanşare a activităţii i (momentul în care resursele necesare pentru declanşarea activităţii i sunt disponibile; o activitate nu se declanşează însă obligatoriu în acest moment)

-ur este momentul când resursa r este disponibilă pentru prima activitate a secvenţei sale a1(r)

Dacă (j, i) U , atunci

xi xj + tij