Vai al contenuto

25.2 Un algoritmo di PD per l'ULS

Parte 3 · Programmazione dinamica · Capitolo 25 · Capitolo 25: Lot sizing senza capacità (ULS) · Dispensa, volume 3 (PDF) · Slide · Esercizi: Lot sizing senza capacità (ULS) · App: Wagner-Whitin per il lot sizing senza capacità

25.2.1 Il costo di un lotto di produzione

  • Per la proprietà zero-inventory ordering, una soluzione ottima è una sequenza di lotti di produzione: un lotto produce in un periodo \(j\) le domande dei periodi \(j,\dots,t\), e il lotto successivo inizia nel periodo \(t+1\) con la scorta vuota.

  • Per ogni \(j,t \in T\) con \(j\le t\), sia \(c_{j,t}\) il costo del lotto di produzione che produce nel periodo \(j\) le domande dei periodi \(j,\dots,t\):

\[\begin{equation*} \label{eq:cjt} c_{j,t}= sc_j + vc_j\, D_{j,t} + \sum_{k=j}^{t-1} hc_k\, D_{k+1,t}. \tag{25.2} \end{equation*}\]

  • Il primo termine è il costo di setup del periodo \(j\), il secondo è il costo variabile delle \(D_{j,t}\) unità prodotte, e l'ultimo è il costo di mantenimento a scorta: alla fine di ogni periodo \(k\in\{j,\dots,t-1\}\) la scorta contiene le domande \(D_{k+1,t}\) dei periodi successivi del lotto.

  • Per un periodo \(j\) fissato, i costi \(c_{j,j},c_{j,j+1},\dots,c_{j,m}\) si possono calcolare uno dopo l'altro. Un'unità usata nel periodo \(t\) e prodotta nel periodo \(j\) costa

    \[ u_{j,t}=vc_j+\sum_{k=j}^{t-1} hc_k, \]

    quindi \(u_{j,j}=vc_j\), \(u_{j,t}=u_{j,t-1}+hc_{t-1}\), e aggiungere il periodo \(t\) al lotto aggiunge \(d_t\) unità di costo \(u_{j,t}\):

    \[ c_{j,j}=sc_j+vc_j\, d_j, \qquad c_{j,t}=c_{j,t-1}+u_{j,t}\, d_t \quad \text{se } t>j. \]

Questo è lo pseudocodice che calcola la matrice dei costi dei lotti di produzione:

Algoritmo: CostMatrix

Input: Un'istanza dell'ULS data dal numero \(m\) di periodi e dai vettori \(d[1..m]\), \(sc[1..m]\), \(vc[1..m]\), \(hc[1..m]\)
Output: La matrice dei costi dei lotti di produzione
1Function CostMatrix(\(m,d,sc,vc,hc\))
2\({c} := \textnormal{new array}[1..m][1..m]\)
3for \(j := 1\) to \(m\) do
4\(\mathit{u} := vc[j]\)
5\(\mathit{g} := sc[j] + vc[j]\cdot d[j]\)
6\({c}[j][j] \leftarrow \mathit{g}\)
7for \(t := j+1\) to \(m\) do
8\(\mathit{u} \leftarrow \mathit{u} + hc[t-1]\)
9\(\mathit{g} \leftarrow \mathit{g} + \mathit{u}\cdot d[t]\)
10\({c}[j][t] \leftarrow \mathit{g}\)
11end
12end
13return \({c}\)

  • La variabile \(\mathit{u}\) è il costo unitario \(u_{j,t}\) e la variabile \(\mathit{g}\) è il costo \(c_{j,t}\) del lotto corrente; si usano solo le celle \({c}[j][t]\) con \(j\le t\).

Esempio 25.4: Calcolo dei costi dei lotti di produzione

Consideriamo l'istanza dell'ULS dell'Esempio 25.1:

\[ \begin{array}{l|rrrrr} \hline {t} & {1} & {2} & {3} & {4} & {5} \\ \hline {d_t} & {20} & {10} & {30} & {40} & {10} \\ {sc_t} & {50} & {50} & {50} & {50} & {50} \\ {vc_t} & {0} & {0} & {0} & {0} & {0} \\ {hc_t} & {1} & {1} & {1} & {1} & {1} \\ \hline \end{array} \]

Per ogni passo, la tabella riporta i valori di \(j\) e \(t\), il valore corrente di \(\mathit{u}\), la cella \({c}[j][t]\) e l'operazione eseguita; la cella \({c}[j][t]\) è evidenziata in blu quando viene assegnata.

