Accelerated solutions to the multistage lot-sizing problem with lead time through the use of strong valid inequalities

The scheduling of lot-sizes in multistage production structures with time-varying costs and nonzero lead times is formulated as a mixed zero-one linear program for which strong valid inequalities are derived. A fast algorithm that selects a most-violated inequality is developed and used repeatedly in a cutting plane algorithm. The efficiency of the cutting plane algorithm in accelerating a branch and bound search is analyzed in an example. The example shows the strength of the cuts in terms of reduction of the number of nodes explored to achieve a near-optimal solution