Dynamic Programming Part II
1 Lot Sizing with Dynamic Programming
In this lecture, we continue our study of dynamic programming (DP) by
addressing a problem from the production and inventory domain: lot sizing.
Consider Company XYZ, which is planning the production of a staple
product for the next n months. The demand for the product in each month
i = 1, . . . , n is known in advance and denoted by Di . No shortages are
permitted, meaning that Company XYZ must absolutely fulfill the demand
in each period. Production incurs a setup cost whenever production is started
in a given period i. This fixed setup cost is denoted by Ki , for i = 1, . . . , n,
and is applied in addition to a marginal production cost per unit, ci (zi ),
where zi is the production quantity in period i. Although ci (zi ) could be
non-linear, we will assume it is linear
(
0 if zi = 0
Ci (zi ) =
Ki + ci (zi ) if zi > 0
An inventory holding cost is incurred for carrying inventory from one period
to the next. The cost from period i to i + 1 is denoted by the function hi (y),
where y represents the inventory quantity carried over.
To model this problem using DP, we define the following elements:
1. Stages: Each period i represents a stage in the planning horizon.
2. State: The state at the beginning of each period i is defined by the
inventory level yi on hand.
3. Decision: The decision variable zi represents the number of units pro-
duced during period i.
1
4. Cost-to-go function: Let fi (y) represent the minimum total cost
starting from period i with an inventory level of y, taking into account
optimal decisions for periods i, i + 1, . . . , n.
5. Optimal value sought: The goal is to find f1 (y0 ), where y0 is the
initial inventory level, assumed to be zero unless otherwise specified.
P i = 1, . . . , n − 1 and all possi-
6. Recursive equation: For each period
ble inventory levels yi (from 0 to nj=i Dj , the maximum cumulative
demand) is:
fi (yi ) = min {Ci (zi ) + hi (zi + yi − Di ) + fi+1 (zi + yi − Di )}
zi :zi +yi −Di ≥0
7. Boundary Condition: For the final period n is:
fn (yn ) = Cn ((Dn − yn )+ )
that is the cost for the production strictly required to meet the demand
at period n, where (Dn − yn )+ = max(0, Dn − yn ), which ensures that
the inventory is zero at the end of the planning horizon.
In practice, the state space can be huge for high demand values. We
will explore a refined DP approach (Model II) that handles dimensionality
more efficiently, reducing computational effort. To illustrate Model I with
manageable calculations, we present a small numerical example.
The following table provides data for a three-period example:
Table 1: Example data for lot sizing over three periods.
Period Demand (Di ) Setup Cost (Ki ) Inventory Holding Cost (hi )
1 3 3 1
2 2 7 3
3 4 6 2
Demand and production quantities are in discrete units (integers), and
the initial inventory is set to 1 unit. We consider a production function that
is piecewise linear, identical across each period. The costs are structured as
follows: (
10 · z if 0 ≤ z ≤ 3
C(z) =
30 + 20(z − 3) if z > 3
2
We start from the last period and move backward to find the optimal
production decisions for each period.
In the final period (period 3), we compute the cost-to-go function values
for different inventory levels y3 :
Next, we compute the cost-to-go function for period 2:
3
Since the initial inventory is 1 unit, we reduce the first period demand to
2 units and calculate the minimum costs for producing 2 to 8 units in period
1, that is f1 (0):
The minimum cost is achieved by producing 2 units in period 1, with a
cost of 99. Thus, the optimal policy is: Produce 2 units in period 1, produce
3 units in period 2, and produce 3 units in period 3.
2 The Wagner-Whitin Property and Concave
Lot Sizing
When specific conditions are met, it becomes possible to simplify the dynamic
programming recursion significantly.
The property we leverage is known as concavity. For the production
cost function C to be considered concave in this context, it must satisfy the
following condition:
C(z + 2) − C(z + 1) ≤ C(z + 1) − C(z), ∀z
This condition ensures that the incremental cost of increasing production
decreases as the production level increases. When dealing with integer quan-
tities, as in most practical inventory problems, this definition applies straight-
forwardly. The same condition applies to the inventory holding cost function
h. Notably, if C and h are linear functions, they naturally satisfy concavity
(i.e., the concavity condition hold as equality).
4
Proposition 1 (Wagner-Whitin Property) If both Ci and hi are con-
cave for each period i, then there exists an optimal production policy such
that yi · zi = 0 for each period i = 1, . . . , n.
This means that if production occurs in a period, there should be no inventory
carried over from that period.
As a consequence, once production occurs in period i, then it is selected
to cover an integer number of future periods, thus creating specific regen-
eration points where production is active. Solving the lot sizing problem
then reduces to identifying the optimal regeneration points that minimize
the combined production and inventory holding costs.
In the case of a retailer placing orders with a supplier, the production
cost is replaced by an ordering cost. But otherwise the problem does not
change.
Now, we introduce a new DP formulation to accommodate the concave
cost functions and take advantage of the Wagner-Whitin Property.
Let A be the fixed cost (setup cost) for production or, in the context of
a retailer, the fixed ordering cost. Let moreover H be the inventory holding
cost per unit per period. The demand for period j, where j = 1, . . . , N , is
denoted as Dj .
The total cost, K(t, m), of production or ordering at period t to cover
demands from period t up to period m can be written as:
m
X
K(t, m) = A + H (j − t)Dj
j=t+1
Here, A accounts for the fixed production or ordering cost, while H m
P
j=t+1 (j−
t)Dj calculates the inventory holding cost for covering periods t to m.
For simplicity, we are assuming the production cost zero for the retailer.
Assume also for simplicity that the variable cost of ordering is also nil.
The objective is to minimize the total cost across periods, given the de-
mand Dj for each period j.
1. Stages: Each period m = 1, . . . , N is a stage.
2. State: index t where the regeneration point is set.
3. Decision: Order quantity to cover the demand from period t up to
period m.
5
4. Cost-to-go function: We denote K ∗ (m) as the optimal ordering and
inventory holding policy at period m given the optimal policy carried
out through periods 1, . . . , m − 1.
5. Optimal value sought: The overall goal is to find K ∗ (N ), the optimal
policy from period 1 up to period N .
6. Recursive equation: For all m = 1, . . . , N
K ∗ (m) = min {K ∗ (t − 1) + K(t, m)}
t=1,...,m
7. Boundary Condition: Ensuring that no cost is incurred before any
ordering takes place.
K ∗ (0) = 0
Note that this DP formulation uses a forward recursion.
The following table provides data for a four-period example:
Table 2: Example data for lot sizing over periods.
Week 1 2 3 4
Demand 100 75 175 200
Let moreover A = $50 the ordering cost and H = $0.5 the unit inventory
cost per week. We want to determine the optimal lot sizing policy for 4
periods.
Boundary condition holds K ∗ (0) = 0.
At stage 1
For stage 2
6
In stage 3
Finally, for stage 4
The optimal policy is: Order 175 units in period 1, no unit in period 2,
175 units in period 3, and 200 units in period 4.