\(j\) \(t\) \(\mathit{u}\) \({c}[j][t]\) Azione
\(1\) \(1\) \(0\) \(50\) \(\mathit{u}\leftarrow vc[1]=0\), \(\mathit{g}\leftarrow sc[1]{+}vc[1]\cdot d[1]=50{+}0\cdot 20=50\), \({c}[1][1]\leftarrow 50\)
\(1\) \(2\) \(1\) \(60\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[1]=0{+}1=1\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[2]=50{+}1\cdot 10=60\), \({c}[1][2]\leftarrow 60\)
\(1\) \(3\) \(2\) \(120\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[2]=1{+}1=2\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[3]=60{+}2\cdot 30=120\), \({c}[1][3]\leftarrow 120\)
\(1\) \(4\) \(3\) \(240\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=2{+}1=3\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=120{+}3\cdot 40=240\), \({c}[1][4]\leftarrow 240\)
\(1\) \(5\) \(4\) \(280\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[4]=3{+}1=4\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[5]=240{+}4\cdot 10=280\), \({c}[1][5]\leftarrow 280\)
\(2\) \(2\) \(0\) \(50\) \(\mathit{u}\leftarrow vc[2]=0\), \(\mathit{g}\leftarrow sc[2]{+}vc[2]\cdot d[2]=50{+}0\cdot 10=50\), \({c}[2][2]\leftarrow 50\)
\(2\) \(3\) \(1\) \(80\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[2]=0{+}1=1\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[3]=50{+}1\cdot 30=80\), \({c}[2][3]\leftarrow 80\)
\(2\) \(4\) \(2\) \(160\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=1{+}1=2\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=80{+}2\cdot 40=160\), \({c}[2][4]\leftarrow 160\)
\(2\) \(5\) \(3\) \(190\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[4]=2{+}1=3\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[5]=160{+}3\cdot 10=190\), \({c}[2][5]\leftarrow 190\)
\(3\) \(3\) \(0\) \(50\) \(\mathit{u}\leftarrow vc[3]=0\), \(\mathit{g}\leftarrow sc[3]{+}vc[3]\cdot d[3]=50{+}0\cdot 30=50\), \({c}[3][3]\leftarrow 50\)
\(3\) \(4\) \(1\) \(90\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[3]=0{+}1=1\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[4]=50{+}1\cdot 40=90\), \({c}[3][4]\leftarrow 90\)
\(3\) \(5\) \(2\) \(110\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[4]=1{+}1=2\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[5]=90{+}2\cdot 10=110\), \({c}[3][5]\leftarrow 110\)
\(4\) \(4\) \(0\) \(50\) \(\mathit{u}\leftarrow vc[4]=0\), \(\mathit{g}\leftarrow sc[4]{+}vc[4]\cdot d[4]=50{+}0\cdot 40=50\), \({c}[4][4]\leftarrow 50\)
\(4\) \(5\) \(1\) \(60\) \(\mathit{u}\leftarrow \mathit{u}{+}hc[4]=0{+}1=1\), \(\mathit{g}\leftarrow \mathit{g}{+}\mathit{u}\cdot d[5]=50{+}1\cdot 10=60\), \({c}[4][5]\leftarrow 60\)
\(5\) \(5\) \(0\) \(50\) \(\mathit{u}\leftarrow vc[5]=0\), \(\mathit{g}\leftarrow sc[5]{+}vc[5]\cdot d[5]=50{+}0\cdot 10=50\), \({c}[5][5]\leftarrow 50\)

Questa è la matrice \({c}\) dopo l'esecuzione dell'algoritmo (per esempio, \(c_{1,3}=sc_1+vc_1\,D_{1,3}+hc_1\,D_{2,3}+hc_2\,D_{3,3}=50+0\cdot 60+1\cdot 40+1\cdot 30=120\) per la formula \(\eqref{eq:cjt}\)):

\[ \begin{array}{l|rrrrr} \hline {{c}[j][t]} & {t=1} & {t=2} & {t=3} & {t=4} & {t=5} \\ \hline {j=1} & {50} & {60} & {120} & {240} & {280} \\ {j=2} & {-} & {50} & {80} & {160} & {190} \\ {j=3} & {-} & {-} & {50} & {90} & {110} \\ {j=4} & {-} & {-} & {-} & {50} & {60} \\ {j=5} & {-} & {-} & {-} & {-} & {50} \\ \hline \end{array} \]

Avanti: 25.2.2 Un algoritmo di PD per l'ULS: Passo 1 e Passo 2