AN EFFECTIVE ALGORITHM FOR THE CAPACITATED SINGLE ITEM LOT-SIZE PROBLEM

This paper studies a deterministic, single product capacitated dynamic lot size model with linear production and holding costs where the setup costs, unit production costs, and capacities are arbitrary functions of the period, and the unit production costs satisfy the growth constraint: The unit production cost in any period can never exceed the sum of the unit production cost and the unit holding cost in the previous period. Our main result is an algorithm which combines dynamic programming with branch and bound. Although the problem considered here is known to be NP-hard, this algorithm handles many reasonable sized problems. A number of tests covering a fairly wide range of parameter values are run to evaluate its effectiveness. The average CPU time required to find an optimal solution to our 96 period test problems on a VAX 11/750 minicomputer is 13.3 seconds.