5.9 An algorithm for the \((s, S)\) and \((T, S)\) policies

We develop an algorithm by which we can compute the long-run average cost for a single-item inventory system under periodic review and controlled by the \((s, S)\) or the \((T, S)\) policy. This algorithm finds its importance in its underlying ideas: hitting (or stopping) problems, the renewal reward theorem, and dynamic programming. We start with the \((T, S)\) policy, then move on to the \((s, S)\) policy, and then extend to a combination of the other two, the \((T, s, S)\) policy, to be introduced presently.

Recall that under the \((T, S)\) policy, we place a replenishment order every \(T\) periods such that the inventory position \(P\) equals \(S\) after the replenishment. When the inventory level \(I\) equals \(x\), the inventory cost is given by

By conditioning on \(P=x\), and using¹¹See Th. 5.7.3. that \(I=P-X\), it follows that

is the expected inventory cost per period when \(P=x\).

Let us write \(V(n, x)\) for the expected cost until reordering if we start at position \(P=x\) and there are \(n\), \(0\leq n \leq T\), periods remaining. By reasoning analogously as in Section 5.6, \(V(n, x)\) satisfies the recursion

To see this, observe that when \(P=x\) and \(n>0\), we first pay \(L(x)\) for keeping inventory during one period, then a demand \(D\) arrives, and for the next period we have one less period to go until ordering. When \(n=0\), we pay the order cost \(K\) to replenish to \(S\). Note that this recursion always terminates because \(V(n, \cdot)\) is expressed in terms of \(V(n-1, \cdot)\), so always one period less to go.

Since a (renewal) cycle starts at level \(S\), the expected cycle cost is \(V(T, S)\) and the expected cycle duration is \(T\) periods. The renewal reward theorem implies that the long-run average cost is given by \(V(T, S)/T\).

To facilitate the development of the other models, we introduce some important definitions²²Of dynamic programming. that are used in the above recursion: \(L(x)\) is called the running cost, \(K\) the hitting cost, \(T\) is the hitting time, and \(\set{n : n=0}\) is the hitting set.³³We use the adjectives hitting and stopping interchangeably.

With this terminology we can easily structure the analysis of the \((s,S)\) policy. In view of (2.5.3), when the inventory position \(P\) enters (or hits) the stopping set \(\set{i : i \leq s}\) we place an order and pay a stopping cost \(K\). When \(P>s\), we pay the running cost \(L(x)\) and continue for another period. Hence, the expected cost until stopping satisfies the recursion

For the hitting time we find

because the running cost is \(1\) if we continue for another period, and when the process hits the stopping set, the time stops counting, so the stopping cost is \(0\). Note that this recursion is structurally identical to that of \(V\).

To find an algorithm, we expand the recursion for \(V\) at \(x>s\) as

Clearly, \(V(s, x)\) appears at the LHS and RHS, so \(V(s, x)\) is expressed in terms of itself, that is, circular.⁴⁴This is different from the recursion for the \((T,S)\) policy. The way out is to isolate \(V(s, x)\) by rewriting this as

Thus, assuming that⁵⁵This is not restrictive, because \(\P{D=0} = 1\) implies that there is no demand, in which case there is no need to keep inventory. \(f_0 < 1\),

We can now use one algorithm to compute \(V\) and \(T\) by adjusting the running and stopping cost accordingly.

Finally, when the expected cycle cost \(V(s, S)\) and expected hitting time \(T(s,S)\) have been computed, the long-run average cost is \(V(s,S)/T(s,S)\).

By combining the two policies above we obtain the \((T,s,S)\) policy. The recursion for \(V(n, s, x)\) specifies the behavior:

The structure of the recursion for \(T(n, s, x)\) is the same, but with running cost \(1\) and stopping cost \(0\).

To see how the \((s,S)\) and \((T,s,S)\) policy relate, realize that when \(T\) becomes very large, the set \(set{i : i \leq s}\) will be hit with overwhelming probability long before the time-to-go has become \(0\). Therefore, the average cost under the \((s,S)\) policy must be \(V(s,S)/T(s,S) = \lim_{n\to\infty} V(n, s, S)/T(n, s, S)\). By similar reasoning, \(V(T,S)/T = \lim_{s\to-\infty} V(T, s, S)/T(T, s, S)\).

It is interesting to understand why we can obtain the closed-form expression \(T(q) = q/(\mu-\lambda)\) in (5.6.1), while for the \((s,S)\) and \((T,s,S)\) policies we need an algorithm. The difference is that in the earlier situation⁶⁶So, possibly big steps upward, but only single steps downward. \(T(q) = 1 + \E{T(q+Y-1)}\) while in the case of inventory control, the inventory position can jump down by more than one unit when \(\P{D\geq 2} > 0\). Thus, the behavior of \(v\) and \(T\) just above \(s\) is more complicated. Moreover, in the queueing situation, the queue length can never be negative, while in the inventory situation the level \(I\) can take negative values. As a consequence, the cost function \(L(x)\) is not linear⁷⁷But still convex., hence the idea to substitute \(T(q) = \alpha q + \beta\) and solve for \(\alpha\) and \(\beta\) will not work in general.

