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

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.