Scenario-based planning for lot-sizing and scheduling with uncertain processing times

This paper addresses the identical parallel machine lot-sizing and scheduling problem with sequence-dependent set-up costs and uncertain processing times. The evolution of the uncertain parameters is modelled by means of a scenario tree, giving rise to a multistage stochastic mixed-integer program. Fix-and-relax procedures, exploiting the specific structure of the problem, are developed and compared. Computational results on a large set of randomly generated instances show that the gap between the best heuristic solutions and the lower bounds provided by a truncated branch-and-bound never exceeds 3%.