Multi-item lot-sizing with a joint set-up cost

Shoshana Anily, Michal Tzur and Laurence A. Wolsey

No 2005070, LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE)

Abstract: We consider a multi-item lot-sizing problem in which there are demands, and unit production and storage costs. In addition production of any mix of items is measured in batches of fixed size, and there is a fixed set-up cost per batch in each period. Suppose that the unit production costs are constant over time, the storage costs are nonnegative, and for any two items the one that has a higher storage cost in one period has a higher storage cost in every period. Then we show that there is a linear program with O(mTexp.2) constraints and variables that solves the multi-item lot-sizing problem, thereby establishing that it is polynomially solvable, wheremis the number of items and T the number of time periods. This generalizes an earlier result of Anily and Tzur who presented a O(mTexp.m+5) dynamic programming algorithm for essentially the same problem. Under additional conditions, a similar linear programming result is shown to hold in the presence of backlogging when the batch size is arbitrarily large. Brief computational results on two instances with varying batch sizes are presented and discussed.

Keywords: multi-item lot-sizing; joint set-up cost; convex hull; extended formulation; mixed integer programming (search for similar items in EconPapers)
Date: 2005-10
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://sites.uclouvain.be/core/publications/coredp/coredp2005.html (text/html)

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:cor:louvco:2005070

Access Statistics for this paper

More papers in LIDAM Discussion Papers CORE from Université catholique de Louvain, Center for Operations Research and Econometrics (CORE) Voie du Roman Pays 34, 1348 Louvain-la-Neuve (Belgium). Contact information at EDIRC.
Bibliographic data for series maintained by Alain GILLIS ().