An optimal algorithm for the multi-item capacitated production planning problem

The multi-item capacitated production planning problem consists of scheduling the size and the timing of the production for several items over a finite horizon so as to meet known future demand without incurring backlogs. The objective is to minimize the total cost of production, holding and resource over the horizon subject to a constraint on total production capacity in each period. The special model to be considered in this paper assumes that only two resources (regular time and overtime) are available and the unit production, holding and resource costs are linear and time-invariant. The authors study some optimal properties and propose an exact polynomial time algorithm based on these properties for this model. An extensive computational experiment is conducted which shows that the proposed algorithm outperforms the general-purpose transportation algorithm by far.