Capacitated lot-sizing with minimum batch sizes and setup times

A multi-item, capacitated lot-sizing problem is introduced in which the effects of setups are modelled using minimum batch sizes and setup times. A heuristic algorithm for solving the problem is proposed. This is based on a Lagrangean relaxation of the capacity constraints which decomposes the problem into independent single-item subproblems. The single-item, uncapacitated subproblems can be solved using an algorithm based on dynamic programming. Computational experience with the heuristic is reported.