Computationally Efficient Optimal Solutions to the Lot-Sizing Problem in Multistage Assembly Systems

TLDR

Lot‑sizing scheduling in multistage production is a core MRP problem, yet optimal solutions have only been achieved for small instances despite many heuristics. The authors propose a novel formulation of the multistage assembly lot‑sizing problem that enables an efficient optimization algorithm. By expressing the problem in terms of echelon stock, they decompose it with a Lagrangean relaxation and then solve it with a Branch‑and‑Bound algorithm that exploits the resulting bounds. Experiments on 120 randomly generated instances with up to 50 items, 15 stages, and 18 periods demonstrate the algorithm’s effectiveness.

Abstract

The scheduling of lot sizes in multistage production environments is a fundamental problem in many Material Requirements Planning Systems. Many heuristics have been suggested for this problem with varying degrees of success. Research to date on obtaining optimal solutions has been limited to small problems. This paper presents a new formulation of the lot-sizing problem in multistage assembly systems which leads to an effective optimization algorithm for the problem. The problem is reformulated in terms of “echelon stock” which simplifies its decomposition by a Lagrangean relaxation method. A Branch and Bound algorithm which uses the bounds obtained by the relaxation was developed and tested. Computational results are reported on 120 randomly generated problems involving up to 50 items in 15 stages and up to 18 time periods in the planning horizon.