Multistage lot sizing problems via randomized rounding
成果类型：
Article
署名作者：
Teo, CP; Bertsimas, D
署名单位：
National University of Singapore; Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT)
刊物名称：
OPERATIONS RESEARCH
ISSN/ISSBN：
0030-364X
DOI：
10.1287/opre.49.4.599.11222
发表日期：
2001
页码：
599-608
关键词：
摘要：
We study the classical multistage lot sizing problem that arises in distribution and inventory systems. A celebrated result in this area is the 94% and 98% approximation guarantee provided by power-of-two policies. In this paper, we propose a simple randomized rounding algorithm to establish these performance bounds. We use this new technique to extend several results for the capacitated lot sizing problems to the case with submodular ordering cost. For the joint replenishment problem under a fixed base period model, we construct a 95.8% approximation algorithm to the (possibly dynamic) optimal lot sizing policy. The policies constructed are stationary but not necessarily of the power-of-two type. This shows that for the fixed based planning model, the class of stationary policies is within 95.8% of the optimum, improving on the previously best known 94% approximation guarantee.