Laurence
A. Wolsey
Title:
Multi-item lot-sizing with joint set-up cost
Abstract:
We consider a multi-item lot-sizing problem with joint set-up
costs and constant capacities. Apart from the usual per unit
production and storage costs for each item, a set-up cost is
incurred for each batch of production, where a batch may include
any quantity composition of items of up to $C$ units. In addition, an
upper bound on the number of batches may be employed.
Under widely applicable conditions on the storage costs, namely
that the production and storage costs are nonspeculative, and for any
two items
the one that has a higher storage cost in one period has a higher
storage cost in every
period,
we show that there is a linear program with $O(mT^2)$
constraints and variables that solves the joint set-up multi-item
lot-sizing problem,
where $m$ is the number of items and $T$ the number of time
periods. This establishes
that under the above storage cost conditions this problem is
polynomially solvable and resolves a
long standing open question concerning its complexity.
A similar linear programming result is shown to hold in the
presence of backlogging under more restrictive conditions on the
storage and backlogging costs and when the capacity/batch size is
arbitrarily large.
Computational results are presented to test the effectiveness of
using these tight linear programs in strengthening the basic mixed
integer programming formulations of the joint set-up problem both
when the storage cost conditions are satisfied, and also when they are
violated.