A variable, X_ijt, can be used to represent the amount
ordered for stocking point i in level j at period
t. The lower bound of each X_ijt is 0. A
conservative upper bound on X_ijt is found simply by summing
the demands at all leaves under this stocking point from now until the
end of the planning horizon. This is equivalent to assuming that all
necessary stock for the remaining periods will be ordered immediately.
Orders for period t are assumed to be made (and fulfilled,
there is a 0 lead time assumption) before period t
begins. Inventory levels for period t refer to the end of
period t. There are two common methods of representing the
inventory remaining after each period, as discussed below.
Inventory in the Conventional Model
In the conventional model, a variable,
I_ijt, is used to
represent the amount of stock held at stocking point
i in
level
j after period
t.
The objective can now be expressed:
- Minimise:
sum_{t=1..T}
sum_{j=1..L}
sum_{i=1..N_j}
(c_ij I_ijt +
c0_ij (X_ijt > 0))
where
N_j denotes the number of nodes in level
j.
Note that the objective as expressed above involves the reification of
(
X_ijt > 0). This expression can be bound to an explicit 0/1
variable (
δ_ijt, the approach commonly adopted in
the MIP model of this problem) and the
δ variables
used for branching.
Further constraints govern how inventory is supplied between stocking
points:
- I_ijt = I_ij(t-1) + X_ijt -
sum_{m in W(i,j,j-1)}
(X_mt)
where
W(i,j,j-1) denotes the children of the
ith
stocking point in level
j. In short, the above expression
specifies that the closing inventory for
I_ijt is the closing
inventory for the same stocking point in the previous period, plus the
amount ordered, minus the amount supplied.
Inventory in the Echelon Model
An alternative model views the supply-chain structure in
echelons.
An echelon is a stocking point and all of its descendants, as follows:
Ech6***************************** Level
* | *
* V *
* +---+ *
* | F | * 3
* +---+ *
* ___/ \___ *
* / \ *
*Ech4******V********** Ech5V*****
** +---+ * * +---+ **
** | D | * * | E | ** 2
** +---+ * * +---+ **
** _/ \_ * * | **
** / \ * * | **
** V V * * V **
**Ech1*** Ech2**** *Ech3*****
***+---+* *+---+** **+---+***
***| A |* *| B |** **| C |*** 1
***+---+* *+---+** **+---+***
*****|***********|**** ****|*****
V V V
A variable,
E_ijt, represents the amount of stock held at the
end of period
t in the echelon whose highest node is the
ith node in level
j. The conventional holding cost
per unit of inventory is replaced by an
echelon holding cost,
e_ij, defined as follows:
- e_ij = c_ij - c_iW(i,j,j+1)
where
W(i,j,j+1)denotes the parent of the
ith stocking
point in level
j.
Recall the assumption that a parent always has a smaller holding cost
than any of its children. Hence,
e_ij can be thought of as the
incremental cost of holding a unit of inventory at stocking point
ij instead of its parent.
The objective can now be expressed:
- Minimise:
sum_{t=1..T}
sum_{j=1..L}
sum_{i=1..N_j}
(e_ij E_ijt +
c0_ij (X_ijt > 0))
The constraints governing how inventory is supplied between stocking
points are as follows:
- E_ijt = E_ij(t-1) + X_ijt -
sum_{m in V(i,j)}
(d_mt)
where
V(i, j) denotes the leaves descended from stocking
point
i in level
j, and
d_i1t is the
demand at leaf
i in period
t. That is, inventory
held in an echelon at the end of period
t is the inventory
in the same echelon in the previous period plus the inventory ordered
minus the demand at the leaves associated with that echelon.
One further set of constraints relate an echelon whose highest
stocking point is stocking point i in level j and
the echelons whose highest stocking points are the children of
stocking point ij:
- E_ijt >= sum_{m in
W(i,j,j-1)} (E_mt)
where again
W(i,j,j-1) denotes the children of the
ith stocking point in level
j.
Implied Constraints
A variety of implied constraints can be used to improve these basic
models.
- In an optimal solution, clearly the inventory for every stocking
point at the end of the last period must be 0. In both models,
therefore, the inventory variables for the last period can be
pre-set.
- In an optimal solution, if a node in a higher level places an
order, at least one of its children must also. This can be seen by
considering that if no children make an order, the higher node incurs
a holding cost that can be removed by delaying the order until a
subsequent period when at least one child does place an order.
- An upper bound can be derived for the inventory variables in the
conventional formulation by considering that it is only worth holding
stock at a node if it is cheaper than ordering it at the next period.
That is:
- I_ijt c_ij <= c0_ij + I_ijt c_W(i,j,j+1)
which simplifies to:
- I_ijt <= (c0_ij)/(c_ij-c_W(i,j,j+1))
This can easily be applied to the echelon model by substituting
in the equality:
- I_ijt = E_ijt - sum_{m in G(i,j)}
(I_mt)
where G(i,j) is the set of all descendents of stocking point
i in level j
- Similarly, an upper bound can be derived for
the order variables at the leaf nodes. The principle is the same:
it is only worth ordering stock not absorbed by demand at the
current period if it is cheaper than waiting and ordering in a
subsequent period. Consider first a bound based on deferring an
order into the next period:
- (X_i1t-d_i1t)c_i1 <= c0_i1+c_m(X_i1t-d_i1t)
which can be re-arranged:
- X_i1t <= d_i1t + (c0_i1)/(c_i1-c_m)
This can be generalised to consider deferring an order into
any of the following periods up to the planning horizon:
- X_i1t <= min_{t’ = t .. T}
sum_{i=t..t’} (d_i1t) +
(c0_i1)/((t’-t+1)(c_i1-c_m))
- In an optimal solution, an order is only made at a node when the
inventory is 0. This can be seen by considering that if an order is
made at a node with some stock at period t, the cost incurred
by holding that stock from period t-1 to t can be
removed by increasing the size of the order at period t.
- The domains of the order (X) variables can be reduced
by exploiting the fact that, in an optimal solution, the sizes of all
orders made are composed from the demands of the children of the
associated node for a continuous stretch of time from between the
current period to the end of the planning horizon. It is therefore
possible to enumerate the domain elements for each X variable,
replacing the simple upper/lower bounds representation. The time
complexity of this process is exponential in the number of leaves
beneath the order node in question, but can usefully be applied when
the number of leaves is small.
Code
A basic Ilog Solver 5.x program to solve the Wagner-Whitin problem can be found below:
This work is licensed under a Creative Commons Attribution 4.0 International License.