A polynomial algorithm for a multi-item capacitated production planning problem

In this paper the authors present a linear programming model for production planning in certain manufacturing environments where demand is not periodic. The model looks at a T-period planning horizon and can be used for determining lot sizes and planned due-dates for the N products in a production orders set. The authors present a polynomial time algorithm for solving the linear program. The algorithm finds an optimal solution to the linear program after solving at most T knapsack problems and has a worst case computational bound of O(NT). The authors also discuss the links between the model and the classical single machine static scheduling problem.