Approximation algorithms for capacitated stochastic inventory systems with setup costs

Cong Shi, Huanan Zhang, Xiuli Chao, Retsef Levi

Research output: Contribution to journalArticlepeer-review

15 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)304-319
Number of pages16
JournalNaval Research Logistics
Issue number4
StatePublished - Jun 2014

All Science Journal Classification (ASJC) codes

  • Modeling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'Approximation algorithms for capacitated stochastic inventory systems with setup costs'. Together they form a unique fingerprint.

Cite this