Modelli di sistemi di produzione II
Metaeuristiche:
Rollout eVNS
Ing. Michele Ciavotta
Sommario









Introduzione: complessità e Metaeuristiche
Uno strumento flessibile: Rollout, Rollout
Modificato
Un esempio applicativo : scheduling di macchine
parallele.
Euristiche usate: MJS
Euristiche usate: Delta
VNS
Mosse ed Vicinati proposti
Utilizzo della VNS nell’esempio applicativo
Esercizio: Rollout
2
Introduzione
Analisi complessità
Problemi Facili
Rilassamenti
Problemi Difficili
Algoritmi esatti o
euristici
Algoritmi approssimati
3
Rollout
Il Rollout è un metodo costruttivo cioè
realizza iterativamente una soluzione per il
problema.
 E’ applicabile a quelle classi di problemi la
cui soluzione può essere rappresentata da
una o può sequenze di componenti.
 Un esempio è costituito dai problemi di
scheduling.

4
Rollout






L’idea base della metaeuristica di ROLLOUT è quella di utilizzare q
euristiche costruttive (H1, H2, H3,…., Hq), q≥1, per potenziarne l’effetto
nella costruzione di una buona soluzione.
Una soluzione s = (s1, s2, s3,…, sm-1, sm) viene prodotta in modo
sequenziale, fissando una componente per volta.
Definiamo k-stato (Sk) una soluzione parziale in cui sono state fissate
le prime k componenti: Sk = (s1, s2, s3,…, sk-1, sk), k≤m.
Definiamo Hi(Sk-1 ,sk) il costo della soluzione ottenuta dall’euristica Hi,
applicata a partire dallo stato Sk = (Sk-1 ,sk).
Data una soluzione “parziale” Sk-1, e detto σk l’insieme dei possibili
valori della k-esima componente sk, definiamo:
C(Sk)= min {Hi(Sk-1 ,sk), i=1,..q, sk in σk }
il costo delle sequenze ottenute dalle q euristiche, partendo da Sk-1 e
per ogni possibile scelta della k-esima componente.
Ad ogni iterazione, si fissa la componente sk che ha prodotto il costo
C(Sk), cioè Sk = (Sk-1 ,argmin{C(Sk)}).
5
Rollout
Sia J l’insieme di tutte le componenti e σk l’insieme delle componenti
direttamente schedulabili (non soggette a vincoli di precedenza) e sia H
l’insieme delle euristiche utilizzate dal rollout.
Il rollout può essere schematizzato nel modo seguente:
Per ogni ji appartenente a σk si applicano tutte le euristiche in H sull’insieme J - {ji}.
Si valutano quindi le soluzioni { ji,Hk(J - {ji}) } per ogni k e si aggiunge alla soluzione
parziale ji per cui si ottiene la soluzione migliore.
Si elimina quindi da J tale elemento e si aggiorna σk.
Si prosegue cosi fino a che non rimangono elementi in J.
6
Rollout
S0 = Ø
While(J != Ø)
{
For any ji in σk
{
for(k=0;k<num_eur;k++)
{
sol(i,k) = { ji, Hk(J-{ji})}
}
}
(i’.k’) = arg min {sol(i.k)}
Sp = (Sp-1 , ji’),p++
σk =update(σk , ji’)
J=J\{ji}
}
7
Rollout
H1
H
J12
H1
J3
H2
H1
H2
J1
Hq
H1
J2
J3
H2
Hq
Jn
Jn
J6
Hq
J8
Hq
J4
H1
…
Jp
H1
H2
H2
H1Hq
H1
H2
H2
J4
Hq
H1
H2
Euristica provata
Euristica migliore
Hq
Hq
Hq
8
Rollout Modificato
E’ una versione semplificata del Rollout
che permette di ridurre il tempo di calcolo
complessivo.
 L’idea è di sostituire alla formula

C(Sk)= min {Hi(Sk-1 ,sk), i=1,..q, sk in σk }
 La formula semplificata
