Lagrangean Relaxation for the Multi-Item Capacitated Lot-Sizing Problem: A Heuristic Implementation

The multi-item capacitated lot-sizing problem consists of determining the magnitude and the timing of some operations of durable results for several items in a finite number of processing periods so as to satisfy a known demand in each period. The subgradient algorithm implemented to minimize the processing costs is based on a Lagrangean relaxation of the capacity constraints imposed on the resources. The method incorporates a primal partitioning scheme—with a network flow subproblem—to obtain good feasible solutions.