25.2 A DP algorithm for the ULS¶
Part 3 · Dynamic programming · Chapter 25 · Chapter 25: Uncapacitated lot sizing (ULS) · Lecture notes, volume 3 (PDF) · Slides · Exercises: Uncapacitated lot sizing (ULS) · App: Wagner-Whitin for uncapacitated lot sizing
25.2.1 The cost of a production run¶
-
By the zero-inventory ordering property, an optimal solution is a sequence of production runs: a run produces in a period \(j\) the demands of periods \(j,\dots,t\), and the next run starts in period \(t+1\) with an empty inventory.
-
For any \(j,t \in T\) with \(j\le t\), let \(c_{j,t}\) be the cost of the production run that produces in period \(j\) the demands of periods \(j,\dots,t\):
-
The first term is the setup cost of period \(j\), the second term is the variable cost of the \(D_{j,t}\) produced units, and the last term is the holding cost: at the end of each period \(k\in\{j,\dots,t-1\}\) the inventory contains the demands \(D_{k+1,t}\) of the following periods of the run.
-
For a fixed period \(j\), the costs \(c_{j,j},c_{j,j+1},\dots,c_{j,m}\) can be computed one after the other. A unit used in period \(t\) and produced in period \(j\) costs
\[ u_{j,t}=vc_j+\sum_{k=j}^{t-1} hc_k, \]so that \(u_{j,j}=vc_j\), \(u_{j,t}=u_{j,t-1}+hc_{t-1}\), and adding period \(t\) to the run adds \(d_t\) units of cost \(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{if } t>j. \]
This is the pseudo-code that computes the matrix of the production-run costs:
Algorithm: CostMatrix
- The variable \(\mathit{u}\) is the unit cost \(u_{j,t}\) and the variable \(\mathit{g}\) is the cost \(c_{j,t}\) of the current run; only the cells \({c}[j][t]\) with \(j\le t\) are used.
Example 25.4: Computation of the production-run costs
We consider the ULS instance of Example 25.1:
For each step, the table shows the values of \(j\) and \(t\), the current value of \(\mathit{u}\), the cell \({c}[j][t]\), and the operation performed; the cell \({c}[j][t]\) is highlighted in blue when assigned.
| \(j\) | \(t\) | \(\mathit{u}\) | \({c}[j][t]\) | Action |
|---|---|---|---|---|
| \(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\) |
This is the matrix \({c}\) after the execution of the algorithm (for instance, \(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\) by formula \(\eqref{eq:cjt}\)):