Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published August 2009 | public
Journal Article

A Fully Polynomial-Time Approximation Scheme for Single-Item Stochastic Inventory Control with Discrete Demand

Abstract

The single-item stochastic inventory control problem is to find an inventory replenishment policy in the presence of independent discrete stochastic demands under periodic review and finite time horizon. In this paper, we prove that this problem is intractable and design for it a fully polynomial-time approximation scheme.

Additional Information

Copyright © 2009 by INFORMS. Received March 10, 2006; revised July 23, 2007, June 30, 2008, and March 3, 2009. Published online in Articles in Advance August 6, 2009. The authors thank the referees for their detailed comments, which helped us to improve the presentation of this paper considerably. They thank Retsef Levi for pointing out that our original proof of #P-hardness for stochastic inventory control also implies the #P-hardness of evaluating cdfs for convolutions of discrete variables. Last, the authors thank Oded Goldreich for inspiring discussions and Leslie Ann Goldberg for pointing out references. The first, second, third, and fifth authors were supported by ONR Contracts N00014-95-1-0232 and N00014-01-1-0146; NSF Contracts DMI-0085683 and DMI-0245352; and by the NASA interplanetary supply chain and logistics architectures project. The fourth author was supported in part by ONR Grant N000140810029. The first, fourth, and fifth authors were also supported by NSF Contract CMMI-0758069. MSC2000 subject classification: Primary: 90B05, 90C39, 68W25; secondary: 90C15, 90C25, 49M25 OR/MS subject classification: Primary: inventory/production; approximations/heuristics; secondary: production/scheduling; approximations/heuristics

Additional details

Created:
August 21, 2023
Modified:
October 19, 2023