14.2 Un modello PLI per il problema di scheduling su macchine parallele identiche¶
Parte 2 · Formulazioni dei problemi e loro proprietà · Capitolo 14 · Capitolo 14: Problemi di scheduling · Dispensa, volume 2 (PDF) · Slide · Esercizi: Problemi di scheduling
Il problema di questa sezione è lo scheduling su macchine parallele identiche (\(P\|C_{\max}\)), definito nel Capitolo 7 «Problemi di scheduling».
-
Date \(m\) macchine identiche e un insieme \(\mathscr{J}=\{1,2,\ldots,n\}\) di \(n\) lavori, con tempi di processamento \(t_j\), indichiamo con \(\mathscr{H}=\{1,2,\ldots,m\}\) l'insieme delle macchine.
-
Introduciamo le seguenti \(nm\) variabili binarie:
\[ x_{jh}= \begin{cases} 1 & \text{se il lavoro $j$ è assegnato alla macchina $h$}\\[1.5ex] 0 & \text{altrimenti} \end{cases} \qquad \forall j\in\mathscr{J},~\forall h\in\mathscr{H}, \]e una variabile continua non negativa:
\[ C_{\max}=\text{makespan della schedula}. \]
Usando queste variabili, un modello di programmazione lineare intera (PLI) per il problema di scheduling su macchine parallele identiche (\(P\|C_{\max}\)) è il seguente:
Questo modello PLI si chiama modello \(\mathrm{ILP}_{P\|C_{\max}}\).
-
Descrizione della funzione obiettivo e dei vincoli del modello \(\mathrm{ILP}_{P\|C_{\max}}\):
-
la funzione obiettivo lineare \(\eqref{obj:PCMAX}\) minimizza il makespan;
-
i vincoli \(\eqref{assign:PCMAX}\) garantiscono che ogni lavoro sia assegnato a esattamente una macchina (\(n\) vincoli lineari);
-
i vincoli \(\eqref{load:PCMAX}\) collegano le variabili di assegnamento con la variabile di makespan. In particolare, garantiscono che il makespan sia maggiore o uguale al carico di ogni macchina (\(m\) vincoli lineari);
-
infine, i vincoli \(\eqref{bin:PCMAX}\) e \(\eqref{nonneg:PCMAX}\) definiscono le variabili del modello PLI.
-
Spiegazione del legame fra le variabili
-
Per ogni macchina \(h\), il makespan e il suo carico devono soddisfare la relazione diretta
\[ C_{\max}\ge \sum_{j\in\mathscr{J}}t_jx_{jh}, \]che è imposta dal vincolo \(\eqref{load:PCMAX}\).
-
Poiché il vincolo vale per ogni macchina, esso impone
\[ C_{\max}\ge \max_{h\in\mathscr{H}}\left\{\sum_{j\in\mathscr{J}}t_jx_{jh}\right\}. \] -
In ogni soluzione ottima vale l'uguaglianza. Infatti, se \(C_{\max}\) fosse maggiore del carico massimo, sostituendo \(C_{\max}\) con il carico massimo tutti i vincoli \(\eqref{load:PCMAX}\) resterebbero soddisfatti e il valore obiettivo diminuirebbe di una quantità positiva, il che contraddice l'ottimalità.
-
Quando a una macchina non è assegnato alcun lavoro, il suo carico è zero.
Esempio 14.1: Modello \(\mathrm{ILP}_{P\|C_{\max}}\)
Consideriamo \(m=3\) macchine (\(\mathscr{H}=\{1,2,3\}\)) e un insieme \(\mathscr{J}=\{1,2,\dots,7\}\) di \(7\) lavori (\(n=7\)), con i seguenti tempi di processamento:
È l'istanza dell'Esempio 7.1 del Capitolo 7 «Problemi di scheduling»; la chiamiamo Esempio 14.1. Il modello \(\mathrm{ILP}_{P\|C_{\max}}\) per questa istanza è:
Una soluzione ottima \((\tilde{\vet x},\tilde C_{\max})(\mathrm{ILP}_{P\|C_{\max}})\) è:
Assegna i lavori \(\{1,3\}\) alla macchina \(1\), \(\{2,4\}\) alla macchina \(2\) e \(\{5,6,7\}\) alla macchina \(3\), con carichi \(9\), \(9\) e \(9\). Il valore ottimo \(z(\mathrm{ILP}_{P\|C_{\max}})\) è \(9\), poiché raggiunge il lower bound
14.3 Un primo rilassamento lineare¶
Per ottenere un rilassamento lineare (LP) del modello \(\mathrm{ILP}_{P\|C_{\max}}\), rilassiamo i vincoli \(\eqref{bin:PCMAX}\) in vincoli di non negatività. Il modello LP ottenuto è il seguente:
Questo modello LP si chiama modello \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\).
Esempio 14.2: Modello \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\)
Il modello \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\) per l'istanza dell'Esempio 14.1 è:
Una soluzione ottima \((\tilde{\vet x},\tilde C_{\max})(\mathrm{LP}\text{-}0_{P\|C_{\max}})\) è:
Il valore ottimo \(z(\mathrm{LP}\text{-}0_{P\|C_{\max}})\) è \(9\). Di conseguenza, abbiamo il lower bound:
Usando una variabile duale libera \(\mu_j\) per ogni vincolo \(\eqref{assign:LP0-PCMAX}\) e una variabile duale non negativa \(\pi_h\) per ogni vincolo \(\eqref{load:LP0-PCMAX}\), il modello duale del modello \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\) è:
Questo modello LP si chiama modello \(D(\mathrm{LP}\text{-}0_{P\|C_{\max}})\).
Esempio 14.3: Modello \(D(\mathrm{LP}\text{-}0_{P\|C_{\max}})\)
Il modello duale \(D(\mathrm{LP}\text{-}0_{P\|C_{\max}})\) per l'istanza dell'Esempio 14.1 è:
Una soluzione ottima \((\tilde{\vet\mu},\tilde{\vet\pi})(D(\mathrm{LP}\text{-}0_{P\|C_{\max}}))\) è:
Il valore ottimo \(z(D(\mathrm{LP}\text{-}0_{P\|C_{\max}}))\) è \(9\).
Proposizione 14.1: Valore ottimo di \(\mathrm{LP}\text{-}0_{P\|C_{\max}}\)
Per ogni istanza di \(P\|C_{\max}\),
Dimostrazione
Poniamo \(x_{jh}=1/m\) per ogni lavoro e ogni macchina, e poniamo
Ogni vincolo \(\eqref{assign:LP0-PCMAX}\) è soddisfatto e ogni macchina ha il carico indicato, quindi questa è una soluzione primale ammissibile. Nel duale, poniamo
I vincoli \(\eqref{x:DLP0-PCMAX}\) valgono all'uguaglianza, \(\sum_h\pi_h=1\), e il valore obiettivo duale è
Per la dualità debole della PL, le due soluzioni sono ottime, e il valore ottimo è il valore comune delle funzioni obiettivo. □
14.4 Un secondo rilassamento lineare¶
Per ottenere un rilassamento lineare del modello \(\mathrm{ILP}_{P\|C_{\max}}\), rilassiamo i vincoli \(\eqref{bin:PCMAX}\) nei bound \(0\le x_{jh}\le 1\). Il modello LP ottenuto è il seguente:
Questo modello LP si chiama modello \(\mathrm{LP}_{P\|C_{\max}}\).
-
I vincoli \(\eqref{ub:LP-PCMAX}\) non cambiano il rilassamento: per \(\eqref{assign:LP-PCMAX}\) e \(\eqref{nonnegx:LP-PCMAX}\), ogni \(x_{jh}\) vale al più uno. Quindi
\[ z(\mathrm{LP}_{P\|C_{\max}})=z(\mathrm{LP}\text{-}0_{P\|C_{\max}})=\frac{\sum_{j\in\mathscr{J}}t_j}{m}. \]
Esempio 14.4: Modello \(\mathrm{LP}_{P\|C_{\max}}\)
Il modello \(\mathrm{LP}_{P\|C_{\max}}\) per l'istanza dell'Esempio 14.1 è:
Una soluzione ottima \((\tilde{\vet x},\tilde C_{\max})(\mathrm{LP}_{P\|C_{\max}})\) è la soluzione dell'Esempio 14.2:
Il valore ottimo \(z(\mathrm{LP}_{P\|C_{\max}})\) è \(9\). Di conseguenza, abbiamo lo stesso lower bound.
Usando una variabile duale libera \(\mu_j\) per ogni vincolo \(\eqref{assign:LP-PCMAX}\), una variabile duale non negativa \(\pi_h\) per ogni vincolo \(\eqref{load:LP-PCMAX}\) e una variabile duale non positiva \(\lambda_{jh}\) per ogni vincolo \(\eqref{ub:LP-PCMAX}\), il modello duale del modello \(\mathrm{LP}_{P\|C_{\max}}\) è:
Questo modello LP si chiama modello \(D(\mathrm{LP}_{P\|C_{\max}})\).
Esempio 14.5: Modello \(D(\mathrm{LP}_{P\|C_{\max}})\)
Il modello duale \(D(\mathrm{LP}_{P\|C_{\max}})\) per l'istanza dell'Esempio 14.1 è:
Una soluzione ottima \((\tilde{\vet\mu},\tilde{\vet\pi},\tilde{\vet\lambda})(D(\mathrm{LP}_{P\|C_{\max}}))\) è la soluzione dell'Esempio 14.3 con \(\tilde\lambda_{jh}=0\) per ogni lavoro e ogni macchina:
Il valore ottimo \(z(D(\mathrm{LP}_{P\|C_{\max}}))\) è \(9\).
14.4.1 Alcune proprietà teoriche importanti¶
Proposizione 14.2: Rapporto nel caso peggiore del bound LP
Per ogni istanza di \(P\|C_{\max}\),
Dimostrazione
Assegnando ogni lavoro a una sola macchina otteniamo una schedula ammissibile di makespan \(\sum_jt_j\). Quindi \(z(\mathrm{ILP}_{P\|C_{\max}})\le\sum_jt_j\). Per la Proposizione 14.1,
□
Proposizione 14.3: Il rapporto \(1/m\) è raggiunto asintoticamente
Per un numero fissato \(m \ge 2\) di macchine, esistono istanze per cui
Dimostrazione
Per \(M\in\Z_{\ge2}\), consideriamo un lavoro di tempo di processamento \(M\) e \(m\) lavori di tempo di processamento uno. Il lavoro lungo da solo impone \(z(\mathrm{ILP}_{P\|C_{\max}})\ge M\). La schedula che assegna il lavoro lungo da solo alla macchina \(1\) e gli \(m\) lavori unitari alle altre \(m-1\) macchine ha carichi al più \(2 \le M\), quindi il makespan \(M\) è ammissibile. Quindi \(z(\mathrm{ILP}_{P\|C_{\max}})=M\). La Proposizione 14.1 dà
Di conseguenza,
□
Esempio 14.6: Un gap di integralità
Consideriamo due macchine e tre lavori con tempi di processamento \((3,3,2)\). La Proposizione 14.1 dà \(z(\mathrm{LP}_{P\|C_{\max}})=8/2=4\). In ogni schedula intera una macchina esegue almeno due dei tre lavori, quindi il suo carico è almeno \(3+2=5\); la schedula \(\{3,2\},\{3\}\) lo raggiunge, quindi \(z(\mathrm{ILP}_{P\|C_{\max}})=5\). L'assegnamento frazionario
ha carico quattro su entrambe le macchine, mentre l'ottimo intero ha carichi cinque e tre.
14.5 Considerazioni aggiuntive¶
-
Per ogni lavoro \(j\), la disuguaglianza
\[\begin{equation*} C_{\max}\ge t_j \label{valid:job-PCMAX} \tag{14.6} \end{equation*}\]è una disuguaglianza valida per il modello (14.1). In ogni schedula intera, il lavoro \(j\) è assegnato a una macchina, il cui carico, e quindi il makespan, vale almeno \(t_j\) (\(n\) vincoli lineari);
-
La disuguaglianza
\[\begin{equation*} C_{\max}\ge\left\lceil\frac{\sum_{j\in\mathscr{J}}t_j}{m}\right\rceil \label{valid:average-PCMAX} \tag{14.7} \end{equation*}\]è anch'essa una disuguaglianza valida per il modello (14.1): gli \(m\) carichi delle macchine hanno somma \(\sum_jt_j\), quindi il loro massimo vale almeno la loro media ed è intero in ogni schedula intera (un vincolo lineare);
-
Le macchine sono identiche. I vincoli
\[\begin{equation*} \sum_{j\in\mathscr{J}}t_jx_{jh}\ge \sum_{j\in\mathscr{J}}t_jx_{j,h+1} \qquad \forall h\in\{1,\ldots,m-1\} \label{symmetry:PCMAX} \tag{14.8} \end{equation*}\]sono vincoli che preservano l'ottimalità: non sono validi per ogni assegnamento ammissibile, ma le macchine di ogni schedula si possono rinumerare in modo che i carichi siano non crescenti, senza cambiare il makespan.
-
I vincoli \(\eqref{symmetry:PCMAX}\) eliminano le rinumerazioni equivalenti delle macchine solo quando i carichi sono distinti. Con carichi uguali non ne eliminano nessuna: nell'istanza del capitolo tutte le schedule ottime hanno carichi \(9\), \(9\), \(9\), e tutte le \(12\) soluzioni ottime del modello li soddisfano.
14.6 Errori tipici¶
Attenzione
-
Usare solo il bound LP. Il valore \(\sum_j t_j/m\) ignora il lavoro più lungo: con un lavoro molto lungo è molto più piccolo del valore ottimo. Bisogna aggiungere la disuguaglianza valida \(C_{\max}\ge t_j\).
-
Dimenticare l'arrotondamento per eccesso. Tutti i tempi di processamento sono interi, quindi \(C_{\max}\) è intero in ogni schedula intera: il lower bound è \(\lceil \sum_j t_j/m \rceil\).
-
Credere che i vincoli di simmetria eliminino tutte le soluzioni equivalenti. Eliminano le rinumerazioni delle macchine solo quando i carichi sono distinti; con carichi uguali non ne eliminano nessuna.
-
Dimenticare il verso dei vincoli di carico. I vincoli \(\eqref{load:PCMAX}\) limitano \(C_{\max}\) dal basso: è la minimizzazione che rende \(C_{\max}\) uguale al carico massimo.
-
Confondere gli indici. La variabile \(x_{jh}\) ha il lavoro \(j\) come primo indice e la macchina \(h\) come secondo.
14.7 In sintesi¶
In sintesi
-
Il modello \(\mathrm{ILP}_{P\|C_{\max}}\) ha \(n \cdot m\) variabili di assegnamento \(x_{jh}\) e la variabile di makespan \(C_{\max}\), collegate da un vincolo di carico per ogni macchina.
-
Il rilassamento lineare ha valore ottimo \(z(\mathrm{LP}_{P\|C_{\max}}) = \sum_j t_j / m\), raggiunto assegnando ogni lavoro con valore \(1/m\) a ogni macchina; la soluzione duale è \(\tilde{\pi}_h = 1/m\) e \(\tilde{\mu}_j = t_j/m\).
-
Il rapporto fra \(z(\mathrm{LP}_{P\|C_{\max}})\) e \(z(\mathrm{ILP}_{P\|C_{\max}})\) vale almeno \(1/m\), e \(1/m\) è raggiunto asintoticamente.
-
Le disuguaglianze valide \(C_{\max} \ge t_j\) e \(C_{\max} \ge \lceil \sum_j t_j/m \rceil\) rafforzano il modello.
Quadro riassuntivo dell'istanza del capitolo (\(m=3\), \(t=(5,5,4,4,3,3,3)\)). Lower bound sul valore ottimo \(9\):
| Bound | Valore | Da |
|---|---|---|
| Rilassamento lineare | \(9\) | \(\sum_j t_j / m = 27/3\) |
| Disuguaglianze valide | \(9\) | \(\max\{5, \lceil 27/3 \rceil\}\) |
| Valore ottimo | \(9\) | carichi \(9\), \(9\), \(9\) |
Sull'istanza del gap di integralità (\(m=2\), \(t=(3,3,2)\)) il bound LP vale \(4\) e il valore ottimo è \(5\).
Esercizi su questo capitolo: Problemi di scheduling