Partitioning Heuristics for the Multi-Item Capacitated Lot Sizing Problem

Awi Federgruen, Jörn Meissner, Michal Tzur

Abstract This paper addresses the multi-item 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 branch-and-bound 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 branch-and-bound method.

The partitioning heuritic can, in the single item case, be implemented with complexity O($T^2 \log \log T$) and for the general multi-item 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 set-up 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 Arbeitspapier
Download Revised and renamed in November 2003: Progressive Interval Heuristics for Multi-Item Capacitated Lot Sizing Problems
Reference BibTeX, Plain Text
Back to Publications