Schedulazione: più macchine Schedulazione: più macchine

Schedulazione: più macchine
Schedulazione: più macchine
casi:
– job composti di un unico task da schedulare su una tra più
macchine;
– open shop (tutti i job hanno task su tutte le macchine, ma non
le stesse precedenze);
– flow shop (tutti i job hanno task su tutte le macchine e le
stesse precedenze;
– job shop (caso generale, non tutti i job hanno task su tutte le
macchine, ma possono avere più task sulla stessa macchina).
Raffaele Pesenti
1
job composti di un unico task da schedulare su una tra più
macchine;
Raffaele Pesenti
Modello
Modello
Ogni job i degli n da eseguire si ritiene caratterizzato da:
• parametri
–
–
–
–
2
• variabili decisionali (caso senza preemption)
– xij: assegnamento job i macchina j
– Ci: tempo completamento job (completion time) di solito variabile
principale
– ti = Ci - pi : tempo inizio esecuzione (starting time)
– Wi = ti - ri : tempo attesa (waiting time)
– Fi = Ci - ri : tempo permanenza/attraversamento nel sistema (flow time)
– Li = Ci - di : tempo di ritardo (lateness)
– Ti = (Ci - di)+: ritardo (tardiness)
– Ui = 1{Ci > Di}: violazione della deadline (tardy)
– Ei = (di - Ci)+: anticipo (earliness)
pi: tempo di esecuzione (processing time)
ri: tempo di rilascio/lancio (release time)
di: data di consegna (due date)
Di: data di recesso (deadline)
Ogni macchina j delle m parallele si ritiene caratterizzato da:
• parametri
– oj: tempo di inizio disponibilità (opening time)
– clj: tempo di termine disponibilità (closing time)
– vij: velocità* esecuzione job i (speed)
* il tempo effettivo di esecuzione è pi/vij
Raffaele Pesenti
3
Raffaele Pesenti
4
P/ /ΣiCi
Terminologia
A seconda della velocità relativa le macchine si dicono
– P: parallele, vij= v, ∀i,j, dal punto di vista operativo le macchine sono
identiche,
– Q: uniformi, vij= vj, ∀i, la velocità relativa delle macchine non dipende
dal job eseguito,
– R: non correlate, vij≠ vik, ∀i,j,k la velocità relativa delle macchine
dipende dal job eseguito
• Problema: minimizzare il tempo medio di completamento su
macchine parallele di job con identica release time.
Uno scheduling è detto List Scheduling (LS) quando i job
vengono ordinati secondo un criterio qualunque e, non appena una
macchina è disponibile, viene eseguito quello il job con priorità più
alta tra quelli immediatamente disponibili.
Raffaele Pesenti
5
• Teorema: la politica Shortest Processing Time first (SPT)
determina la soluzione ottima. Si eseguono per prima i task con
tempo di esecuzione minore assegnandoli alla prima macchina
disponibile.
Raffaele Pesenti
R/ /ΣiCi
P/ .../ΣiCi
Definendo xijk la variabile che indica che il jmo job deve essere
assegnato alla ima macchina in kma posizione dalla fine,
formulando il problema come PLI si osserva che si ottiene un
problema di bipartite matching O(n3):
I problemi diventano NP-hard non appena viene introdotta
qualche complicazione, e.g.,
P 2//Σi wiCi , P 2/tree/ Σi Ci , P 2/ri / Σi Ci , P 2//Cmax.
min Σi Σj Σk k pj xijk /vij
(si moltiplica per k poichè il job influenzerà i k-1 job successivi)
Σi Σk xijk =1
∀j
(job assegnato)
Σj xijk ≤ 1
∀ i,k (non più di un job per posizione)
xijk ∈ {0, 1}
Raffaele Pesenti
6
7
Applicando la regola di Smith per P 2//Σi wiCi si ottiene una
(1+√2)/2 approssimazione.
Nel caso P//Σi wiCi si possono anche definire schemi
completamente polinomiali nel numero di job, ma esponenziali
nel numero di macchine
Raffaele Pesenti
8
Q/pj=1/Σjgj
Q/pj=1/gmax
Il problema Q/pj=1/Σjgj è risolvibile tramite bipartite matching:
• si definisce xijk la variabile binaria che indica che il jmo job deve
essere assegnato alla ima macchina nella kma slot temporale
• il costo è min Σi Σj Σk gj (k/vi) xijk
Q/pj=1/gmax per g generico è risolvibile generalizzando Lawler:
si considerano i completion time Cj possibili dal minimo al
massimo e per ognuno di essi si schedula il job con costo
minimo.
Q/pj=1/Σj wiCi, Q/pj=1/Σj Ti, Q/pj=1/Σj wiUi, sono risolti anche con
algoritmi ad hoc.
Q/ rj, pj=1/Σj Ci, è NP-hard
Raffaele Pesenti
9
Q/pj=1/Lmax, Q/ rj, pj=1/Lmax sono risolti anche con algoritmi ad
hoc.
Raffaele Pesenti
P/pmtn/Σi wiCi
P/ /Cmax
• Per il problema P/pmtn/Σi wiCi il teorema di McNaughton indica
che non c’è alcuno schedule con un numero finito di preemption
(si può generalizzare all’infinito) che garantisca una soluzione
migliore di quella senza preemption. I risultati sulla complessità
risultano inoltre identici al caso senza preemption.
• Il teorema non si applica nel caso di macchine uniformi
Q/pmtn/Σi wiCi, comunque Q/pmtn/ wCmax + Σi Ci è
polinomiale.
• Il problema Q/pmtn/Σi wiUi è NP-hard anche se wi=1.
Raffaele Pesenti
10
11
• Problema: minimizzare il tempo di completamento dell’ultimo
job su macchine parallele di job con identica release time.
• Teorema: il problema è NP-hard (riduzione da bin packing). La
politica Longest Processing Time first (LPT) è in generale una
buona euristica. Si eseguono per prima i task con tempo di
esecuzione maggiore assegnandoli alla prima macchina
disponibile.
Raffaele Pesenti
12
Esempio: P 2//Cmax vs P 2/ /ΣiCi
P/ /Cmax
Teorema: qualunque List Scheduling (LS) è 2-1/m approssimante.
Prova: sia k l’ultimo job ad essere schedulato l’approssimazione si
ottiene osservando che
Cmax(LS) ≤ Σj≠k pj /m + pk
Tale valore è stretto, m(m-1) job con pj=1 e pn=m.
In probabilità se n cresce più velocemente di m, il LS è ottimo.
Se si si sceglie LPT si ottiene una 4/3-1/3m approssimazione.
Da studi probabilistici LPT sembra essere migliore di un
arbitrario LS, inoltre per n che tende all’infinito l’errore rispetto
allo scheduling ottimo tende a zero quasi sicuramente con
velocità n-c per qualche c costante.
Raffaele Pesenti
13
Job
j1
j2
j3
j4
j5
j6
j7
j8
pi
3
4
2
4
4
2
13
2
j1
j3
0
0
Raffaele Pesenti
j6
LPT non ottimo
j4
j5
j1
j6
j8
schedule LPT , Cmax= 17 ottimo, ΣiCi/n = 12.625
j3
j6
j8
j1
j2
j5
j4
j7
schedule SPT, Cmax= 22, ΣiCi/n = 7.5 ottimo
14
P/ /Cmax
j5
j4
j6
schedule ottimo
j1
j3
j2
j3
Raffaele Pesenti
Esempio
Problema P 3/ / Cmax
Job
pi
j1
6
j2
4
7
j3
j4
3
5
j5
j6
9
2
j7
j8
3
j7
• Migliori approssimazioni in tempi O(nlogn+knlogm) possono
ottenersi con il MultiFit (MF), dove si cerca di trovare,
attraverso ricerca binaria e k tentativi di packing, la capacità
minima che m ‘bin’ possono avere per contenere i job che sono
assegnati al primo bin in cui riescono ad essere inseriti.
• Una variazione del MF detto dual approximation algorithm
produce uno schema di approssimazione polinomiale. Fissato il
numero di macchine esistono schemi polinomiali che usano
anche la programmazione dinamica.
• Siccome il problema è NP-hard in senso forte non dovrebbe
esistere uno schema di approssimazione completamente
polinomiale.
j7
j8
j2
13
j5
j2
j8
j7
j4
14
15
Raffaele Pesenti
16
P/ri /Lmax
Q/ /Cmax
• Il problema P/ri/Lmax è NP-hard
– LS è 2 approssimante;
– EDD induce un errore massimo t.c.:
Lmax(EDD) - L*max ≤ (2m - 1)maxjpj/ m;
Per il problema Q//Cmax si estendono i risultati del caso P//Cmax,
cambiano di poco in peggio i valori delle approssimazioni.
Negli schedule può essere conveniente inserire degli idle time,
invece di assegnare alla prima macchina libera si deve assegnare
alla prima macchina che termina i job.
• Il problema P/ri,pj=p/Lmax è polinomiale.
Raffaele Pesenti
17
Raffaele Pesenti
R/ /Cmax
P/pmtn /Cmax
Nel caso di R//Cmax i problemi sono più difficili che nel caso
uniforme.
Non dovrebbero esistere polinomial scheme c-approssimante con
c <3/2. Anche se , fissato il numero delle macchine esistono fully
polinomial scheme.
Una variante del LS è 1+2.5√m +1/(2√m) approssimante. Mentre
un algoritmo di Potts basato sulla programmazione lineare è 2approssimante.
Raffaele Pesenti
18
19
Il problema P/pmtn /Cmax è risolto dall’algoritmo wrap-around
di McNaughton, che parte dalla osservazione che
Cmax=max{maxjpj,(Σjpj)/m}
(estendibile opportunamente al caso macchine uniformi), si
riempiono quindi le macchine successivamente fino a soddisfare
tale valore, spezzando tra una macchina e la successiva i job che
eventualmente lo viola.
In questo caso vi sono al massimo (m-1) preemption.
È NP-hard determinare uno scheduling ottimo che minimizzi il
numero di preemption.
Raffaele Pesenti
20
Esempio
Problema P 3/ pmtn / Cmax (McNaughton)
Job
pi (mac.)
6
(A)
j1
j2
3
(A)
j1
7 (B,A)
j3
j4
3
(B)
j3(parte 1)
j5
8
(B,C)
j5(parte 1)
9
(C)
j6
j7
1
(C)
0
2
(C)
j8
Esempio
j2
j4
j3(parte 2)
j5(parte 2)
j6
j8
Raffaele Pesenti
Q/pmtn /Cmax
j7
13
21
j1
j4
Raffaele Pesenti
R/pmtn /Cmax
J5(parte 2)
j8
j7
18
22
P/pmtn,ri ,Di /Cmax
• Il problema Q/pmtn/Cmax può essere risolto in O(mn2) con una
variazione di LPT che assegna il job con il massimo largest
remaining processing time al processore più veloce disponibile.
Esistono anche algoritmi più efficienti che supponendo le
macchine e i job già ordinati sono O(n).
• Nel caso R/pmtn/Cmax il valore di Cmax si può trovare attraverso
programmazione lineare, la soluzione può essere costruita in un
tempo polinomiale utilizzando un algoritmo per Q/pmtn/Cmax .
Raffaele Pesenti
Problema P 3/ pmtn / Cmax (McNaughton)
Job pi (mac.)
j1 18 (A)
j2
3 (B)
7 (B)
j3
j2
j3
j4
3 (B)
j5
8 (B,C)
j5(parte 1)
j6
9 (C)
j6
0
j7
1 (C)
2 (C)
j8
23
• per il problema P/pmtn,ri ,Di /Cmax l’esistenza di uno scheduling
ammissibile può essere verificato con modelli di network flow
O(n3). I problemi si risolvono quindi polinomialmente facendo
bisezione su Cmax;
• i risultati si generalizzano a Lmax;
• generalizzazioni polinomiali si hanno anche per R/pmtn,ri /Cmax.
Raffaele Pesenti
24
P/prec,pi=1/Cmax
P 2/prec,pi=1/Cmax
• Il problema P/prec,pi=1/Cmax è NP-hard, e non può essere
trovata un’approssimazione polinomiale con c < 4/3;
• P 2/prec,pi=1/Cmax è polinomiale, non è noto per un altro
numero di macchine fissato;
• P/tree,pi=1/Cmax è polinomiale si applica l’algoritmo di Hu del
Critical Path (CP). In ogni slot temporale deve essere
schedulato il job da cui dipende la più lunga catena di job non
eseguiti;
• P/intree,pi=1/Lmax è polinomiale si applica l’algoritmo CP;
• P/outtree,pi=1/Lmax è NP-hard;
• altri casi P|prec,p=1|Cmax polinomiali si possono avere per grafi
di precedenza particolari.
• Il problema P 2/prec,pi=1/Cmax è polinomiale con l’algoritmo di
Coffman e Graham (CG) O(n3)
• CG funziona assegnando il label k+1, essendo già assegnate k
etichette, a quel job che ha gli immediati successori già
etichettati e tali che le etichette dei sui immediati successori
siano lessicograficamente minime.
• Gabow definisce un algoritmo O(n2) che usa le operazioni
cosiddette di union-find.
Raffaele Pesenti
Raffaele Pesenti
25
P/prec, pi=1/ΣiCi
P/prec/Cmax
• Il problema P/prec, pi=1/ΣiCi è NP-hard,
• P/outtree, pi=1/ΣiCi è polinomiale con CP;
• in generale, anche in questi casi non si possono dare
approssimazioni con c<4/3:
– CP è 4/3 approssimante per m=2, e 2-1/(m-1) per m>2,
– CG è 2-1/m approssimante,
– MS che assegna il job con maggior numero di successori è
4/3 approssimante per m=2.
Raffaele Pesenti
26
Il problema P/prec/Cmax è 2-1/m approssimato da LS e da CP.
Poco meglio si riesce a fare con algoritmi ad hoc su grafi di
precedenza particolari.
27
Raffaele Pesenti
28
P/prec/Cmax e LS paradossi
Esempio: P 2/prec/Cmax
Attenzione: il LS, che di solito esprime una priorità tra i job, può
avere comportamenti a paradossali.
j1: p1=3
Dato un problema P/prec/Cmax (ma anche in altre situazioni e per
altre misure), il makespan può aumentare anche se:
– si aumenta il numero delle macchine
– si diminuisce il tempo di esecuzione delle operazioni
– si eliminano alcune precedenze
– si cambia la priorità tra i task.
Raffaele Pesenti
j7: p7=13
j8: p8=2
29
j3
j4
j5
j2
j6
j2
j8
j3
j2
j4
j5
j7
j5
j2
j7
j3
cambio di LS, nuovo LS = {j1, j2, j3, j4, j5, j6, j8, j7}, Cmax= 23
Raffaele Pesenti
j6 j8
tempi di esecuzione diminuiti di un unità, Cmax= 18
j6
j5
j6: p6=2
30
j1
j4
j5: p5=4
Raffaele Pesenti
j1
j8
j7
j3
j4: p4=4
Esempio: P 2/prec/Cmax
schedule ottimo Cmax= 17
j1
j3: p3=2
LS = {j1, j2, j3, j4, j5, j6, j7, j8}
Esempio: P 2/prec/Cmax
j1
j2: p2=4
j6
j4
j7
j8
una macchina in più, Cmax= 19
31
Raffaele Pesenti
32
Esempio: P 2/prec/Cmax
j1: p1=3
j2: p2=4
j7:
p7=13
j3: p1=2
j8: p8=2
j1
j2
j3
j4: p4=4
j5
j4
P/pmtn, prec/Cmax
j5: p5=4
j6: p6=2
j7
j6
• Il problema P/pmtn, prec/Cmax è NP-hard,
• P 2/pmtn, prec/Cmax e P/pmtn, tree/Cmax sono polinomiali
tramite l’algoritmo di Muntz e Coffman.
• In generale tale algoritmo garantisce una 2-1/m
approssimazione, e nel caso Q/pmtn, prec/Cmax una √(3m/2)approssimazione.
j8
meno precedenze, Cmax= 22
Raffaele Pesenti
33
Raffaele Pesenti
Stochastic machine scheduling
Modelli multi-operation
• P/pi~exp(λi)/ECmax è minimizzato da Longest Expected
Processing Time (LEPT);
• Q/pmtn,pi~exp(λi)/ECmax è minimizzato da preempted LEPT;
• P/pi~exp(λi)/EΣiCi è minimizzato da SEPT;
Job composti da più task da schedulare su più macchine;
• Q/pmtn,pi~exp(λi)/EΣiCi è minimizzato da preempted SEPT.
Solo pochissimi casi di modelli multi-operation sono
polinomiali, i più noti sono:
Nel caso di scheduling stocastico algoritmi che sono solo
euristici nel caso deterministico diventano ottimi quando la
probabilità dei casi peggiori tende a zero.
In generale le politiche ottime sono dinamiche e si basano sulla
storia realizzata fino all’istante corrente.
Raffaele Pesenti
34
F2//Cmax, O2//Cmax, O/pmtn/Cmax.
35
Raffaele Pesenti
36
Open shop
Open shop
• O/pmtn/Lmax è polinomiale, (Lenstra et al. in O(n)), questo
implica...
• O/pmtn/Cmax è polinomiale;
Gonzalez e Sahni provano che Cmax coincide con il bound
max{maxΣipij,maxΣjpij};
• O/pmtn, ri /Lmax, l’ammissibilità può essere verificata tramite
programmazione lineare e quindi il valore ottimo può essere
cercato per bisezione;
• O2/pmtn/ΣiCi è aperto tutti gli altri problemi sono NP-hard.
• O2//Cmax è polinomiale O(n),
Gonzalez e Sahni costruiscono uno schedule che coincide con il
lower bound max{Σjp1j,Σjp2j,maxj(p1j+p2j)}, imponendo che non
ci siano idle time dall’inizio della prima operazione al termine
dell’ultima su ognuna delle due macchine;
• O2/rj/Cmax, e O2//Lmax sono NP-hard in senso forte;
• O3//Cmax NP-hard in senso normale.
Raffaele Pesenti
Raffaele Pesenti
37
38
Esempio
Flow shop
• F2//Cmax è polinomiale.
L’algoritmo di Johnson lo risolve in O(nlogn) sequenziando
prima i job con p1j≤ p2j per p1j crescenti quindi i rimanenti job
per p2j decrescenti. Si ottiene un permutation schedule (ogni
macchina processa i job nello stesso ordine), basta un
interchanging argument per provare che almeno un permutation
schedule ottimo esiste;
• F2//Lmax , F2/ri/Cmax,sono NP-hard nel senso forte;
• per F2/ri/Cmax un algoritmo approssimato che applica una
variante la regola di Johnson è 5/3-approssimato.
Raffaele Pesenti
39
Problema F 2/ / Cmax (Johnson)
T5A
T1A
T5B
T4A
T1B
Job piA
j1
4
4
j2
j3 10
6
j4
j5
2
T3A
T4B
piB
5
2
4
12
3
T2A
T3B
T2B
0
30
Raffaele Pesenti
40
Flow shop
Flow shop
• F3//Cmax è NP-hard in senso forte,
diventa polinomiale sotto varie ipotesi di rapporti particolari tra
i processing times, oppure se la macchina intermedia è non
bottleneck, cioè può processare più job contemporaneamente.
• Fm//Cmax, per m≥ 4, viene affrontato con qualche successo
anche dalla simulated annealing (dove si intendono adiacenti
permutazioni che coincidono tranne per la posizione di un job),
euristiche basate su Johnson sono ⎣m/2⎦-approsimanti.
Raffaele Pesenti
Fm//Cmax, per m≥ 4 , non necessariamente ammette soluzioni ottime
che siano permutation schedule anche se esiste una soluzione ottima
che ha una stessa sequenziazione su M1 e M2 e una su Mm-1 e Mm.
Se ci si limita lo stesso a cercare solo permutation schedule i migliori
bound si ottengono considerando tutte le macchine u, v (u≤v), tranne
due, di infinita capacità (possono processare più job assieme).
Cmax={minjΣi=1,u-1pij+contributo_macchine_da_u_a_v+minjΣi=v+1,mpij},
– se u=v, contributo_macchine_da_u_a_v = Σj puj,
– se v=u+1 si risolve con Johnson,
– altrimenti si considerano le macchine intermedie tra u e v come un’unica
macchina non bottleneck.
41
Raffaele Pesenti
Flow shop no-wait
Job shop
• Ogni istanza di J//Cmax può venire rappresentata attraverso un
grafo disgiuntivo*, dove ad ogni insieme di operazioni sulla
stessa macchina corrisponde una clique.
Ogni soluzione ammissibile corrisponde a rendere il grafo
orientato e senza circuiti scegliendo un orientamento per gli
archi disgiuntivi.
Un flow-shop è no-wait se ogni job, una volta iniziato, deve
essere processato senza soluzione di continuità.
• F/no-wait/Cmax può essere formulato come un TSP
n+1 città 0,1,...,n con distanze
cjk=max1≤i≤m{Σh=1,iphj- Σh=1,i-1phk} con pi0=0.
• F2/no-wait/Cmax è un TSP particolare risolvibile in O(n2),
• tutte le altre variazioni sono NP-hard (anche F2/no-wait/ΣiCi,
F2/no-wait/Lmax O2/no-wait/Cmax J2/no-wait/Cmax etc..).
Una gestione no wait può allungare considerevolmente lo
scheduling fino a, ma escluso, m volte.
Raffaele Pesenti
42
* Un grafo disgiuntivo G=(N,C∪ D) ha un nodo in N per ogni task, un arco
orientato (congiuntivo) in C per ogni relazione di precedenza tra due task, un
arco non orientato (disgiuntivo) in D per ogni coppia di task in competizione
per la stessa macchina.
43
Raffaele Pesenti
44
Job shop
Job shop
• J2/m≤ 2/Cmax può essere risolto con una modifica dell’algoritmo
di Johnson. Su M1 si sequenziano i job secondo la regola
(J12,J1,J21), dove il pedice degli insiemi indicano l’ordine delle
macchine su cui devono essere eseguiti, J12, J21 ordinati secondo
Johnson, su M2 si sequenzia secondo (J21,J2,J12);
• J2/pij=1/Cmax (Lmax) è polinomiale;
• J//Cmax polinomiale se si considerano solo due job con
precedenze complete. Ci si riconduce alla ricerca di un percorso
minimo;
• J2/pmtn/ΣiCi e gli altri job shop sono in generale NP-hard in
senso forte.
Raffaele Pesenti
45
Resource constrained
project scheduling
Sliding/shifting bottleneck machine e simulated annealing sono
le euristiche più usate (scheduling adiacenti sono quelli che
scambiano due job sul maximum weight path)
Raffaele Pesenti
46
Problemi reali
• P2/pj=1/Cmax, con risorse con disponibilità costante Rh, t.c. ogni
job ne abbisogni di rjh è polinomiale.
Il problema si trasforma in maximum cardinality matching. Si
costruisce un grafo che ha per vertici i job e presenta archi che
uniscono le coppie di job che possono essere eseguite
contemporaneamente.
• In generale i problemi sono NP-hard, anche perché la
disponibilità e la richiesta di risorse possono variare nel tempo o
per l’uso.
Raffaele Pesenti
Il problema del job-shop è in genere risolto tramite B&B
facendo il branching sulla direzione degli archi non orientati del
grafo disgiuntivo.
I bound che vengono calcolati generalmente con rilassamento
surrogato (sulla capacità delle macchine o i vincoli di
precedenza).
47
La realtà è spesso molto più complessa di quella ipotizzata nei
semplici modelli considerati. Si incontrano quasi sempre dei job
shop, in cui i task di uno stesso job posson dovere essere
eseguiti in momenti diversi sulla stessa macchina, in cui sono
inoltre spesso presenti:
– stocasticità;
– dinamicità;
– disturbi;
– congestione;
– ambiguità negli obiettivi e nei vincoli;
– ...
Raffaele Pesenti
48
Obiettivi
Euristiche
Nella maggiore parte dei casi reali è difficile definire
esattamente in modo formale l’obiettivo perseguito.
I problemi reali sono spesso NP-hard e vengono risolti tramite
euristiche.
In genere si vuole comunque ridurre
– flow time medio
– wip medio*
– tardiness media e massima (in presenza di due date)
I modelli semplificati visti in precedenza servono comunque a:
– suggerire dei modelli di comportamento su cui basare le
euristiche;
– valutare le prestazioni delle euristiche in situazioni in cui è
possibile calcolare i valori ottimi.
* il metodo dei kanban pone dei limiti per il wip massimo in presenza di produzioni
molto regolari
Raffaele Pesenti
49
Raffaele Pesenti
Approcci generali
50
Approcci generali
In problemi di scheduling quanto affermato si traduce nel
cercare di schedulare al meglio le macchine collo di bottiglia (le
macchine con throughput minimo, lungo le loro linee di
produzione, che determinano la prestazione della linea) e le
attività critiche (task il cui ritardo nell’esecuzione si traduce in
un ritardo complessivo nel completamento del job di
appartenenza).
Regola di buon senso:
quando si affronta un problema complesso conviene cercare di
decomporlo e concentrare l’attenzione solo su quegli aspetti in
cui vi sia probabilità di maggiore miglioramento delle
prestazioni per unità di “sforzo” impiegato.
Purtroppo sia le macchine collo di bottiglia che le attività
critiche sono spesso dipendenti dai job e tempo varianti.
Raffaele Pesenti
51
Raffaele Pesenti
52
Approcci generali
Approcci generali
Per i colli di bottiglia si propongono approcci generali in cui si
individua un collo di bottiglia alla volta e si cerca di schedularlo
al meglio (e.g., sliding/shifting bottleneck, OPT), oppure in cui
si cerca di schedulare le altre macchine in modo che le le
macchine collo di bottiglia non rimangano mai idle (starvation
avoidance).
Le euristiche orientate alla riduzione del flow time medio
tendono ad eseguire i task più veloci e a fare uscire dal sistema i
job che siano più avanti nelle lavorazioni.
Per l’identificazione delle attività critiche si utilizzano
metodologie PERT-CPM.
In seguito vengono presentate le euristiche generali che hanno di
solito le migliori prestazioni. Euristiche più complesse in genere
non presentano risultati apprezzabilmente diversi.
Raffaele Pesenti
53
Notazione
Raffaele Pesenti
54
Euristiche relative al flow time
•
•
•
•
•
•
Z: indice minimizzato,
t: tempo corrente,
di: due date job i,
pij: tempo (atteso) di esecuzione del task del job i sulla macchina j,
ni: numero di task ancora da eseguire per il job i al tempo t,
wij : tempo di attesa che un task del job i si supponga (date le
informazioni all’istante t) debba spendere prima di essere eseguito
sulla macchina j,
• sli : slack sli = di - ( t + Σj∈S(i) pij )
• S(i): macchine su cui devono essere ancora eseguiti i task del job i
al tempo t.
Raffaele Pesenti
Le euristiche orientate al rispetto delle due date tendono ad
eseguire i task in un qualche senso più urgenti.
55
• SI: Shortest Imminent Operation, Z = pij
• SR: Shortest Remaining Processing Time, il primo task del job
per cui è minimo Z = Σj∈S(i) pij
Possibili correzioni
• SI troncata FCFS: quando l’attesa di un task eccede una data
soglia, viene posto su una coda prioritaria gestita FCFS.
• SI*: i task dei job con sli - Σj∈S(i) wij <0 vengono posti su una
coda prioritaria, anche essa gestita SI;
• SPT-T: il primo task del job per cui è minimo
Z = min{pij+ r, sli /ni}, dove r parametro fissato.
Raffaele Pesenti
56
Euristiche relative alla tardiness
•
•
•
•
EDD: Earliest Due Date, Z = di,
Slack: slack minimo , Z = sli,
Slack/OPN:slack per operation, Z = sli /ni,
Critical Ratio: Z = Σj∈S(i) pij /(di - t)
Appendice Matematica
Euristiche ed Approssimazioni
Per due date stringenti (meno di circa sei volte il tempo di esecuzione
complessivo dei job) o sistemi congestionati >90% della capacità disponibile
le politiche SI o SI corrette hanno buone prestazioni, se non migliori delle
regole specifiche, anche per la tardiness (questo poiché i job tendono
comunque ad essere in ritardo).
17/12/2004 11.25
Raffaele Pesenti
Raffaele Pesenti
57
Soluzioni approssimate e algoritmi
euristici
Errori
Quando è possibile (non sempre lo è) è opportuno dare una
stima per eccesso dell’errore compiuto accettando la soluzione
di un algoritmo euristico rispetto a quella ottima
Trovare la soluzione ottima di problemi di ottimizzazione NPhard può risultare in pratica troppo oneroso, inoltre dato che i
parametri del modello considerato possono essere affetti da
errori tale sforzo potrebbe essere anche poco rilevante.
Nei casi pratici possono essere anche accettate delle soluzioni
“buone” che, sperabilmente, non siano lontane dall’ottimo.
Algoritmo euristico:
algoritmo che risolve un problema di ottimizzazione, utilizzando
in genere regole di buon senso, e fornisce una soluzione
ammissibile ma non necessariamente ottima.
Raffaele Pesenti
59
Errori:
dato un problema (F,c; max), detti zopt= {max c(x) : x∈F} il
valore della soluzione ottima e zA il valore fornito dall’algoritmo
euristico A si definiscono
– errore assoluto: EA= zopt - zA
– errore relativo: RA= (zopt - zA)/zopt
Raffaele Pesenti
60
Algoritmi approssimati
Algoritmi approssimati
Algoritmo ε-approssimato:
algoritmo che garantisce un errore relativo non maggiore di ε > 0:
Ra ≤ ε
Schema di approssimazione:
algoritmo che garantisce Ra ≤ ε per qualunque ε > 0
– schema di approssimazione polinomiale: schema di
approssimazione con complessità polinomiale nelle dimensioni
dell’istanza
– schema di approssimazione pienamente polinomiale: schema di
approssimazione con complessità polinomiale nelle dimensioni
dell’istanza e in 1/ε
Raffaele Pesenti
61
Commenti:
• Quando esistono conviene applicare algoritmi approssimati, per
i quali è calcolabile, per definizione, un limite massimo
dell’errore compiuto, rispetto a degli algoritmi euristici basati
sul buonsenso, ma per cui non si può fornire un limite massimo
dell’errore.
• Per alcuni problemi non sono noti algoritmi approssimati, per
altri il migliore algoritmo approssimato ha valori di ε grandi
(maggiori di 0.5). Inoltre algoritmi euristici con accettabili
prestazioni medie vengono a volte preferiti ad algoritmi
approssimati (almeno in prima battuta) perché sono più facili da
implementare e generalmente più veloci.
Raffaele Pesenti
Tipi di euristiche
Tipi di euristiche
Commenti:
in genere le soluzioni fornite dalle euristiche costruttive e
quelle utilizzate dalle euristiche di miglioramento sono
soluzioni ammissibili. Per certi problemi risulta anche
estremamente complesso determinare una prima soluzione
ammissibile, allora può convenire rilassare lagrangianamente
alcuni vincoli, i.e., determinare una prima soluzione che
soddisfi almeno parte dei vincoli e penalizzare il fatto che altri
vincoli non siano rispettati. Quindi iterativamente a partire
dalla soluzione (non ammissibile ottenuta) cercano di
determinarne una che rispetti maggiormente i vincoli
nell’intorno di quella data
Euristiche costruttive
costruiscono una soluzione del problema
Euristiche di miglioramento
iterativamente a partire da una soluzione del problema
cercano di determinarne una migliore nell’intorno di quella
data
Raffaele Pesenti
62
63
Raffaele Pesenti
64
Metaeuristiche
Metaeuristica greedy
Affinché una euristica sia efficace deve sfruttare le
caratteristiche strutturali del problema che deve risolvere, per
questo motivo non esiste una euristica generale.
Esistono però degli approcci generali a cui si può fare
riferimento per sviluppare euristiche specifiche. Tali approcci
vengono detti metaeuristiche.
Esempi:
metaeuristica costruttiva:
– greedy
metaeuristica migliorativa:
– ricerca locale
• simulated annealing
• tabu search
Raffaele Pesenti
Metaeuristica greedy
1. inizializzazione:
Si ordinano gli elementi e1, e2,..., em che concorrono a comporre una
soluzione in modo non decrescente(c1≤c2≤... ≤cm) rispetto ai loro costi
(oppure in modo non crescente rispetto ai profitti o comunque in
modo monotono rispetto ad una funzione euristica di valutazione).
Si pone F0=∅, //insieme degli elementi che compongono la soluzione
65
Raffaele Pesenti
Metaeuristica greedy
Euristiche greedy
2. iterazione:
while non si è costruita completamente una soluzione {
si sceglie ek,
if Fk-1∪{ek} non viola i vincoli dati Fk=Fk-1∪{ek},
else Fk=Fk-1
}
return /Fk è l’insieme degli elementi che costituiscono la soluzione
Raffaele Pesenti
66
67
Esempi:
• problema dello zaino KP(U,s,c,B, max): si ordinano gli oggetti
per densità decrescente c(u)/s(u) e a partire dal primo si prova
ad inserire gli oggetti nello zaino lasciando in esso quelli che vi
possono essere contenuti, e.g.,
max zRL= 12x1 +36 x2 +42 x3 +16 x4 + 25x5
3x1 + 10x2+ 14x3 + 6x4 + 10 x5 ≤ 23
xi ∈{0,1}
(oggetti già ordinati) soluzione greedy x= [1,1,0,1,0]
Raffaele Pesenti
68
Euristiche greedy
Euristiche greedy
Esempi (cont.):
• problema del commesso viaggiatore TSP(G(V,E), c,s,min):
euristica detta del nodo più prossimo (nearest neighbor), si
parte da un nodo qualunque ed ad ogni passo si va al nodo più
vicino non ancora visitato.
Esempio (supponendo distanze euclidee):
Esempi (cont.):
Problema di scheduling 1/ri/ΣCi(U,p,r, min): si eseguono
immediatamente le operazioni disponibili, se più operazioni
sono disponibili si sceglie secondo shortest processing time
first.
Esempio con tre operazioni:
– J1: ri = 0, pi=10
– J2: r2 = 1, p2=1
ΣCi =10+11+13=34
– J3: r3 = 4, pi=2
J1
J2 J3
Commenti:
non funziona molto bene:
i primi archi sono brevi, gli ultimi molto lunghi
nodo iniziale
però gli archi molto lunghi sono pochi:
può essere una buona base da migliorare
semplice da implementare
soluzioni mediamente del 25% superiori al minimo effettivo
troppo lento per più di 10.000 nodi
Raffaele Pesenti
0
69
Metaeuristica RicercaLocale
1. inizializzazione:
si genera una soluzione iniziale ammissibile x0
2. iterazione:
do {
//dove f(xk) è una funzione che,
//data una soluzione ammissibile,
//ne genera una nuova ammissibile non peggiore
} while xk+1 ≠ xk
//esce dal loop quando la condizione è falsa
return
//xk+1 è un ottimo locale
Raffaele Pesenti
Raffaele Pesenti
70
Metauristica ricerca locale
Metaeuristica ricerca locale
xk+1 = f(xk)
10 11 13
71
Commenti:
• in generale si determina solo un ottimo locale, se, come spesso avviene
nei problemi combinatori, vi sono molti ottimi locali, applicando
semplicemente una ricerca locale è molto probabile che venga
determinato un ottimo locale lontano dall’ottimo globale
• la funzione f(xk) deve determinare la soluzione successiva rapidamente,
quindi in genere si limita a valutare le soluzioni ammissibili
appartenenti all’intorno della soluzione corrente xk
• un intorno di x è una funzione che dato x restituisce un insieme di
soluzioni ammissibili I(x) t.c.
– x ∈ I(x) i.e., x appartiene al suo intorno
– ∀x, y ∈ S, ∃{x0, ..., xr} t.c. x= x0, y= xr, e xs∈ I(xs-1) s=1,...,r
i.e., è possibile andare da x a y passando per punti che appartengono
uno all’intorno dell’altro.
Raffaele Pesenti
72
Ricerca locale
2-opt
Esempi:
problema del commesso viaggiatore TSP(G(V,E), c,s,min):
euristica detta 2–opt. Concetto base: ad ogni passo si eliminano
due rami, si ricongiungono i due semicircuiti.
Circuito iniziale
archi da rimuovere
Semicircuiti
Algoritmo 2-opt:
si parte da un circuito hamiltoniano,
si eseguono tutti gli scambi 2–opt
(fra tutte le coppie di rami del circuito)
che riducono la lunghezza.
Efficacia: 8% più del minimo in media
Raffaele Pesenti
Circuito passo 1
nuovi archi
notare l’inversione del verso di
percorrenza di un semicircuito
73
Raffaele Pesenti
archi da rimuovere
74
archi da rimuovere
Circuito passo 1
Circuito passo 2
nuovi archi
Circuito passo 3
nuovi archi
Circuito passo 2
ecc..
Raffaele Pesenti
75
Raffaele Pesenti
76
Ricerca locale
Ricerca locale
Esempi (cont.):
problema del commesso viaggiatore TSP(G(V,E), c,s,min):
euristica detta 3–opt. Concetto base: ad ogni passo si eliminano
tre rami, si ricongiungono i tre semicircuiti.Efficacia: 4% più del
archi da rimuovere
minimo in media.
Si generalizza a k-opt.
Esempi (cont.):
Problema di scheduling 1/ri/ΣCi(U,p,r, min): ad ogni passo si
scambiano di posto due operazioni (anche non necessariamente
adiacenti)
Scheduling iniziale
Circuito iniziale
J1
ΣCi =10+11+13=34
J2 J3
0
10 11 13
Scheduling dopo scambio J1 con J2
J2
Nuovo circuito
Raffaele Pesenti
0 1 2
77
J3
ΣCi =2+12+14=28
12 14
Raffaele Pesenti
78
Simulated annealing
Altre strategie di esplorazione
dell’intorno
• Utilizzando una funzione f(xk) che determina una soluzione
successiva non peggiore (o addirittura che determina la
soluzione successiva ottima tra quelle appartenenti all’intorno)
in generale si rimane intrappolati in un ottimo locale.
• Può allora convenire usare una funzione g(xk) che a volte
determina una soluzione successiva peggiore della precedente
nella speranza di ‘saltare’ fuori dall’ottimo locale. Su questa
filosofia si basano, ad esempio, due metaeuristiche di ricerca
locale:
– simulated annealing
– tabu search
Raffaele Pesenti
J1
79
La simulated annealing è un algoritmo per la soluzione di
problemi combinatori NP-hard basato sulla metafora della
tempratura dei metalli: si raggiunge uno stato di minima energia
non troppo velocemente in modo da evitare che si raggiunga uno
stato finale.
La simulated annealing è una metaeuristica di ricerca locale che
permette passi in cui avvengono dei peggioramenti con probabilità
che decrsce nel tempo.
Il tasso di decremento è definito dal cooling schedule; molto
spesso consiste semplicemente nel fissare un parametro
caratterizzante in un decadimento esponenziale.
Se valgono alcune (deboli) ipotesi sul cooling schedule si può
dimostrare che l’algoritmo converge all’ottimo in probabilità (ma
in
tempi esponenziali).
Raffaele Pesenti
80
Simulated annealing
Simulated annealing
Metaeuristica SimulatedAnnealing(a: parametro di raffreddamento)
1. inizializzazione:
si genera una soluzione iniziale ammissibile x0
Raffaele Pesenti
81
2. iterazione:
do {cambiamento = FALSE
for (i = 0,( i < N) && (cambiamento = FALSE), i++) {
y =g(xk)
∆ = cy - cxk //valutazione della soluzione y generata
if (∆ <0)
{xk+1 = y; cambiamento = TRUE}
else (con probabilità exp(-∆ /t))
{ xk+1 = y; cambiamento = TRUE}
}
t = at
} while cambiamento //esce dal loop quando la condizione è falsa
return
//viene restituita la migliore soluzione xk ottenuta
Raffaele Pesenti
82
Tabù search
Simulated annealing
Tabu search:
Commenti:
Sia la simulated annealing che la tabu search appaiono
promettenti per la risoluzione euristica di problemi difficili quali
quelli di scheduling le cui istanze reali attualmente appaiono di
dimensione troppo grande per essere affrontate con gli algoritmi
esatti disponibili.
Raffaele Pesenti
83
la tabu search è una metaeuristica di ricerca locale che permette passi in cui
avvengono dei peggioramenti con criteri deterministici.
Si definiscono dei criteri di accettazione della soluzione generata a soglia
basati non necessariamente solo sul valore della funzione obiettivo.
Poiché si accettano anche soluzioni che inducono peggioramenti della
funzione obiettivo, per evitare di ritornare su soluzioni già visitate, ad ogni
passo viene aggiornata una lista di operazioni vietate (tabù) che
riporterebbero su soluzioni già visitate.
Raffaele Pesenti
84
Tabù search
Tabù search
Metaeuristica TabuSearch
1. inizializzazione:
si genera una soluzione iniziale ammissibile x0, si pone TabuList = nil, k = 0;
2. iterazione:
do {
[y1, y2, ..., yn] =g(xk)
//genera un insieme di nuove soluzioni alternative
y = h((y1, y2, ..., yn), TabuList,
xk)
//seleziona la migliore alternativa se esiste
if (y = nil) {cambiamento = FALSE}
}
else { xk+1 = y; cambiamento = TRUE, aggiorna(TabuList) }
k= k+1
} while (cambiamento and k < M) //rimane nel loop se si è verificato un cambiamento di
//soluzione e se non si è superato un limite massimo di mosse
return
//viene restituita la migliore soluzione xk ottenuta
Raffaele Pesenti
function h((y1, y2, ..., yn), TabuList, xk)
1. inizializzazione:
z* = ∞, i* = 0, y0= nil;
2. iterazione:
for (i = 1; i <= n; i++) {
if ((yi not in TabuList) or (f(yi) == TRUE) //valuta se yi non è tabù o soddisfa delle “aspirazioni”
//valuta se yi è migliore della soluzione yi* corrente
if (cyi < z*) {z* = cyi, i* = i}
85
return (yi*)
//viene restituita la migliore soluzione yi* ottenuta
Raffaele Pesenti
86
Tabù search
Tabù search
Commenti:
• Sono ovviamente critiche per algoritmi tabù search la definizione delle
funzioni:
– g(xk) che determina un insieme di nuove soluzioni nell’intorno di xk, nei
metodi più semplici tale insieme è generato in modo casuale, nei metodi
più complessi tenendo conto delle statistiche delle soluzioni già visitate e
delle caratteristiche strutturali del problema;
– h((y1, y2, ..., yn), TabuList, xk) che ad ogni iterazione deve determinare la
nuova migliore soluzione;
– f(y) che descrive i criteri di aspirazione ovvero l’insieme di quelle
condizioni che permettono di violare i tabù;
• nello pseudocodice presentato per semplicità concettuale le funzioni g(.) e
h(.) sono presentate separatamente ma in molti algoritmi sono fuse assieme;
• la tabù search viene applicata con discreto successo anche quando alcuni dei
vincoli del problema originale vengono rilassati lagrangianamente. In questo
caso i criteri di aspirazione possono prevedere la soddisfazione dei vincoli.
Commenti (continuazione):
• la TabuList ha una lunghezza massima prefissata (o anche definibile
dinamicamente), una volta raggiunto il limite massimo di mosse tabù (in
generale non più di una decina) un nuovo tabù può essere immesso nella lista
solo dopo averne eliminato uno già presente;
• gli algoritmi più avanzati tengono contemporaneamente conto di più
TabuList contemporaneamente. Possono convivere liste che descrivono una
memoria a breve termine e liste che descrivono una memoria a lungo termine
(che cioè impediscono la generazione di determinate soluzioni per un più
lungo periodo). La memoria a breve termine favorisce una ricerca intensiva
di un intorno di soluzioni, la memoria a lungo termine la diversificazione
delle soluzioni generate, in questo caso le TabuList possono essere usate
anche dalla funzione g(xk). Possono anche convivere liste che tengono conto
di aspetti diversi del problema (e.g., in un problema di scheduling
l’assegnazione e la sequenziazione delle operazioni);
• definire i criteri di aggiornamento delle TabuList è un altro degli aspetti
critici delle euristiche tabù search.
Raffaele Pesenti
Raffaele Pesenti
87
88
Tabù search
Tabù search
archi dell’albero
Esempio*:
Problema - minimo albero ricoprente con vincoli aggiuntivi (side constraints):
data la rete in figura determinare l’albero ricoprente minimo che soddisfi le
seguenti condizioni aggiuntive:
– solo uno tra gli archi a, b, f può essere presente
– l’arco a può essere presente solo se è presente anche l’arco c
a6
c 18
b9
d2
e0
g 12
f8
*tratto dal lavoro di Glover (vedi bibliografia)
a6
d2
89
Tabù search
a6
b9
d2
e0
g 12
f8
a6
d2
f8
Raffaele Pesenti
c 18
b9
c 18
e0
g 12
passo 2: scambio di f con g.
Scambio che induce un peggioramento,
inevitabile data l’ottimalità della soluzione
al passo precedente, z = 32
passo 3: scambio di c con b.
Scambio che viola un tabù, ma che viene
effettuato in quanto induce una soluzione
migliore di quella correntemente ottima.
Nuova soluzione correntemente ottima,
z = 23.
La soluzione corrente è l’ottimo assoluto.
91
a6
d2
f8
Raffaele Pesenti
c 18
e0
g 12
f8
Approccio basato su tabù search
• la scelta dell’intorno è basata su scambio di archi
• il tabù impedisce di scambiare gli
ultimi due archi inseriti
• il criterio di aspirazione permette di violare il
tabù se si ottiene una soluzione migliore di quella
correntemente ottima
• i vincoli possono essere violati pagando una
penalità di 50 per ogni violazione
Raffaele Pesenti
b9
b9
arco escluso dall’albero
tramite scambio
archi tabù dell’albero
passo 0: soluzione generata con algoritmo di Prim
trascurando i vincoli.
Soluzione correntemente ottima,
ma non ammissibile z = 116
c 18
e0
g 12
passo 1: scambio di a con c.
Ottimo locale.
Soluzione correntemente ottima,
z = 28
90