Approximation algorithms for capacitated stochastic inventory systems with setup costs
We develop the first approximation algorithm with worst-case performance guarantee for capacitated stochastic periodic-review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is a...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Wiley Blackwell
2017
|
| Online Access: | http://hdl.handle.net/1721.1/109090 https://orcid.org/0000-0002-1994-4875 |
| _version_ | 1811094768821731328 |
|---|---|
| author | Shi, Cong Zhang, Huanan Chao, Xiuli Levi, Retsef |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Shi, Cong Zhang, Huanan Chao, Xiuli Levi, Retsef |
| author_sort | Shi, Cong |
| collection | MIT |
| description | We develop the first approximation algorithm with worst-case performance guarantee for capacitated stochastic periodic-review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near-optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst-case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst-case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. |
| first_indexed | 2024-09-23T16:04:48Z |
| format | Article |
| id | mit-1721.1/109090 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:04:48Z |
| publishDate | 2017 |
| publisher | Wiley Blackwell |
| record_format | dspace |
| spelling | mit-1721.1/1090902022-10-02T06:14:35Z Approximation algorithms for capacitated stochastic inventory systems with setup costs Shi, Cong Zhang, Huanan Chao, Xiuli Levi, Retsef Sloan School of Management Levi, Retsef We develop the first approximation algorithm with worst-case performance guarantee for capacitated stochastic periodic-review inventory systems with setup costs. The structure of the optimal control policy for such systems is extremely complicated, and indeed, only some partial characterization is available. Thus, finding provably near-optimal control policies has been an open challenge. In this article, we construct computationally efficient approximate optimal policies for these systems whose demands can be nonstationary and/or correlated over time, and show that these policies have a worst-case performance guarantee of 4. We demonstrate through extensive numerical studies that the policies empirically perform well, and they are significantly better than the theoretical worst-case guarantees. We also extend the analyses and results to the case with batch ordering constraints, where the order size has to be an integer multiple of a base load. National Science Foundation (U.S.) (CMMI-1362619) National Science Foundation (U.S.) (CMMI-1131249) National Science Foundation (U.S.) (DMS-0732175) National Science Foundation (U.S.) (CMMI-0846554) National Science Foundation (U.S.) (FA9550-08-1–0369) 2017-05-16T13:44:29Z 2017-05-16T13:44:29Z 2014-06 2014-03 Article http://purl.org/eprint/type/JournalArticle 0894-069X 1520-6750 http://hdl.handle.net/1721.1/109090 Shi, Cong; Zhang, Huanan; Chao, Xiuli and Levi, Retsef. “Approximation Algorithms for Capacitated Stochastic Inventory Systems with Setup Costs.” Naval Research Logistics (NRL) 61, no. 4 (April 2014): 304–319. © 2014 Wiley Periodicals, Inc. https://orcid.org/0000-0002-1994-4875 en_US http://dx.doi.org/10.1002/nav.21584 Naval Research Logistics (NRL) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Wiley Blackwell Other univ. web domain |
| spellingShingle | Shi, Cong Zhang, Huanan Chao, Xiuli Levi, Retsef Approximation algorithms for capacitated stochastic inventory systems with setup costs |
| title | Approximation algorithms for capacitated stochastic inventory systems with setup costs |
| title_full | Approximation algorithms for capacitated stochastic inventory systems with setup costs |
| title_fullStr | Approximation algorithms for capacitated stochastic inventory systems with setup costs |
| title_full_unstemmed | Approximation algorithms for capacitated stochastic inventory systems with setup costs |
| title_short | Approximation algorithms for capacitated stochastic inventory systems with setup costs |
| title_sort | approximation algorithms for capacitated stochastic inventory systems with setup costs |
| url | http://hdl.handle.net/1721.1/109090 https://orcid.org/0000-0002-1994-4875 |
| work_keys_str_mv | AT shicong approximationalgorithmsforcapacitatedstochasticinventorysystemswithsetupcosts AT zhanghuanan approximationalgorithmsforcapacitatedstochasticinventorysystemswithsetupcosts AT chaoxiuli approximationalgorithmsforcapacitatedstochasticinventorysystemswithsetupcosts AT leviretsef approximationalgorithmsforcapacitatedstochasticinventorysystemswithsetupcosts |