31.8 \(P\,||\,C_{\max}\): move e swap¶
Parte 4 · Algoritmi euristici · Capitolo 31 · Capitolo 31: Ricerca locale · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Ricerca locale · App: TSP: nearest neighbour e 2-opt
- Le mosse di \(P\,||\,C_{\max}\) trasferiscono tempo di lavorazione fra due macchine: una move del lavoro \(j\) dalla macchina \(a\) alla macchina \(b\) trasferisce \(\delta=t_j\) da \(a\) a \(b\); uno swap dei lavori \(j\) (su \(a\)) e \(k\) (su \(b\)) trasferisce \(\delta=t_j-t_k\), che può essere negativo. In entrambi i casi i nuovi carichi sono \(L_a-\delta\) e \(L_b+\delta\), e \(F(L,a,b,\delta)\) indica la variazione risultante dell'obiettivo.
31.8.1 La ricerca locale move¶
La ricerca locale move per \(P\,||\,C_{\max}\) esamina le riassegnazioni di un lavoro a un'altra macchina, ne applica una migliorante scelta con la regola first improvement o best improvement, aggiorna i due carichi coinvolti, e si ferma quando nessuna riassegnazione diminuisce l'obiettivo.
Algoritmo: Passo move per \(P\,||\,C_{\max}\)
31.8.2 La ricerca locale swap¶
La ricerca locale swap per \(P\,||\,C_{\max}\) esamina gli scambi di due lavori su macchine diverse, ne applica uno migliorante scelto con la regola first improvement o best improvement, aggiorna i due carichi coinvolti, e si ferma quando nessuno scambio diminuisce l'obiettivo.
Algoritmo: Passo swap per \(P\,||\,C_{\max}\)
- Per il makespan, la variazione dell'obiettivo è
calcolata in tempo \(O(m)\) dai carichi \(L_1,\dots,L_m\) della soluzione corrente.
-
Una move o uno swap è migliorante se e solo se \(F(L,a,b,\delta)<0\). Poiché cambiano solo \(L_a\) e \(L_b\), il makespan può diminuire solo se \(a\) è l'unica macchina critica: se un'altra macchina ha carico \(C_{\max}\), nessuna mossa fra due macchine può abbassare il makespan.
-
Un'iterazione costa tempo \(O(nm^2)\) per move e \(O(n^2m)\) per swap, a causa della valutazione in \(O(m)\) di \(F\); tenere i carichi ordinati lo riduce, ma qui basta la versione semplice.
-
Una move cambia il numero di lavori su due macchine, uno swap mantiene il numero di lavori su ogni macchina: se una macchina ha troppi lavori, solo una move può correggerlo, e i due intorni si completano a vicenda.
Esempio 31.5: La soluzione di \(LPT\) è un ottimo locale per move, ma non per swap
La soluzione di \(LPT\) sull'istanza di riferimento di \(P\,||\,C_{\max}\) ha \(J_1=\{1,5,7\}\), \(J_2=\{2,6\}\), \(J_3=\{3,4\}\), carichi \((11,8,8)\) e \(C_{\max}=11\). La macchina \(1\) è l'unica macchina critica.
Move. Le \(14\) mosse danno i carichi
| mossa | carichi | \(C_{\max}\) | mossa | carichi | \(C_{\max}\) |
|---|---|---|---|---|---|
| lavoro \(1\): \(M_1\to M_2\) | \((6,13,8)\) | \(13\) | lavoro \(4\): \(M_3\to M_2\) | \((11,12,4)\) | \(12\) |
| lavoro \(1\): \(M_1\to M_3\) | \((6,8,13)\) | \(13\) | lavoro \(5\): \(M_1\to M_2\) | \((8,11,8)\) | \(11\) |
| lavoro \(2\): \(M_2\to M_1\) | \((16,3,8)\) | \(16\) | lavoro \(5\): \(M_1\to M_3\) | \((8,8,11)\) | \(11\) |
| lavoro \(2\): \(M_2\to M_3\) | \((11,3,13)\) | \(13\) | lavoro \(6\): \(M_2\to M_1\) | \((14,5,8)\) | \(14\) |
| lavoro \(3\): \(M_3\to M_1\) | \((15,8,4)\) | \(15\) | lavoro \(6\): \(M_2\to M_3\) | \((11,5,11)\) | \(11\) |
| lavoro \(3\): \(M_3\to M_2\) | \((11,12,4)\) | \(12\) | lavoro \(7\): \(M_1\to M_2\) | \((8,11,8)\) | \(11\) |
| lavoro \(4\): \(M_3\to M_1\) | \((15,8,4)\) | \(15\) | lavoro \(7\): \(M_1\to M_3\) | \((8,8,11)\) | \(11\) |
Nessuna mossa diminuisce il makespan: spostare il lavoro \(1\) via dalla macchina \(1\) porta la macchina ricevente a \(8+5=13\), e spostare il lavoro \(5\) o \(7\) abbassa la macchina \(1\) a \(8\) ma alza la macchina ricevente a \(8+3=11\). La soluzione di \(LPT\) è un ottimo locale per move, con \(C_{\max}=11\).
Swap. Il primo swap esaminato scambia il lavoro \(1\) (su \(M_1\), \(t_1=5\)) e il lavoro \(3\) (su \(M_3\), \(t_3=4\)): \(\delta=1\), i carichi diventano \((10,8,9)\) e \(C_{\max}=10\). È migliorante, e first improvement lo accetta subito; best improvement esamina tutti i \(13\) swap e ne trova altri due con \(C_{\max}=10\) (lavori \(1\) e \(4\), lavori \(1\) e \(6\)), quindi accetta lo stesso swap, il primo trovato. Ora \(J_1=\{3,5,7\}\), \(J_2=\{2,6\}\), \(J_3=\{1,4\}\).
Nella seconda iterazione, lo swap del lavoro \(3\) (su \(M_1\), \(t_3=4\)) e del lavoro \(6\) (su \(M_2\), \(t_6=3\)) ha \(\delta=1\) e dà i carichi \((9,9,9)\): si trova dopo \(9\) valutazioni, ed è l'unico swap con \(C_{\max}<10\), quindi entrambe le regole lo accettano. La nuova soluzione \(J_1=\{5,6,7\}\), \(J_2=\{2,3\}\), \(J_3=\{1,4\}\) ha \(C_{\max}=9=\left\lceil 27/3\right\rceil\): è ottima.
-
In questo esempio l'intorno move si ferma a \(11\), e l'intorno swap raggiunge l'ottimo \(9\). Come osservato per il KP nel capitolo «Algoritmi euristici: definizioni», l'ottimo locale dipende dall'intorno.
-
Un intorno più grande non sempre aiuta. Sull'istanza con \(m=4\) macchine e \(12\) lavori con tempi \(t=(11,10,9,8,7,7,6,5,4,4,3,2)\), il cui makespan ottimo è \(z(I)=19=\lceil 76/4\rceil\), \(LPT\) dà \(J_1=\{1,8,10\}\), \(J_2=\{2,7,11\}\), \(J_3=\{3,6,12\}\), \(J_4=\{4,5,9\}\), con carichi \((20,19,18,19)\): questa soluzione è un ottimo locale sia per move sia per swap.