Dynamic programming algorithms for the parallel machine lot sizing problem

Several multi-item lot sizing problems can be decomposed into single-item subproblems. In this work we consider a single-item parallel machine dynamic lot sizing problem which results from the Lagrangean relaxation with respect to capacity constraints. This problem is an extension of the single machine case considered by Wagner and Whitin, whose objective is to determine a minimum cost production plan that satisfies forecast demand for the item. A characterization of the extreme points of the solution set is given and then we extend two single machine dynamic programming algorithms for the parallel machine case. The first one is an efficient implementation of the Wagner–Whitin algorithm and the second is a lower complexity algorithm proposed in the literature. Computational tests are reported.