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 条

[1] Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity [J].

Dean, Brian C. ;

Goemans, Michel X. ;

Vondrak, Jan .

MATHEMATICS OF OPERATIONS RESEARCH, 2008, 33 (04) :945-964

[2] Approximately counting Hamilton paths and cycles in dense graphs [J].

Dyer, M ;

Frieze, A ;

Jerrum, M .

SIAM JOURNAL ON COMPUTING, 1998, 27 (05) :1262-1272

[3] The relative complexity of approximate counting problems [J].

Dyer, M ;

Goldberg, LA ;

Greenhill, C ;

Jerrum, M .

ALGORITHMICA, 2004, 38 (03) :471-500

[4]

DYER M., 2003, Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, P693

[5] AN EFFICIENT ALGORITHM FOR COMPUTING OPTIMAL (S,S) POLICIES [J].

FEDERGRUEN, A ;

ZIPKIN, P .

OPERATIONS RESEARCH, 1984, 32 (06) :1268-1285

[6] COMPUTATIONAL ISSUES IN AN INFINITE-HORIZON, MULTIECHELON INVENTORY MODEL [J].

FEDERGRUEN, A ;

ZIPKIN, P .

OPERATIONS RESEARCH, 1984, 32 (04) :818-836

[7]

Garey M. R., 1979, COMPUTERS INTRACTABI

[8] A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries [J].

Jerrum, M ;

Sinclair, A ;

Vigoda, E .

JOURNAL OF THE ACM, 2004, 51 (04) :671-697

[9] APPROXIMATING THE PERMANENT [J].

JERRUM, M ;

SINCLAIR, A .

SIAM JOURNAL ON COMPUTING, 1989, 18 (06) :1149-1178

[10] Approximation algorithms for Stochastic inventory control models [J].

Levi, Retsef ;

Pal, Martin ;

Roundy, Robin O. ;

Shmoys, David B. .

MATHEMATICS OF OPERATIONS RESEARCH, 2007, 32 (02) :284-302

← 1 2 3 →