Flow Shop Scheduling Problem V3(1) [608877]

Facultatea de Construcții de Mașini Școala doctorală
Departamentul de Ingineria Fabricatiei
Conducător Științific: Profesor dr. ing. Ancău Mircea Doctorand: [anonimizat] 1/34

Cuprins
1. Incadrarea temei de cercetare in domeniul stiintific ………………………………………………… 3
1.1 Introducere……………………………………………………………………………………………………. 3
1.2. Stadiul actual al cercetarilor ………………………………………………………………………….. 4
1.2.1 Notatii…………………………………………………………………………………………………….. 4
1.2.2 Tehnici de rezolvare a flowshop scheduling problem ……………………………………. 7
1.2.2.1 Algoritmi euristici ………………………………………………………………………………. 7
1.2.2.2 Algoritmi metaeuristici ………………………………………………………………………. 7
1.2.2.2.1 Algoritmi Single Point ……………………………………………………………………… 8
1.2.2.2.2 Algoritmi Population Based Search ………………………………………………….. 9
1.2.3 Clasificarea problemelor de planificare a executarii joburilor pe masini in functie
de mediul de productie …………………………………………………………………………………. 10
1.2.3.1 Flow shop scheduling problem cu capacitate de stocare intermediara
nelimitata …………………………………………………………………………………………………. 10
1.2.3.2 Permutation flow shop scheduling problem ……………………………………… 11
1.2.3.2.1 Indexarea ………………………………………………………………………………….. 12
1.2.3.2.2 Construirea solutiei …………………………………………………………………….. 15
1.2.3.2.3 Imbuntatirea solutiei …………………………………………………………………… 19
1.2.3.2.4 Algoritmi metaeuristici de cautare …………………………………………………. 20
1.2.3.3 Flow shop scheduling problem cu diferite constrangeri ………………………. 25
1.2.3.3.1 Flow shop scheduling problem cu capacitate de stocare limitata ……..25
1.2.3.3.2 No-wait flow shop scheduling problem ………………………………………….. 26
1.2.3.3.3. Sequence-dependent set-up times flow shop scheduling problem
(SDST)…………………………………………………………………………………………………….. 26
1.2.3.4. Flow shop scheduling problem cu mai multe functii obiectiv …………………27
2. Relevanta temei in raport cu cercetarile existente. …………………………………………………. 29
Bibliografie…………………………………………………………………………………………………………… 30
Pag. 2/34

1. Incadrarea temei de cercetare in domeniul stiintific
1.1 Introducere
Flow shop scheduling problem face parte din job shop scheduling clasa problemelor
de planificare in care fluxul de productie permite procesarea unei secvente de joburi pe un
set de masini si se doreste mentinerea unui flux continuu in procesarea taskurilor,
minimizarea timpului in care masinile nu sunt folosite, minimizarea timpului de asteptare.
Flow shop scheduling problem este un caz special al job shop scheduling in care este
mentinuta ordinea stricta a operatiilor pe masini, masinile fiind aranjate in ordinea
efectuarii operatiilor si fluxul de productie este unidirectional. In productie pentru joburile
cu operatii multiple masinile sunt instalate in serie. Mai intai materia prima ajunge pe prima
masina si cand jobul procesat este terminat pe prima masina el se muta pe masina
urmatoare. Daca urmatoarea masina nu este libera jobul trebuie sa astepte pana cand
masina il poate procesa.
Flow shop scheduling problem are multiple aplicatii si o biectivele principale sunt
imbunatatirea utilizarii resurselor si cresterea profitabilitatii productiei. In ciuda simplicitatii
ei aparente este foarte dificil de rezolvat optim intr-un timp polinomial fiind de domeniul
problemelor de optimizare combinatorica NP-hard.

Flow shop scheduling problem se poate enunta in modul urmator:
Consideram o multime de n piese (sau loturi de piese) ce trebuie prelucrate pe m masini
diferite in aceeasi ordine. Obiectivul principal este determinarea ordinii de prelucrare a
pieselor (loturilor de piese) astfel incat timpul total de prelucrare notat Cmax (total
completion time sau makespan) sa fie minim. Timpii de prelucrare pieselor (loturilor de
piese) pe masini, notati pij (i = 1,2, …, n, j = 1,2, …, m) , sunt cunoscuti in prealabil,
constanti ca valoare si pozitivi.
In cadrul acestei probleme se pleaca de regula de la o serie de presupuneri:
a) toate job-urile sunt independente si disponibile pentru prelucrare la momentul t = 0,
b) toate masinile sunt in permanenta disponibile,
c) fiecare job poate fi prelucrat la un moment dat pe o singura masina,
d) fiecare masina poate executa la un moment dat o singura lucrare,
e) odata inceputa o prelucrare, aceasta nu poate fi intrerupta,
f) timpii de pregatire-incheiere (set-up times) sunt inclusi in timpii de fabricatie,
g) timpii auxiliari de organizare a joburilor pe fiecare dintre masini se neglijeaza,
h) daca masina care urmeaza in itinerarul tehnologic nu este disponibila(fiind ocupata cu
un alt job) urmatoarele job-uri din lista vor fi repartizate intr-o lista de asteptare.
Pag. 3/34

1.2. Stadiul actual al cercetarilor
1.2.1 Notatii
Cele trei componente ale unei probleme de scheduling sunt:
numarul de joburi , numarul de masini si timpul de procesare al fiecarui job pe fiecare
masina.
un set de constrangeri in executarea operatiilor pe masini 
o functie obiectiv care consta in unul sau mai multe criterii de decizie (denumite si 
obiective de optimizat)
Pentru o mai buna descriere a problemelor de scheduling Graham(1979)[103] a propus
urmatoarea tripleta a | b | g . Notatia sa, preluata de cercetarile ulterioare, foloseste trei
parametrii :
–a – configuratia mediului de productie.
–b contine constrangeri speciale ale mediului de productie sau parametrii
impredictibili. De exemplu c onstangerea asupra fiecarei masini de a avea o coada
de asteptare de tip FIFO. Dupa terminarea unui job pe o masina acesta este inclus
in coada de asteptare a joburilor de executat pe urmatoarea masina. In general
ordinea de parcurgere a cozii de asteptare este First In First Out (FIFO) pentru
joburile care vor fi efectuate . In acest caz parametrul b va contine notatia prmu si
avem o problema de tip permutation flow shop
–g corespunde criteriului de decizie sau obiectivelui de optimizare
Flow shop scheduling problem intr-un mediu de productie cu m masini in serie si n
joburi, in care fiecare job trebuie sa fie procesat o data pe fiecare masina si toate joburile
urmeaza acceasi ordine (se proceseaza prima data pe prima masina, pe urma pe a doua
masina si asa mai departe) este notat Fm.
In lumea reala, mediile de productie sunt supuse unor factori impredictibili care pot avea un
impact major cum ar fi oprirea sau revizia unei masini, joburi cu importananta mai mare fata
de altele, nu se stie cu exactitate timpul de executie al unui job inainte de inceperea
procesului, etc.
Pinedo(2008)[1] prezinta si noteaza principalele constrangeri ale unui Fm :
–Breakdowns (brkdwn). Se considera ca o masina nu este tot timpul disponibila, de
obicei perioada de indisponibilitate a masinii se considera fixa.
–Blocking (block). In general capacitatile de stocare (sau buffer) intre masinile
succesive se considera a fi nelimitate in cazul cand produsele procesate sunt fizic
mici (ex placi de circuite integrate), facand relativ usor stocarea unor cantitati mari
intre masini. Atunci cand produsele sunt fizic mari (de exemplu, televizor, copiator)
capacitatea de stocare intre doua masini succesive poate fi limitata, provocand
blocarea. Blocarea are loc cand buffer-ul este plin. Masina anterioara nu finalizeaza
jobul curent si este impiedicata sa efectueze urmatorul job deoarece nu are voie sa
trimita produsul in capacitatea de stocare.
Pag. 4/34

–No-wait (nwt). Job-urile nu au voie sa-si astepte procesarea intre doua masini
succesive. Timpul de start al job-ului pe prima masina va fi intarziat pentru a se
asigura ca job-ul nu va astepta sa fie procesat pe urmatoarele masini.
–Preemptions (prmp) Nu este necesara mentinerea pe o masina a prelucrarii unui
job o data ce a inceput prelucrarea si este permisa intreruperea procesarii jobului in
orice moment de timp si schimbarea jobului cu altul. Partea efectuata deja pe jobul
intrerupt nu este pierduta, executia lui continuind pe o masina paralela care va
efectua doar timpul ramas.
–Release dates (rj ) Timpul in care jobul ajunge in sistemul de prelucrare sau cel
mai rapid timp pentru care poate incepe procesarea jobul j .
–Due date (dj) data pana la care trebuie sa fie terminat jobul. In cazul in care
finalizarea jobului este permisa dupa aceasta data se prevad penalitati. Cand exista
cerinta specifica ca prelucrarea jobului trebuie sa atinga valoarea due date atunci
constrangerea se numeste deadline (dj).
–Weight (wj) ponderea job-ului j in raport cu altele
Completion time (C).
Timpul in care se efectueaza jobul j pe masina i se noteaza Cij .
Timpul necesar efectuarii jobului j pana la ultima masina se noteaza Cj .
Lateness sau intarzierea efectuarii jobului j se defineste prin Lj = Cj −dj
Cand Lj > 0 jobul este terminat mai tarziu.
Cand Lj < 0 jobul este terminat mai repede .
Tardiness sau cea mai mare intarziere a efectuarii jobului j se defineste prin
Tj = max(Cj − dj , 0) = max(Lj, 0)
Spre deosebire de lateness, tardiness nu poate fi niciodata negativa
Unit penalty Unitatea de penalizare pentru jobul j are valorile 1 sau 0.
1 daca Cj > dj sau 0 in restul situatiilor.
Obiectivele de optimizat sau criteriile de decizie ale Fm pot fi de doua tipuri:
•Functii monotone necrescatoare in completion times C 1, . . ., Cn :
1.Makespan Cmax = max(C1, . . ., Cn)
Este echivalent cu timpul scurs pana la executia ultimului job . Un makespan minim
implica o buna utilizare a masinilor.
2.Maximum Lateness Lmax = max(L1, . . ., Ln).
Masoara cea mai mare depasire a due dates (a datelor pana la care trebuie
terminate joburile).
Pag. 5/34

3.Total weighted completion time sau weighted flow time S (wjCj) .
Este suma totala ponderata a timpul de finalizare a n joburi
Suma totala a timpul de finalizare a n joburi se numeste flow time.
4.Total weighted completion time sau weighted flow time S (wjCj) .
Este suma totala ponderata a timpul de finalizare a n joburi si este o functie de cost
ce indica costurile suportate de planificare.
5.Discounted total weighted completion time S wj ( 1−e−rCj ) .
Functie de cost in care costurile sunt reduse la o rata r unde 0 <r <1 pe unitatea de
timp.
Daca jobul j nu este finalizat in timpul t un cost suplimentar wj r e−rt dt este suportat
pe perioada [ t, t + dt ].
Daca jobul j este finalizat in timpul total t atunci costul total este wj ( 1− e−rt) pe
perioada [0, t] .Valoarea r este apropiata de 0 (ex. 0,1 sau 10%).
6.Total weighted tardiness S wjTj
Este suma ponderata a timpilor de finalizare.
7.Weighted number of tardy jobs S wjUj
Este suma ponderata a joburilor cu intarziere
•Functii neregulate in completion times C 1, . . ., Cn :
1.Total earliness + total tardiness S Ej + S Tj , j = 1 … n
Ej = max(dj − Cj , 0) defineste earliness penalty sau penalitate timpurie pentru un
job j avand due date egala cu dj .
2.Total weighted earliness + total weighted tardiness S w'j Ej + S w''j Tj , j = 1…n
w'j reprezenta ponderea asociata cu earliness penalty pentru jobul j
w''j reprezenta ponderea asociata cu tardiness pentru jobul j
Diagrama Gantt reprezentarea grafica in care axa orizontala reprezinta timpul de
prelucrare a joburilor si axa verticala reprezinta masinile.
Ex. Diagrama Gantt pentru cazul prelucrării a 3 joburi pe 3 masini
Pag. 6/34

