Esercitazione Blocking Job sul Blocking Job Shop Scheduling: Gröflin & Klinkert 2009. 09/06/2011 Ottimizzazione…

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

09/06/2011 Ottimizzazione della Logistica dariano,pacciarelli@dia.uniroma3

1

Esercitazione sul Blocking Job Shop Scheduling:

Grflin & 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 dallordinamento: 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 lordine di esecuzione di x e y sulla stessa macchina.

(x) =lop. che segue x sul suo job se x blocking, es: (B) = C

lop. 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 larco ((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 larco ((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 lazione 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 larco ((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 lordine topologico dopo laggiunta 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 nellordinamento 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 lordine topologico dopo laggiunta 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 posizion