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

被引：44

作者：

Halman, Nir ^{[1
,2
]}

Klabjan, Diego ^{[3
]}

Mostagir, Mohamed ^{[4
]}

Orlin, Jim ^{[5
]}

Simchi-Levi, David ^{[1
]}

机构：

[1] MIT, Dept Civil & Environm Engn, Cambridge, MA 02139 USA

[2] Hebrew Univ Jerusalem, Sch Business Adm, IL-91905 Jerusalem, Israel

[3] Northwestern Univ, Dept Ind & Management Sci, Evanston, IL 60208 USA

[4] CALTECH, Div Humanities & Social Sci, Pasadena, CA 91125 USA

[5] MIT, Alfred P Sloan Sch Management, Cambridge, MA 02139 USA

来源：

MATHEMATICS OF OPERATIONS RESEARCH | 2009年 / 34卷 / 03期

基金：

美国国家科学基金会;

关键词：

stochastic inventory management; approximation algorithms; stochastic dynamic programming; ALGORITHM; POLICIES;

D O I：

10.1287/moor.1090.0391

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：674 / 685

页数：12

共 26 条

[11] Provably near-optimal sampling-based policies for stochastic inventory control models [J].

Levi, Retsef ;

Roundy, Robin O. ;

Shmoys, David B. .

MATHEMATICS OF OPERATIONS RESEARCH, 2007, 32 (04) :821-839

[12] Approximation Algorithms for Capacitated Stochastic Inventory Control Models [J].

Levi, Retsef ;

Roundy, Robin O. ;

Shmoys, David B. ;

Truong, Van Anh .

OPERATIONS RESEARCH, 2008, 56 (05) :1184-1199

[13] On the number of Eulerian orientations of a graph [J].

Mihail, M ;

Winkler, P .

ALGORITHMICA, 1996, 16 (4-5) :402-414

[14]

Porteus E.L., 2002, Foundations of stochastic inventory theory

[15]

Preparata FP, 1985, COMPUTATIONAL GEOMET

[16] On the hardness of approximate reasoning [J].

Roth, D .

ARTIFICIAL INTELLIGENCE, 1996, 82 (1-2) :273-302

[17] Heuristic computation of periodic-review base stock inventory policies [J].

Roundy, RO ;

Muckstadt, JA .

MANAGEMENT SCIENCE, 2000, 46 (01) :104-109

[18]

Safer HM, 1995, 375795 SLOAN SCH MAN

[19] An approximation scheme for stochastic linear programming and its application to stochastic integer programs [J].

Shmoys, David B. ;

Swamy, Chaitanya .

JOURNAL OF THE ACM, 2006, 53 (06) :978-1012

[20]

Simchi-Levi D, 2005, LOGIC LOGISTICS THEO

← 1 2 3 →