C(Sk)= min {Hi(Sk-1), i=1,..q}
9
Rollout Modificato
S0 = Ø
While(Jtot != Ø)
{
for(k=0;k<num_eur;k++)
{
sol(k) = { Hk(Jtot)}
}
k’ = arg min {sol(k)}
Sp = (Sp-1 , {H(k’)0}),p++
Jtot=Jtot\{ji}
}
Primo elemento
della soluzione
Trovata dalla k-esima
euristica
10
Rollout Modificato
S0 = Ø
While(J != Ø)
{
For any ji in σk
{
for(k=0;k<num_eur;k++)
{
sol(i,k) = { ji, Hk(J-{ji})}
}
}
(i’.k’) = arg min {sol(i.k)}
Sp = (Sp-1 , ji’),p++
σk =update(σk , ji’)
J=J\{ji}
}
Complessità
O(n*q)
S0 = Ø
While(Jtot != Ø)
{
for(k=0;k<num_eur;k++)
{
sol(k) = { Hk(Jtot)}
}
k’ = arg min {sol(k)}
Sp = (Sp-1 , {H(k’)0}),p++
Jtot=Jtot\{ji}
}
Complessità
O(n2*q)
11
Rollout Modificato
H51(s)
H41(s)
H11(s)
H61(s)
H31(s)
H21(s)
H52(s)
J4
H42(s)
H12(s)
J2
H22(s)
J1
H13(s)
J3
H32(s)
H22(s)
H32(s)
H42(s)
H43(s)
H33(s)
H62(s)
J5
Jn
H925(s)
Hnq(s)
H53(s)
H53(s)
H23(s)
J9
H13(s)
H63(s)
J6
J8
H63(s)
H81(s)
J7
H5q(s)
H4q(s)
H1q(s)
H6q(s)
H712(s)
Euristica provata
H3q(s)
H2q(s)
Euristica migliore
12
Caso di studio:Dispensa e Counting
Dispensa
Manifattura
Counting
Confezionamento
Uno schedulatore di dettaglio
deve:
• sequenziare i JOB in ogni
Work-Center, assegnando la
relativa tempistica e le risorse
umane
• determinare le date di transito
tra le aree
Nell’abito di studio sono
presenti 4 work-center
ognuno addetto ad un
particolare compito
all’interno della produzione
di farmaci:
•Dispensa
•Manifattura
•Counting
•Confezionamento
13
Caso di studio:Dispensa e Counting
In particolare ci riferiamo ai dipartimenti di
Dispensa e Counting.
 Il dipartimento di Dispensa ha il compito di
rilasciare le varie quantità di prodotti chimici
che andranno a costituire i farmaci.
 Il dipartimento di Counting ha il compito di
rilasciare i materiali di assemblaggio utilizzati
dal dipartimento di Confezionamento.
14
Caso di studio:Dispensa e Counting





Il dipartimento di Dispensa è costituito da 2 macchine
parallele identiche gestite da turni di operai specializzati.
Tali turni implicano delle indisponibilità programmate con
incidenza giornaliera e settimanale.
Lo stesso discorso vale anche per il dipartimento di
Counting, costituito però da 3 macchine parallele.
Entrambi i dipartimenti processano job caratterizzati da
un tempo di rilascio e da una duedate o deadline.
Il dipartimento di dispensa è costretto a pagare un setup
ogni volta vi è un cambio di tipo di job in processamento.
In tale dipartimento sono anche previste dimensioni
massime per le campagne di produzione
15
Indici di prestazione
Massima
Lateness
Lmax  max L1 ,..., Ln 
ove
Makespan
Li  Ci  d i
Cmax  max C1 ,..., Cn 
16
Modello (α|β|γ)
di Lawler-Graham
 Per
classificare
i
problemi
di
schedulazione abbiamo usato la codifica
a tre campi (α|β|γ) di Lawler-Graham.
Configurazione delle macchine
Presenza di eventuali vincoli da rispettare
Misure di prestazione
17
Esempio applicativo:
il Modello (α|β|γ)











Campo α:
Macchine Parallele Identiche (Pm)
Campo β:
Release time (ri)
Due-date (di)
Deadline (Di)
Set-up: C_Min (si può considerare inglobato al tempo di processo) e
C_Maj
Preemption non ammessa
Possibilità di indisponibilità di macchine.
Limite sul Max numero di OP per campagna: dipende da OP
Campo γ:
Si individua Lmax come principale funzione obiettivo da minimizzare
Secondarie funzioni obiettivo sono Cmax ed il numero di Tardy Job
Si utilizza un approccio multiobiettivo di tipo lessicografico.
18
Caso di Studio
Come detto il rollout è un algoritmo costruttivo, ovvero un algoritmo che, se
applicato allo scheduling, costruisce una schedula aggiungendo un job
alla volta, seguendo un insieme di regole che si propongono di
salvaguardare l’ammissibilità e la qualità della soluzione.
Ammissibilità:

