Abstract: 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. An approximation algorithm is described, which is based on simulated annealing algorithm. The method incorporates a primal partitioning scheme— with a network flow subproblem—to obtain good feasible solutions.