Feasible sequential decisions and a flexible Lagrangean-based heuristic for dynamic multi-level lot sizing

We propose an extended model for dynamic mutli-level lot sizing with general acyclic product structure and unconstrained resources (MLUR), including additional constraints on lot sizes and cumulative production. These allow for interactive decisions and flexible planning sequences. For three types of decisions we examine the space of feasible decisions, the main part being dedicated to single-product decisions, in order to be able to solve the single-product problems with the algorithm by Chen et al. We focus on the case where the decision space can be given by upper and lower bound constraints on lot sizes and cumulative production. We establish a characterization of this case as well as sufficient conditions of wide applicability and give algorithms to compute the bounds. As an application, we formulate a Lagrangean-based heuristic using a primal procedure with flexible planning sequence. Extensive testing on classical MLUR problems shows consistent improvement in solution quality compared with other heuristics.