We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
LOT-SIZING WITH CONSTANT BATCHES: FORMULATION AND VALID INEQUALITIES.
- Authors
Pochet, Yves; Wolsey, Laurence A.
- Abstract
We 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). We first show that the classical dynamic program for LCC simplifies for LCB leading to an O(n² min{n, C}) algorithm (where n is the number of periods and C the batch size). Using this new algorithm, we show how to formulate both problems as linear programs with O(n³) variables and constraints. A class of so-called (k, 1, S, I) inequalities are described for LCB which capture both the dynamic nature of the problem as well as the capacity aspects. For LCB, we prove that these inequalities are the only facet-defining inequalities of a certain form. For LCC, we show that these inequalities include all the known classes of valid inequalities. Finally, we discuss several open questions and possible extensions.
- Subjects
ECONOMIC lot size; POLYHEDRA; LINEAR programming; SOLID geometry; INTEGER programming; DYNAMIC programming; MATHEMATICAL optimization; ALGORITHMS
- Publication
Mathematics of Operations Research, 1993, Vol 18, Issue 4, p767
- ISSN
0364-765X
- Publication type
Article
- DOI
10.1287/moor.18.4.767