Approximation Algorithms for Capacitated Stochastic Inventory Control Models

Retsef Levi (), Robin O. Roundy (), David B. Shmoys () and Truong Van Anh ()
Additional contact information
Retsef Levi: Sloan School of Management, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139
Robin O. Roundy: Mission Church of Jesus Christ of Latter Day Saints Apartado Aereo, Barranquilla, Colombia
David B. Shmoys: School of Operations Research and Information Engineering, and Department of Computer Science, Cornell University, Ithaca, New York 14853
Truong Van Anh: Fixed Income, Global Modelling, and Analytics Group, Credit Suisse Securities, New York, New York 10010

Operations Research, 2008, vol. 56, issue 5, 1184-1199

Abstract: We develop the first algorithmic approach to compute provably good ordering policies for a multiperiod, capacitated, stochastic inventory system facing stochastic nonstationary and correlated demands that evolve over time. Our approach is computationally efficient and guaranteed to produce a policy with total expected cost no more than twice that of an optimal policy. As part of our computational approach, we propose a novel scheme to account for backlogging costs in a capacitated, multiperiod environment. Our cost-accounting scheme, called the forced marginal backlogging cost-accounting scheme , is significantly different from the period-by-period accounting approach to backlogging costs used in dynamic programming; it captures the long-term impact of a decision on system performance in the presence of capacity constraints. In the likely event that the per-unit order costs are large compared to the holding and backlogging costs, a transformation of cost parameters yields a significantly improved guarantee. We also introduce new semimyopic policies based on our new cost-accounting scheme to derive bounds on the optimal base-stock levels. We show that these bounds can be used to effectively improve any policy. Finally, empirical evidence is presented that indicates that the typical performance of this approach is significantly stronger than these worst-case guarantees.

Keywords: stochastic inventory control; heuristics; approximation algorithms (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (28)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.1080.0580 (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:56:y:2008:i:5:p:1184-1199

Access Statistics for this article

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