We study the static chance-constrained lot sizing problem, in which production decisions over a planning horizon are made before knowing random future demands, and the backlog and inventory variables are then determined by the demand realizations. The chance constraint imposes a service level constraint requiring that the probability that any backlogging is required should be below a given threshold. We model uncertain outcomes with a finite set of scenarios, and begin by applying existing results about chance-constrained programming to obtain an initial extended mixed-integer programming formulation. We further strengthen this formulation with a new class of valid inequalities that generalizes the classical (l,S) inequalities for the deterministic uncapacitated lot sizing problem. In addition, we prove an optimality condition of the solutions under a modified Wagner-Whitin condition, and based on this derive a new extended mixed-integer programming formulation. We also discuss how our model and methods can be extended to a model in which the time horizon is split into two parts, where demands are known in the first part and random in the latter part. We conduct a thorough computational study demonstrating the effectiveness of the new valid inequalities and extended formulation.
Article
View New Valid Inequalities and Formulation for the Static Chance-constrained Lot-Sizing Problem