This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Teo, C.-P. Articles by Bertsimas, D. Search for Related Content

Multistage Lot Sizing Problems via Randomized Rounding

Department of Decision Sciences, Faculty of Business Administration, National University of Singapore
Sloan School of Management and Operations Research Center, MIT, Cambridge, Massachusetts 02139
fbateocp{at}nus.edu.sg
dbertsim{at}mit.edu

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.

Subject classifications: Production/scheduling: lot sizing; Programming/integer: randomized rounding.
History: Received January 1999; revision received March 2000; accepted June 2000.

This article has been cited by other articles:

				C.-P. Teo and J. Shu Warehouse-Retailer Network Design Problem Operations Research, May 1, 2004; 52(3): 396 - 408. [Abstract] [PDF]