un job è schedulabile dopo il suo rilascio

nessun job è schedulabile su una macchina indisponibile

una macchina può processare un solo job alla volta

un job è schedulabile su una macchina in grado (per tipologia,
attrezzaggio e disponibilità) di eseguire le operazioni richieste da esso.
Qualità

di seguire una sequenza di lavorazione specifica (es. earliest due date
(EDD) per minimizzare Lmax);

di seguire una particolare sottosequenza o successione di job per
19
ridurre i tempi di setup (migliorando Cmax).
Euristiche usate nel Rollout
TL : istante di tempo al quale si libera la prima macchina.
RJD: insieme dei job rilasciati al tempo TL con deadline
RJd: insieme dei job rilasciati al tempo TL senza deadline
RJ: insieme totale dei job rilasciati al tempo TL
(RJ =RJD U RJd)
ML: insieme delle macchine libere al tempo TL
20
Euristiche usate nel Rollout:
Modified Jackson Schedule
Modified Jackson Schedule (MJS)
Input: un insieme P di ordini di produzione;
t = min{ri : i in P}, S = Ø;
While (P != Ø){
R = {i in P : ri ≤ t}
if (c’è un job in R con deadline){
scegli un job j in R con la più piccola deadline}
else if (c’è un job in R con duedate){
scegli un job j in R con la più piccola duedate}
else {t = min{ri : i in P}, R = {i in P : ri ≤ t} }
if (un job è stato selezionato) {
assegno j alla macchina che può completarlo per
primo,tenendo in conto i setup, le campagne e la
disponibilità della macchina
S = S U {j}, P = P \ {j}
aggiorna t al più piccolo completion time di tutte le
macchine disponibili}
}
21
Euristiche usate nel Rollout:
Delta
Schedulare i job di RJ secondo le seguenti regole:
Step 1. ordinare RJ per duedate crescenti;
Step 2. individuare i sottoinsiemi di job di RJ con duedate compresa tra d
e d+ e aggiornare d
Step 3. ordinare RJ per Deadline crescenti;
Step 4. Per ciascun job di RJD, scegliere la macchina presente in ML il cui
ultimo job schedulato è della stessa tipologia del job considerato,
altrimenti schedulare il job sull’ultima macchina dell’insieme ML,
aggiornare RJ e ML e reiterare il passo 4 finchè min{ # RJD, # ML}=0;
Step 5. Per ciascun job di RJd, scegliere la macchina presente in ML il cui
ultimo job schedulato è della stessa tipologia del job considerato,
altrimenti schedulare il job sull’ultima macchina dell’insieme ML,
aggiornare RJ e ML e reiterare il passo 5 finchè min{ n RJd, n ML }=0;
Step 6. vengono quindi aggiornati TL, RJD, RJd e ML e la procedura viene
reiterata dal passo 4 finché non sono stati schedulati tutti i job.
22
Euristiche usate nel Rollout:
Delta




L’insieme delle due date dei job rilasciati all’istante TL viene diviso in
intervalli di ampiezza .
Ad ogni job viene assegnata una nuova due date “fittizia”, il cui valore
è un multiplo di , a seconda dell’intervallo in cui cade.
Tale procedimento consente di creare famiglie di job con due date
coincidenti per le quali sono meglio gestibili i tempi di setup (ad
esempio formando delle campagne).
Ogni euristica è caratterizzata da un diverso valore di .

d1
d2
d3
d4
d5
d6 d7
d8
d2
t
 grande

d1
dn
d3
d4
d5
d6
d7
d8
d23
n
t
Variable Neighborhood Search

La VNS è un algoritmo che applica strategie
di ricerca locale per individuare
miglioramenti alle soluzioni ottenute nel
primo livello.

La ricerca viene effettuata su opportuni
intorni adoperando adeguate “mosse”.
24
Variable Neighborhood Search
VNS:
Algoritmo di ricerca
locale che si basa
su vicinati sempre
più ampi.
Ogni volta viene
individuata una
soluzione migliore
rispetto a quella
candidata
l’algoritmo riprende
l’esplorazione a
partire dal vicinato
più piccolo.
N1
N2
N3
25
Variable Neighborhood Search
N1
N2
N3
26
Mosse Proposte
Mosse per la ricerca locale sulla sequenza delle
singole macchine
SHIFT
J1
Jk-1
Jk
MOVE
J1
Jk-1
Jk
Jk+m
Jn
SWAP
J1
Jk-1
Jk
Jk+m
Jn
Jk+1
Jn
27
Mosse
Mosse per la ricerca locale sull’assegnazione
alle macchine
J1
Jk-1
Jk
Jk+1
Jn
Macchina A
J1
Js-1
Js
Js+1
Jn
Macchina B
M-MOVE
J1
Jk-1
Jk
Jk+1
Jn
Macchina A
J1
Js-1
Js
Js+1
Jn
Macchina B
M-SWAP
28
Esempio Applicativo: VNS





Variable Neighborhood
Search (VNS)
Data una soluzione iniziale
begin
do
La metaeuristica opera in 3 intorni {cerca una mossa migliorante in N1
di ricerca N1, N2 ed N3 associati if mossa trovata then applica la mossa in N1
a tre diverse “mosse” applicabili. else
begin
L’euristica compie
{ cerca una mossa migliorante in N2
un’esplorazione dell’intorno, se
if mossa trovata then applica la mossa in N2
trova una mossa che migliora la
else
soluzione esegue nuovamente la
begin
ricerca altrimenti passa all’intorno
{ cerca una mossa migliorante in N3
successivo.
if mossa trovata then applica la mossa in N3
Ogni volta che viene trovata una
end }
mossa “migliorante” si riparte
end }
dall’esplorazione dell’intorno N1.
La procedura termina quando non }
while una mossa viene eseguita
vengono più trovate mosse
end
“miglioranti”.
29
Vicinati Di Ricerca
Mosse di ricerca locale implementate

Primo intorno di ricerca (N1)
Si applica la mossa SHIFT solo per spostare un JOB di un posto
indietro in una data sequenza. E’ applicata ai JOB in ordine
decrescente di Lateness.

Secondo intorno di ricerca (N2)
Si applica lal mossa MOVE ai JOB che violano le deadline (in ordine
decrescente) scegliendo il parametro m in modo da anticipare il
JOB alla prima posizione utile affinché rispetti il suo tempo di
consegna.

Terzo intorno di ricerca (N3)
Si applica la mossa SHIFT 2 per spostare un JOB di un posto in
avanti nella schedula, ritardandone quindi l’esecuzione.
30
Esercizio: Rollout
Applicheremo
l’algoritmo del rollout
su una istanza
caratterizzata dalla
presenza di una
macchina singola e
da relazioni di
precedenza tra i job.
Funzione obiettivo: ΣwiTi
2
1
3
4
5
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
31
Esercizio: Rollout
Useremo per il rollout due semplici
euristiche :
 EDD : Erliest DueDate (H1)
 SPT : Shortest Processing Time (H2)
32
Esercizio: Rollout
Al primo passo del rollout
σ1={1,5} quindi
il primo elemento proposto
sarà 1.

H1(2,3,4,5)= 5, 2, 3, 4 -> 1,
5, 2, 3, 4
H2(2,3,4,5)= 2, 5, 3, 4 ->1,
2, 5, 3, 4
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
1
5
2
3
4
tot
c.T
4
6
7
10
14
14
wt
0
2
0
0
12
14
Job
1
2
5
3
4
tot
c.T
4
5
7
10
14
14
wt
0
0
3
0
12
15
33
Esercizio: Rollout
Al primo passo del rollout
σ1={1,5} quindi
il secondo elemento
proposto sarà 5.

H1(1,2,3,4)= 1, 2, 3, 4 -> 5,
1, 2, 3, 4
H2(1,2,3,4)= 1, 2, 3, 4 ->5,
1, 2, 3, 4
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
5
1
2
3
4
tot
c.T
2
6
7
10
14
14
wt
0
3
0
0
12
15
Job
5
1
2
3
4
tot
c.T
2
6
7
10
14
14
wt
0
3
0
0
12
15
34
Esercizio: Rollout
Al primo passo del rollout
si fissa 1, al secondo
σ2={2,3,5} quindi
il primo elemento proposto
sarà 2.
H1(3,4,5)=5, 3, 4 -> 1, 2, 5,
3, 4

H2(3,4,5)= 5, 3, 4 ->1, 2, 5,
3, 4
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
1
2
5
3
4
tot
c.T
4
5
7
10
14
14
wt
0
0
3
0
12
15
Job
1
2
5
3
4
tot
c.T
4
5
7
10
14
14
wt
0
0
3
0
12
15
35
Esercizio: Rollout
Al primo passo del rollout
si fissa 1, al secondo
σ2={2,3,5} quindi
il secondo elemento
proposto sarà 3.
H1(2,4,5)=5, 2, 4 -> 1, 3, 5,
2, 4

H2(2,4,5)= 2, 5, 4 ->1, 3, 2,
5, 4
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
1
3
5
2
4
tot
c.T
4
7
9
10
14
14
wt
0
0
5
0
12
17
Job
1
3
2
5
4
tot
c.T
4
7
8
10
14
14
wt
0
0
0
6
12
18
36
Esercizio: Rollout
Al primo passo del rollout
si fissa 1, al secondo
σ2={2,3,5} quindi
il terzo elemento proposto
sarà 5.
H1(2,3,4)=2, 3, 4 -> 1, 5, 2,
3, 4

H2(2,3,4)= 2, 3, 4 ->1, 5, 2,
3, 4
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
1
5
2
3
4
tot
c.T
4
6
7
10
14
14
wt
0
2
0
0
12
14
Job
1
5
2
3
4
tot
c.T
4
7
8
10
14
14
wt
0
2
0
0
12
14
37
Esercizio: Rollout
Al secondo passo del
rollout si fissa 5, al terzo
σ3={2,3} quindi
il primo elemento proposto
sarà 2.
H1(3,4)= 3, 4 -> 1, 5, 2, 3, 4

H2(3,4)= 3, 4 -> 1, 5, 2, 3, 4
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
1
5
2
3
4
tot
c.T
4
6
7
10
14
14
wt
0
2
0
0
12
14
Job
1
5
2
3
4
tot
c.T
4
7
8
10
14
14
wt
0
2
0
0
12
14
38
Esercizio: Rollout
Al secondo passo del
rollout si fissa 5, al terzo
σ3={2,3} quindi
il secondo elemento
proposto sarà 3.
H1(2,4)= 2, 4 -> 1, 5, 3, 2, 4

H2(2,4)= 2, 4 -> 1, 5, 3, 2, 4
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
1
5
3
2
4
tot
c.T
4
6
9
10
14
14
wt
0
2
0
0
12
14
Job
1
5
3
2
4
tot
c.T
4
6
9
10
14
14
wt
0
2
0
0
12
14
39
Esercizio: Rollout
Al terzo passo del rollout
si fissa 3, al terzo
σ3={2,4} quindi
il primo elemento proposto
sarà 2.
H1(4)= 4 -> 1, 5, 3, 2, 4

H2(4)= 4 -> 1, 5, 3, 2, 4
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
1
5
3
2
4
tot
c.T
4
6
9
10
14
14
wt
0
2
0
0
12
14
Job
1
5
3
2
4
tot
c.T
4
6
9
10
14
14
wt
0
2
0
0
12
14
40
Esercizio: Rollout
Al terzo passo del rollout
si fissa 3, al terzo
σ3={2,4} quindi
il secondo elemento
proposto sarà 4.
H1(2)= 2 -> 1, 5, 3, 4, 2

H2(2)= 2 -> 1, 5, 3, 4, 2
Ji
pi
di
wi
1
4
5
3
2
1
10
2
3
3
11
1
4
4
11
4
5
2
4
1
Job
1
5
3
4
2
tot
c.T
4
6
9
13
14
14
wt
0
2
0
8
8
18
Job
1
5
3
4
2
tot
c.T
4
6
9
13
14
14
wt
0
2
0
8
8
18
41
Esercizio: Rollout
Al quarto passo del rollout si fissa 2, e
quindi 4
 La soluzione finale sarà:
1,5,3,2,4 con funzione obiettivo pari a 14

42