Approximation algorithms for capacitated stochastic inventory systems with setup costs. (11th April 2014)

• Record Type: Journal Article
• Authors: Shi, Cong; Zhang, Huanan; Chao, Xiuli; Levi, Retsef
• Is Part Of: Naval research logistics. Volume 61:Number 4(2014:Jun.)
• Page Start: 304
• Page End: 319
• Publication Date: 2014-04-11
• Subjects: inventory -- setup cost -- capacity -- approximation algorithms -- bounds -- randomized cost‐balancing -- worst‐case performance guarantees; Logistics, Naval -- Periodicals; Supplies and stores -- Periodicals; 359.07
• DOI: 10.1002/nav.21584
• Languages: English
• ISSNs: 0894-069X

Abstract

Abstract: We develop the first approximation algorithm with worst‐case performance guarantee for capacitated stochastic periodic‐review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near‐optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst‐case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst‐case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. © 2014 Wiley Periodicals, Inc. Naval Research Logistics 61: 304–319, 2014