Improved Algorithms for Inventory and Replacement-Stocking Problems

This paper is devoted to improving known schemes for computing optimal policies in stochastic decision problems. Improved procedures are developed for computing optimal $( s,S)$ policies in the convex inventory problem with set-up cost. A more efficient algorithm is also developed for a joint replacement and stocking problem. Stopping rule theory is used to exploit the known structure of an optimal policy for each problem. Improved algorithms are obtained through the analysis of stopping problems imbedded in the inventory and replacement-stocking problems. The inventory and replacement-stocking problems which we consider are known to have optimal policies of simple structure. Taking advantage of this structure, we use stopping rule theory to construct algorithms for the computation of such policies. In § 1 some known results from stopping rule theory are introduced. We use these results in § 2 to improve Veinott and Wagner’s algorithm [7] for optimal $( s,S)$ policies in inventory problems with set-up costs. The remainder of this paper is devoted to Derman and Lieberman’s replacement-stocking problem [3] described in § 3. Our algorithm is presented in § 4.