1.2.2 Tehnici de rezolvare a flowshop scheduling problem
Flowshop scheduling problem face parte din categoria problemelor de optimizare
combinatorica NP-hard.
Tehnicile de optimizare combinatoriala folosite se pot grupa in doua categorii generale:
•metode exacte – care urmaresc rezolvarea problemei garantand solutia optimala.
Acestea sunt mai putin folosite in problemele de dimensiuni mari din lumea reala
datorita timpului mare de calcul. Una dintre metodele este enumerarea tuturor
solutiilor si explorarea fiecareia cu scopul gasirii celei optime. Alta metoda exacta
folosita este tehnica branch-and-bound(B&B) unde limitele upper bounds sau
lower bounds ale solutiei sunt folosite ca sa restictioneze spatiul de cautare.
•metode aproximative (euristice si metaeuristice). Agrawal(2015)[5] trece in
revista principale metode euristice si metaeuristice.
Alte tehnici folosite sunt retelele neuronale .
1.2.2.1 Algoritmi euristici
Algoritmi heuristici reprezinta tehnica prin care se gasesc solutii bune cu un cost
computational rezonabil, solutia gasita nefiind intotdeuna si cea optima. Exista doua
tipologii de algoritmi euristici:
•constructive heuristics care construiesc treptat o solutie posibila (secventa de
joburi) si incearca sa reduca costul functiei obiectiv, dependenta de timpii de
executie, pe baza anumitor decizii (ex FIFO) sau reguli de permutare
•improvement sau iterative heuristics pornesc de la o solutie care poate fi chiar
furnizata de un algoritm din prima categorie, sau o solutie slaba si o i mbunatatesc
la fiecare iteratie, printr -o anumita metoda pentru a obtine o solutie mai buna.
1.2.2.2 Algoritmi metaeuristici
Algoritmii metaeurisrici vin in sprijinul optimizarii solutiei algoritmilor euristici, ei propunand
solutii de buna calitate la probleme de optimizare combinatorica NP-hard intr-un timp
rezonabil. Procesul de generare a solutiei este iterativ facandu-se ghidarea in explorarea
spatiului de cautare a unui euritic subordonat. Se folosesc strategii de invatare pentru a
organiza informatia in scopul gasirii celor mai apropiate solutii optime.
Proprietatile algorimilor metaheuristici:
•non deterministici,
•incorporeaza mecanisme care ii ajuta sa nu ramana blocati pe un optim local cand
exploreaza spatiul
•permit un nivel abstract de descriere,
•nu se adreseaza unei probleme specifice,
•exploreaza spatiul in ordinea gasirii celei mai apropiate solutii optime.
Algoritmii metaheuristii folosesc doua tipuri de proceduri de cautare:
•single point
•population based search
Pag. 7/34

1.2.2.2.1 Algoritmi Single Point
Algoritmii de tipul Single Point se concentreaza pe modificarea si imbunatirea unei
singure solutii candidat.
Tipurile de algoritm Single point includ Tabu Search si Simulated Annealing
•Tabu Search (TS)
Tabu Search (TS) este tehnica meta-euristica de cautare care are la baza ideea propusa
de Fred Glover (1977, 1986) [36] de a depasi bariera optimului local. Algoritmul se
bazeaza pe o lista de configuratii prohibite (lista ' tabu') care este o lista a tuturor mutarilor
posibile asociate cu o solutie si ghideaza procedura de cautare locala heuristica in
explorarea spatiului. Se porneste cu o solutie initiala care este obtinuta cu un algoritm
constructiv si apoi strategia de mutare determina modul in care vecinii vor fi vizitati. Pentru
diversificarea cautarii fiecare mutare este inclusa in lista tabu si pastrata un numar de
iteratii prestabilit.
1.Creaza solutia initiala (care poate fi generata si aleator), numita solutia curenta
2.Cauta cel mai bun vecin al solutiei curente aplicand cateva mutari
3.Daca cel mai bun vecin este gasit se accepta solutia noua ca si solutie curenta si se
efectueaza o miscare non-tabu, altfel se continua cautarea celui mai bun vecin
non-tabu
4.Daca numarul maxim de iteratii este atins (sau alta conditie de oprire), se executa
pasul 5 altfel se executa pasul 2.
5.Cea mai buna solutie globala este cea mai buna solutie solutia curenta sau cea mai
buna solutie intalnita este returnata

Printre cercetatorii care au folosit abordari ale Tabu Search in rezolvare problemelor
flowshop sheduling se numara Taillard(1990)[4], Reeves (1993)[16] si Mocellin(2005)[17]
•Simulated Annealing (SA)
Simulated Annealing ofera o solutie buna nu neaparat optima intr-un timp rezonabil, a
fost introdusa de Kirkpatrick (1983) [18]. In general se cauta minimul sau maximul global
al unei functii intr-un spatiu mare care contine mai multe minime sau maxime locale. Ea
este inspirata din tehnica de cristalizare fizica a materialelor solide folosita in metalurgie
care implica incalzirea unui metal pana la o temperatura mare urmand ca acesta sa fie
racit treptat si controlat (in functie de metal). Acest proces intareste metalul si elimina
defectele.
In cazul optimizarii algoritmul este asemanator cu procesul fizic asa cum a arata Cerny
(1985)[19], folosind un parametru numit temperatura care porneste de la o valoare initiala
mare si care scade treptat in fiecare iteratie. Aceasta valoarea controleaza probabilitatea
cu care solutiile mai putin bune decat cea curenta sunt acceptate.
Simulated Annealing poate fi aplicat pentru a optimiza o solutie, acesta aducand
modificari mici solutiei curente pentru a explora spatiul. Scopul algoritmului este de a gasi
o solutie cu energie minima pornind de la o solutie initiala oarecare, in unele cazuri chiar
aleatoare, evaluata la o anumita energie initiala.
La fiecare pas Simulated Annealing evalueaza una sau mai multe solutii vecine ale
solutiei curente alese dupa o anumita regula sau aleator. In cazul in care o solutie vecina
este mai buna decat cea curenta, algoritmul trece la aceasta solutie.
Daca solutia noua nu este mai buna decat cea curenta aceasta poate totusi sa fie
Pag. 8/34

acceptata cu o anumita probabilitate. Aceasta probabilitate depinde atat de temperatura
curenta (cu cat temperatura este mai mare cu atat probabilitatea de acceptare este mai
mare) cat si de diferenta dintre energia solutiei noi si cea a solutiei curente (cu cat aceasta
diferenta este mai mare cu atat probabilitatea de acceptare este mai mica).
Simulated Annealing continua pana cand una dintre conditiile de terminare este atinsa:
–O solutie care este considerata indeajuns de buna a fost deja gasita, deci
continuarea executiei algoritmului nu este necesara
–Dupa un anumit numar predefinit de iteratii nu a fost gasita o solutie mai buna decat
cea curenta
–Un numar maxim de iteratii a fost atins
–Timpul alocat pentru executia algoritmului a expirat, solutia curenta sau cea mai
buna solutie intalnita este returnata.
1.2.2.2.2 Algoritmi Population Based Search
Algoritmi Population Based Search mentin si imbunatatesc solutii candidat multiple,
bazandu-se in ghidarea cautarii pe caracteristicile populatiei. Algoritmii furnizeaza o solutie
optima prin mutarea unei multimi de solutii de la o generatie la alta . Principala lor limitare
este ca in gasirea solutiei optime pe langa parametrul de control sunt ceruti si alti
parametrii specifici. In flow shop scheduling problem parametrul specific creaza dificultati
atunci cand creste numarul de masini si de joburi.
•Genetic Algorithm (GA) – Algoritmi Genetici
Algoritmi Genetici pornesc de la o populatie initiala generata aleator si ruleaza pana
cand conditia de oprire este indeplinita: gasirea unei solutii suficient de buna, expirarea
timpului, etc. Dupa evaluarea populatiei initiale algoritmul genetic intra in secventa loop
principala si daca nu se indeplineste conditia de oprire intra in faza de selectie in care
anumiti indivizi din intreaga populatie devin parinti. Parintii vor produce urmasi folosind
incrucisarea si/sau mutatia si indivizii rezultati vor forma generatia urmatoare care va fi
supusa evaluarii. In functie de algoritm o noua populatie de parinti se obtine in mod simplu
folosind urmasii pe post de parinti sau prin alte mecanisme de combinare precum elitismul
in care se aleg atat parinti cat si urmasi.
•Bio-inspired Algorithms:
1. Particle Swarm Optimization (PSO)
Optimizarea prin modelul ansamblurilor de particule face parte din categoria
algoritmilor inspirati din natura de comportamentul stolului de pasari. In PSO indivizii
(numiti particule) “zboara” in spatiul desemnat urmand cel mai bun individ. Indivizii sunt
modelati in spatiul multidimenional ca avand asociate o pozitie si o viteza. Indivizii se
evalueaza ei insasi si isi reamintesc locatiile unde au avut cel mai mare succes. Toti
indivizii sunt informati despre cel mai bun succes individual gasit si miscarea in spatiul de
cautare este ghidata de succesele anterioare. Fiecare individ isi ajusteaza propria pozitie
si viteza pe baza acestor informatii.
2. Ant Colony optimization algorithm (ACO)
Algoritm methauristic inspirat din comportamentul furnicilor. Ideea principala consta in
comunicarea indirecta dintre furnici, prin urmele de feromoni lasate, ceea ce le ajuta sa
gaseasca un drum cat mai scurt intre locul in care se gaseste hrana si musuroiul lor. In
natura, furnicile umbla de obicei aleator iar la gasirea hranei se intorc la musuroi lasand
Pag. 9/34

urme de feromon. Daca alte furnici gasesc aceste urme de feromoni, ele sunt norocoase
deoarece nu trebuie sa mai caute hrana umbland la intamplare ci urmarind aceste urme
de feromoni si intarindu-le in cazul in care gasesc si ele la randul lor hrana. Oricum, odata
cu trecerea timpului, feromonul incepe sa se evapore. Cu cat unei furnici ii ia mai mult timp
sa mearga de-a lungul urmei, sa gaseasca hrana si sa se intoarca, cu atat feromonul se
va evapora mai repede (iar urma de feromon va fi mai putin proeminenta). Cu cat o dara
este mai scurta, cu atat va fi vizitata de mai multe furnici iar densitatea de feromon va fi
mai mare si va rezista un timp mai indelungat. ACO este implementata ca o echipa de
agenti inteligenti ce simuleaza comportamentul furnicilor, bazandu-se pe mecanismul de
cooperare si adaptare.
3. Artificial Bee Colony Algorithm (ABC)
Algoritm methauristic inspirat din comportamentul albinelor in gasirea celei mai bune surse
de hrana bazat pe modelul propus de D. Karaboga[37] in 2007. In modelul ABC colonia
de albine artificiale contine trei categorii de indivizi: lucratori, privitori si cercetasi. O albina
care cauta in jurul sursei de hrana vizitata de catre aceasta anterior (pozitia sa la iteratia
anterioara) este denumita albina lucratoare, o albina care asteapta ın ”‘zona de dans”’
pentru a lua o decizie de a alege o sursa de hrana este denumita o albina privitoare
(dansul albinelor este presupus ca metoda de comunicatie intre albine), si o albina care
efectueaza o cautare aleatorie este denumita albina cercetas. De fiecare data cand o
albina lucratoare se deplaseaza intr-o pozitie mai buna, aceasta identifica o noua sursa de
hrana si cantitatea de nectar a sursei de hrana corespunde la calitatea (performanta)
solutiei asociate. Ca surse de hrana ın jurul carora are loc cautarea sunt considerate
numai pozitiile albinelor angajate, ın timp ce ca solutii posibile ale problemei de optimizare
sunt considerate toate pozitiile de albine (lucratoare, privitoare, cercetas). Fiecare iteratie
consta din trei faze:
•trimiterea albinelor angajate la sursele de hrana si apoi masurarea cantitatilor de
nectar (Faza Albinelor Lucratoare);
•selectia surselor de hrana de catre albinele privitoare dupa obtinerea informatiilor
detinute de albinele lucratoare si determinarea cantitatii de nectar a surselor de
hrana (Faza Albinelor Privitoare);
•determinarea albinelor cercetas si apoi trimiterea acestora pentru cautarea de
posibile noi surse de hrana (Faza Albinelor Cercetas).
1.2.3 Clasificarea problemelor de planificare a executarii joburilor pe
masini in functie de mediul de productie
1.2.3.1 Flow shop scheduling problem cu capacitate de stocare intermediara
nelimitata
Notatie : Fm||Cmax
Algoritmul lui Johnson din 1954([3]) este metoda clasica ce ofera solutia optima pentru
F2||Cmax timpul de rezolvare fiind polinomial.
Pag. 10/34

