Esercitazione Blocking Job...

09/06/2011 Ottimizzazione della Logistica dariano,[email protected]

1

Esercitazione sul Blocking Job Shop Scheduling:

Gröflin & Klinkert 2009


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

π

π


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 *


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


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


6


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


7


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


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)


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


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


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


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


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;


14



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’).


15

Procedura G&K09 per generare un vicino ammissibile



3. Implicare gli archi disgiuntivi delle coppie nonancora selezionate come nella soluzione di partenza.


16


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.



3. Implicare gli archi disgiuntivi delle coppie nonancora selezionate come nella soluzione di partenza.


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


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


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).


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 *


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.


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) !!!


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).


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


25

v(E,P): Aggiorniamo l’ordine topologicoIl nuovo ordine topologico si ottiene da quello della soluzione precedente:


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


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


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


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


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


30

v(N,H): Aggiorniamo l’ordine topologicoIl nuovo ordine topologico si ottiene da quello della soluzione precedente:


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


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


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)

Esercitazione Blocking Job...

Documents

Transcript of Esercitazione Blocking Job...