Please use this identifier to cite or link to this item: http://scholarbank.nus.edu.sg/handle/10635/44894
Title: Multistage lot sizing problems via randomized rounding
Authors: Teo, C.-P. 
Bertsimas, D.
Issue Date: 2001
Source: Teo, C.-P.,Bertsimas, D. (2001). Multistage lot sizing problems via randomized rounding. Operations Research 49 (4) : 599-608. ScholarBank@NUS Repository.
Abstract: 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.
Source Title: Operations Research
URI: http://scholarbank.nus.edu.sg/handle/10635/44894
ISSN: 0030364X
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

Page view(s)

72
checked on Dec 15, 2017

Google ScholarTM

Check


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.