Regula lui Johnson :
jobul i precede jobul j intr-o seceventa optima daca min {pi1, pj2} ≤ min {pi2, pj1}.
Algoritmul lui Johnson:
Pas 1: min {pi1, pi2}
Pas 2a: Daca timpul minim de procesare este cel de pe masina 1 se plaseaza jobul in
prima pozitie valabila in secventa si se continua cu pasul 3.
Pas 2b: Daca timpul minim de procesare este cel de pe masina 2, se plaseaza jobul in
ultima pozitie valabila in secventa si se continua cu pasul 3
Pas 3: Se sterge jobul din lista de joburi valabile si s econtinua de la pasul 1 pana cand
seventa este completata.
Algoritmul lui Johnson poate fi aplicat si in cazul m = 3. In acest caz se foloseste algoritmul
pentru doua masini si aplica regula lui Johnson’s rule, pornind la primul pas cu cautarea
min { pi1 + pi2 , pi2 + pi3 }. Regula lui Johnson extinsa
1. Daca mink { pk1 } ≥ maxk { pk2 } atunci jobul i precede jobul j intr-o secventa optima
daca min { pi1 + pi2 , pj2 + pj3 } ≤ min { pi2 + pi3 , pj1 + pj2 }
2. Daca mink { pk3 } ≥ maxk { pk2 } atunci jobul i precede jobul j intr-o secventa optima
daca min { pi1 + pi2 , pj2 + pj3 } ≤ min{ pi2 + pi3 , pj1 + pj2 }
Pentru Fm||Cmax , m ≥ 3 problemele devin NP-hard. Un numar mare de cercetari au mers
pe varianta tehnicilor de agregare in algoritmii constructivi avand drept scop reducerea
Fm||Cmax la F2||Cmax problema care se poate rezolva polinomial cu regula lui Johnson
avand complexitatea O(n log n).(Gupta(2006)[7])
Algoritmul CDS, propus in 1970 de catre Campbell, Dudek si Smith[35] este considerat
ca fiind o forma generalizara a tehnicii de agreare. Ei g rupeaza cele m masini in doua
grupe, aceste grupe fiind considerate drept doua masini virtuale, aplicand apoi algoritmul
lui Johnson. Se construiesc (m-1) secvente posibile de prelucrare, in final alegandu-se
dintre acestea cea mai buna varianta, algoritmul avand complexitatea O(m2n log n)
(Ruiz(2005)[8])
Algoritmul euristic HFC propus de Koulamas[66] in1988, in primafaza foloseste algoritmul
lui Johnson, urmand ca in partea a doua sa imbunatateasca varianta gasita anterior .
1.2.3.2 Permutation flow shop scheduling problem
Notatie : Fm|prmu|Cmax
Daca pentru problema generala a prelucrarii n joburi pe m masini sunt luate in
considerare (n!)m secvente, restrictia de a executa joburile in aceeasi ordine reduce
numarul de secvente posibile la n!.
Completion time se caluleaza in felul urmator:
C1,1 = p1,1
Ci,1 = Ci-1 ,1 + pi,1 i = 2,…, n
C1,j = C1 , j – 1 + p1,j j = 2,…, m
Pag. 11/34

Ci,j = max { Ci-1, j , Ci, j – 1+ pi ,j } i = 2,…, n , j= 2,…, m
Cmax = Cn, m
Framinan(2002)[6] realizeaza o trecere in revista a principalilor algoritmi euristici folositi
pentru Fm|prmu|Cmax care urmeaza etapele unui algoritm euristic: indexarea, construirea
solutiei si imbunatatirea solutiei . Un singur algoritm heuristic poate avea una sau mai
multe etape din cele enumerate mai sus, care in general sunt independente una de alta.
1.2.3.2.1 Indexarea
In prima etapa indexarea, joburile sunt aranjate intr-o anumita ordine (de ex. timpul de
procesare al jobului pe toate masinile). Joburile astfel ordonate vor fi prelucrate in etapa
urmatoare.
Palmer(1965)[39] a propus atribuirea unui index numit "slope index" si notat SI i fiecarui
job i
m
SI i = – S  m –( 2 j – 1)  pij / 2
j = 1
si aranjarea joburilor in ordine descrescatoare in secventa in raport cu acest index

SI 1 ≥ SI 2 ≥ … ≥ SI n
Gupta (1971)[43] a imbunatatit indexul lui Palmer[39] si a introdus conceptul de "sorting
analogy".

SI i = ei / min { pik + pi, k+1 }
1 ≤k ≤m – 1
unde ei = 1 daca pi1 < pim si ei = -1 daca pi1 ≥ pim

Bonney si Gundry (1976) [48] au folosit o varianta a acestei sortari care implica doi indexi
pentru fiecare job.
In general, in etapa de indexare se folosesc analogii cu alte probleme cunoscute sau care
se pot rezolva prin metode polinomiale:
•F2| |Cmax
•Travelling Salesman Problem (TSP)
•Vector Summation Problem
Toti algoritmii prezentati in Tabelul 1 (Framinan(2002)[6]) cu exceptia lui Lai (1996)[32]
rezolva F2| |Cmax folosind regula lui Johnson [3] si folosesc acea solutie ca si solutie a
problemei Fm|prmu|Cmax
Pag. 12/34

Tabelul 1
P i1'P i2'
Campbell
(1970) [35] k
S pij
j = 1
(k = 1, … , m-1) m
S pij
j = m – k + 1
(k = 1,…, m -1)CDS[35] grupeaza cele m masini in doua
grupe considerate doua masini virtuale,
aplicand apoi algoritmul lui Johnson [3]. Se
construiesc (m-1) secvente posibile de
prelucrare, in final alegandu-se dintre
acestea cea mai buna varianta
Dannenbring
(1977) [28] m
S ( m –j + 1) pij
j = 1 m
S j pij
j = 1Rapid Access (RA) combinatie intre
algoritmul lui Jonson si metoda indexarii lui
Palmer[39]. Cele doua masini virtuale sunt
definite precum in algoritmul CDS[35], dar
in loc sa se aplice direct regula lui
Jonson[3], se calculeaza doua scheme
ponderale cu timpii de procesare pentru
fiecare masina si apoi se aplica algoritmul
lui Johnson[3].
Lai
(1996) [32]  m / 2 
S pij
j = 1
unde  x cel mai
mare intreg mai mic
sau egal cu x m
S pij
j = m –  m / 2  + 1Clasifica un job i in unul din cele doua
grupuri: U { i : pi1' ≤ pi2'} sau V { i : pi1' > pi2'}
in maniera regulii lui Johnson [3]. Joburile
din fiecare grup nu sunt sortate ci
distribuite arbitrar, singura conditie este ca
joburile din grupul U trebuie sa preceada
joburile din grupul V.
Röck
si
Schmidt
(1983) [40] m / 2 
S pij
j = 1
unde  x  este cel
mai mic intreg mare
mic sau egal cu x m
S pij
j =  m / 2  + 1
Selim
si
Al-Turki
(1987) [41] m
S l j pij
j = 1 m
S m j pij
j = 1Se incearca optimizarile lui lj si mj
( j = 1,…, m) si se obtin rezultate bune
doar pentru probleme cu numar mic de
date de intrare.
Toti algoritmii prezentati in Tabelul 2 (Framinan(2002)[6]) functioneaza pe baza analogiei
cu Travelling Salesman Problem (TSP) problema cunoscuta ca fiind NP-hard.
Problema comisului voiajor presupune cautarea unui traseu optim, adica fie de lungime, fie
de cost minim daca acesta nu este direct proportional cu distanta parcursa, pentru un
comis voiajor care trebuie sa viziteze n orase o singura data (ciclu hamiltonian) si apoi sa
se intoarca de unde a plecat. Numarul total de solutii posibile este n!
Pag. 13/34

Tabelul 2
Matricea distantelor din TSP pentru n orase este setata cu timpii de
procesare pe m masini 1 ≤ u, v ≤ n
Gupta
(1968)
[42] m
Cuv = ( CTm(u,v) – S puj ) unde
j = 1 j
CT0 ( u,v) = 0 si CTj ( u,v) = max {CT j –1 (u,v) ; S pvk }
k= 1
Stinson
si
Smith
(1982)
[54] m m
Cuv = S | puj – pv, j – 1 | ; Cuv = S { puj – pv, j- 1 }2
j = 2 j = 2

m
Cuv = S |min{puj –pv, j – 1 + min{( pu, j- 1– pv, j – 2 ) ; 0}; 0}|
j = 2
m
Cuv = S |puj –pv, j – 1 + min{( pu, j- 1– pv, j – 2 ) ; 0}|
j = 2
m
Cuv = S {puj –pv, j – 1 + min{( pu, j- 1– pv, j – 2 ) ; 0}}2
j = 2
m
Cuv = S max{( puj –pv, j – 1 ) ;0}+ 2 | min{( pu, j- 1– pv, j – 2) ;0}|
j = 2 Propun 6 moduri
diferite de a popula
matricea distantelor
si deoarece TSP
este din categoria
NP-hard autorii
sugereaza
construirea unui
euristic polinomial
Widmer
si
Hertz –
SPIRIT
(1989)
[52] m
Cuv = pu1 + S ( m – k) | puj –pv, j – 1 | + pvm
j = 2 Imbunatatete
solutia printr-un
algoritm tabu
search.
Primele doua joburi
Ji, Jk din lista se
aleg astfel incat
timpul necesar
fabricatiei celor
doua sa fie minim.
Se introduc in
ordine aleatoare in
secventa partiala
urmatoarele joburi,
in acea pozitie din
lista ce corespunde
unei cresteri
minime a timpului
de fabricatie.
Moccellin
(1995)
[33]Cuv = UBX( m) uv unde
UBX(1) uv = 0 Farthest Insertion
Travelling
Salesman
Procedure (FITSP)
Pag. 14/34

