30.6 Scheduling su macchine parallele: prima i lavori più lunghi¶
Parte 4 · Algoritmi euristici · Capitolo 30 · Capitolo 30: Euristiche costruttive · Dispensa, volume 4 (PDF) · Slide (1/2) · Slide (2/2) · Esercizi: Euristiche costruttive · App: Euristiche per il bin packing · App: List scheduling e LPT · App: Colorazione: greedy e DSATUR · App: TSP: nearest neighbour e 2-opt
- Per \(P\,||\,C_{\max}\) gli elementi sono gli assegnamenti dei lavori alle macchine, e ogni assegnamento è ammissibile. Una regola greedy naturale assegna ogni lavoro alla macchina che in quel momento è la meno carica, così che i carichi crescano nel modo più uniforme possibile. Come per il BPP, la regola sceglie la macchina, e l'ordine dei lavori è una seconda scelta, indipendente.
30.6.1 List scheduling¶
Il List Scheduling Algorithm (indicato con \(LIST\)) è un'euristica costruttiva per \(P\,||\,C_{\max}\). Esamina i lavori nell'ordine di una lista data \(\rho\) e assegna ogni lavoro a una macchina con il carico corrente minimo (in caso di pareggio, la macchina con l'indice minimo).
Algoritmo: List Scheduling
-
\(LIST\) è il corrispondente, nello scheduling, di una regola online: non ha bisogno di conoscere i lavori futuri, e si usa, per esempio, quando i lavori arrivano uno alla volta. Con una scansione lineare delle macchine richiede tempo \(O(nm)\), e tempo \(O(n\log m)\) con un heap dei carichi.
-
Nell'istanza di riferimento, \(t=(5,5,4,4,3,3,3)\), i lavori sono elencati per tempo di esecuzione non crescente, che è un ordine favorevole. Per vedere l'effetto dell'ordine, l'esempio esamina gli stessi lavori nella lista inversa.
Esempio 30.5: \(LIST\) sull'istanza di riferimento, prima i lavori più brevi
Consideriamo la lista \(\rho=(7,6,5,4,3,2,1)\), cioè i lavori per tempo di esecuzione non decrescente. I carichi prima di ogni assegnamento e la macchina scelta sono:
| lavoro \(j\) | \(t_j\) | carichi \((L_1,L_2,L_3)\) prima | macchina |
|---|---|---|---|
| \(7\) | \(3\) | \((0,0,0)\) | \(1\) |
| \(6\) | \(3\) | \((3,0,0)\) | \(2\) |
| \(5\) | \(3\) | \((3,3,0)\) | \(3\) |
| \(4\) | \(4\) | \((3,3,3)\) | \(1\) |
| \(3\) | \(4\) | \((7,3,3)\) | \(2\) |
| \(2\) | \(5\) | \((7,7,3)\) | \(3\) |
| \(1\) | \(5\) | \((7,7,8)\) | \(1\) |
I carichi finali sono \((12,7,8)\), con \(J_1=\{7,4,1\}\), \(J_2=\{6,3\}\), \(J_3=\{5,2\}\), e \(LIST(I)=12\):
L'ultimo lavoro della lista è uno dei più lunghi: quando arriva, la macchina meno carica ha già carico \(7\), e il makespan salta a \(12\), tre unità sopra il lower bound \(9\) (linea grigia tratteggiata).
Proposizione 30.3
Per ogni istanza di \(P\,||\,C_{\max}\), che indichiamo con \(I\), e ogni lista \(\rho\),
Dimostrazione
Dimostrazione omessa. Il risultato è dovuto a
R.L. Graham, Bounds for certain multiprocessing anomalies, Bell System Technical Journal 45 (1966) 1563–1581. □
\(LIST\) è un algoritmo di \(\left(2-\frac{1}{m}\right)\)-approssimazione per \(P\,||\,C_{\max}\), qualunque sia l'ordine della lista.
- Nell'esempio, \(LIST(I)=12\le \frac{5}{3}\cdot 9=15\).
30.6.2 Longest processing time first¶
Il Longest Processing Time first Algorithm (indicato con \(LPT\)) è un'euristica costruttiva per \(P\,||\,C_{\max}\). Ordina i lavori per tempo di esecuzione non crescente e applica \(LIST\) a questa lista: ogni lavoro, dal più lungo al più breve, si assegna a una macchina meno carica.
Algoritmo: Longest Processing Time first
-
Perché prima i lavori più lunghi. Il makespan è deciso dal lavoro che finisce per ultimo. Se i lavori in fondo alla lista sono brevi, gli ultimi assegnamenti possono aggiungere solo poco alla macchina meno carica, e fanno da “sabbia” che livella i carichi. Il parallelo con FFD è esatto: prima gli elementi grandi, poi quelli piccoli a riempire i vuoti.
-
\(LPT\) richiede tempo \(O(n\log n + n\log m)\).
Esempio 30.6: \(LPT\) sull'istanza di riferimento
I lavori sono già ordinati, \(\rho=(1,2,3,4,5,6,7)\). I lavori \(1\), \(2\), \(3\) vanno sulle tre macchine vuote, con carichi \((5,5,4)\); il lavoro \(4\) va sulla macchina \(3\), la meno carica: \((5,5,8)\); il lavoro \(5\) va sulla macchina \(1\): \((8,5,8)\); il lavoro \(6\) sulla macchina \(2\): \((8,8,8)\); il lavoro \(7\) trova tre macchine con carico \(8\) e va sulla macchina \(1\): \((11,8,8)\). Quindi \(J_1=\{1,5,7\}\), \(J_2=\{2,6\}\), \(J_3=\{3,4\}\), \(mach=(1,2,3,3,1,2,1)\), e \(LPT(I)=11\):
Il lower bound elementare del capitolo «Algoritmi euristici: definizioni» dà \(z(I)\ge\max\left\{\max_j t_j,\left\lceil\frac{\sum_j t_j}{m}\right\rceil\right\}=\max\{5,9\}=9\), e \(z(I)=9\). L'ordinamento migliora il makespan da \(12\) a \(11\), ma \(LPT\) non è ottimo: dopo sei lavori i carichi sono perfettamente bilanciati, \((8,8,8)\), e il settimo lavoro li sbilancia di \(3\).
Proposizione 30.4
Per ogni istanza di \(P\,||\,C_{\max}\), che indichiamo con \(I\),
Dimostrazione
Dimostrazione omessa. Il risultato è dovuto a
R.L. Graham, Bounds on multiprocessing timing anomalies, SIAM Journal on Applied Mathematics 17 (1969) 416–429. □
\(LPT\) è un algoritmo di \(\left(\frac{4}{3}-\frac{1}{3m}\right)\)-approssimazione per \(P\,||\,C_{\max}\): ordinare la lista abbassa la garanzia di \(LIST\) da \(2-\frac{1}{m}\) a \(\frac{4}{3}-\frac{1}{3m}\).
-
Per \(m=3\) il bound è \(\frac{4}{3}-\frac{1}{9}=\frac{11}{9}\), e sull'istanza di riferimento
\[ \frac{LPT(I)}{z(I)}=\frac{11}{9}. \]L'istanza di riferimento raggiunge esattamente il bound di Graham: appartiene alla famiglia di istanze, data da Graham, con \(2m+1\) lavori di tempi di esecuzione \(2m-1,2m-1,2m-2,2m-2,\dots,m+1,m+1,m,m,m\), su cui \(LPT\) dà \(4m-1\) e l'ottimo è \(3m\). Per \(m=3\) questi sono i tempi \((5,5,4,4,3,3,3)\). Il bound della Proposizione 30.4 non si può quindi migliorare.
Avanti: 30.7 Il problema del commesso viaggiatore: accodare o inserire?