A POLYNOMIAL ALGORITHM FOR A MULTIITEM CAPACITATED PRODUCTION PLANNING PROBLEM

In this paper we present a linear programming model for production pla nning in certain manufacturing environments where demand is not period ic. 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 p roduction orders set. We present a polynomial time algorithm for solvi ng the linear program. The algorithm finds an optimal solution to the linear program after solving at most T knapsack problems and has a wor st case computational bound of O(NT). We also discuss the links betwee n the model and the classical single machine static scheduling problem .