UBX(k +1) uv = max{0 ; UBX(k) uv + ( pv, k– pu,k+ 1 ) }foloseste SPIRIT
[52], si calcularea
solutiei initiale si a
distantelor dintre
joburi se face diferit
Analogia cu Vector Summation Problem se face folosind un algoritm polinomial bazat pe
programarea liniara. Idea teoretica a fost prezentata de Sevast’janov (1995)[20] si
implementata de Lourenço (1996) [21] si Lawler (1993)[22].
1.2.3.2.2 Construirea solutiei
In etapa a doua solutia se construieste recursiv prin inserarea joburilor neplanificate in una
sau mai multe pozitii intr-o planificare partiala, pana la realizarea planficarii definitive.
Pentru fiecare pas recursiv etapele sunt :
•selectia job-ului din multimea joburilor neplanificate
•inserarea jobului in planificarea partiala.
Tabelul 3 (Framinan(2002)[6]) sistematizeaza algoritmii constructivi prin alegerile facute
pentru selectia si inserarea jobului. Notatiile folosite sunt Rk pentru subsetul ce contine
joburile neordonate si Sk pentru subsetul ce contine joburile deja ordonate.
Tabelul 3
Selectia jobului corepunzator pasului k
se poate face in doua moduri :
– conform etapei I (indexarea)
– se caluleaza pe rand pentru mai multe
joburi din Rk diferite masuratori ale
frecventei partiale a joburilor obtinuta
pentru fiecare job Insertia jobului la pasul k
poate fi fixa sau se iau in
considerare mai multe pozitii
posibile de inserare si se
calculeaza pe rand diferite
masuratori ale frecventei
partiale a joburilor obtinuta
pentru fiecaremakespan se poate
descompune in timpul
necesar procesarii
tuturor joburilor pe
toate masinile si idle
time al fiecarei masini
pentru fiecare job
Gupta –
MINIT
(1972) [44]un job obtinut din indexare pentru k = 1
toate joburile in Rk pentru
1 < k ≤(n – 2) ( idle time )
toate joburile in Rk pentru
(n –2) < k ≤ n ( makespan )la pozitia k + 1MINIT –
minimum idle time
Gupta –
MICOT
(1972) [44]un job obtinut din indexare pentru k = 1
toate joburile in Rk pentru
1 < k ≤(n – 2) ( completion time )
toate joburile in Rk pentru
(n –2) < k ≤ n ( makespan )la pozitia k + 1MICOT –
minimum completion
time
Gupta –
MINIMAX
(1972) [44]toate joburile in Rk
daca k impar min{pi,j}
daca k par max{pi,j}
unde i in Rk si 1 ≤ j ≤mdaca k impar la pozitia k + 1
daca k par la pozitia 0MINIMAX este bazat
pe regula lui
Johnson[3]
Gupta
si Maykutun job obtinut din indexare pentru k = 1 la pozitia k + 1
Pag. 15/34

(1972) [45]toate joburile in Rk pentru
1 < k ≤( n – 2)
( idle time pe ultima masina)
Gupta
(1979) [46]toate joburile in Rk
(lower bound pentru makespan total)la pozitia k + 1
McCormick
(1989) [47]un job obtinut din indexare pentru k = 1
toate joburile in Rk pentru
1 < k ≤n – 2 ( idle time )la pozitia k + 1
Nawaz
(1983) [11]un job obtinut din indexare toate cele ( k+1) pozitii
posibile sunt incercate
(makespan)
Rajendran
(1993) [49]un job obtinut din indexare limiteaza pozitiile care sunt
incercate de la  k / 2  la
( k+1) (makespan)
Sarin si
Lefoka
(1993) [53]toate joburile in Rk
(idle time pe ultima masina)la pozitia k + 1insereaza jobului ales
la sfarsitul lui Sk
Woo si Yim
(1998) [51]toate joburile in Rk
(makespan)toate cele ( k+1) pozitii
posibile sunt incercate
(makespan)Minimizarea partiala a
makespan la selectia si
inserare
Nawaz(1983)[11] porneste de la urmatoarea regula de selectie a unui job:
jobul cu timpul de procesare cel mai mare pe toate masinile trebuie sa primeasca prioritate
mai mare si elaboreaza algoritmul NEH in care se incearca inserarea jobului in toate
pozitiile posibile :
Pasul 1. Pentru fiecare job i se calculeaza Ti = S ( pij ) i = 1, n si j = 1, m
Pasul 2. Se aranjeaza joburile din Ti in ordinea descrescatoare intr-o lista.
Pasul 3. Se aleg joburile din prima si a doua pozitie din lista de la Pasul 2. si se determina
cea mai buna secventa pentru aceste doua joburi calculand makespan pentru cele doua
posibile secvente . In cea mai buna seceventa partiala obtinuta , in pasii urmatori din
algoritm se considera fixe pozitiile celor doua joburi unul in raport cu celalalt.
Pasul 4. Se alege jobul din pozitia a treia din lista de la Pasul 2. si se vor obtine trei
secvente partiale prin plasarea jobului la inceput, in mijloc si la sfarsit ul secventei partiale
de la Pasul 3. Cea mai buna secventa partiala va considera fixe pozitiile primelor trei
joburi in pasii ce urmeaza.
Pasul 5. Se alege jobul din pozitia i din lista generata in Pasul 2. si se determina cea mai
buna secventa plasand jobul in toate pozitile posibile fara a schimba pozitiile joburilor deja
asignate in pasii anteriori .
Pasul 6 Daca n = i algoritmul se opreste, altfel i = i + 1 si se continua cu Pasul 5.
Numarul de secvente partiale la fiecare iteratie i este egal cu i, i = 2,..,n si dupa n pasi se
obtin in total 2 + 3 + …+ n = n (n+1) / 2 – 1 .
Algoritmul are complexitatea O(n3m).
Taillard(1990)[4] apreciaza NEH ca fiind unul din cei mai performanti algoritmi euristici.
Pag. 16/34

Taillard(1990)[4] a redus complexitatea la O(n2m) divizand secventa partiala in parte
neschimbata si parte schimbata si calculand makespan numai pentru partea schimbata.
Calcularea makespan dupa inserarea jobului k in pozitia i
1) Calculul celui mai bun Cij completion time pentru jobul i pe masina j considerand 0
valoarea timpul de inceput al primui job pe prima masina :
C0j = 0 , Ci0 = 0 , Cij = max {Cj,j –1 ; Cj –1,i} + pij unde i = 1,…,k– 1 , j= 1,…,m
2) Calculul restului duratei dintre timpul de incepere al jobului i pe masina j de pana la
sfarsitul operatiei
qkj = 0 , qi, m+1 = 0 , qij = max {qj,j+1 ; qj+1 ,i} + pij unde i = k– 1,…,n , j= 1,…,m
3) Calculul celui mai bun relativ completion time notat fij pentru jobul k inserat pe
masina j pe pozitia i
fi0 = 0 , fij = max {fi,j –1 ; Ci –1,j} + pkj unde i = 1,…,k, j= 1,…,m
4) Calculul makespan partial notat Mi pentru jobul k inserat pe masina j pe pozitia i
Mi = max j {fij + qij } unde i = 1,…,k, j= 1,…,m
Comparand NEH cu algorimii constructivi cunoscuti, pentru un numar diferit de joburi de la
9 la 50, Taillard[4] arata in Tabelul 4 ca NEH este cel mai performant algoritm:
Tabelul 4
Complexitatea (la calcularea makespan) Calitatea solutiei
Nr. Probleme – 5001001001005050
Nr. de joburi n 91020204050
Nr. de masini m 101010201010
Complexitate
Gupta [42] O(n log(n)+nm )13.412.819.618.818.917.1
Johnson [3] O(n log(n)+nm )10.911.816.716.817.316.3
RA (1977) [28]O(n log(n)+nm )8.59.112.513.413.511.2
Palmer(1965) [39]O(n log(n)+nm )8.3913.312.510.910.7
CDS [35] O(m2n log(n))4.55.29.78.69.99.3
NEHT [14] sau NEH cu
imbunatatirea lui Taillard O(n2m)2.12.23.93.82.62.1
Pag. 17/34

Formula de masurare a performantei este data de relative percentage deviation (RPD)
sau abaterea fata de upper bound in %
Heusol – Optsol
RPD = ––––– . 100
Optsol
Heusol sau LB (lower bound) este valoarea lui Cmax obtinuta de algoritm.
Optsol sau UB (upper bound) este cea mai mica valoare a lui Cmax cunoscuta in literatura.
Solutia optima este furnizata in benchmark-uri clasice de catre Taillard[4].
Fie bi timpul minim de asteptare inainte ca masina i sa porneasca :
i – 1
bi = min j ( S dkj )
j = 1 … n k = 1
Fie ai timpul minim de inactivitate al masinii i dupa ce termina operatiile :
m
ai = min j ( S dkj )
j = 1 … n k = i + 1,
Fie Ti timpul total de procesare pe masina i :
n
Ti = S dij
j = 1
Taillard[14] stabileste urmatoarea relatie intre solutia optima sau lower bound (LB) si
solutia algoritmului
LB = maxi ( bi + Ti + ai ) ≤ Cmax
i = 1 … m
Taillard[14] ofera pentru fiecare set de teste timpul de prelucrare al fiecarui job pe fiecare
masina, upper bound sau solutia optimala si lower bound sau cea mai mai apropiata de
solutia optimala obtinuta.
Pornind de la algoritmul NEH un numar mare de cercetatori au propus diferite variante:
•Xiao-ping(2004)[23] a imbunatatit pasul de sortare;
•Dong (2008)[24] a ordonat joburile dupa suma dintre timpul mediu de procesare si
deviatia standard a timpilor de procesare;
•Singhal(2012)[25] : pentru insertia jobului urmator cele mai bune secvente partiale
sunt determinate de primele patru joburi din lista sortata pornind de la parametrul k;
•Baskar si Xavior (2013)[26] pentru secventa initiala partiala iau in considerare
primul si ultimul job, doua joburi din mijloc si ultimele doua joburi spre deosebire de
NEH unde secventa initiala partiala se face ordonand descrescator joburile dupa
Pag. 18/34

timpul de procesare;
•Baskar(2016)[12] pornind de la NEH propune sapte variante noi de insertie initiala,
complexitatea algoritmului ramanand aceeasi. El subliniaza importanta insertiei ca
fiind ce mai puternica componenta a lui NEH, urmata de aranjarea initiala a joburilor
pe baza ordonarii descrescatoare a timpul de procesare.
1.2.3.2.3 Imbuntatirea solutiei
In etapa a treia algoritmii incep de la o secventa de prelucrare deja construita si prin
diferite procedee se incearca imbunatatirea rezultatului.
Toti algoritmii prezentati in Tabelul 5 sunt algoritmi de tipul improvement heuristic folosind
descending local searches (Framinan(2002)[6] si Ruiz (2005)[8])
Tabelul 5
Aggarwal si
Stafford
(1975) [29]AS Tip de vecinatate :
general-neighbourhood
Dannenbring
(1977) [28]Rapid Access with Close Order Search
(RACS)
Porneste de la o solutie generata de RA
euristic constructiv [28] si schimba intre ele
doua joburi adiacente unei secvente, in n-1
pasi. Rezultatul se obtine din cea mai buna
secventa generata in cei n-1 pasi Tip de vecinatate :
general-neighbourhood

Rapid Access with Extensive
Search (RAES) Se aplica RACS in
mod repetat
King si
Spachis
(1980) [34]Propun cinci euristici a caror solutie este
imbunatatita in faza a doua prin
interschimbarea ultimelor doua joburi
inserate in functie de makespan Tip de vecinatate :
general-neighbourhood
Se face distinctia intre secvente de
tipul ‘single chain’ si ‘multiple chain’ in
functie de numarul de pozitii in care
se incearca inserarea
Ho si Chang
(1991) [30]Algoritm care porneste de la o secventa
generata de CDS[35] si calculeaza "gap"- ul
pentru toate perechile posibile de joburi si
masini si alege joburile pe baza valorii "gap"
asociate fiecaruia.Tip de vecinatate :
specific-neighbourhood
"gap"- ul (timpul scurs dintre sfasitul
procesarii unui job pe masina curenta
pana la inceperea procesarii jobului
pe urmatoarea masina)
Suliman
(2000) [31]Algoritm care porneste de la o secventa
generata de CDS[35] si foloseste un
mecanism exhaustiv de schimb de perechi,
legat de directionalitateTip de vecinatate :
specific-neighbourhood
Daca printr-o mutare inaintea a unui
job se obtine o secventa mai buna se
mentine aceasta directie de
schimbare a joburilor
Ruiz (2005)[8] pornind de la instantele lui Taillard[14] pentru 120 de probleme de diferite
marimi compara algoritmi euristici constructivi si euristici cu imbunatatirea solutiei.
Formula de masurare a performantei este a baterea fata de upper bound in % (Tabelul 6).
Pag. 19/34

