Approximation Algorithms for the Stochastic Lot-Sizing Problem with Order Lead Times

• 成果类型: Article
• 署名作者: Levi, Retsef; Shi, Cong
• 署名单位: Massachusetts Institute of Technology (MIT); University of Michigan System; University of Michigan
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2013.1162
• 发表日期: 2013
• 页码: 593-602
• 关键词: inventory control-models; efficient algorithm; s policies; demand; randomization; optimality; systems

摘要

We develop new algorithmic approaches to compute provably near-optimal policies for multiperiod stochastic lot-sizing inventory models with positive lead times, general demand distributions, and dynamic forecast updates. The policies that are developed have worst-case performance guarantees of 3 and typically perform very close to optimal in extensive computational experiments. The newly proposed algorithms employ a novel randomized decision rule. We believe that these new algorithmic and performance analysis techniques could be used in designing provably near-optimal randomized algorithms for other stochastic inventory control models and more generally in other multistage stochastic control problems.