5.8 Analytic Results for the \((Q,r)\) Policy

In this section, we extend the analysis of a single-item inventory system under a base-stock policy to a \((Q,r)\) inventory system.

There is a convenient way to relate the \((Q,r)\) system to a number of base-stock systems. To see this, imagine two animals, a squirrel that observes the \((Q,r)\) system at the end of each demand period, and a bear that only wakes up when the inventory position right at the start of the interval equals some fixed \(i\), where \(i\) must lie in the set \(\{r+1, \ldots r+Q\}\); if not, the bear hibernates. Clearly, from the bear’s point of view, the system behaves as a base-stock system with order-up-to level \(i\), because whenever the bear wakes, the inventory position is \(i\), and the position just before the bear falls asleep is \(i-D\). More generally, we can associate a different bear with each position in the set \(\{r+1, \ldots r+Q\}\), so exactly one bear is awake at any time. To combine the statistics observed by the bears and the statistics observed by the squirrel, we need, for each \(i\), the long-run fraction of periods in which the inventory position \(\IP\) equals \(i\). For instance, if the squirrel knows¹¹We assume that the limit over all sample paths \(\{\IP_{k}\}\) exists almost surely, so that we can invoke the strong law of large numbers.

\begin{equation*} p(i) = \lim_{T\to \infty} \frac{1}{T} \sum_{k=1}^{T}\1{\IP_k = i}, \end{equation*}

for all \(i\in \{r+1, \ldots, r+Q\}\), then it can retrieve the ready rate \(\sum_{i=r+1}^{Q+r} p(i) \alpha(i)\) from the ready rate \(\alpha(i)\) observed by the bear with order-up-to level \(i\).²²We label the ready rate of the base-stock model by the order-up-to level.

Proof

For simplicity take \(Q=3, r=0\), so that the inventory position \(\IP\) cycles between the levels \(1, 2\) and \(3\).³³The proof is the same for general \(Q\) and \(r\), but needs a bit more notation. We apply level-crossing arguments, as follows. Write \(f_{i} = \P{D\in \{i, i+3, i+6, \ldots\}}\) for the probability that the period demand equals a multiple of \(3\) plus \(i\), \(i=0, 1, 2\). Suppose that, at the start of period \(k\), the position \(\IP_{k} = 3\). Since we order in multiples of \(Q=3\), the probability \(\P{\IP_{k+1} =3|\IP_{k}=3} = f_{0}\), i.e., equal to the probability that \(D_{k}\) is a multiple of \(3\). Likewise, \(\P{\IP_{k+1} = 2|\IP_k=3} = f_{1}\), and \(\P{\IP_{k+1} = 1|\IP_k=3} = f_{2}\). Next, since we again order in multiples of \(Q\), \(\P{\IP_{k+1} = 1|\IP_k=2} = f_{1}\), and similarly for the other possibilities. Therefore, we can use level crossing to conclude that in the long run, \((f_{1}+f_2)p(3) = f_1p(2) + f_2 p(1)\). However, because of the \((Q,r)\) ordering rule, we can cyclically change \(p(1), p(2)\) and \(p(3)\) in this equality. By symmetry, the only possible solution is \(p(i) = 1/3\) for all \(i\).

For the second claim, condition on the inventory position. When \(\IP = i\), the system behaves as a base-stock system with order-up-to level \(i\), so by Th. 5.7.3, the conditional rv \(\IL \mid \IP = i \sim i - X\). Since \(\IP\) and \(X\) are independent (the position depends on past demands, while \(X\) is the lead-time demand over future periods), it follows that \(\IL \sim \IP - X\).

With the above theorem the ready rate for the \((Q,r)\) model can be computed with the formula

\begin{align*} \alpha = \frac1Q \sum_{i=r+1}^{r+Q} \alpha(i) = \frac{1}{Q} \sum_{i=r+1}^{r+Q} \P{X+D\leq i}, \tag{5.8.1} \end{align*}

where \(\alpha(i)\) is the ready rate of the base-stock model with reorder level \(i\).

For the average inventory level, we write \(I(i)\) for the inventory level of the base-stock model with order-up-to level \(i\), and get

\begin{align*} \E{I} &= \frac1Q\sum_{i=r+1}^{r+Q} \E{I(i)} = \frac1Q\sum_{i=r+1}^{r+Q} (i - \E X) = \frac{Q+1}2 + r - \E X. \end{align*}

The expected number of backorders \(\E{I^-}\) and expected on-hand inventory \(\E{I^+}\) can be found by equivalent summations:

\begin{align*} \E{I^{+}} &= \frac1Q\sum_{i=r+1}^{r+Q} \E{I^{+}(i)}, & \E{I^{-}} &= \frac1Q\sum_{i=r+1}^{r+Q} \E{I^{-}(i)}, \end{align*}

using (5.7.3) and (5.7.4) of the base-stock model.

Finally, with \(h\) and \(b\) the holding and backorder cost per item per period, the total average cost becomes