Tabelul 6
n x mJohnson
[3]Palmer
[39]CDS
[35]Gupta
[42]RA
[28]RACS
[28]RAES
[28]NEH
[11]Ho si
Chang [30] Suliman
[31]
20×512.7810.589.5412.458.867.714.953.356.944.46
20×1019.9715.2812.1324.4815.410.668.625.0210.517.84
20×2016.4716.349.6422.5316.358.166.413.738.36.69
50×510.435.346.112.436.35.43.280.843.332.2
50×1021.914.0112.9822.0515.0512.1910.415.1211.298.46
50×2022.8115.9913.8523.6618.8812.86106.212.49.62
100×56.842.385.016.023.544.583.250.462.71.28
100×1015.019.29.1515.1210.488.727.312.137.965.75
100×2021.1514.4113.1222.6816.9612.4810.565.1111.19.28
200×1011.475.137.3811.86.177.116.161.435.114.09
200×2018.9313.1712.0819.6712.6711.8310.394.379.998.85
500×2014.077.098.5513.668.348.387.772.247.146.06
Media15.9910.749.9617.2111.589.177.433.338.066.21
1.2.3.2.4 Algoritmi metaeuristici de cautare
Algoritmi metaheuristici sunt proceduri euristice generale care se aplica mai multor tipuri
de probleme. Aceste proceduri euristice pornesc se la o secventa construita de un alt
algoritm euristic si itereaza pana cand se indeplineste criteriul de oprire.
•Simulated Annealing (SA)
Algoritm general (Reza(2005)[2]) :
1.Selectarea unei solutii intiale S0
2.Initializarea parametrilor mecanismului de recristalizare:
b0 , bend , p0 , N0
a parametrul care determina cum va scadea temperatura.
Repeat
Repeat
Selectarea aleatoare a unei solutii S din vecinatatea lui S0
Calculeaza d = Cmax (S) – Cmax (S0 )
If d < 0 then
S0 = S
else
Genereaza aleator x o distributie uniforma din [0,1)
If x < exp (- d / k b n) probabilitate de acceptare then
S0 = S
End if
End if
Pag. 20/34

