Dynamic lot-size model

We have available a forecast of product demand d_t over a relevant time horizon t=1,2,...,N (for example we might know how many widgets will be needed each week for the next 52 weeks). There is a setup cost s_t incurred for each order and there is an inventory holding cost i_t per item per period (s_t and i_t can also vary with time if desired). The problem is how many units x_t to order now to minimize the sum of setup cost and inventory cost. Let us denote inventory:

${\displaystyle I=I_{0}+\sum _{j=1}^{t-1}x_{j}-\sum _{j=1}^{t-1}d_{j}\geq 0}$

The functional equation representing minimal cost policy is:

${\displaystyle f_{t}(I)={\underset {x_{t}\geq 0 \atop I+x_{t}\geq d_{t}}{\min }}\left[i_{t-1}I+H(x_{t})s_{t}+f_{t+1}\left(I+x_{t}-d_{t}\right)\right]}$

Where H() is the Heaviside step function. Wagner and Whitin[1] proved the following four theorems:

• There exists an optimal program such that Ix_t=0; ∀t
• There exists an optimal program such that ∀t: either x_t=0 or ${\displaystyle x_{t}=\textstyle \sum _{j=t}^{k}d_{j}}$ for some k (t≤k≤N)
• There exists an optimal program such that if d_t* is satisfied by some x_t**, t**<t*, then d_t, t=t**+1,...,t*-1, is also satisfied by x_t**
• Given that I = 0 for period t, it is optimal to consider periods 1 through t - 1 by themselves

The precedent theorems are used in the proof of the Planning Horizon Theorem.[1] Let

${\displaystyle F(t)=\min \left[{{\underset {1\leq j<t}{\min }}\left[s_{j}+\sum _{h=j}^{t-1}\sum _{k=h+1}^{t}i_{h}d_{k}+F(j-1)\right] \atop s_{t}+F(t-1)}\right]}$

denote the minimal cost program for periods 1 to t. If at period t* the minimum in F(t) occurs for j = t** ≤ t*, then in periods t > t* it is sufficient to consider only t** ≤ j ≤ t. In particular, if t* = t**, then it is sufficient to consider programs such that x_t* > 0.

Wagner and Whitin gave an algorithm for finding the optimal solution by dynamic programming.[1] Start with t*=1:

1. Consider the policies of ordering at period t**, t** = 1, 2, ... , t*, and filling demands d_t , t = t**, t** + 1, ... , t*, by this order
2. Add H(x_t**)s_t**+i_t**I_t** to the costs of acting optimally for periods 1 to t**-1 determined in the previous iteration of the algorithm
3. From these t* alternatives, select the minimum cost policy for periods 1 through t*
4. Proceed to period t*+1 (or stop if t*=N)

Because this method was perceived by some as too complex, a number of authors also developed approximate heuristics (e.g., the Silver-Meal heuristic[3]) for the problem.

• Infinite fill rate for the part being produced: Economic order quantity
• Constant fill rate for the part being produced: Economic production quantity
• Demand is random: classical Newsvendor model
• Several products produced on the same machine: Economic lot scheduling problem
• Reorder point

• Lee, Chung-Yee, Sila Çetinkaya, and Albert PM Wagelmans. "A dynamic lot-sizing model with demand time windows." Management Science 47.10 (2001): 1384–1395.
• Federgruen, Awi, and Michal Tzur. "A simple forward algorithm to solve general dynamic lot sizing models with n periods in 0 (n log n) or 0 (n) time." Management Science 37.8 (1991): 909–925.
• Jans, Raf, and Zeger Degraeve. "Meta-heuristics for dynamic lot sizing: a review and comparison of solution approaches." European Journal of Operational Research 177.3 (2007): 1855–1875.
• H.M. Wagner and T. Whitin, "Dynamic version of the economic lot size model," Management Science, Vol. 5, pp. 89–96, 1958
• H.M. Wagner: "Comments on Dynamic version of the economic lot size model", Management Science, Vol. 50 No. 12 Suppl., December 2004

• Solving the Lot Sizing Problem using the Wagner-Whitin Algorithm
• Dynamic lot size model
• Python implementation of the Wagner-Whitin algorithm.