Approximating the Nonlinear Newsvendor and Single-Item Stochastic Lot-Sizing Problems When Data Is Given by an Oracle

Nir Halman (), James B. Orlin () and David Simchi-Levi ()
Additional contact information
Nir Halman: Jerusalem School of Business Administration, The Hebrew University, 91905 Jerusalem, Israel; Department of Civil and Environmental Engineering, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
James B. Orlin: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
David Simchi-Levi: Department of Civil and Environmental Engineering and Division of Engineering Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139

Operations Research, 2012, vol. 60, issue 2, 429-446

Abstract: The single-item stochastic lot-sizing problem is to find an inventory replenishment policy in the presence of discrete stochastic demands under periodic review and finite time horizon. A closely related problem is the single-period newsvendor model. It is well known that the newsvendor problem admits a closed formula for the optimal order quantity whenever the revenue and salvage values are linear increasing functions and the procurement (ordering) cost is fixed plus linear. The optimal policy for the single-item lot-sizing model is also well known under similar assumptions.In this paper we show that the classical (single-period) newsvendor model with fixed plus linear ordering cost cannot be approximated to any degree of accuracy when either the demand distribution or the cost functions are given by an oracle. We provide a fully polynomial time approximation scheme for the nonlinear single-item stochastic lot-sizing problem, when demand distribution is given by an oracle, procurement costs are provided as nondecreasing oracles, holding/backlogging/disposal costs are linear, and lead time is positive. Similar results exist for the nonlinear newsvendor problem. These approximation schemes are designed by extending the technique of K -approximation sets and functions.

Keywords: stochastic inventory control; hardness results; fully polynomial time approximation schemes (search for similar items in EconPapers)
Date: 2012
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1110.1031 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:60:y:2012:i:2:p:429-446

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().