A POLYNOMIAL ALGORITHM FOR A MULTIITEM CAPACITATED PRODUCTION PLANNING PROBLEM

In this paper we 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. We 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). We also discuss the links between the model and the classical single machine static scheduling problem.