Optimal Lot-Sizing Algorithms for Complex Product Structures

Lot sizing of products that have complex bills of materials plays an important role in the efficient operations of modern manufacturing and assembly processes. In this paper we develop algorithms for optimal lot sizing of products with a complex product structure. We convert the classical formulation of the general structure problem into a simple but expanded assembly structure with additional constraints, and solve the transformed problem by a branch-and-bound based procedure. The algorithm uses a Lagrangean relaxation and subgradient optimization procedure to generate tight lower bounds on the optimal solutions. In computational experiments, a code based on this method was able to solve single end product problems with up to 40 stages in the product structure. The model is extended to handle problems with multi-end items in the product structure, but with less favorable computational results.