CaltechAUTHORS
Published August 2009 | Version public
Journal Article Metadata-only

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

Creators

  • 1. ROR icon Massachusetts Institute of Technology
  • 2. ROR icon Hebrew University of Jerusalem
  • 3. ROR icon Northwestern University
  • 4. ROR icon California Institute of Technology

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

Identifiers

Eprint ID
15802
Resolver ID
CaltechAUTHORS:20090911-153600795

Funding

Office of Naval Research
N00014-95-1-0232
Office of Naval Research
N00014-01-1-0146
NSF
DMI-0085683
NSF
DMI-0245352
NASA
Office of Naval Research
N000140810029
NSF
CMMI-0758069

Dates

Created
2009-09-29
Created from EPrint's datestamp field
Updated
2021-11-08
Created from EPrint's last_modified field