\begin{equation*} c(Q,r) = K\frac{\E D}{Q} + h \E{I^{+}} + b \E{I^-}. \end{equation*}

With regard to the first term, note that \(\E D\) is the average demand per period, so \(\E D / Q\) is the order frequency.

It remains to find optimal values for \(r\) and \(Q\). Fast algorithms exist to compute optimal \(r\) and \(Q\), but we omit this. A simple workaround is to perform a complete grid search over a reasonable set of pairs of \(r\) and \(Q\). Another simple heuristic is to use the EOQ⁴⁴See Exercise 7, and set \(d=\E D\). formula to set \(Q = \sqrt{2\E{D}K/h}\) and then search for \(r\) such that the total average cost is minimal.⁵⁵For that value of \(Q\)!

With similar methods we can search for an \(r\) such that the \(\alpha\) or \(\beta\) service level criteria are met.

The cost is the sum of the ordering cost and the inventory cost.

\begin{algorithm}
\caption{Compute the average cost of a \((Q,r)\) policy.}
\begin{algorithmic}[1]
\State \textbf{Input:} inventory and demand pmf maps \(p_I,p_D\), costs \(h,b,K\), order size \(Q\)
\State \textbf{Output:} average cost
\Procedure{QRCost}{\(p_I,p_D,h,b,K,Q\)}
    \State \(c_{\mathrm{order}}\gets K\,\pr{Mean}\rb{p_D}/Q\)
    \State \(c_{\mathrm{inventory}}\gets\pr{InventoryCost}\rb{p_I,h,b}\)
    \Return \(c_{\mathrm{order}}+c_{\mathrm{inventory}}\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

The procedure \(\pr{EvaluateQR}\) implements the preceding formulas. It uses Th. 5.8.1 to construct the uniform pmf of the inventory position and then reuses the procedures developed for the base-stock model.

\begin{algorithm}
\caption{Compute the performance of a \((Q,r)\) policy.}
\begin{algorithmic}[1]
\State \textbf{Input:} demand pmf map \(p_D\), lead time \(\leadtime\), costs \(h,b,K\), and policy parameters \(Q,r\)
\State \textbf{Output:} ready rate \(\alpha\), fill rate \(\beta\), and average cost \(c\)
\Procedure{EvaluateQR}{\(p_D,\leadtime,h,b,K,Q,r\)}
    \State \(p_X\gets\pr{Convolution}\rb{p_D,\leadtime}\)
    \State \(p_{\IP}\gets\pr{Map}()\)
    \For{\(i=r+1,\ldots,r+Q\)}
        \State \(p_{\IP}(i)\gets1/Q\)
    \EndFor
    \State \(p_I\gets\pr{Subtract}\rb{p_{\IP},p_X}\)
    \State \(\alpha\gets\pr{ReadyRate}\rb{p_I,p_D}\)
    \State \(\beta\gets\pr{FillRate}\rb{p_I,p_D}\)
    \State \(c\gets\pr{QRCost}\rb{p_I,p_D,h,b,K,Q}\)
    \Return \(\alpha,\beta,c\)
\EndProcedure
\end{algorithmic}

\end{algorithm}

For the Lighthouse Company case of Section 2.5, we compute the performance of a \((Q,r)\) policy with the above formulas and the algorithms of Section 1.4. To select the policy parameters, we apply the general grid-search algorithm of Alg. 2.5.2 to the exact cost \(c(Q,r)\).

\begin{algorithm}
\caption{Find a low-cost \((Q,r)\) policy for the Lighthouse Company.}
\begin{algorithmic}[1]
\State \textbf{Input:} policy cost function \(c(Q,r)\)
\State \textbf{Output:} best \((Q,r)\) on the specified grid and its cost
\State \(G\gets\qb{(Q,r):Q\in\qb{1,\ldots,30},\ r\in\qb{-5,\ldots,15}}\)
\State \(\mathit{qr\_cost}\gets\lambdafun{(Q,r)}{c(Q,r)}\)
\State \((Q^\star,r^\star),c^\star\gets
       \pr{GridSearch}\rb{\mathit{qr\_cost},G}\)
\Return \((Q^\star,r^\star),c^\star\)
\end{algorithmic}

\end{algorithm}

For every displayed value of \(Q\), the table gives the value of \(r\) with the lowest cost in the grid, together with the resulting ready rate, fill rate, and average cost.

\(Q\)	\(r\)	\(\alpha(Q,r)\)	\(\beta(Q,r)\)	\(c(Q,r)\)
16	5	0.899	0.906	14.003
17	5	0.905	0.911	13.864
18	5	0.911	0.916	13.777
19	5	0.915	0.921	13.734
20	5	0.920	0.925	13.729
21	5	0.923	0.928	13.756
22	5	0.927	0.931	13.811
23	5	0.930	0.934	13.890
24	4	0.905	0.909	13.972

Over the entire grid, the lowest cost is attained at \((Q^\star,r^\star)=(20,5)\), with \(c^\star\approx13.73\).