Scheduling su macchine parallele identiche (\(P\|C_{\max}\))¶
Definizione 1: Scheduling su macchine parallele identiche
Dati:
-
un insieme di \(m\) macchine identiche,
-
un insieme \(\mathscr{J} = \{1,2,\dots,n\}\) di \(n\) lavori,
-
per ogni lavoro \(j \in \mathscr{J}\), un tempo di processamento \(t_j \in \Z_{\ge 1}\),
il problema \(P\,||\,C_{\max}\) chiede di assegnare ogni lavoro a una macchina, in modo da minimizzare il tempo necessario per completare tutti i lavori, cioè il massimo tempo di processamento totale assegnato a una macchina.
Ipotesi
-
Facciamo la seguente ipotesi:
-
Ci sono più lavori che macchine (altrimenti ogni lavoro ha una macchina tutta per sé, e il makespan ottimo è \(\max_j t_j\)). Formalmente:
\[ n > m \]
-
Che cosa fa il corso su questo problema¶
Proprietà¶
-
NP-difficile in senso forte quando \(m\) fa parte dell'input; NP-difficile in senso debole per un numero fissato di macchine (Cap. 1).
-
Lower bound \(\max\{\max_j t_j, \lceil \sum_j t_j/m \rceil\}\); non è sempre raggiunto: \((4,3,3)\) su due macchine dà \(5\), l'ottimo è \(6\) (Cap. 7).
-
Esiste un makespan al più \(T\) se e solo se i lavori entrano in \(m\) contenitori di capacità \(T\) (Cap. 7).
Formulazioni¶
-
Il modello \(\ILP_{\PCmax}\) ha \(nm\) variabili binarie \(x_{jh}\) e la variabile continua \(C_{\max}\) (Cap. 14).
-
Il bound del rilassamento lineare è \(\sum_j t_j/m\); il suo rapporto con l'ottimo è almeno \(1/m\), e \(1/m\) è raggiunto al limite (Cap. 14).
-
Le disuguaglianze valide rafforzano il modello; l'ordinamento dei carichi rompe la simmetria solo quando i carichi sono distinti (Cap. 14).
Euristiche¶
-
Sull'istanza del Cap. 7 (tre macchine, ottimo \(9\)) LIST con i lavori più brevi per primi dà \(12\) e LPT dà \(11\) (Cap. 30).
-
La soluzione di LPT è un ottimo locale per la mossa move, mentre due swap raggiungono \(9\); l'obiettivo ausiliario \(\sum_h L_h^2\) dà una pendenza ai plateau (Cap. 31).
-
Tabu search e VNS raggiungono \(9\) sulla stessa istanza (Cap. 32).
Euristiche MIP¶
-
Sull'istanza del Cap. 7 il diving frazionario si ferma a \(10\), il diving guidato da LPT trova \(9\), la feasibility pump restituisce \(11\) (Cap. 33).
-
RINS, local branching e proximity search, partendo da LPT, raggiungono \(9\); proximity search ne dimostra anche l'ottimalità (Cap. 33).