Next, we note that deriving a recursive algorithm for the cost under the \((Q,r)\) policy seems not so attractive. To see why, observe that the stopping cost is given by \(V(r, x) = V(r, x + Q)\), that is, it is no longer constant such as \(K\), but dependent on other values of \(v\). Therefore, the simplifying trick that led to (5.9.2) cannot be applied here.

The recursions lead directly to algorithms. We first construct the running-cost function. For a position \(x\), the inventory level has the same distribution as \(x-X\), so we can reuse the procedures developed for the base-stock model.

\begin{algorithm}
\caption{Construct the running-cost function for an inventory model.}
\begin{algorithmic}[1]
\State \textbf{Input:} demand pmf map \(p_D\), lead time \(\leadtime\), costs \(h,b\)
\State \textbf{Output:} running-cost procedure \(L\)
\Procedure{RunningCost}{\(p_D,\leadtime,h,b\)}
    \State \(p_X\gets\pr{Convolution}\rb{p_D,\leadtime}\)
    \Procedure{L}{\(x\)}
        \State \(p_I\gets\pr{Subtract}\rb{\pr{Constant}\rb{x},p_X}\)
        \Return \(\pr{InventoryCost}\rb{p_I,h,b}\)
    \EndProcedure
    \Return \(L\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

Recall from Alg. 1.1.2 that caching speeds up recursive procedures by reusing results for states already visited. The hitting-value procedures use a map \(C\) as the cache and \(\pr{InCache}\rb{C.store}\) to check whether a result is stored. Calling \(C(q)\) for this check would insert an absent key with the default value.

The procedure \(\pr{TsSHittingValue}\) returns the function \(V\) for the \((T,s,S)\) policy.

\begin{algorithm}
\caption{Construct a hitting-value function for a \((T,s,S)\) policy.}
\begin{algorithmic}[1]
\State \textbf{Input:} demand pmf map \(p_D\), running-cost function \(R\), and stopping-cost function \(H\)
\State \textbf{Output:} a hitting-value function \(V\)
\Procedure{TsSHittingValue}{\(p_D,R,H\)}
    \State \(C\gets\pr{Map}()\)
    \State \(\pr{inCache?}\gets\pr{InCache}\rb{C.store}\)
    \Procedure{Stop?}{\(n,s,x\)}
        \Return \(x\leq s\) or \(n=0\)
    \EndProcedure
    \Procedure{V}{\(n,s,x\)}
        \State \(q\gets(n,s,x)\)
        \If{\(\pr{inCache?}\rb{q}\)} \Comment{Reuse a cached value}
            \Return \(C(q)\)
        \EndIf
        \If{\(\pr{Stop?}\rb{n,s,x}\)}
            \State \(C(q)\gets H(x)\)
        \Else
            \State \(C(q)\gets R(x)+\pr{Sum}\rb{\qb{p_D(d)\pr{V}\rb{n-1,s,x-d}:d\in\pr{Keys}\rb{p_D}}}\)
        \EndIf
        \Return \(C(q)\)
    \EndProcedure
    \Return \(V\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

For the \((s,S)\) policy, the recursion does not reduce a time index. We therefore remove the term for \(D=0\) from the sum and divide by \(1-p_D(0)\), as in (5.9.3).

\begin{algorithm}
\caption{Construct a hitting-value function for an \((s,S)\) policy.}
\begin{algorithmic}[1]
\State \textbf{Input:} demand pmf map \(p_D\), running-cost function \(R\), and stopping-cost function \(H\)
\State \textbf{Output:} a hitting-value function \(V\)
\Procedure{sSHittingValue}{\(p_D,R,H\)}
    \State \(C\gets\pr{Map}()\)
    \State \(\pr{inCache?}\gets\pr{InCache}\rb{C.store}\)
    \Procedure{Stop?}{\(s,x\)}
        \Return \(x\leq s\)
    \EndProcedure
    \Procedure{V}{\(s,x\)}
        \State \(q\gets(s,x)\)
        \If{\(\pr{inCache?}\rb{q}\)} \Comment{Reuse a cached value}
            \Return \(C(q)\)
        \EndIf
        \If{\(\pr{Stop?}\rb{s,x}\)}
            \State \(C(q)\gets H(x)\)
        \Else
            \State \(C(q)\gets\dfrac{R(x)+\pr{Sum}\rb{\qb{p_D(d)\pr{V}\rb{s,x-d}:d\in\pr{Keys}\rb{p_D},\ d>0}}}{1-p_D(0)}\)
        \EndIf
        \Return \(C(q)\)
    \EndProcedure
    \Return \(V\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The procedure \(\pr{sSAverageCost}\) provides the direct interface for an \((s,S)\) policy. It uses the hitting-value procedure once with the inventory costs and once with a running cost of one to obtain the expected cycle cost and cycle duration.

\begin{algorithm}
\caption{Compute the long-run average cost of an \((s,S)\) policy.}
\begin{algorithmic}[1]
\State \textbf{Input:} demand pmf map \(p_D\), lead time \(\leadtime\), costs \(h,b,K\), levels \(s,S\)
\State \textbf{Output:} long-run average cost
\Procedure{sSAverageCost}{\(p_D,\leadtime,h,b,K,s,S\)}
    \State \(L\gets\pr{RunningCost}\rb{p_D,\leadtime,h,b}\)
    \State \(V\gets\pr{sSHittingValue}\rb{p_D,L,\lambdafun{x}{K}}\)
    \State \(\tau\gets\pr{sSHittingValue}\rb{p_D,\lambdafun{x}{1},\lambdafun{x}{0}}\)
    \Return \(V(s,S)/\tau(s,S)\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The corresponding interface for a \((T,s,S)\) policy differs only in the hitting-value procedure and its arguments.

\begin{algorithm}
\caption{Compute the long-run average cost of a \((T,s,S)\) policy.}
\begin{algorithmic}[1]
\State \textbf{Input:} demand pmf map \(p_D\), lead time \(\leadtime\), costs \(h,b,K\), levels \(T,s,S\)
\State \textbf{Output:} long-run average cost
\Procedure{TsSAverageCost}{\(p_D,\leadtime,h,b,K,T,s,S\)}
    \State \(L\gets\pr{RunningCost}\rb{p_D,\leadtime,h,b}\)
    \State \(V\gets\pr{TsSHittingValue}\rb{p_D,L,\lambdafun{x}{K}}\)
    \State \(\tau\gets\pr{TsSHittingValue}\rb{p_D,\lambdafun{x}{1},\lambdafun{x}{0}}\)
    \Return \(V(T,s,S)/\tau(T,s,S)\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The \((T,S)\) policy follows by taking \(s=-\infty\) in \(\pr{TsSAverageCost}\).

The two hitting-value procedures above have the same basic structure. Each accepts a running-value function \(R\) and a stopping-value function \(H\). With \(R=L\) and \(H(x)=K\), the returned procedure computes the expected cost until stopping. With \(R(x)=1\) and \(H(x)=0\), it computes the expected time until stopping. The average-cost procedures divide the first quantity by the second.

The policies differ in their stopping rules. For the \((T,s,S)\) policy, the process stops when \(x\leq s\) or \(n=0\). For the \((s,S)\) policy, it stops when \(x\leq s\). Moreover, because \(D\) can be zero, the latter recursion contains \(V(s,x)\) on both sides. Isolating this term produces the factor \(1-p_D(0)\) in (5.9.3).

An important point is that \(\pr{TsSHittingValue}\) and \(\pr{sSHittingValue}\) return an inner procedure \(V\), rather than a number. This procedure retains access to \(p_D\), \(R\), \(H\), and the cache \(C\) created by the enclosing procedure. Only when we call \(V(T,s,S)\) or \(V(s,S)\) do we obtain a numerical value. Thus, \(V\) is a closure; see for a simpler example.

Let us examine a few numerical examples.

We can check that for \(T\) large, the \((T,s,S)\) policy and the \((s,S)\) have the same average cost.

For the \((T,S)\) policy, setting \(T\) to a large value is costly, as expected.

For the Lighthouse Company case, take \(s=16\) and \(S=20\). For the \((s,S)\) policy, the algorithms give the following cycle statistics and long-run average cost.

For the \((T,s,S)\) policy, the average cost approaches that of the \((s,S)\) policy as \(T\) increases.

For the \((T,S)\) policy, taking \(T\) too large is costly, as expected.

\begin{algorithm}
\begin{algorithmic}[1]
\State \(V_{sS}\gets\pr{sSHittingValue}\rb{p_D,L,\lambdafun{x}{K}}\)
\State \(V_{TS}\gets\pr{TsSHittingValue}\rb{p_D,L,\lambdafun{x}{K}}\)
\end{algorithmic}

\end{algorithm}

\begin{algorithm}
\begin{algorithmic}[1]
\Procedure{V}{\(s,x\)}
    \If{\(x\leq s\)}
        \Return \(K\)
    \EndIf
    \Return \(L(x)+\pr{Sum}\rb{\qb{p_D(d)\pr{V}\rb{s,x-d}:d\in\pr{Keys}\rb{p_D},\ d>0}}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}