UNIVERSITATEA “LUCIAN BLAGA” SIBIU
F a c u l t a t e a d e Ş t i i n ţ e
ş.l. ing. Adalbert Golomety
CERCETĂRI PRIVIND MODELAREA PROCESELOR ECONOMICE PARALELE
Rezumat TEZĂ DE DOCTORAT
Conducător ştiinţific: Prof. univ. dr. Emil M. Popa
Cuprins:
rezumat teză INTRODUCERE 1 1. NOŢIUNI INTRODUCTIVE DE TEORIA LIMBAJELOR FORMALE 5 12
1.1 Limbajul formal mijloc de descriere a proceselor economice 12 1.2 Gramatici clasice Chomsky 17 1.3 Operaţii paralele cu limbaje 21 1.4 Arbori de derivare 26
2. ACTIVITĂŢI PARALELE ŞI DISTRIBUITE REFLECTATE IN LIMBAJE FORMALE 7 29
2.1 Paralelismul natural în limbaje formale 29 2.2 Gramatici distribuite 41 2.3 Gramatici controlate 46 2.4 Paralelismul orizontal al gramaticilor 52
2.4.1 Gramatici compuse S. Abraham, remarci proprii 52 2.4.2 Ierarhia lui Th.Rus, remarci proprii 57
3. MODELAREA PROCESELOR ECONOMICE PARALELE PRIN GRAMATICI MATRICIALE 7 61
3.1 Gramatici paralele 62 3.2 Gramatici matriciale 63
3.2.1 Tipuri de gramatici matriciale 65 3.2.2 Paralelismul vertical al limbajelor matriciale 66 3.2.3 Proprietăţi ale gramaticilor matriciale 68
3.3 Gramatici bi-paralele 75 3.3.1 Divizarea orizontală 76 3.3.2 Divizarea verticală şi sincronizarea gramaticilor verticale 82 3.3.3 Restricţii 86 3.3.4. Gramatici matriciale cu ramuri comunicante 87
4. VERIFICAREA SUCCESIUNII ACTIVITĂŢILOR ECONOMICE PRIN AUTOMATE DE CONTRACŢIE 8 90
4.1 Automate de acceptare pentru limbaje formale clasice 92 4.1.1 Automate si gramatici de precedenţa simplă 98
4.2 Automate şi gramatici contextuale 104 4.3. Automate pentru recunoaşterea limbajelor matriciale 117
4.3.1 Automate de contracţie 119 4.3.2 Construirea automatelor de contracţie 122
4.4 Automatul de contracţie generalizat 127 4.4.1 Automatul de contracţie generalizat cu relaţii de precedenta 130
2
rezumat teză 4.5 Automate pentru gramatici bi-paralele 135
5. MODELUL FORMAL LINGVISTIC AL PROCESULUI DE PRODUCŢIE 14 138 5.1 Modelul Gh. Păun, operaţia Shuffle 138 5.2 Implementarea planificării producţiei prin operaţia Shuffle 149
5.2.1 Formula Computaţionala pt. Shuffle 150 5.2.2 Algoritm implementare, rezultate 158
5.3 Optimizarea operatei Shuffle 162 5.3.1 Reducerea numărului de configuraţii 163 5.3.2 Mărirea gradului de paralelism 164 5.3.3 Alocarea fluentă a posturilor de lucru 164
6. MODELE UZUALE DE PLANIFICARE A PROCESELOR DE PRODUCŢIE 15 166 6.1 Planificare globală şi planificare calendaristică a producţiei 167 6.2 Concepte şi terminologie de bază în planificarea producţiei 171 6.3 Modele de planificare bazate pe fezabilitate 172 6.4 Criterii de performanţă în planificarea producţiei 174 6.5 Abordări şi soluţii uzuale, remarci 179
7. MODELUL DE PLANIFICARE A PRODUCŢIEI BAZAT PE GRAMATICI MATRICIALE 16 181
7.1 Paralelism in planificarea producţiei 184 7.2 Modelare structurii produsului 185 7.3 Modelarea fazelor de execuţie 190 7.4 Algoritm planificare faze de execuţie 192 7.5 Fabricaţia în serie 195 7.6 Fabricaţie in mai multe loturi şi mai multe produse 196 7.7 Modificarea planificării propuse de algoritm 200 7.8 Model distribuit planificare 201
CONCLUZII 21 204 Glosar de termeni 206 Bibliografie 23 208
3
REZUMAT Paralelismul proceselor economice Procesele economice conţin activităţi care in majoritatea lor se desfăşoară in paralel. Există
mai multe tipuri de paralelism:
• vertical, apare la procesele (sau activităţile componente) care se desfăşoară in paralel
fără a interacţiona ierarhic unul cu celălalt sau ca un proces să coordoneze ierarhic pe
altul.
• orizontal, se manifestă la procese şi activităţi care sunt subordonate ierarhic
• procese care se desfăşoară distribuit în mai multe locaţii
Paralelismul de tip vertical apare pe mai multe nivele de descompunere a proceselor chiar
în cadrul unei firme. Există un prim paralelism vertical intre procesele economice de natură
diferită aparţinând de compartimente diferite ca funcţionare, cum ar fi procesul de fabricaţie,
cel de logistică (aprovizionare de materiale, scule, utilaje), controlul fabricaţiei, întreţinerea
utilajelor, managementul comenzilor şi livrărilor la clienţi, managementul financiar. Aceste
procese interacţionează între ele pentru a atinge scopurile firmei şi pentru a creşte performanţa
firmei. Ele sunt subordonate ierarhic doar managerului general .
Al doilea nivel de paralelism vertical apare chiar in cadrul proceselor de acelaşi tip între
activităţile care compun acele procese. Fabricaţia mai multor produse identice sau diferite se
face in paralel. In cadrul departamentelor de logistică, de control, întreţinere se desfăşoară
activităţi paralele (mai mulţi angajaţi ai compartimentului, mai multe controale in parale
pentru fabricaţia mai multor produse, întreţinerea şi repararea mai multor utilaje in paralel) .
Există chiar şi al treilea nivel de paralelism vertical în fabricaţia unui singur produs care
are in componenţă mai multe subansamble şi repere ce pot fi fabricate in paralel şi apoi
asamblate.
Paralelismul de tip orizontal apare intre compartimentele subordonate ierarhic din cadrul
firmei. Exisă cel puţin două nivele ierarhice majore: managementul firmei (conducerea) şi
departamentele firmei. Chiar in interiorul acestor două nivele există o ierarhie care poate fi
descompusă pe niveluri orizontale (există un manager general şi manageri de departamente).
Pentru aceste procese ce prezintă paralelism orizontal în desfăşurarea lor, subordonarea
ierarhică este strictă şi la fel comunicarea dintre ele pe nivelurile orizontale.
4
Multe companii mari au mai multe locaţii de desfăşurare a activităţilor economice. Poate
fi un holding central al companiei şi firme componente care au sediul în alte locaţii (în
perimetrul aceleaşi localităţi sau chiar in alte localităţi sau alte arii geografice). Chiar în cadrul
aceleaşi firme fabricaţia produselor poate avea loc în mai multe ateliere care au locaţii
distincte. Procesele aferente acestor activităţi se desfăşoară in mod distribuit cu mecanisme
comunicare şi de sincronizare între ele.
Lucrarea de faţă tratează modelarea funcţionării acestor procese economice care prezintă
paralelism in desfăşurarea lor. Am ales ca mecanism de modelare limbajele formale mai
specific gramaticile matriciale din motive care vor fi prezentate în continuare.
1. Limbajul formal mijloc de descriere a proceselor economice
Plecăm de la de la un exemplu de proces simplu de fabricaţie şi notaţiile pentru reprezentarea
lui. Avem un produs notat cu P compus din doua piese p1 şi p2. Procesul de fabricaţie se
desfăşoară in modul următor. Se prelucrează o piesa p1 pe un post de lucru, acţiune notată cu
a. Se prelucrează cealaltă piesă p2 pe un alt post de lucru (diferit de primul post), acţiune
notată cu b. Apoi se asamblează cele două piese rezultând un produs finit, acţiune notată cu c.
Prelucrarea pieselor p1 şi p2 poate fi făcută in orice ordine. Putem construi secvenţe de acţiuni
pentru acest proces de fabricaţie prin notaţiile precedente. Secvenţele posibile şi corecte de
acţiuni pentru fabricaţie sunt două:
a b c = prelucrare piesa p1 apoi prelucrare piesa p2 şi asamblare
b a c = prelucrare piesa p2 apoi prelucrare piesa p1 şi asamblare
Secvenţele de mai sus sunt de fapt şiruri de simboluri, fiecare simbol având semnificaţia unei
acţiuni de fabricaţie. Mulţimea acestor două secvenţe constituie un limbaj pentru fabricarea
unui singur produs finit notat cu:
L={abc,bac}
Aceste secvenţe por fi considerate posibile planuri de fabricaţie pentru produsul ales.
De prelucrarea şirurilor de simbolurilor şi de limbaje se ocupă teoria limbajelor formale.
Ca definiţie generală un limbaj formal descrie un sistem formal. Sistemul formal are ca intrări
un set de axiome(adevăruri) şi pe baza unor reguli de compunere generează la ieşire teoreme.
In literatura de ştiinţa calculatoarelor limbaje formale sunt asociate cu gramaticile formale. La
5
fel ca orice alt sistem, o gramatică pleacă de la un set de simboluri de intrare(vocabularul),
are un set de reguli de compunere şi generează la ieşire secvenţe (şiruri) de simboluri.
Mulţimea acestor secvenţe de simboluri formează un anumit limbaj. În concepţia acestei
lucrări despre o gramatică, ea arată grafic astfel:
Intrări Logică de funcţionare Ieşiri
Vocabular (simboluri)
Reguli de compunere (producţii)
şiruri de simboluri (Limbaj)
Se observă uşor din figura de mai sus faptul că o gramatică este analogă unui sistem sau
proces general care are intrări, logică de funcţionare şi generează ieşiri. Logica de funcţionare
a unui proces oarecare poate fi modelată prin regulile de compunere ale gramaticilor. Pe scurt
rolul unei gramatici este acea de a genera şiruri de simboluri aparţinând unui limbaj.
Procesul de generare pleacă totdeauna de la un anumit simbol al vocabularului numit simbol
de start.
Din punct de vedere formal o gramatică este un qvadruplu: G = (N,T,S,P) unde N,T sunt
alfabete (vocabulare) disjuncte ,N = neterminale, T = terminale, S∈N este simbolul de start
şi P este un set finit de reguli de compunere (reguli de derivare, reguli de rescriere) . Regulile
din P sunt perechi (w,v) notate: w→ v ( w se rescrie ca v ) astfel încât w,v ∈ ( N ∪ T )* şi w
conţine cel puţin un simbol din N . In continuare vom nota cu litere mici simbolurile
neterminale şi cu litere mari simbolurile terminale. Ca exemplu luăm gramatica care generează
limbajul prezentat mai sus L={abc,bac} . Ea va arăta astfel, G = (N,T,S,P) cu:
N={S,A,B,C} ,T={a,b,c}, S={S}, P={S→aB, S→bA, B→bC, A→aC, C→c}
Procesele secvenţiale de generare a celor două şiruri de simboluri abc şi bac vor arăta
astfel:
S→ aB→ abC→ abc şi S→ bA→ baC→ bac
Un limbaj in sens general este o colecţie (finită sau nu) de secvenţe finite formate cu
elementele (simbolurile) unui vocabular finit. Semnificaţia elementelor vocabularului
6
determină aria de aplicare a limbajului. Pot fi limbaje naturale (elementele sunt cuvinte),
limbaje de programare (teoria compilatoarelor), limbaje ce descriu procese economice sau
activităţi umane (vocabularul este constituit din codificări ale acţiunilor elementare), limbaje
ce descriu procese biologice (sisteme Lindenmayer). Cu toate că vocabularul este finit,
limbajul poate fi infinit. Un limbaj infinit nu poate fi enumerat, el poate fi descris si manipulat
prin reguli de formare a şirurilor sau a frazelor sale. Aceste reguli sunt descrise prin limbaje
formale care sunt gramaticile asociate limbajelor. Regulile din cadrul unei gramatici
furnizează un mecanism de generare si un criteriu de corectitudine a frazelor limbajului. În
capitolul 1 sunt descrise pe larg din punct de vedere formal noţiunile de limbaj şi gramatică.
Revenind la exemplu anterior cu fabricaţia acelui produs P, am arătat că o gramatică
clasică (în care regulile de compunere se aplică secvenţial) poate uşor genera limbajul
L={abc,bac}. Gramaticile clasice pot modela simplu procese secvenţiale. Dar pentru că
ordinea de prelucrare a celor două piese nu contează ele ar putea fi prelucrate in paralel (mai
ales că se execută pe posturi de lucru diferite) . O formă de reprezentare a acestui paralelism
este următorul arbore, în care pe orizontala ar fi axa timpului:
a
b
c
Acest arbore este reprezentat orizontal pentru a evidenţia fabricaţia in timp a produsului P
şi fabricaţia in paralel pentru piesele p1 şi p2. Dacă rotim acest arbore şi dăm direcţie
legaturilor el va arăta astfel:
a b
c
Săgeţile din arbore indică faptul că de prelucrările a şi b se vor face înaintea fazei de
asamblare c . Faptul că prelucrările a şi b se pot face in paralel este indicat de poziţia lor pe
acelaşi nivel orizontal şi de faptul că sunt separate vertical. Acest din urmă arbore seamănă
foarte mult cu un arbore ce descrie procesul de generare şirurilor dintr-o gramatică.
7
2. Activităţi paralele şi distribuite reflectate in limbaje formale
Multe alte fenomene şi procese care prezintă paralelism în evoluţia lor se modelează prin
gramatici nonclasice specifice fiecărui tip de fenomen. Ar fi de remarcat evoluţia distribuită şi
cooperantă a celulelor în sisteme biologice, precum evoluţia mediului şi a agenţilor de
modificare din ecosisteme. În multe din aceste limbaje formale nonclasice care modelează
aceste fenomene, paralelismul este implementat prin dependenţa de context. Această
dependenţă de context reflectă atât interacţiunea între activităţi cît şi paralelismul lor.
Fenomenele cu grad de paralelism şi gramaticile nonclasice specifice lor sunt prezentate pe
larg in capitolul 2.
3. Modelarea proceselor economice paralele prin gramatici matriciale
Pentru că gramaticile clasice nu prezintă paralelism am ales pentru modelarea proceselor
paralele gramaticile matriciale. Aceste gramatici au în mod intrinsec paralelism vertical. În
aceste gramatici mai multe reguli de compunere, grupate in matrice de reguli (de unde vine şi
numele), se aplica deodată în paralel. Astfel mai multe simboluri vor apărea deodată în cadrul
procesului de generare de şiruri. Aceste simboluri care apar simultan vor fi activităţile care se
pot desfăşura în paralel. În capitolul 3 sunt prezentate pe larg gramaticile matriciale. Din punct
de vere formal o gramatică matricială este GM = (N,T,S,M) cu N,T,S având aceiaşi semnificaţie
ca la gramaticile clasice, iar M este mulţimea de matrice de reguli de rescriere. În continuare
luăm ca exemplu gramatica matricială care generează limbajul din exemplul anterior
L={abc,bac} dar in paralel. GM = (N,T,S,M) cu:
N={S,A,B } ,T={a,b,c}, S={S}, M={m0,m1}
m0 = [S→ABc], m1 = [A→a, B→b]
Gramatica este mai simplă decât gramatica clasică anterioară. Simbolurile a şi b din
matricea m1 vor apărea simultan într-un pas al procesului de generare, pentru că fac parte din
regulile aceleiaşi matrice. Procesul de generare decurge astfel: S → ABc → abc . Activităţile a
şi b vor fi activităţi care se pot desfăşura în paralel şi nu va conta ordinea in care apar in şirul
generat.
8
Procesele de producţie, ca şi procesele economice, pot avea o mulţime de activităţi ce se
pot desfăşura în paralel atât pe orizontală (ierarhic) cât si pe verticală (execuţie in paralel).
Pentru a putea modela aceste două tipuri de paralelism am construit un algoritm propriu de
divizare orizontală şi verticală a unei gramatici matriciale. Gramaticile rezultate in urma
divizării le-am denumit gramatici bi-paralele şi am construit mecanisme de sincronizare intre
ele atât pe orizontală cât şi pe verticală prezentate pe larg în subcapitolul 3.3.
Un exemplu de divizare a unei gramatici matriciale este prezentat în continuare. Se pleacă
de la gramatica matricială : GM=(N,T,S,M) cu:
N={ S,A,B,C }
T={ a,b,c } S={S}
M={ m1, m2, m3 }
m1 : [S → ABC ]
m2 : [A → aA, B → bB, C→ cC ]
m3 : [A → a, B → b, C→ c ]
GM generează acelaşi limbajul : L(GM) = { anbncn : n ≥ 1 }. Pentru şirul a2b2c2 procesul de
derivare este:
S⇒ABC⇒aAbBcC⇒aabbcc= a2b2c2
S-au folosit în acest proces de derivare matricele în ordinea m1,m2, m3 . Arborele de
derivare care are proprietăţi bi-paralele este arătat în figura următoare.
S
A B C
a A b B c C
a b c
G1
G21 G2
2 G23
Liniile întrerupte arată paralelismul orizontal şi vertical din GM. Această gramatică
matricială poate fi divizată orizontal şi vertical. Notaţiile G1,G21,G2
2,G23 încadrate de pătrate
sunt gramaticile în care gramatica GM poate fi divizată. Această divizare va fi făcută în doi
paşi: divizare orizontală şi apoi divizare verticală .
9
Divizarea orizontală va fi făcută într-o manieră top-down prin mecanismul de la
gramaticile compuse. Părerea mea este că maniera top-down de divizare este de preferat
manierei bottom-up pentru că într-un arbore de derivare cu ramuri nebalansate (nu sunt egale
ca număr de nivele), nu toate terminalele au acelaşi nivel ierarhic. Indexul superior i din
notaţia pentru gramatica Gij indică nivelul ierarhic orizontal al acelei gramatici. Algoritmul de
divizare orizontală se bazează pe un operator propriu GMC(Ni) (Grammar Matrix
Constructor ) definit astfel:
GMC(N i) = { mk : mk∈M şi există A→ w∈ mk cu A∈N i }
Operatorul GMC(N i) ia din setul de matrice iniţial M , matricele mk care conţin reguli de
rescriere cu neterminalii din partea dreaptă incluşi în setul N i. Gramaticile bi-paralele vor avea
mai multe simboluri de start. Setul de neterminale vor fi şi setul de simboluri de start. Din
pasul de divizare orizontală gramaticile rezultate G1 şi G2 sunt de asemeni gramatici
matriciale.
G1= (N1,T1,M1) cu:
N1 = { S }
M1= { [S → ABC ] }
T1 = { A, B, C }
şi
G2= (N2,T2,M2) cu:
N1 = { A, B, C }
M2= { m2 , m3 }
m2 : [A → aA, B → bB, C→ cC ]
m3 : [A → a, B → b, C→ c ]
T2 = { a, b, c }
Divizarea verticala va fi făcută prin divizarea matricelor de reguli în ramurilor verticale
din, ramuri care conţin aceleaşi neterminale. Gramaticile rezultate sunt gramatici independente
de context sau gramatici matriciale. Pentru fiecare gramatică G2j , 1≤ j ≤ vn construcţia începe
cu construcţia setului de neterminale Nkj prin operatorul propriu GNC(Nk
i) (Grammar
Nonterminal Constructor) definit astfel:
GNC(Nki)=Nk
i∪ {Ak :Ak∈Nki şi există Ai∈Nk
1 şi m∈M şi Ai→u1Aku2∈m, u1,u2∈(Nki∪ Tk
i)* }
Cu alte cuvinte un set Nkj va conţine: un neterminal Ai din Nk şi acele neterminale din Nk care
10
apar în partea dreaptă a regulilor de rescriere care au pe Ai în partea stângă (“ramurile”
verticale comunică) . Aceste reguli de rescriere apar setul de matrice Mk .
Gramatică orizontală G2 poate fi divizată în trei gramatici verticale G21, G2
2, G23 cu
formulele astfel:
G21= (N2
1,T21,M2
1) cu : G22= (N2
2,T22,M2
2) cu : G23= (N2
3,T23,M2
3) cu :
N21
= { A } N22
= { B } N131
= { C }
M21= { m21 , m31 } M2
2={ m22 , m32 } M23= { m23 , m33 }
m21 : [A → aA ] m22 : [ B → bB ] m23 : [ C → cC ]
m31 : [A → a ] m32 : [ B → b ] m33 : [ C → c ]
T21
= { a } T22
= { b } T23
= { c }
Pentru gramaticile verticale, restricţia de a utiliza regulile din aceiaşi matrice într-un pas de
derivare şi de a folosii în aceiaşi ordine setul de matrice este implementat de un mecanism tip
listă de matrice utilizate(matrix trace-list) care este arătat în secţiunea 3.3.1. Prima gramatică
care va face o derivare va completa în această listă numărul matricei care a folosit-o.
Următoarele gramatici vor citii aceasta listă şi vor alege aceleaşi matrici pentru derivarea.
Dacă o gramatică depăşeşte numărul de paşi de derivare specificaţi in listă ea va adăuga la
sfârşitul listei matricea utilizată in plus.
Gramaticile paralele orizontal rezultate din divizare pot fi utilizate în sisteme ierarhice
(management, procese economice) care au un oarecare paralelism orizontal. Divizare
orizontală poate fi utilizată ca o funcţie de descompunere pentru sistemele ierarhice
(descompunerea unei decizii/acţiuni). Reconstrucţia finală poate fi utilizată ca o de funcţie de
agregare (compunerea unei decizii/acţiuni) în sistemele ierarhice.
Procesul de generare de şiruri poate fi făcut (mai repede şi sigur) într-un mediu paralel
MIMD (Multiple Instruction Multiple Data) .
Gramaticile bi-paralele pentru că au o funcţionare separată pot modela şi procese
distribuite.
11
4. Verificarea succesiunii activităţilor economice prin automate de contracţie
Gramaticile au rolul de a genera şiruri de simboluri (cuvinte) aparţinând unui limbaj. Problema
verificării corectitudinii şirurilor sau a apartenenţei şirurilor la un limbaj dat este rezolvată de
automate. Acestea funcţionează invers decât gramaticile, ele pleacă de la şirurile deja formate,
le citesc simbol cu simbol şi după o serie de tranziţii ajung sau într-o stare finală sau într-una
de eroare. În starea finală şirul a fost recunoscut ca şi corect (aparţine limbajului). În starea de
eroare şirul a fost catalogat ca fiind incorect, cu un mesaj de eroare specific din care
utilizatorul să poată corecta şirul.
Planificarea automată a proceselor de fabricaţie (sau a altor procese economice) o poate
rezolva o gramatica matricială prin generare de şiruri de simboluri ce reprezintă fazele de
fabricaţie (sau activităţile din care este compus un proces economic). Utilizatorul planului de
fabricaţie ar putea să facă modificări în această planificare automată sau chiar să facă o
planificare manuală. Verificarea corectitudinii acestor modificări sau a planificării manuale o
poate face doar un automat asociat gramaticii matriciale folosită la modelarea procesului de
fabricaţie. Automatele asociate gramaticilor matriciale se numesc automate de contracţie
pentru că ele reduc (contractă) pas cu pas şirul analizat până la un singur simbol (simbolul de
start al gramaticii) şi numai atunci validează şirul analizat. Automatele de contracţie sunt
descrise pe larg in capitolul 3. Am mers în această lucrare pe ideea construirii efective a
automatului plecând de la o gramatică matricială. Literatura parcursă tratează sau cazuri
particulare de automate de contracţie sau nu dă o procedură efectiva de construcţie a acestui
tip de automat care este in general nedeterminist. Am propus în referatul 2 [20], şi apoi am
implementat, în cadrul unor proiecte, un automat propriu numit automat de contracţie
generalizat care poate fi construit direct dintr-o gramatică matricială destul de generală.
Problema a fost înlăturarea pe cât posibil a comportării (tranziţiilor) nedeterministe din
funcţionarea automatului de contracţie. Luăm ca exemplu gramatica matricială recursivă la
stânga:
G3L : m1: (S–>AB), N={S,A,B} T={a,b,c}
m2: (A–>aAb, B–>Bc),
m3: (A–>ab, B–>c),
şi un şir generat de această gramatică: aabbcc. Problema este de a reduce prin contracţii
12
succesive acest şir la simbolul de start S. Reducerile(contracţiile) corecte sunt:
aabbcc (m3) => aAb Bc (m2) => AB (m1) => S
Cu caractere subliniate s-au trecut părţile drepte ale regulilor de rescriere din matrici. Între
paranteze rotunde au fost trecute matricele prin care s-au făcut reducerile. Aici am ales în şirul
iniţial pentru reducere primul caracter c. Dacă luăm insă o gramatica de pornire echivalentă
recursivă la dreapta:
G3R : m1: (S–>AB), N={S,A,B} T={a,b,c}
m2: (A–>aAb, B–>cB),
m3: (A–>ab, B–>c),
şi acelaşi şir generat de această gramatică: aabbc, aceleaşi reduceri ne duc la :
aabbcc (m3) => aAb Bc (eroare)
Pentru o evoluţie corectă a automatului trebuie să luăm ultimul caracter c din şirul iniţial
pentru reducere:
aabbcc (m3) => aAb cB (m2) => AB (m1) => S
Pentru a rezolva această comportare nedeterministă a automatului am extins relaţiile de
precedenţă Wirth-Weber dintre simbolurile unei gramatici (specifice gramaticilor de
precedenţă clasice) la gramatici matriciale. Am obţinut astfel pentru cele două gramatici şi
pentru şirul aabbcc două configuraţii :
<.a<.a=.b>.b>.c>.c>. pentru G3L şi
<.a<.a=.b>.b>.c<.c>. pentru G3R
În aceste ultime configuraţii părţile drepte pentru reducere (cele subliniate) au fost alese
de la primele simboluri >. începând spre stânga până la un simbol diferit de =. Aici este
deosebirea faţă de gramaticile de precedenţă simple care mergeau spre stânga până la
întâlnirea simbolului <.
Această extindere cu relaţii de precedentă care a redus substanţial non-determinismul
automatului de contracţie clasic este prezentată pe larg in subcapitolul 4.4.
13
5. Modelul formal lingvistic al procesului de producţie
Lucrarea de fată este focalizată în ultima parte pe implementarea modelelor bazate pe
gramatici în procesul de planificare calendaristică a proceselor de producţie. Planificarea
calendaristică a producţiei este procesul prin care fiecărei activităţi de producţie i se
repartizează un post de lucru pentru o secvenţă fixă de timp. Această secvenţă de timp este
fixată atât ca durată cât si ca timp de început pentru activitatea respectivă. In urma planificării
calendaristice rezultă un plan de producţie care trebuie urmat şi respectat in cadrul fabricaţiei.
Pentru început am implementat in cadrul unei aplicaţii modelul lingvistic al procesului de
producţie propus de Ghe Păun in [37]. Am ales acest model pentru simplitatea formalismului
său mai ales in partea de planificare a procesului de producţie. Modelul se bazează pe
gramatici clasice mergând până la cele mai simple (regulate) care pot fi mapate uşor pe
grafurile reprezentând relaţiile de precedenţa (succesiunea in timp) a operaţiilor de fabricaţie.
Planificarea producţiei în acest model are la bază operaţia shuffle (care amestecă in toate
modurile posibile două secvenţe de simboluri aşa cum se pot amesteca două pachete de cărţi
de joc) pentru a simula paralelismul in fabricaţia mai multor produse. Am completat acest
model cu o formulă computaţională proprie pentru implementarea operaţiei shuffle (de
amestecare) a două secvenţe de operaţii. Modelul şi implementarea lui sunt prezentate in
capitolul 5.
In primul rând am obţinut un număr mare de configuraţii de secvenţe chiar pentru numai 2
produse. Acest lucru este uşor de arătat chiar pentru exemplul ales înainte al produsului P cu
fazele de fabricaţie a, b, c. Presupunem fabricarea a 2 produse finite unde operaţiile de
prelucrare nu se desfăşoară in paralel şi operaţia de asamblare finală nu trebuie făcută chiar la
sfârşitul prelucrării celor două piese componente ale fiecărui produs. Secvenţele aferente
limbajului de fabricaţie obţinute prin operaţia shuffle constituie o mulţime notată cu MS
(mulţime shuffle):
MS = {abcabc, abcbac, bacabc, bacbac, aabcbc, ababcc, abacbc, abbacc, bbacac, babacc,
baabcc, bbaacc, aabcbc, abbcac, babcac, aabbcc }
Se observă că sunt un număr de 16 asemenea secvenţe, toate corecte, care pot constitui tot
atâtea planuri de fabricaţie. Am făcut o serie de optimizări ale algoritmului de implementare
14
ale formulei pentru shuffle şi am obţinut rezultatele:
Apoi am redus numărul de configuraţii eliminând pe cele cu timpi de execuţie egali:
Număr faze de execuţie Număr serii execuţie Configuraţii obţinuteConfiguraţii reduse
2 3 90 7
7 4 3432 9
În continuare am modificat algoritmul de generare configuraţii shuffle pentru mărirea
gradului de paralelism intre produse sau serii de executat. Pentru exemplu cu cele două
produseşi seriile din mulţimea MS, dacă cele două produse se pot fabrica in paralel unul cu
celălalt, numai ultima secvenţă ar fi de folos pentru o planificare calendaristică paralelă pentru
că fazele sunt intercalate uniform pentru cele două produse.
In final am introdus ca ultimă optimizare alocare fluentă a fazelor de execuţia pe posturi.
Astfel o serie va ţine ocupat un post de lucru pentru cât mai multe faze de execuţie
consecutive.
Analiza rezultatelor obţinute şi optimizările pe care am fost nevoit să le fac pentru
reducerea numărului mare de planuri de producţie obţinute au condus spre o nouă abordare a
modelării planificării producţiei prezentată in capitolul 7.
Număr de serii execuţie Număr configuraţii iniţial Nr.configuraţii după eliminare duplicate
2 12 6
3 768 90
4 245760 2520
6. Modele uzuale de planificare a proceselor de producţie
Am căutat in literatura de specialitate alte modele de planificare a producţiei şi am găsit o serie
de modele şi metode uzuale de planificare. In majoritatea acestor modele se pune accent pe
faza de repartizare a fazelor de execuţie pe posturi de lucru într-un mod cât mai eficient
conform unor criterii de performanţă. Totuşi nu am găsit modele uzuale care să folosească
posibilitatea fabricaţiei în paralel a subansamblelor şi reperelor care compun chiar un singur
produs. Rezultatul acestor cercetări este prezentat in capitolul 6.
15
7. Modelul de planificare a producţiei bazat pe gramatici matriciale
In final am propus un model propriu de planificare a fabricaţiei unui produs sau a mai multora
bazat pe gramatici matriciale. Aici am conceput un algoritm propriu de planificare care mai
întâi extrage paralelismul din structura unui produs şi îl adaugă la paralelismul activităţilor de
fabricaţie aferente mai multor produse, apoi face repartizarea (alocarea) fazelor de fabricaţie
pe posturi de lucru. Pentru a face acest lucru am modelat intr-un mod unitar atât structura
produsului cât şi fazele de fabricaţie ale produsului. Pentru exemplul nostru simplu de produs
P a rezultat modelul următor.
P(c)
p2(b)p1(a)
În acest ultim model, între paranteze rotunde sunt trecute fazele de fabricaţie aferente fiecărei
componente a produsului. La nivelul superior al produsului finit P se face operaţia de
asamblare c ale celor două piese p1 şi p2. Modelarea prin intermediul unei gramatici matriciale
a structurii produsului permite extragerea tuturor fazelor de fabricaţie ce se pot executa in
paralel intr-o mulţime, numită mulţime pool, distinctă de restul celorlalte faze. Notăm această
mulţime cu Mp. În cazul nostru această mulţime notată este formată din fazele a şi b.
Mp = { a, b }
Fazele din mulţimea Mp se pot planifica in execuţie paralel pe posturi de lucru. După
planificarea tuturor fazelor din mulţimea Mp iniţială se încearcă formarea unei noi mulţimi
pool şi apoi planificarea noilor faze. Acest proces (formare mulţime pool apoi planificare)
începe de la baza arborelui (nivelul de jos) şi ia sfârşit când se ajunge la produsul finit. El este
esenţa algoritmului de planificare prezentat în diverse variante in subcapitolele 7.4, 7.5, 7.6.
Pentru două produse dintre care primul este produsul P şi al doilea este notat cu PP
’ cu
aceiaşi componenţă, arborii de structură arată astfel:
p1(a) p2(b) p1(a) p2(b)
P(c) P’(c)
Prima mulţime pool pentru planificarea fabricaţiei celor două produse este:
Mp = { a, b, a, b }
16
Se observă uşor că această mulţime este numai o secvenţă (secvenţă a şasea) din mulţimea
shuffle MS din modelul anterior de planificare bazat pe operaţia shuffle. De fapt concluzia
analizei implementării primului model este că operaţia shuffle trebuie înlocuită prin paralelism
al modelului.
Ordinea planificării pentru această mulţime de faze, Mp = { a, b, a, b }, se alege conform
unor criterii de ordonare suplimentare (cel mai scurt sau cel mai lung timp de execuţie pentru
fiecare operaţie din mulţime, cel mai scurt termen de livrare dintre cele două produse, etc.)
care sunt detaliate in 7.6. După planificarea tuturor operaţiilor din Mp se construieşte o nouă
mulţime Mp cu operaţii ce se pot executa in paralel si anume:
Mp = { c, c’ }
La final se vor planifica operaţiile din această nouă mulţime în paralel. Rezultă astfel un
proces de fabricaţie cu un grad mare de paralelism, atât între produse cât şi in interiorul
structurii lor. Tot structura de arbore a produsului (completată cu faze de execuţie) ne indică şi
ce repere nu pot fi fabricate în paralel datorită plasării pe un nivel ierarhic superior cum este
cazul operaţiei de asamblare c care apare ca o sinteză a operaţiilor a şi b.
Dacă intre parantezele rotunde apar mai multe faze de prelucrare, acestea se planifică in
execuţie in secvenţa in care apar intre paranteze. Paralelismul din cadrul unui produs se
extrage doar la nivelul de repere şi subansamble, iar fazele aferente unui reper se planifică şi
execută secvenţial pentru a respecta tehnologia de fabricaţie. Se construiesc in acest fel
mulţimi Mp de seturi de faze secvenţiale, seturi care se pot executa in paralel. Pentru un produs
P cu următoarea structură:
P
S1 S2 S3
S11 S12 r2 S31
r11 S121 r311 r312
r121
17
Cu litere mari S s-au notat subansamblele iar cu litere mici r reperele. Succesiunea indicilor
inferiori reflectă structura produsului. Gramatica matricială corespunzătoare produsului P este:
mo [ P → S1 S2 S3 ]
m1 [ S1 → S11 S12 , S2→ r2 , S3 → S31 ]
m2 [ S11→ r11 , S12 → S121 , S31 → r311 r312 ]
m3 [ S121→ r121 ]
Completăm arborele de structură cu matricele de derivare şi cu fazele de execuţie pentru
fiecare subansamblu şi reper. Matricele sunt trecute intre paranteze drepte şi vor fi atribute ale
simbolurilor gramaticii (care sunt subansamble sau repere) . Faze vor fi notate cu simboluri fi
şi vor fi trecute între paranteze rotunde tot ca nişte atribute. Indicele inferior al fazelor arată
ordinea tehnologică in care se vor desfăşura. Arborele astfel completat va arăta astfel
P (f1 ,f2 ,f3 )
S 1 [m 0 ] S 2 [m 0] S 3 [m 0] ( f1 ,f2 ,f3 ,f4 ) ( f1 ) ( f1 ,f2 )
S 1 1 [m 0 , m 1] S 1 2 [m 0 , m 1] r 2 [m 0 , m 1] S 3 1 [m 0 , m 1] (f1 ) ( f1 ,f2 ) ( f1 ,f2 ) ( f1 )
r 1 1 [m 0 , m 1 ,m 2] S 1 2 1 [m 0 , m 1 ,m 2] r 3 1 1 [m 0 , m 1 ,m 2] r 3 1 2 [m 0 , m 1 ,m 2 ] (f1 ,f2 ,f3 ) (f1 ,f2 ) ( f1 ) ( f1 ,f2 )
r 1 2 1 [m 0 , m 1 ,m 2,m 3] ( f1 ,f2 )
Această structură cu atribute permite formarea mulţimilor pool prin două reguli simple:
a) - fiecare subansamblu sau reper poate fi programat în fabricaţie in paralel cu
subansamble care au aceleaşi numere de matrice m sau al căror şir de matrice sunt conţinute
în şirul propriu de matrice.
b) - condiţia de non paralelism este ca reperele să nu facă parte din aceiaşi ramură a
structurii produsului
Conform regulii a) r121 , r11 şi S121 fac parte din aceiaşi mulţime pool. Regula b) elimină insă
18
pe S121 pentru că r121 face parte din S121
Structura liniarizată a produsului completată cu listele de matrice şi cu fazele de execuţie
va arăta astfel:
P (f1,f2,f3) S1[m0] (f1,f2,f3,f4)
S11[m0,m1](f1) r11[m0,m1,m2] (f1,f2,f3)
S12[m0,m1] (f1,f2) S121[m0,m1,m2] (f1,f2) r121[m0,m1,m2,m3] (f1,f2)
S2[m0](f1) r2[m0,m1] (f1,f2)
S3[m0] (f1,f2) S31[m0,m1](f1)
r311[m0,m1,m2] (f1)
r312[m0,m1,m2] (f1,f2)
Această structură se obţine din procesul de derivare caracteristic gramaticilor matriciale.
Pentru a păstra si simbolurile neterminale care reprezintă subansamble am modificat regulile
de derivare din matrice astfel:
mo [ P →P S1 S2 S3 ]
m1 [ S1 → S1S11 S12 , S2→ S2 r2 , S3 → S3 S31 ]
m2 [ S11→ S11 r11 , S12 → S12 S121 , S31 → S31 r311 r312 ]
m3 [ S121→ S121 r121 ]
Simbolurile subliniate semnifică că ele au fost deja rescrise şi nu vor mai fi expandate prin
derivare. Ele de fapt ajung pe post de terminale.
Algoritmul de planificare va scana (parcurge) structura liniarizată de la dreapta la stânga
înaintea uneia sau mai multor alocări de faze la posturi de lucru în vederea depistării fazelor ce
pot fi executate in paralel. Pe ultimul exemplu prima mulţime pool construită cu cele două
reguli a) şi b) va fi:
r11 (f1,f2,f3), r121 (f1,f2), r2 (f1,f2), r311 (f1), r312(f1,f2)
Fazele aferente unui reper (dintre paranteze rotunde) se planifică şi execută secvenţial
pentru a respecta tehnologia de fabricaţie.
În acest din urmă caz s–a ajuns astfel la o planificare în execuţie a unor fire de execuţie
în care pot fi folosite diverse metode de alocare a resurselor unele chiar împrumutate din teoria
sistemelor de operare.
Algoritmul de planificare alocă fazele pe posturi de lucru dintr-o mulţime pool apoi
formează o nouă mulţime pool pentru alocare pe posturi de lucru. Acest proces se repetă până
19
când se planifică toate fazele de execuţie aferente unui produs sau a tuturor produselor de
fabricat.
Formarea unei noi mulţimi pool se poate face la sfârşitul planificării tuturor fazelor din
mulţime pool anterioară sau chiar pe parcurs după alocare tuturor fazelor unui reper, pentru a
mării gradul de paralelism. În exemplu nostru după planificare fazelor reperului r121 se poate
forma o nouă mulţime pool ce va include subansamblu imediat superior acestui reper şi anume
S121(f1,f2)
Pentru fabricaţia pe loturi sau a mai multor produse, loturile sau produsele vor fi
considerate implicit ca putând fi planificate in execuţie in paralel. Mulţimile pool vor fi de fapt
seturi de mulţimii pool aferente fiecărui lot sau produs. Se ajunge astfel la o ierarhie de fire de
execuţie in care se pot stabili diverse strategii de priorităţi în planificare. În interiorul unui lot
sau produs priorităţile pot fi:
o1) - timpul cel mai scurt de execuţie pentru a nu ţine ocupat un post de lucru prea mult in
detrimentul altuia, sau
o2) - o ordine in funcţie de lungimea ramurii din care provine faza respectivă preferându-
se ramurile lungi in timp pentru a scurta pe total timpul de execuţie, sau
o3) - o ordine in funcţie de nişte priorităţi stabilite de utilizator anterior sau
o4) - pur şi simplu in ordinea apariţiei in structura liniarizată.
Între loturi sau produse priorităţile pot fi:
op1 – în funcţie de termenul de predare a seriei produselor p, cele cu termen de predare
mai devreme vor avea o prioritate mai mare
op2 - în funcţie de numărul total de faze de execuţie pentru un produs, cele cu faze mai
multe cu prioritate mai mare
op3 - în funcţie de timpul total de execuţie al uni produs, cele cu timpi totali mai mari să
aibă prioritate mai mare. Timpul total de execuţie pentru un produs este
însumarea timpului tuturor fazelor de execuţie dacă acestea ar fi executate
secvenţial şi continuu.
Un algoritm complet ar folosi pe rând priorităţile de mai sus şi ar combina priorităţile de tip
ox) cu cele de tip opy. Ar rezulta mai multe planuri de fabricaţie din care utilizatorul să îl
aleagă pe cel mai performant, conform cerinţelor stabilite de utilizator.
Algoritmii pentru planificare sunt prezentaţi pe larg in capitolul 7.
20
CONCLUZII
Gramaticile bi-paralele matriciale pot fi utilizate în sisteme ierarhice (management,
procese de fabricaţie ) care au un oarecare paralelism orizontal şi (sau) vertical.
Divizarea orizontală poate fi utilizată ca o funcţie de descompunere pentru sistemele
ierarhice (descompunerea unei decizii/acţiuni). Modelarea planificării producţiei prin gramatici regulate şi operaţia shuffle este simplă
ca şi instrument de modelare dar necesită resurse de memorie şi timp considerabile.
Operaţia shuffle nu se poate substitui unui model paralel şi nu poate modela
paralelismul din cadrul structurii unui produs
Modelarea producţiei prin gramatici matriciale oferă un grad mai mare de paralelism în
planificare, mergând chiar până în interiorul structurii produsului
Modelul planificării producţiei bazat pe gramatici matriciale permite o implementare
unitară (structură împreună cu tehnologie), mai uşoară şi algoritmi de planificare ai
producţiei mai eficienţi decât cei bazaţi pe operaţia shuffle
Gramaticile matriciale pot modela uşor şi fabricaţia distribuită. Gramaticile matriciale
bi-paralele pot face planificări ale procesului de fabricaţie separat pe departamente şi
secţii de fabricaţie. Mecanismele de sincronizare între gramaticile bi-paralele asigură
tratarea în ansamblu a producţiei distribuită.
Algoritmul de planificare a operaţiilor de fabricaţie poate fi folosit şi pentru alte tipuri
de activităţi care au operaţii cu timpi de execuţie cunoscuţi sau aproximaţi dinainte.
Pentru o modelare a procesului de fabricaţie cu gramatici matriciale (sau bi-paralele)
automatele de contracţie generalizate (sau automatele bi-paralele) pot verifica
corectitudinea unei planificări manuale sau a unor modificări manuale făcute unei
planificări generate de model. Modificările pot apare pe parcursul fabricaţiei datorită
unor evenimente neprevăzute (lipsă material, operator utilaj indisponibil pe o
perioadă, utilaj defect).
Prin gramatici matriciale se pot modela şi alte tipuri de activităţi care presupun
paralelism
Contribuţiile proprii din această lucrare sunt:
• gramaticile bi-paralele obţinute prin divizarea unei gramatici matriciale;
21
construcţia lor efectivă si modul detailat de funcţionare şi sincronizare a lor sunt
prezentate pe larg in subcapitolul 3.3, în articolele ştiinţifice [12], [13], [14] şi în
[19]
• automatul de contracţie generalizat cu relaţii de precedenţă ; acest automat este
valabil pentru mai multe tipuri de gramatici matriciale şi are un grad redus de non-
determinism; foloseşte în acţiunea de contracţie relaţiile de precedenţă Wirth-
Weber; automatul este introdus şi prezentat în subcapitolele 4.4, 4.5 şi în [20]
• formula computaţională pentru operaţia shuffle şi optimizarea ei; determinarea
formulei s-a făcut prin inducţie matematică; implementarea ei, analiza rezultatelor
şi optimizările aduse sunt prezentate pe larg în subcapitolele 5.2 şi 5.3, în
comunicări ştiinţifice [15 ] , [16 ] , [17 ] precum şi în [21]
• modelul de planificare a producţiei bazat pe gramatici matriciale; model care
tratează in mod unitar structura şi tehnologia produsului şi scoate in evidenţă
paralelismul operaţiilor de fabricaţie; este introdus şi prezentat pe larg în
subcapitole 7.2, 7.3, 7.8, precum şi în [21]
• algoritm planificare producţie in paralel ; bazat pe modelul produsului
implementat prin gramatici matriciale, algoritmul extrage înaintea oricărei
planificări fazele de execuţie care pot fi executate în paralel; variantele
algoritmului(producţie unicat, de serie, în loturi, mai multe produse diferite) sunt
prezentate în subcapitole 7.5, 7.6 precum şi în [21]
22
Bibliografie: [1] Abraham S., Some Question of Language Theory, International conference on Computational
Linguistic, pg. 7-11, 1965, Budapest, Hungary [2] Abraham S., Compound and serial grammars, Information and Control, 20, pg. 432-438, 1972 [3] Baker, K.R., Introduction to Sequencing and Scheduling, John Wiley & Sons, New York, 1974 [4] Baker, K.H. and Scudder, G.D., Sequencing with earliness and tardiness penalties: a review,
Operations Res., 30, 22, 1990 [5] Balakrishnan, N., Kanet, J.J., and Sridharan, V., Early/tardy scheduling with sequence dependent
setups on uniform parallel machines, Computers Operations Res., 26, 127, 1999 [6] Blazewicz, J., Ecker, K.H., Pesch, E., Schmidt, G., and Weglarz, J., Scheduling in Computer and
Manufacturing Systems, Springer Verlag, Berlin, 1994 [7] Brucker, P., Scheduling Algorithms, Springer Verlag, Berlin, 2001 [8] Clark, A.R., Approximate combinatorial optimization models for large-scale production lot sizing
and scheduling with sequence-dependent setup times, in Proc. IV ALIO/EURO Workshop Appl. Combinatorial Optimization, Pucón, Chile, November 2002
[9] Clark, A.R. and Armentano, V.A., A heuristic for a resource-capacitated multistage lot-sizing problem with lead times, J. Operational Res. Soc., 46, 1208, 1995
[10] Ferrel, W., Jr., Sale, J., Sams, J., and Yellamraju, M., Evaluating simple scheduling rules in a mixed shop environment, Computers Ind. Eng., 38, 39, 2000
[11] Ginsburg, S. Greibach A., – “Abstract Families of Language”, American Math. Society Memoirs, pg.30-76, 1969
[12] Golomety A., Horizontal Parallel Grammars, Proc of 5thRoedunet IEE International Conference, Sibiu România, 1-3 iunie 2006, pp.300-305, ISBN(10) 973-739-277-9
[13] Golomety A., Popa E.M., Strings Generation By Bi-Parallel Grammars In Distributed Models, Proc of the 8th WSEAS Int. Conf. on Mathematical Methods and Computational Techniques in Electrical Engineering MMACTEE 2006, Bucharest, Romania 16-18 octomber 2006, pg.124-29, ISBN: 960-8457-54-8, ISSN: 1790-5117
[14] Golomety A., Popa E.M., Formal modeling by a bi-parallel grammar, WEAS Transaction on Information Science and Application, volume 4 January, 2007, pg.139-144, ISSN:1790-0832
[15] Golomety A., Pitic Alina, Golomety I., Pitic Antoniu, Implementation Of Shuffle Operation In Manufacturing Process Planning,, Proc of the 3rd International Conference On Manufacturing Science And Education - MSE 2007, Sibiu, Romania, July 12-14, 2007 pp. 161-162, ISSN: 1583-7904
[16] Golomety A, Pitic Alina., Golomety I, Pitic Antoniu, Production Planning by Shuffle Operation, Proc of the 11th WSEAS International Conference on COMPUTERS, Agios Nikolaos, Crete Island, Greece, July 26-28, 2007 pp. 178-183,ISBN: 978-960-8457-95-9, ISSN: 1790-5117
[17] Golomety A., Pitic Alina, Golomety I., Pitic Antoniu, Implementation Of Shuffle Operation In Manufacturing Process Planning,, Academic Journal of Manufacturing Engineering Volume 5 Number 2/2007 , Timişoara, Romania 2-14, 2007 pp. 161-162, ISSN: 1843-2522
[18] Golomety A., Proiectarea translatoarelor, Editura Universităţii Sibiu 1997, ISBN 973-9280-59-9, Bibl. ULBS, DEP 41.646
[19] Golomety A., Paralelismul natural in limbaje formale, Referat 1, Stagiu doctorat, octombrie 2005 [20] Golomety A., Automate pentru gramatici matriciale, Referat 2, Stagiu doctorat, octombrie 2006
23
[21] Golomety A., Modele formale în programarea producţiei, Referat 3, Stagiu doctorat, noiembrie 2007
[22] Golomety A., Transformation des languages secventielles dans des languages concurentes, Acta Universitatis Cibiensis, vol.IX, Universitarea din Sibiu, pg.95-100, ISSN 1221-4930, 1993
[23] Golomety A., Volovici D., Nilsson Algorithm in Semantic Analyse of Attributes Grammars, Acta Universitatis Cibiensis, vol.nr. XXXI, pg.55-64, ISSN 1221-4930, 1998
[24] Golomety A., Spatial Locality by Automatic Layout, Acta Universitatis Cibiensis, vol. nr. XXXI, pg.75-83, ISSN 1221-4930, 1998
[25] Gorsher Jay, Shullfe languages, Petri nets and context sensitive grammars, Comunications of ACM, vol.24 isue 9 , 1981, pp. 328-342
[26] Greibach S, Hopcroft J., Scattered context-grammars, Journal. of Computer şi System Science, 3, pg.233-247, 1969
[27] Ibarra O., Simple matrix languages, Information şi Control 17, pg. 359-394, 1970 [28] Irani, S. and Karlin, A.R., Online computation, in Approximation Algorithms for NP-Hard
Problems, Hochbaum, D.S., Ed., PWS Publishing Company, Boston, 1996 [29] Kim, J. and Kim, Y., Simulated annealing and genetic algorithms for scheduling products with
multilevel product structure, Computers Operations Res., 23, 857, 1996 [30] Lawler, E.L., Lenstra, J.K, Rinnooy Kan, A.H.G., and Shmoys, D.B., Sequencing and scheduling:
algorithms and complexity, in Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, Graves, S., Rinnooy Kan, A.H.G., and Zipkin, P.H., Eds., 4, North–Holland, 445, 1993
[31] Marcus S., Contextual grammars,Rev.Roumaine Math. Pures et Appl., 14,10, 1969, pg.1523-1534 [32] Martin-Vide C. Formal Languages for Linguists: Classical şi Nonclasical Models, Conf. TALN
2001, pg. 26-51, 2001 [33] Massimo P., Roberto S.,Agent-Based Manufacturing and Control Systems, Auerbach Publications,
chapter 3, 2005 [34] McClellan, M., Applying Manufacturing Execution Systems, St. Lucie Press, Boca Raton, FL, 1997 [35] Panwalkar, S.S. and Iskander, W., A survey of scheduling rules, Operation Res., 25, 45, 1977 [36] Nahmias, S., Production and Operation Analysis, 3rd ed., Irwin, Burr Ridge, IL, 1997 [37] Păun Ghe., Mecanisme Generative pentru Procese Economice, Ed.Tehnica, pg. 48-53,
112-116, 1980 [38] Păun Ghe., Gramatici contextuale, Ed.Academiei, pg. 14-32, 138-142, 1982 [39] Păun Ghe., Gramatici matriciale, Ed.Stiintifică şi Enciclopedică, pg. 35-45,104-109, 1981 [40] Pinedo, M., Scheduling: Theory, Algorithms & Systems, Prentice Hall, Upper Saddle, NJ, 2002 [41] Rus Th., Mecanisme Formale pentru Specificarea Limbajelor, Ed.Academiei, pg.52-55,86-96.
1983 [42] Shapiro, J.F., Mathematical programming models and methods for production planning and
scheduling, in Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, Graves, S., Rinnooy Kan, A.H.G., and Zipkin, P.H., Eds, North–Holland, Amsterdam, 4, 1993
[43] Shen-Pei Wang P., Grosky W.I., A language for Two-Dimensional Digital Picture Procesing, ACM symposium on Graphic languages, pg.1-4, 1976
[44] Shen, W. and Norrie, D.H., Agent-based systems for intelligent manufacturing: a state-of-the-art survey, Knowledge Inf. Syst. Int. J., 1, 129, 1999
24
[45] Shen, W., Distributed manufacturing scheduling using intelligent agents, Intelligent Syst., 17, 88, 2002
[46] Shen, W. and Norrie, H.N., An agent-based approach for dynamic manufacturing scheduling, in Proc. Autonomous Agents’98 Workshop Agent-Based Manuf., Minneapolis/St.Paul, MN, 117, 1998
[47] Sgall, J., On-line scheduling, in On-line Algorithm: the State of the Art, Lecture Notes in Computer Science, Fiat, A. and Woeginger, G.J., Eds., Springer, Berlin, 1442, 196, 1998
[48] Sridharan, V. and Kanet J.J., Scheduling with inserted idle time: problem taxonomy and literature review, Operations Res., 48, 99, 2000
[49] Thomas, L.J. and McClain, J.O., Overview of production planning, in Logistics of Production and Inventory, Handbooks in Operations Research and Management Science, Graves, S., Rinnooy Kan, A.H.G., and Zipkin, P.H., Eds,, North–Holland, Amsterdam, 4, 1993
[50] Wagner, H.M. and Whitin, T.M., Dynamic version of the economic lot size model, Manage. Science, 5, 89, 1958
[51] Wolsey, L.A., MIP modelling of changeovers in production planning and scheduling problems, Eur. J. Operational Res., 99, 154, 1997
[52] ANSI/ISA-95.00.01-2000, Enterprise-control system integration part 1: models and terminology, ANSI/ISA-95.00.02-2001, Enterprise-control system integration part 2: object model attributes, available at http://www.isa.org/
[53] ISA-5.1-1984 - (R1992): Instrumentation symbols and identification available at www.isa.org
25