In this dissertation we address the dynamic multi-level lot sizing problem with general acyclic product structure and unconstrained or constrained resources. We propose new approaches based on an extended model which includes lower and upper bounds on lot sizes and cumulative production. These additional constraints allow for interactive decisions and flexible planning sequences.

We first formulate our new approaches for uncapacitated problems. For three types of decisions we examine the space of feasible decisions, the main part being dedicated to so-called single-item decisions. We focus on the case where the decision space can be given by lower and upper bounds on lot sizes and cumulative production. This case allows us to compute the decision space efficiently and to solve the cor-responding single-item problem. 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 for uncapacitated problems using a primal procedure with flexible planning sequence. Extensive computational tests on classical uncapacitated multi-level problems show consistent improvement over other heuristics.

Extension of our flexible methods to capacitated problems is not straightforward since single-item deci-sion spaces can no longer be given by lower and upper bounds even for simple capacitated multi-level problems. However, a relaxation of the original problem (limiting cumulative capacity consumption) is amenable to our flexible methods. Based on this, we develop a Lagrangean-based heuristic for capacitated problems which first constructs a solution for the relaxed problem and then applies several adjustment procedures, aiming at insuring feasibility of capacity constraints. Also here, our heuristic compares favorably to other current heuristics.

For further information, please contact Professor Heinz Gröflin (heinz.groeflin@unifr.ch)