Until numarul de incercari ale lui b ajunge la N0
Seteaza b = a * b
Until b < bend
Reza(2005)[2] si Ruiz (2005)[8] prezinta o trecere in revista a cercetarilor legate de
tehnica Simulated Annealing (SA)
Osman si Potts (1989)[38] propun algoritmul de tipul Simulated Annealing in care vecinii
se obtin prin interschimbarea joburilor, cautare in spatiul solutiilor fiind aleatoare. Tipul de
vecinatate este general-neighbourhood si pentru o solutie se exploreaza n (n − 1) / 2
vecini.
Ogbu si Smith (1990[55], 1991[56]) propun algoritmul de tipul SA in care initializarea se
face folosind euristica lui Palmer[39] si Dannenbring[28] . Se alege un spatiu de cautare
mare pentru vecini prin i nserarea si schimbarea perechilor de joburi .
Functia pentru probabilitatea de acceptare este independenta de valoarea makespanului
secventei rezultate. Performantele sunt asemanatoare algoritmului lui Osman si Potts[38].
Ishibuchi (1995) [68] prezinta doi algoritmi de tipul Simulated Annealing cu performanta
robusta in raport cu racirea temperaturii iar performante sunt asemanatoare algoritmului lui
Osman si Potts[38].
Zegordi (1995)[57] foloseste in algoritmul SAMD o tehnica hibrida prin introducerea
tabelului MDJ (Move Desirability for Jobs) incorporand reguli care faciliteaza procesul
de recristalizare, reducand astfel numarul parametrilor de control. Perechea de joburi
interschimbabile este controlata de valoarea indexului MDJ care se construieste la fiecare
iteratie si masoara imbunatatirea makespan dupa interschimbarea pozitiei joburilor in
solutia curenta. Tipul de vecinatate este s pecific – neighbourhood si MDJ controleaza
subsetul de vecini explorati din multimea n (n − 1) / 2. Algoritmul este usor inferior dar mai
rapid decat cel al lui Osman si Potts[38]
•Tabu Search(TS)
In tehnica Tabu Search porneste de la solutia curenta fezabila x din multimea solutiilor
fezabile X careia i se aplica o functie m(x) care transforma x in x', o noua solutie fezabila
x'= m(x). Aceasta transformare poarta numele de mutare si multimea
{ x' : x' = m(x) ; x , x'  X , m  M(x) }
se numeste vecinatatea lui x unde M(x) este multimea mutarilor aplicabile unei solutii
fezabile x sau vecinatate.
In ideea evitarii repetarii unui element t asociat cu m si x, se defineste un set de mutari
care sunt tabu (interzise) si se salveaza intr-o multime T numita lista tabu. In particular t
interzice aplicarea acelor functii m' pentru x' care ar transforma inpoi pe x' in x. Numarul
de miscari care nu se pot aplica solutiei curente din lista T este limitat de un parametru s
numit marimea listei tabu .
Daca ITI = s inainte de a adauga elementul t in T atunci trebuie sters un element, de
obicei cel mai vechi.
Widmer si Hertz (1989) [52] in algoritmul heuristic SPIRIT, in prima faza se genereaza
solutia in analogie cu OSTP si apoi in a doua faza solutia este imbunatatita folosind Tabu
Search cu parametrii standard si schimbarea vecinilor .
Pag. 21/34

Taillard (1990)[4] prezinta un algoritm similar lui Widmer si Hertz[52] in care tehnica
Tabu Search este aplicata unei solutii generate de NEH.
Algoritm general (Taillard (1990)[4]):
1.Porneste de la o solutie fezabila x0 si T fara nici un element
Fie x* = x0, c* = C( x0) si k = 0 (x* cea mai buna solutie gasita pana acum si c*
valoarea functiei obiectiv pentru aceasta solutie .)
2.Alege mutarea m  M(xk) care transforma xk astfel incat sa minimizeze c(m(xk) ) si
care nu este in lista tabu T. Fie xk+1 = m(xk)
3.Daca este gasit cel mai bun vecin se accepta solutia noua ca si solutie curenta, se
efectueaza o miscare non-tabu, altfel se continua cautarea celui mai bun vecin non-
tabu. C
Daca C( xk+1) < c*, fie c*= c(xk+1) si x*= xk+1.
4.Daca nr. maxim de iteratii este atins (conditie de oprire) se executa pasul 5, altfel :
daca ITI = s sterge cel mai vechi element din T si adauga elementul t in T
definit de m si xk+1,
1. k= k + 1 si se executa pasul 2.
5.Cea mai buna solutie globala este cea mai buna solutie solutia curenta
Ruiz (2005)[8] prezinta o trecere in revista a cercetarilor legate de tehnica Tabu Search
Moccellin (1995) [33] propune un algoritm bazat pe SPIRIT[52], singura diferenta fiind in
pasul initial unde se calculeaza solutia initiala a problemei. Se pastreaza analogia cu
OSTP dar distanta dintre joburi se calculeaza folosind the farthest Insertion Travelling
Salesman Procedure (FITSP) .
Nowicki si Smutnicki (1996) [58] propun un metaeuristic de tipul Tabu Search care
evalueaza o parte redusa a vecinilor si foloseste o metoda rapida de calculare a
makespan. Reducerea vecinilor se face pe baza conceptului de block properties unde
mutarile se fac la nivelul clusterului de joburi nu al jobului.
Ben-Daya si Al-Fawzan (1998) [69] au implementat un algoritm TS bazat pe intensificarea
si diversificarea schemelor care furnizeaza solutii mai bune in procesul tabu s earch.
Algoritmul proous are rezultate similare cu TS al lui Taillard (1990).
Solimanpur(2003) [70] propune un algoritm neuro-tabu search care implementeaza block
properties.
Grabowski si Wodecki (2004) [71] propun un algoritm tabu search rapid, in care ordinea
de procesare notata cu p se calculeaza folosind urmatoarea formula:
t1 t2 n
Cmax( p) = max ( S pp ( j) 1 + S pp ( j) 2 + … + S pp ( j) m )
1 ≤ t1 ≤t2 … ≤t m – 1 ≤ n j = 1 j = t 1 j = t m – 1
unde (j) este al j – lea element din permutarea p
Pag. 22/34

Makespan-ul asociat lui p se considera a fi drumul de la nodul (1, 1) la nodul ( m, n) in
graph-ul de tip grid. In acest graph fiecare drum este compus din sub-drumuri verticale si
orizontale. Un sub-drum orizontal se mai numeste block.
Pentru drumul u ( u1, u2 , . . . , um-1 ) se considera
u1 u2 n
Cmax( p) = C( p , u) = ( S pp ( j) 1 + S pp ( j) 2 + … + S pp ( j) m )
j = 1 j = u1 j = um- 1
atunci Bk = p ( uk- 1 ) , p ( uk- 1 + 1) , … , p ( uk )
block-ul k in seceventa p este drumul critic in raport cu secventa p a joburilor
•Algoritmii genetici
Genetic Algorithms (GAs) au fost descrisi de Holland (1975)[59] pe baza procesului de
evolutie biologica avand dublu scop: sa imbunatateasca intelegerea proceselor naturale
de adaptare si sa proiecteze sisteme artificiale similare celor naturale .
Algoritmii genetici aplicati in flowshop scheduling problem, trateaza secventele de joburi
ca pe indivizi sau membrii ai unei populatii. Fiecare individ este caracterizat de o functie
fitness asociata cu valoarea unei functii obiectiv. Procedura se executa iterativ, fiecare
iterare numindu-se generatie. Populatia unei generatii consta din indivizii care au
supravietuit din generatia anterioara si noile pemutari sau urmasii generatiei precedente
obtinuti prin reproducere sau mutatie. Dimensiunea populatiei ramane constanta. Indivizii
mai sunt numiti si cromozomi . Mutatia intr-un cromozom parinte poate consta in
schimbarea perechilor de joburi in secventa de joburi corespunzatoare. Din perspectiva
procesului de cautarie GA difera de SA si TS deoarece la fiecare iteratie este generat si
transmis la urmatorul pas un numar diferit de permutari de joburi. In simulated annealing si
tabu-search o singura permutare este trimisa de la o iteratie la alta, SA si TS putand fi
tratate ca si cazuri particulare ale GA pentru dimensiunea populatiei egala cu 1.
O caracteristica importanta a GA este diversitatea schemei. O noua permutare de joburi
se poate genera din combinarea diferitelor permutari de joburi care apartin generatiei
curente. Acest mecanism se numeste crossover operator (operator de incrucisare)
Algoritm general ( Pinedo(2008)[1]):
Pas 1.
Set k = 1.
Selecteaza l secvente initale S1,1 . . . , S1,l aleator sau prin alte euristici
Pas 2.
Selecteaza cele mai bune doua secvente Sk+ si Sk+ + dintre Sk,1 . . . , Sk,l
Selecteaza cele mai proaste doua secvente Sk- si Sk- – dintre Sk,1 . . . , Sk,l
Genereaza doi urmasi S ∗si S ∗ ∗ din parintii Sk+ si Sk+ +
Pag. 23/34

Inlocuieste Sk- si Sk- – cu S ∗si S ∗ ∗
Pastreaza restul permutarilor neschimbate si continua cu Pas 3.
Pas 3.
k = k + 1
Daca k = N atunci STOP, altfel continua cu Pas 2.
Ruiz (2005)[8] realizeaza o trecere in revista a studiilor care folosesc algoritmii genetici in
rezolvarea flow shop problem.
Chen (1995)[60] a dezvoltat un GA in care populatia initiala este generata folosind
algoritmii euristici CDS[35] si RA. Se foloseste doar operatorul crossover fara mutatie
numit Partially Mapped Crossover ( PMX) . PMX alege prima data doua puncte de
incrucisare, schimba subsecventele parintilor intre cele doua puncte, umple cromozomii
prin mapare partiala in extreme acestora.
Reeves (1995)[61] a propus un GA in care populatia initiala este generata cu NEH.
Urmasul generat in fiecare pas nu inlocuieste parintii ci alti indivizi din generatie care au
valoarea functiei fitness sub medie. Reeves a folosit operatorul crossover numit C1 care
este echivalent cu One Point Order Crossover. Algoritmul utilizeaza mutatia prin care
schimba pozitia unui job. Primul parinte este selectat folosind o distributie a functiei fitness
si al doilea parinte este ales folosind o distributie uniforma .
Murata, Ishibuchi si Tanaka(1996)[62] propun un GA folosind operatorul two-point
crossover si mutatia in raport cu strategia elitista, pe care, l-au imbunatatit ulterior
implementand doua versiuni hibride: genetic simulated annealing si genetic local search.
In aceste versiuni faza de imbunatatire are loc inainte de selectie si de incrucisare folosind
simulated annealing si local searh si obtine rezultate mai bune decat in versiunea
originala. In cazul operatorului two-point crossover, cromozomul parinte este taiat aleator
in doua locuri. Joburile aflate la extreme celor doua taieturi sunt mostenite de urmasi in
aceeasi locatie si acceasi ordine in care ele apar in cromozom. Partea centrala a
urmasului este completata cu joburile importante in ordinea in care acestea apar la
parinte.
Reeves si Yamada (1998)[63] dezvolta un GA folosind operatorul Multi-Step Crossover
Fusion sau MSXF care aduce la un loc un crossover operator si local search. Operatorul
MSXF, definit folosind structura vecinatatii si masura distantei, efectueaza o cautare locala
la un parinte folosind celalalt parinte ca si referinta.
Ponnambalam(2001) [64] evalueaza un GA care pornind de la o solutie initiala generata
aleator foloseste operatorul GPX crossover (Generalised Position Crossover) si
mutatia realizata prin schimbarea joburilor.
Wang si Zheng (2003)[65] au prezentat un GA complex si hybrid in care initializarea
populatiei initiale se face cu NEH si operatorul de mutatie este inlocuit de SA. Algoritmul
foloseste operatori de tipul multicrossover aplicati la sub-populatii ale populatiei originale.
Ruiz (2005)[8] pornind de la instantele lui Taillard[14] pentru 120 de probleme de diferite
marimi compara algoritmi metaeuristici. F ormula de masurare a performantei este
abaterea fata de upper bound in % (Tabelul 7).

Pag. 24/34

Tabelul 7
n x mOsman si Potts[38]Spirit[52]Chen[60]Reeves[63]Murata[62]
20×51.472.143.670.713.28
20×102.573.095.031.975.53
20×202.222.994.021.484.33
50×50.520.572.310.231.96
50×103.654.086.652.476.25
50×204.974.787.923.897.53
100×50.420.321.180.181.33
100×101.731.693.911.063.66
100×204.94.497.823.849.7
200×101.330.952.70.856.47
200×204.43.857.013.4714.56
500×203.482.175.621.9812.47
Media2.642.64.821.846.42
1.2.3.3 Flow shop scheduling problem cu diferite constrangeri
1.2.3.3.1 Flow shop scheduling problem cu capacitate de stocare limitata
Notatie : Fm|block|Cmax
In functie de capacitatea de stocare in procesul de productie problemele de tip flowshop
se clasifica in
• Unlimited intermediate storage (UIS): capacitate de stocare nelimitata
• No intermediate storage (NIS): fara capacitate de stocare intre etapele productiei, caz
in care joburile trebuie procesate imediat . Aceste probleme se mai numesc zero-wait sau
no-wait
• Limited intermediate storage (LIS): capacitate de stocare maxima.
Pentru fiecare stagiu s > 1 se considera capacitate de stocare maxima sk ≥. 0
Leisten(1990)[72] porneste de la premisa ca unitatea de stocare masoara un numar de
joburi si propune urmatorul algoritm: la inceput se genereaza secventa de joburi pe prima
masina si se transfera in unitatea de stocare pana cand este atins numarul de joburi.
Urmatorul job nu poate fi transferat in unitatea de stocare si ramane pe prima masina,
masina devenind blocata. Din unitatea de stocare se extrage un job si se distribuie pe a
doua masina, deci jobul blocat de pe prima masina poate sa paraseasca prima masina
deorece este un loc liber in unitatea de stocare. Urmatorul job poate fi prelucrat pe prima
masina dar aceasta devine blocata deoarece unitatea de stocare este plina.
Procedura continua in mod analog, acest tip de euristici incercand intotdeuna sa utilizeze
integral unitatea de stocare.
Abadi si Sriskandarajah(1995) [73] descriu blocking flowshop in care fluxul de productie
nu foloseste bufferi intermediari pentru joburi. Jobul nu poate parasi masina curenta pana
cand urmatoarea masina din linia de productie nu este libera. In acest caz se considera
atat jobul cat si masina ca fiind blocate. Dupa ce s-a terminat executia jobului i pe masina
r, acesta nu poate avansa pe masina r + 1, daca aceasta masina inca proceseaza
Pag. 25/34

predecesorul jobului i din secventa de joburi. Jobul i trebuie sa ramana pe masina r, care
este temporar blocata pentru a executa succesorul jobului i din secventa de joburi, pana
cand jobul i nu poate avansa pe masina r + 1.
Witt(2005)[9] descriu trei algoritmi euristici pentru scheme de masini legate in serie
(MODSGS) in paralel (MODPGS) si bazate pe deblocarea recursiva (UNBLOCK).
Spre deosebire de alti algoritmi de blocking flowshop unitatea de stocare masoara
cantitati si nu un numar de joburi. Algoritmii pornesc de la premisa ca unitatea de stocare
maxima este q j = 1 pentru fiecare job j.
Pinedo(2008)[1] arata ca o problema flow shop cu unitate de stocare intermediara limitat
definita printr-un numar maximal de joburi se poate transpune in flow shop problem cu
capacitate de stocare zero deoarece fiecare unitate de stocare se poate considera o
masina in care timpul de procesare este 0 pentru toate tipurile de joburi. Asemanator,
daca unitatea de stocare se gaseste la inceputul fiecarui stagiu de productie, se poate
inlocui cu un numar de masini egal cu numarul de joburi din unitatea de stocare masurata.
1.2.3.3.2 No-wait f low shop scheduling problem
Notatie : Fm|nwt |Cmax
No-wait flow shop scheduling problem este o varianta a problemei flowshop unde
joburile nu pot forma cozi de asteptare.
Hejazi(2005)[2] realizeaza un review al principalelor abordari ale n o-wait flowshop
scheduling problem .
Wismer (1972)[74] a stabilit legatura intre no-wait flowshop scheduling problem si
Asymmetric Traveling Salesman Problem. Stafford si Tseng (1990)[75] si Wismer
(1972)[74] au denumit inital aceasta problema cu NIQ (no intermediate queues
flowshop problem).
Alte contributii inspirate din algoritmul NEH au fost aduse de catre Piehler (1960), Reddi
si Ramamoorthy (1972) [76] , Bonney si Gundry (1976) [78], King si Spachis (1980) [34].
Rock(1984)[82] analizeaza complexitatea NP pentru F3|nwt |Cmax si care este NP-hard in
timp ce problema F2|nwt |Cmax ea poate fi rezolvata polinomial avand O(n log n)
Aldowaisan si Allahverdi (1998) [80] descriu problema no-wait flowshop. O data ce se
incepe procesarea jobului pe masina 1 din linia de productie , procesarea acestuia trebuie
sa continue pe linia de productie fara nici o intarziere pana pe ultima din linia de productie.
Bertolissi(2000)[77], Aldowaisan si Allahverdi (2004) [79] prezinta no-wait flowshop cu
diferite criterii.
Stafford si Tseng (2001) [82] propun cazul in care joburile nu pot fi lansate inainte ca
masina 1 sa porneasca si sa fie procesate secvential de toate masinile, fara intarzieri pe
nici o masina.
Aldowaisan si Allahverdi (2003) [81] propun doua metode euristice de tipul Simulated
Annealing si Genetic Algorithm .
1.2.3.3.3. Sequence-dependent set-up times f low shop scheduling problem (SDST)
In fluxul SDST , set-up time, timpul de pregatire a jobului se considera independent de
timpul de executie al jobului dintr-o secventa. Sequence dependent setup times (sjk)
reprezinta secventa de timp definita in afara timpului de procesare a joburilor j si k, unde
s0k este timpul asociat inainte de inceperea primul job k din secventa
Pag. 26/34

sj0 este timpul asociat dupa terminarea ultimul job j din secventa.
Hejazi(2005)[2] realizeaza o trecere in revista a principalelor abordari ale SDST.
O parte din cercetatorii care au analizat SDST extinzand regula lui Johnson [3] sunt: Yoshida
si Hitomi(1979)[83], Sule si Huang(1983)[84], Allahverdi(1995) [86], Proust(1991)[87],
Park si Steudel(1991)[88], Gupta si Tunc(1994)[89], Cao si Bedworth(1992)[90],
Allahverdi (1997)[91], Rajendran si Ziegler(1997)[92].
Khurana si Bagga(1985)[85] au propus o solutie optimala pentru SDST cu m = 2
urmatoarele conditii: timpii de start si stop pentru fiecare job sunt egali si daca timpul de
procesare al unui job pe prima masina este mai mare(mai mic) decat timpul de procesare
pe masina a doua atunci suma timpului de procesare si setup al jobului pe prima masina
este mai mare(mai mic) decat suma timpului de procesare si timpul de setup a jobului pe
masina a doua.
Ruiz (2004)[93] propune doi algoritmi genetici avansati precum si cateva adaptari ale
algoritmilor metaeuristici existenti.
1.2.3.4. Flow shop scheduling problem cu mai multe functii obiectiv
Hejazi(2005)[2] si Minella(2007)[10] realizeaza o trecere in revista a principalelor abordari
in cazul problemelor flow shop cu obiective multiple.
1. Cand criteriile sunt in mod egal importante se obtin solutiile eficiente din care se alege
solutia algoritmului folosind metode de decizie specifice fiecarui criteriu.
2. Ierarhia pe nivele a prioritatilor asociate criteriilor. Problema se rezolva intai pentru
primul criteriu prioritar ignorand alte criterii si apoi se rezolva pentru criteriul urmator ca si
importanta avand constrangerea ca solutia optimala de la primul criteriu sa nu se schimbe
(Gupta(2001)[94] pentru F2| |Cmax ,Tmax )
3. Metoda “a priori”
In metoda “a priori” doua sau mai multe obiective sunt prioritizate si combinate liniar intr-
o singura functie obiectiv. Intr-o problema cu doua obiective unde F1 si F2 sunt functiile
asociate obiectivelor, functia obiectiv este
αF1 + (1 − ) αF2 , 0 ≤ α ≤ 1 , α trebuie cunoscut de la inceput.
Cele mai multe studii folosesc metoda “a priori”.
Rajendran (1992)[67] si in 1994[95], Hoogeveen (1992) [97] au propus abordarea
branch-and-bound( B&B) pentru doua masini cu minimizarea makespan si total flow time
(Cmax si Tmax).
Nagar, Heragu si Haddock(1995)[98] propun procedura B&B pentru doua masini cu
minimizarea makespan si total flow time . Procedura initializeaza arborele branch and
bound cu o solutie initiala fezabila si un upper bound, obtinute dintr-un algoritm euristic de
tip greedy. Aceiasi autori in anul urmator folosesc B&B pentru a furniza populatia initiala
intr-un algoritm genetic. Noul algoritm hibrid B&B+GA depaseste in rezultate B&B dar si
GA .
Sridhar si Rajendran (1996)[50] propun un GA pentru obiectivele makespan, flow time,
si idle time.
Cavalieri si Gaiardelli (1998)[99] propun doi algoritmi genetici in care parametrii sunt
Pag. 27/34

adaptivi pentru obiectivele makespan si tardiness.
Sivrikaya-serifoğlu si Ulusoy (1998)[100] prezinta trei algoritmi B&B si doua euristici
pentru trei masini cu obiectivele makespan si flowtime.
Chakravarthy si Rajendran(1999) [101] propun un algoritm de tip SA si o combinatie
liniara intre makespan si tardiness
T’kindt si Billaut (2001)[102] au trecut in revista 15 flow shop problems cu mai multe
obiective cele mai multe adresandu-se cazului in care exista 2 masini.
4. Metoda “a posteriori”
In metoda “a posteriori” se renunta la conceptul de “optimum” pentru o solutie, toate
solutiile apartinand solutiilor optimale multi-obiectiv Pareto, considerate a fi la fel de bune
si cele mai bune solutii pentru problema.
Daniels si Chambers(1990) [27] propun o procedura B&B pentru Cmax si Tmax care
calculeaza solutiile optimale multi-obiectiv Pareto pentru doua masini.
Murata, Ishibuchi si Tanaka(1996)[62] propune MOGA un GA (pentru makespan si total
tardiness si apoi makespan, total flow time si total tardiness) pentru a cauta in solutiile
optimale multi-obiectiv Pareto. In cadrul GA se copiaza un numar de indivizi in multimea
non-dominanta pastrata extern intr-o arhiva. In cadrul selectiei valoarea functiei fitness
atasata fiecarei solutii este obtinuta pe baza sumei ponderate a valorii obiectivelor. La
fiecare iteratie se atribuie aleator ponderea fiecarui obiectiv. Ishibuchi si Murata (1998)
[96] extind algoritmul aplicand cautarea locala la fiecare solutie noua, dupa procedurile de
incrucisare si mutare.
Sayın si Karabatı (1999)[105] studiaza B&B care genereaza solutiile optimale multi-
obiectiv Pareto pentru doua masini cu makespan si flow time.
Chang, Hsieh si Lin (2002)[106] se ocupa de alocarea graduala a prioritatii obiectivelor in
locul prioritatii variabile pentru a cauta in multimea Pareto a solutiilor optimale pentru multi-
obiectivele makespan, total flow time, total tardiness si maximum tardiness. In abordarea
lor, la inceput se cauta in spatiul solutiilor fezabile primului obiectiv si apoi pentru celalalte
obiective folosind o metoda genetica si una genetica cu cautare locala.
Suresh si Mohanasundaram (2004)[107] au propus un algoritm de tipul simulated
annealing pentru solutiile optimale multi-obiectiv Pareto unde obiectivele considerate sunt
makespan si total flow time.
Rahimi-Vahed si Mirghorbani (2007) [108] au propus MOPS un algoritm hybrid complex
de tipul Particle Swarm Optimization (PSO) cu obiectivele flowtime si total tardiness.
Initializarea particulei swarm se face de catre un algoritm elitist de tipul tabu search.
Solutia reprezentata prin particula swarm este imbunatatita folosind o procedura de
cautare locala paralela.
Pag. 28/34

2. Relevanta temei in raport cu cercetarile existente.
Dezvoltarea unor sisteme de fabricatie eficiente, adaptate la provocarile economiei
globale, din ce in ce mai dinamica, necesita noi tehnologii si instrumente software pentru
optimizarea planificarii automate a productiei.
Problema flow shop scheduling este una dintre problemele cele mai greu de rezolvat
din mediul industrial, inclusa in categoria celor NP-complexe. Abordarile metaeuristice
precum Simulated Annealing , Tabu Search, Genetic Algorithms , Ant Colony
Optimization etc. sunt de preferat in rezolvarea problemelor de optimizare combinatoriala
datorita performantelor computationale. Conform studiilor facute algoritmii de tip GA
furnizeaza rezultate mai bune in timp mai scurt pentru o gama larga de probleme, solutia
obtinuta fiind foarte aprope de solutia optima. Calitatea solutiilor rezultate depinde in mare
masura de tipul operatorilor genetici folositi si de configurarea parametrilor (Ruiz(2005)[8],
Ibrahim(2013)[15]) .
Conform lui Tyagi(2013)[13] desi de peste 60 de ani, modelarea si rezolvarea ei a atras un
numar foarte mare de studii si metode de rezolvare, aria de cercetare se poate largi prin
algoritmii metaeuristici hibrizi obtinuti prin combinatia dintre un metaeuristic si alte
tehnici de optimizare care pot oferi o flexibilitate mai mare in raport cu problemele flow
shop scheduling din lumea reala.
Obiectivul principal al cercetarii doctorale consta in identificarea unei metode de
planificare eficienta in problema flow shop scheduling prin minimizarea timpului total
necesar executiei si dezvoltarea unui algoritm metaheuristic hibrid de planificare a
productiei, bazat pe metoda propusa. Validarea metodei propuse se va face pe baza
seturilor de benchmark-uri clasice propuse de Taillard[14].

Pag. 29/34

Bibliografie
[1] Michael L. Pinedo , "Scheduling Theory, Algorithms, and Systems, Third Edition", 2008
Springer Science+Business Media, LLC, ISBN: 978-0-387-78934-7 e-ISBN: 978-0-387-
78935-4 DOI: 10.1007/978-0-387-78935-4
[2] S. Reza Hejazi, S. Saghafian , "Flowshop-scheduling problems with makespan criterion: a
review", International Journal of Production Research Vol. 43, No. 14, 15 July 2005, 2895–
2929
[3] S. M. Johnson, "Optimal two and three-stage production schedules with setup times
included"
[4] E. Taillard, "Some efficient heuristic methods for the flow shop sequencing problem ",
European Journal of Operational Research 47 (1990) 65-74 65, North-Holland
[5] Shikha Agrawal, Jitendra Agawal, Dolly Gohya, Sanjeev Sharma , "Heuristic and
Metaheuristic algorithm for flow shop scheduling: a survey " , Proceedings of Academics
World 2nd International Conference , Kuala Lumpur, Malaysia, 5th Sept. 2015, ISBN: 978-
93-85465-88-8
[6] Jose M. Framinan, Jatinder N. D. Gupta si Rainer Leisten, "A review and
classification of heuristics for permutation flowshop scheduling with makespan objective ",
Technical report OI/PPC-2001/02 Version 1.2 – 20/07/2002
[7] Jatinder N.D. Gupta , Christos Koulamas, George J. Kyparisis , "Performance
guarantees for flowshop heuristics to minimize makespan ", European Journal of
Operational Research 169 (2006) 865–872
[8] R. Ruiz, C. Maroto , "A comprehensive review and evaluation of permutation flowshop
heuristics", European Journal of Operational Research 165 (2005) 479–494
[9] Andreas Witt, Stefan Voß, "Simple heuristics for scheduling with limited intermediate
storage", Computers & Operations Researc h 34 (2007) 2293 – 2309
[10] Gerardo Minella , Rubén Ruiz, Michele Ciavotta , "A review and evaluation of multi-
objective algorithms for the flowshop scheduling problem" , March 29, 2007
[11] Muhammad Nawaz , E Emory Enscore Jr, Inyong Ham, "A Heuristic Algorithm for
the m-Machine,n-Job Flow-shop Sequencing Problem" OMEA The Int. JI of Mgmt Sci . Vol.
11. No 1. pp 91 95. 1983
[12] A. Baskar , "Revisiting the NEH algorithm – the power of job insertion technique for
optimizing the makespan in permutation flow shop scheduling ", International Journal of
Industrial Engineering Computations 7 (2016) 353–366
[13] Neelam Tyagi, R.G.Varshney and A.B.Chandramouli , "Six Decades of Flowshop
Scheduling Research ", International Journal of Scientific & Engineering Research , Volume
4, Issue 9, September-2013 854 ISSN 2229-5518
[14] E. Taillard, "Benchmarks for basic scheduling problems ", ORWP89/21 Dec. 1989
[15] Adel A. Ibrahim, Raafat H. El-shaer, Hani A. Al-rwasheda, Gamal M. Nawarra ,
"Flow shop scheduling using genetic algorithm:historical review and categorization of
procedures ", The Egyptian Int. J. of Eng. Sci. And T echnology V ol. 16, No. 3 (Sept. 2013)
[16] Reev es C. R., " Improving the ef ficiency of tabu search for machine sequencing problems ", Journal
of the Operational Research Society , 44, 375-382., 1993
[17] Mocellin J.V ., " A new heuristic method for the permutation flow-shop scheduling problem " ,
Journal of the Operational Research Society , 46, 883-886, 1995
[18] Kirkpatrick, S., Gellat, C.D. and V ecchi, M.P . , "Optimization by simulated annealing", Science,1983, 220, 671–
680.
[19] Cerny, V., „ A thermodynamic approach to the traveling salesman problem: An efficient
simulation”, J. Optim.Theory Appl. 45 41-51, 1985
[20] Sevast’janov S., "Vector summation in Banach space and polynomial algorithms for
Pag. 30/34

flow shops and open shops ", Mathematics of Operations Research , 20, 90-103, 1995
[21] Lourenço H.R. , " Sevast’yanov’s algorithm for the flow-shop scheduling problem " ,
European Journal of Operational Research , 91, 176-189,1996
[22] 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 ",
North-Holland,Amsterdam, 1993
[23] Xiao-ping, L., Yue-Xuan, W., & Cheng, W. , „Heuristic algorithms for large flowshop
scheduling problems”, Intelligent Control and Automation, 2004. WCICA 2004. Fifth World
Congress on (Vol. 4, pp. 2999-3003). IEEE
[24] Dong, X., Huang, H., & Chen, P. , „An improved NEH-based heuristic for the permutation
flowshop problem”, Computers & Operations Research , 35(12), 3962-3968, 2008
[25] Singhal, E., Singh, S., & Dayma, A. , „An Improved Heuristic for Permutation Flow
Shop Scheduling. In NEH ALGORITHM”, International Journal of Computational
Engineering Research, 2 (6), 95-100, 2012
[26] Baskar, A., & Xavior, M. , „Optimization of makespan in flow shop scheduling
problems using combinational NEH family of heuristics-An analysis”, International Journal
of Applied Engineering Research , 8(10), 1205-1217, 2013
[27] Daniels, R.L. and Chambers, R.J., „Multi-objective flow shop scheduling”, Naval
Res. Logist. Quart., 1990, 37, 981–995.
[28] Dannenbring, D. G. , "An evaluation of flow-shop sequence heuristics ". Management
Science, 23,1174-1182, 1977.
[29] Aggarwal, S.C., and Stafford, E. , "A heuristic algorithm for the flowshop problem with
a common sequence on all machines ", Decision Science , 6, 237-251, 1975.
[30] Ho, J. C. and Chang, Y. L , "A new heuristic for the n-job, m-machine flow-shop
problem , European Journal of Operational Research ", 52, 194-202 , 1991.
[31] Suliman, S., „A two-phase heuristic approach to the permutation flow-shop scheduling
problem", International Journal of Production Economics 64, 143–152, 2000
[32] Lai, T. "A note on heuristics of flow-shop scheduling ", Operations Research , 44, 648-
652, 1996
[33] Moccellin, J.V., "A new heuristic method for the permutation flow-shop scheduling
problem",Journal of the Operational Research Society , 46, 883-886, 1995
[34] King, J.R., and Spachis, A.S. , "Heuristics for flow-shop scheduling ", International
Journal of Production Research , 18, 345-357, 1980.
[35] Campbell, H. G., Dudek, R. A. and Smith, M. L. , "A heuristic algorithm for the n-job,
m-machinesequencing problem " ,Management Science , 16, B630-B637 , 1970.
[36] Fred Glover, “Tabu Search – Part I” , ORSA journal on computing ,1, 190-206, 1989
[37] D. Karaboga and B. Basturk, ”A powerful and efficient algorithm for numerical
functionoptimization: artificial bee colony (ABC) algorithm ”, Journal of Global Optimization ,
vol. 39, nr. 3, pp. 459-471, 2007
[38] Osman, I.H. and Potts, C.N. , "Simulated Annealing for Permutation Flow-shop
Scheduling",OMEGA, 17, 551-557, 1989
[39] Palmer, D. S., "Sequencing jobs through a multistage process in the minimum total
time: a quick method of obtaining a near-optimum ", Operational Research Quarterly , 16,
101-107, 1965.
[40] Röck, H., and Schmidt, G. , "Machine aggregation heuristics in shop-scheduling ",
Methods of Operations Research , 45, 303-314, 1983
[41] Selim, S.Z., and Al-Turki, U.M. , " A new heuristic algorithm for the flowshop problem ",
Modern Production Management Systems , 91-96, A. Kusiak (Editor), Elsevier Science
1987.
[42] Gupta, J.N.D.,"Travelling salesman problem – a survey of theoretical developments
and applications" , Opsearch (India), 5, 181-192 , 1968.
Pag. 31/34

[43] Gupta, J.N.D., "Flowshop scheduling via sorting analogy ", UARI Research Report
No. 109,University of Alabama 1971.
[44] Gupta, J.N.D., "Heuristic algorithms for multistage flowshop scheduling problem ",
AIIE Transactions, 4, 11-18 , 1972.
[45] Gupta, J.N.D and Maykut, "Heuristic algorithms for scheduling n jobs in a
flowshop1973", Journal of the Operational Research Society of Japan , 16, 131-150,1973.
[46] Gupta, J.N.D., "A review of flowshop scheduling research ", Disaggregation Problems
in Manufacturing and Service Operations , Martin Nijhoff Publishers, 363-388, 1979.
[47] McCormick, S. T., Pinedo, M. L., Shenker, S., and Wolf, B .,"Sequencing in an
assembly line with blocking to minimize cycle time ", Operations Research , 37, 925-936,
1989.
[48] Bonney, M.C. and Gundry, S.W. , „Solution to the constrained flowshop sequencing
problem.”, Operat. Res. Quart. , 1976, 24, 869–883.
[49] Rajendran, C.,"Heuristic algorithm for scheduling in a flowshop to minimise total
flowtime", International Journal of Production Economics , 29, 65-73. 1993.
[50] Sridhar, J. and Rajendran, C. , "Scheduling in flowshop an cellular manufacturing
systems with multiple objectives – a genetic algorithmic approach ", Production Planning &
Control, 7, 374-382, 1996.
[51] Woo, D.S. and Yim, H.S. , "A heuristic algorithm for mean flowtime objective in
flowshopscheduling", Computers and Operations Research , 25, 175-182, 1998.
[52] Widmer, M. and Hertz, A ., "A new heuristic method for the flow-shop sequencing
problem", European Journal of Operational Research , 41, 186-193, 1991
[53] Sarin, S., and Lefoka, M. , "Scheduling heuristic for the n-job m-machine flow shop ",
OMEGA, 21,229-234, 1993.
[54] Stinson, J.P., and Smith, W. , "A heuristic programming procedure for sequencing the
static flowshop", International Journal of Production Research , 20, 753-764.1982.
[55] Ogbu, F.A., y Smith, D.K ., "The application of the simulated annealing algorithm to
the solution of the n/m/Cmax flowshop problem ", Computers Operations Research , 17,
243-253, 1990
[56] Ogbu, F.A., y Smith, D.K. , "Simulated annealing algorithm for the permutation
flowshop problem ", OMEGA, 19, 64-67, 1991
[57] Zegordi, S.H., Itoh, K., and Enkawa, T. , "Minimizing makespan for flow-shop
scheduling by combining simulated annealing with sequencing knowledge ", European
Journal of Operational Research , 85, 515-531, 1995
[58] Nowicki, E., and Smutnicki, C. , "A fast tabu search algorithm for the permutation
flow-shop problem", European Journal of Operational Research , 91, 160-175, 1996.
[59] J. H. Holland, “Adaptation in Natural and Artificial Systems”, Uni-IJSER International
Journal of Scientific & Engineering Research , Volume 4, Issue 9, September-2013 863
ISSN 2229-5518
[60] Chen, C.L., Vempati, V.S., and Aljaber, N. , "An application of genetic algorithms for
flow shop problems", European Journal of Operational Research , 80, 389-396, 1995.
[61] Reeves, C. R., "A genetic algorithm for flowshop sequencing ", Computers and
Operations Research , 22, 5-13, 1995.
[62] Murata, T., Ishibuchi, H. and Tanaka, H. , „Multi-objective genetic algorithm and its
applications to flowshop-scheduling", Comput. Ind. Eng. 1996, 30, 957–968.
[63] Reeves, C. and Yamada, T., „Genetic algorithms, path relinking, and the flowshop
sequencing problem", Evol. Comput., 1998, 6, 45–60.
[64] Ponnambalam, S.G., Aravindan, P. and Chandrasekaran, S. , „Constructive and
improvement flow shop scheduling heuristics: an extensive evaluation", Prod. Plan. Contr. ,
2001, 12, 335–344.
[65] Wang, L. and Zheng, D.Z. , „An effective hybrid heuristic for flow shop scheduling”,
Pag. 32/34

Int. J. Adv. Manuf. Tech., 2003, 21, 38–44.
[66] Koulamas, C., "A new constructive heuristic for the flowshop scheduling problem,
European", Journal of Operational Research , 105, 66-71, 1998.
[67] Rajendran, C., "Two-stage flowshop-scheduling problem with bicriteria", J. Oper. Res.
Soc.,1992, 43, 871–884
[68] Ishibuchi, M., Misaki, S. and Tanaka, H ., „Modified simulated annealing for the flow
shop sequencing problems", Eur. J. Oper. Res. , 1995, 81, 388–398.
[69] Ben-Daya, M. and Al-Fawzan, M. , „A tabu search approach for the flow shop
scheduling problem", Eur. J. Oper. Res. , 1998, 109, 88–95.
[70] Solimanpur, M., Vrat, P. and Shankar , R., „A neuro-tabu search heuristic for the flow
shop scheduling problem", Comput. Oper. Res. , 2004, 31, 2151–2164.
[71] Grabowski, J. and Wodecki, M., „A very fast tabu search algorithm for the
permutation flow shop problem with makespan criterion", Comput. Oper. Res. , 2004, 31,
1891–1909.
[72] Leisten, R., „Flow-shop sequencing problems with limited buffer storage”, Int. J. Prod.
Res.,1990, 28, 2085–2100.
[73] Abadi, I.N.K., Hall, N.G. and Sriskandarajah, C. , „Minimizing cycle time in a blocking
flowshop", Oper. Res., 1996, 48(1), 177–180.
[74] Wismer, D.A., "Solution of the flowshop sequencing problem with no intermediate
queues.", Oper. Res., 1972, 20, 689–697.
[75] Stafford, E.F. and Tseng , F.T., "On the Srikar–Ghosh MILP model for the N X M
SDST flowshop problem. " ,Int. J. Prod. Res., 1990, 28, 1817–1830.
[76] Reddi, S.S. and Ramamoorthy , "C.V., On the flowshop sequencing with no wait-in-
process.", Operat. Res. Quart. , 1972, 23, 323–331.
[77] Bertolissi, E., "Heuristic algorithm for scheduling in the no-wait flow-shop ", J. Mater.
Process.Tech., 2000, 107, 459–465
[78] Bonney, M.C. and Gundry, S.W. , "Solution to the constrained flowshop sequencing
problem", Operat. Res. Quart. , 1976, 24, 869–883
[79] Aldowaisan, T. and Allahverdi, A ., "New heuristics for m-machine no-wait flowshop
to minimize total completion time ", Omega, 2004, 32, 345–352.
[80] Aldowaisan, T. and Allahverdi, A ., "Total flowtime in no-wait flowshops with
separated set-up times ", Comput. Oper. Res. , 1988, 25, 757–765
[81] Aldowaisan, T. and Allahverdi, A , "New heuristics for no-wait flowshops to minimize
makespan", Comput. Oper. Res. , 2003, 30, 1219–1231
[82] Stafford, E.F. and Tseng, F.T. , "Two MILP models for the SSIST flowshop sequencing
problem", DSI National Meetings, 17–20 November 2001
[82] Rock, H., "The three-machine no-wait flowshop is NP-complete ",J. Assoc. Comput .
Mach.,1984, 31, 336–345.
[83] Ham, I., Hitomi, K. and Yoshida, T. , Group Technology , 1985 (Kluwer-Nijhoff: Boston)
[84] Sule, D.R. and Huang , „K.Y ., Sequence on two and three machines with set-up,
processing and removal times separated „ Int. J. Prod. Res., 1983, 21, 723–732.
[85] Khurana, K. and Bagga , P.C., "Scheduling of job-block with deadline in nX2 flowshop
problem with separated set-up times " , Indian J. Pure Appl. Math. , 1985, 16, 213–224
[86] Allahverdi, A., "Two-stage production scheduling with separated set-up times and
stochastic breakdowns", J. Oper. Res. Soc ., 1995, 46, 896–904.
[87] Proust, C., Gupta, J.N.D. and Deschamps, V. , „Flowshop-scheduling with set-up,
processing and removal times separated.", Int. J. Prod. Res., 1991, 29, 479–493
[88] Park, T. and Steudel, H.J. , „Analysis of heuristics for job sequencing in manufacturing
flow line work-cells", Comput. Ind. Eng. , 1991, 20, 129–140.
[89] Gupta, J.N.D. and Tunc, E.A. , "Scheduling a two-stage hybrid flowshop with
separable set-up and removal times ", Eur. J. Oper. Res. , 1994, 77, 415–428.
Pag. 33/34

[90] Cao, J. and Bedworth, D.C. , "Flow shop scheduling in serial multi-product processes
with transfer and set-up times ", Int. J. Prod. Res., 1992, 30, 1819–1830
[91] Allahverdi, A., "Scheduling in stochastic flowshops with independent set-up,
processing and removal times", Comput. Oper. Res. , 1997, 24, 955–960.
[92] Rajendran, C. and Ziegler, H., „Heuristics for scheduling in a flowshop with set-up,
processing, and removal times separated", Prod. Plan. Contr. , 1997, 8, 568–576.
[94] Gupta, J. N. D., V. R. Neppalli, F. Werner ., „Minimizing total flow time in a two-
machine flowshop problem with minimum makespan", International Journal of Production
Economics, 69 323–338, 2001
[95] Rajendran, C., „Heuristics for scheduling in flowshop with multiple objectives.”, Eur. J.
Oper. Res., 1995, 82, 540–555
[96] Ishibuchi, H. and Murata, H. , „Multi-objective genetic local search algorithm and its
applications to flowshop-scheduling.”, IEEE Trans. Sys. Man Cybern. , 1998, 28, 392–403.
[97] Hoogeveen, H., „Multicriteria scheduling”, European Journal of Operational
Research, 167 592–623, 2005.
[98] Nagar, A., Haddock, J. and Heragu, S. , „Multiple and bicriteria scheduling: a
literature survey”,Eur. J. Oper. Res. , 1995, 81, 88–104.
[99] Cavalieri, S., P. Gaiardelli , „Hybrid genetic algorithms for a multiple-objective
scheduling problem", Journal of Intelligent Manufacturing , 9 361–367, 1998 .
[100] Sivrikaya-Serifoğlu, F., G. Ulusoy. , „A bicriteria two-machine permutation flowshop
problem”, European Journal of Operational Research ,107 414–430, 1998.
[101] Chakravarthy, K. and Rajendran, C. , „A heuristic for scheduling in a flowshop with
the bicriteria of makespan and maximum tardiness minimization" , Prod. Plan. Contr. ,
1996, 10, 707–714.
[102] T’kindt, V. and Billaut, J.-C. , „Multicriteria scheduling problems: a survey ”, RAIRO
Oper. Res.,2001, 35, 143–163
[103] Graham, R. L, Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. ,
„Optimisation and approximation in deterministic sequencing and scheduling: a survey",
Annals of Discrete Mathematics , 5, 287-326, 1979
Pag. 34/34