


Awi Federgruen, Joern Meissner, Michal Tzur


Abstract 

This paper addresses the multiitem capacitated lot sizing problem. We consider a family of $N$ items which are
produced in or obtained from the same production facility. Demands are deterministic for each item and each period
within a given horizon of $T$ periods.
First, we consider the case that a single setup cost is incurred in each period when an order for any item is placed
in that period. We develop an exact branchandbound method which can be efficiently used for problems of moderate
size. For large problems we propose a partioning heuristic. The partitioning heuristic partitions the complete $T$
periods into smaller intervalls, and specifies an associated dynamic lot sizing model for each of these.
The intervals are of a size which permits the use of the exact branchandbound method.
The partitioning heuritic can, in the single item case, be implemented with complexity O($T^2 \log \log T$) and for
the general multiitem model, in O($N^2 T^2 \log T \log C^*$) times where $C^*$ represents the largest among all
periods' capacities. We show that our heuristic is $\epsilon$optimal as $T\rightarrow\infty$, provided that some
of the models paramters are uniformly bounded from above and from below.
Subsequently, we further generalize the model to include additional item dependend setup costs and provide extensive
numerial studies to evaluate the performance under various data constellations.


Keywords 

supply chain management, inventory models, lot sizing, time partitioning


Status 

Working Paper 

Download 

Revised and renamed in November 2003: Progressive Interval Heuristics for MultiItem Capacitated Lot Sizing Problems


Reference 

BibTeX,
Plain Text 



