Lot-sizing with constant batches: Formulation and valid inequalities

Lot-sizing with constant batches: Formulation and valid inequalities

0.00 Avg rating0 Votes
Article ID: iaor1994908
Country: United States
Volume: 18
Issue: 4
Start Page Number: 767
End Page Number: 785
Publication Date: Nov 1993
Journal: Mathematics of Operations Research
Authors: ,
Keywords: lot sizing
Abstract:

The authors consider the classical lot-sizing problem with constant production capacities (LCC) and a variant in which the capacity in each period is an integer multiple of some basic batch size (LCB). They first show that the classical dynamic program for LCc simplifies for LCB leading to an O(n2min{n,C}) algorithm (where n is the number of periods and C the batch size). Using this new algorithm, the authors show how to formulate both problems as linear programs with O(n3) variables and constraints. A class of so-called (k,l,S,I) inequalities are described for LCB which capture both the dynamic nature of the problem as well as the capacity aspects. For LCB, they prove that these inequalities are the only facet-defining inequalities of a certain form. For LCC, the authors show that these inequalities include all the known classes of valid inequalities. Finally, they discuss several open questions and possible extensions.

Reviews

Required fields are marked *. Your email address will not be published.