Multistage Lot Sizing Problems via Randomized Rounding

Chung-Piaw Teo () and Dimitris Bertsimas ()
Additional contact information
Chung-Piaw Teo: Department of Decision Sciences, Faculty of Business Administration, National University of Singapore
Dimitris Bertsimas: Sloan School of Management and Operations Research Center, MIT, Cambridge, Massachusetts 02139

Operations Research, 2001, vol. 49, issue 4, 599-608

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.

Keywords: Production/scheduling: lot sizing; Programming/integer: randomized rounding (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (5)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.4.599.11222 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:4:p:599-608

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().