Post on 14-Feb-2019
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
1
Esercitazione sul Blocking Job Shop Scheduling:
Gröflin & Klinkert 2009
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
2
Descrizione del problema di scheduling blockingSono dati 4 jobs da eseguire su 5 macchine blockingM1, M2, M3, M4, M5, descritti nel formato OPERAZIONE (MACCHINA, DURATA):J1: A (M1, 10) B (M2, 10) C (M3, 6) D (M4, 1) J2: E (M2, 12) F (M5, 3) G (M1, 1) H (M3, 10) J3: I (M4, 12) L (M2, 15) M (M1, 6) N (M3, 10) J4: O (M4, 2) P (M2, 4) Q (M3, 18) R (M1, 5)
La soluzione iniziale è data dall’ordinamento: 0 A B C O E F P I L D Q M R N G H *dove “0” e “*” sono le operazioni fittizie start e finish
Studiamo la soluzione e cerchiamo mosse migliorative
π
π
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
3
Costruiamo il grafo disgiuntivo per il problema datoJ1: A (M 1, 10) B (M 2, 10) C (M 3, 6) D (M 4, 1) J2: E (M 2, 12) F (M 5, 3) G (M 1, 1) H (M 3, 10) J3: I (M 4, 12) L (M 2, 15) M (M 1, 6) N (M 3, 10) J4: O (M 4, 2) P (M 2, 4) Q (M 3, 18) R (M 1, 5)
A B C D
E F G H
I L M N
O P Q R
0 *
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
4
Soluzione iniziale sulla macchina M1J1: A (M 1, 10) B (M 2, 10) C (M 3, 6) D (M 4, 1) J2: E (M 2, 12) F (M 5, 3) G (M 1, 1) H (M 3, 10) J3: I (M 4, 12) L (M 2, 15) M (M 1, 6) N (M 3, 10) J4: O (M 4, 2) P (M 2, 4) Q (M 3, 18) R (M 1, 5)
A B C D
E F G H
I L M N
O P Q R
0 *5
πSu M1:6 coppie dis.Quindi vanno selezionati6 archi dis.(ma 3 sono ridondanti) 0
0
00
0
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
5
Soluzione iniziale sulla macchina M2J1: A (M 1, 10) B (M 2, 10) C (M 3, 6) D (M 4, 1) J2: E (M 2, 12) F (M 5, 3) G (M 1, 1) H (M 3, 10) J3: I (M 4, 12) L (M 2, 15) M (M 1, 6) N (M 3, 10) J4: O (M 4, 2) P (M 2, 4) Q (M 3, 18) R (M 1, 5)
A B C D
E F G H
I L M N
O P Q R
0 *
πSu M2:6 coppie dis.Quindi vanno selezionati6 archi dis.(ma 3 sono ridondanti) 0
0
0
0 0
0
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
6
Soluzione iniziale sulla macchina M3J1: A (M 1, 10) B (M 2, 10) C (M 3, 6) D (M 4, 1) J2: E (M 2, 12) F (M 5, 3) G (M 1, 1) H (M 3, 10) J3: I (M 4, 12) L (M 2, 15) M (M 1, 6) N (M 3, 10) J4: O (M 4, 2) P (M 2, 4) Q (M 3, 18) R (M 1, 5)
A B C D
E F G H
I L M N
O P Q R
0 *10
πSu M3:6 coppie dis.Quindi vanno selezionati6 archi dis.(ma 3 sono ridondanti)
0
0 0
00
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
7
Soluzione iniziale sulla macchina M4J1: A (M 1, 10) B (M 2, 10) C (M 3, 6) D (M 4, 1) J2: E (M 2, 12) F (M 5, 3) G (M 1, 1) H (M 3, 10) J3: I (M 4, 12) L (M 2, 15) M (M 1, 6) N (M 3, 10) J4: O (M 4, 2) P (M 2, 4) Q (M 3, 18) R (M 1, 5)
A B C D
E F G H
I L M N
O P Q R
0 *
πSu M4:3 coppie dis.Quindi vanno selezionati3 archi dis.(ma 1 èridondante)
00
0
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
8
Soluzione iniziale su tutte le macchineJ1: A (M 1, 10) B (M 2, 10) C (M 3, 6) D (M 4, 1) J2: E (M 2, 12) F (M 5, 3) G (M 1, 1) H (M 3, 10) J3: I (M 4, 12) L (M 2, 15) M (M 1, 6) N (M 3, 10) J4: O (M 4, 2) P (M 2, 4) Q (M 3, 18) R (M 1, 5)
A B C D
E F G H
I L M N
O P Q R
0 *10
5
πIn totale:21 coppie dis.Quindi vanno selezionati21 archi dis.(ma 10 sono ridondanti)
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
9
Soluzione iniziale è ammissibile? D,H,N ed R non sono operazioni blocking e quindi gli archi di precedenza (N,H) e (R,G) sono pesati con le durate delle operazioni in coda (N e R), tutti gli altri archi tratteggiati hanno peso 0. Il grafo ha due cicli di peso nullo (ovvero DQL e NR). La soluzione data è quindi ammissibile perché nonci sono cicli di peso positivo.
π
A B C D
E F G H
I L M N
O P Q R
0 *10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
10
Soluzione : Teste, code e cammino critico πOper. 0 A B C O E F P I L D Q M R N G H *P. T. - 10 10 6 2 12 3 4 12 15 1 18 6 5 10 1 10 -Teste 0 0 10 20 0 20 32 32 32 44 44 44 59 65 65 70 75 85Code 85 75 65 59 53 53 50 49 41 26 40 23 20 15 10 10 0 0
A B C D
E F G H
I L M N
O P Q R
0 *10
5
N.B. Calcolo teste e code => peso archi disgiuntivi => blocking = 0; ideal = process. nodo coda
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
11
Soluzione : Cammino critico, blocchi e mosseπ
A B C D
E F G H
I L M N
O P Q R
0 *10
5
Cammino critico 0ABCEFPILMNH*Blocchi: BEP; NHMosse ammissibili: v(B,E), v(E,P), v(N,H)N.B. Tutte le mosse ammissibili sono potenzialmente migliorative
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
12
Mossa per il JSS con macchine ideal e blockingDefiniamo v(x,y) la mossa di invertire l’ordine di esecuzione di x e y sulla stessa macchina.
σ(x) =l’op. che segue x sul suo job se x è blocking, es: σ(B) = C
l’op. x stessa se x non è blocking, es: σ(D) = D
A B C D
E F G H
I L M N
O P Q R
0 *10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
13
Procedura per generare vicino ammissibile (G&K09)
La mossav(x,y) richiede di:1. Rimuovere tuttigli altri archi disgiuntivi incidenti (entranti o uscenti) ogni operazione del job di x e lasciare invariati gli altri jobs;
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
14
Procedura per generare vicino ammissibile (G&K09)
La mossav(x,y) richiede di:1. Rimuovere tuttigli altri archi disgiuntivi incidenti (entranti o uscenti) ogni operazione del job di x e lasciare invariati gli altri jobs;
2. Sostituire l’arco (σ(x),y) (arco rimosso) con (σ(y),x) (arco compagno) e selezionare tutti gli archi disgiuntivi delle coppie non selezionate che sono ‘implicati’ da (σ(y),x) cioè gli archi (σ(i),j) con j operazione appartenente allo stesso job di x e tali che (σ(j),i) causerebbe un ciclo a peso positivo nel grafo (azione di ‘feasibility recovery’).
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
15
Procedura G&K09 per generare un vicino ammissibile
La mossav(x,y) richiede di:1. Rimuovere tuttigli altri archi disgiuntivi incidenti (entranti o uscenti) ogni operazione del job di x e lasciare invariati gli altri jobs;
2. Sostituire l’arco (σ(x),y) (arco rimosso) con (σ(y),x) (arco compagno) e selezionare tutti gli archi disgiuntivi delle coppie non selezionate che sono ‘implicati’ da (σ(y),x) cioè gli archi (σ(i),j) con j operazione appartenente allo stesso job di x e tali che (σ(j),i) causerebbe un ciclo a peso positivo nel grafo (azione di ‘feasibility recovery’).
3. Implicare gli archi disgiuntivi delle coppie nonancora selezionate come nella soluzione di partenza.
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
16
Procedura per generare vicino ammissibile (G&K09)
NB: Se lo swap di (σ(x),y) con (σ(y),x) nonintroduce cicli positivi, allora non è necessario eseguire l’azione di feasibility recovery, ovverotutti gli altri archi disg. si selezionano come nella soluzione di partenza.
La mossav(x,y) richiede di:1. Rimuovere tuttigli altri archi disgiuntivi incidenti (entranti o uscenti) ogni operazione del job di x e lasciare invariati gli altri jobs;
2. Sostituire l’arco (σ(x),y) (arco rimosso) con (σ(y),x) (arco compagno) e selezionare tutti gli archi disgiuntivi delle coppie non selezionate che sono ‘implicati’ da (σ(y),x) cioè gli archi (σ(i),j) con j operazione appartenente allo stesso job di x e tali che (σ(j),i) causerebbe un ciclo a peso positivo nel grafo (azione di ‘feasibility recovery’).
3. Implicare gli archi disgiuntivi delle coppie nonancora selezionate come nella soluzione di partenza.
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
17
Valutazione del vicino (G&K09)
Una volta effettuata la mossa v(x,y) ed aver generato un vicino ammissibile secondo la procedura di G&K09, procediamo con il calcolo esatto del makespancome segue:1. Si aggiorna l’ordine topologico dopo l’aggiunta di (σ(y),x) e degli altri archi implicati 2. Si aggiornano le teste delle operazioni (da sinistra a destra) a partire dalla prima op. che ha cambiato posizione nell’ordinamento topologico3. La testa del nodo * ci fornisce il valore del nuovo makespan
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
18
Valutazione del vicino (G&K09)
Una volta effettuata la mossa v(x,y) ed aver generato un vicino ammissibile secondo la procedura di G&K09, procediamo con il calcolo esatto del makespancome segue:1. Si aggiorna l’ordine topologico dopo l’aggiunta di (σ(y),x) e degli altri archi implicati 2. Si aggiornano le teste delle operazioni (da sinistra a destra) a partire dalla prima op. che ha cambiato posizione nell’ordinamento topologico3. La testa del nodo * ci fornisce il valore del nuovo makespan
N.B. Per calcolare il cammino critico bisogna aggiornare anche le codedelle operazioni (da destra a sinistra) a partire dalla prima op. che ha cambiato posizione nell’ordinamento topologico. Le operazioni sul cammino critico hanno la massima somma di testa + proc. time + coda
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
19
Applichiamo la mossa v(x,y) con x = B ed y = E
A B C D
E F G H
I L M N
O P Q R
0 *10
5
Mossa v(B,E): Sostituiamo arco (σ(B),E) con arco (σ(E),B), ovvero (C,E) con (F,B)⇒ Effettuata quest’operazione ‘swap’ non si genera alcun ciclo a peso positivo ⇒ Tutti gli altri archi disg. restano selezionati come nella soluzione di partenza
N.B. Nel grafo disgiuntivo che segue sono rappresentati solo gli archi non ridondanti della soluzione, (solo apparentemente) è stato rimosso (F,P) ed aggiunto (C,P).
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
20
v(B,E): Aggiorniamo l’ordine topologico
A B C D
E F G H
I L M N
O P Q R
0 *10
5
Il nuovo ordine topologico si ottiene da quello della soluzione precedente:
0 A B C O E F P I L D Q M R N G H *
aggiungendo il nuovo arco (F,B) e aggiornando l’ordine di quelli compresi tra la posizione di F e la posizione di B (C,O,E). In particolare B e i suoi successori (solo C) si spostano dopo F. Il nuovo ordine topologico è0 A O E F B C P I L D Q M R N G H *
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
21
v(B,E): Aggiorniamo le teste per calcolare Cmax
A B C D
E F G H
I L M N
O P Q R
0 *10
5
Oper. 0 A O E F B C P I L D Q M R N G H *P. T. - 10 2 12 3 10 6 4 12 15 1 18 6 5 10 1 10 -Teste 0 0 0 0 12 12 22 22 22 34 34 34 49 55 55 55 65 75
N.B. Nell’ordinamento topologico, i cicli nulli LDQ e RN sono considerati come singoli nodi.
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
22
Continuiamo lo studio del vicinato: Mossa v(E,P)Mossa v(E,P): Sostituiamo arco (σ(E),P) con arco (σ(P),E), ovvero (F,P) con (Q,E)⇒ Effettuata quest’operazione ‘swap’ si introduce il ciclo a peso positivo QEFLDQ⇒ Dobbiamo eseguire la procedura G&K2009 per generare un vicino ammissibile:
A B C D
E F G H
I L M N
O P Q R
0 *10
5
1. Si rimuovono tuttigli altri archi incidenti il secondo job (perchéx = E): (F,L), (R,G), (N,H) e (C,E), (B,G), (N,G), (D,H), (Q,H) [in aggiunta ad (F,P)].
N.B. Vanno rimossi anche tutti gli archi ridondanti (non in figura) !!!
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
23
Continuiamo lo studio del vicinato: Mossa v(E,P)
A B C D
E F G H
I L M N
O P Q R
0 *
2. Si aggiunge (Q,E)e si provano uno alla volta tutti gli archi rimossi per vedere se introducono cicli positivi. Se si, viene selezionato l’arco disgiuntivo compagno, se no l’arco in esame NON viene aggiunto in questa fase. Nello specifico si ha che (C,E), (R,G) e (N,H) non introducono cicli positivi, mentre (F,L) introduce il ciclo FLDQEF, quindi viene implicato (M,E), l’arco disgiuntivo compagno di (F,L). Dopo la selezione dell’arco (M,E), non ci sono più cicli positivi. (B,G), (N,G), (D,H), (Q,H) non introducono cicli e neanche gli archi testati in precedenza, ovvero (C,E), (R,G) e (N,H).
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
24
Continuiamo lo studio del vicinato: Mossa v(E,P)
3. Gli archi che non introducono cicli a peso positivo vengono selezionati come nellasoluzione di partenza, ovvero (B,G), (N,G), (D,H), (N,H), (C,E), (R,G) e (Q,H).
Nella figura è mostrata la nuova soluzione, sempre omettendo gli archi ridondanti.
A B C D
E F G H
I L M N
O P Q R
0*10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
25
v(E,P): Aggiorniamo l’ordine topologicoIl nuovo ordine topologico si ottiene da quello della soluzione precedente:
0 A B C O E F P I L D Q M R N G H *
aggiungendo i nuovi archi (Q,E) e (M,E) ed aggiornando l’ordine di quelli compresi tra la posizione di E e la posizione di Q e M. In particolare E e i suoi successori (solo F) si spostano dopo M. Il nuovo ordine topologico è0 A B C O P I L D Q M E F R N G H *
A B C D
E F G H
I L M N
O P Q R
0 *10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
26
v(E,P): Aggiorniamo le teste per calcolare Cmax
Oper. 0 A B C O P I L D Q M E F R N G H *P. T. - 10 10 6 2 4 12 15 1 18 6 12 3 5 10 1 10 -Teste 0 0 10 20 0 20 20 32 32 32 47 47 59 53 53 62 63 73
OSS: Nel nuovo cammino critico non troveremo l’arco disgiuntivo aggiunto (Q,E), che è addirittura ridondante, ma un arco da questi implicato: l’arco (M,E).
A B C D
E F G H
I L M N
O P Q R
0 *10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
27
Completiamo lo studio del vicinato: Mossa v(N,H)Mossa v(N,H): Sostituiamo (σ(N),H) con (σ(H),N), ovvero (N,H) con (H,N)⇒ Effettuata quest’operazione ‘swap’ si introduce il ciclo a peso positivo HNRGH⇒ Dobbiamo eseguire la procedura G&K2009 per generare un vicino ammissibile:
1. Si rimuovono tuttigli altri archi incidenti il terzo job (perchéx = N): (P,I), (L,D), (Q,L), (B,M), (N,R) e (F,L), (C,L), (D,N), (R,N), (N,G) [in aggiunta ad (N,H)]. N.B. Vanno rimossi anche tutti gli archi ridondanti (non in figura) !!!
A B C D
E F G H
I L M N
O P Q R
0 *10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
28
Completiamo lo studio del vicinato: Mossa v(N,H)2. Si aggiunge (H,N)e si provano uno alla volta tutti gli archi rimossi per vedere se introducono cicli positivi. Se si, viene selezionato l’arco disgiuntivo compagno, se no l’arco in esame NON viene aggiunto in questa fase. Nello specifico si ha che (P,I), (L,D), (Q,L), (B,M) non introducono cicli positivi, mentre (N,R) introduce il ciclo NRGHN, quindi viene implicato (R,M).(F,L), (C,L), (D,N), (R,N) non introducono cicli positivi, mentre (N,G) introduce il ciclo NGHN, quindi viene implicato (H,M).
A B C D
E F G H
I L M N
O P Q R
0 *10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
29
Completiamo lo studio del vicinato: Mossa v(N,H)
3. Gli archi che non introducono cicli a peso positivo vengono selezionati come nellasoluzione iniziale, ovvero (P,I), (L,D), (Q,L), (B,M), (F,L), (C,L), (D,N) e (R,N). Nella figura è mostrata la nuova soluzione, sempre omettendo gli archi ridondanti.
A B C D
E F G H
I L M N
O P Q R
0 *10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
30
v(N,H): Aggiorniamo l’ordine topologicoIl nuovo ordine topologico si ottiene da quello della soluzione precedente:
0 A B C O E F P I L D Q M R N G H *
aggiungendo i nuovi archi (H,N), (R,M) e (H,M) ed aggiornando l’ordine tra Q e *.N.B. Non c’è più il ciclo nullo RN, quindi va aggiornato l’ordine dei nodi R e N. Il nuovo ordine topologico è 0 A B C O E F P I L D Q R G H M N *
A B C D
E F G H
I L M N
O P Q R
0 *10
5
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
31
v(N,H): Aggiorniamo le teste per calcolare Cmax
A B C D
E F G H
I L M N
O P Q R
0 *10
5
Oper. 0 A B C O E F P I L D Q R G H M N *P. T. - 10 10 6 2 12 3 4 12 15 1 18 5 1 10 6 10 -Teste 0 0 10 20 0 20 32 32 32 44 44 44 62 62 62 62 68 78
09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3
32
La mossa migliore secondo GK09 è quindiv(E,P)
Oper. 0 A B C O P I L D Q M E F R N G H *P. T. - 10 10 6 2 4 12 15 1 18 6 12 3 5 10 1 10 -Teste 0 0 10 20 0 20 20 32 32 32 47 47 59 50 50 62 63 73Code 73 63 53 47 53 49 41 26 40 23 20 14 11 15 10 10 0 0
A B C D
E F G H
I L M N
O P Q R
0 *10
5
Cammino critico: 0ABCPILMEFGH* (N.B. Anche D e Q sono critiche)