Dynamic Lot Size Models for Multi-Stage Assembly Systems

Abstract

A multi-stage assembly system is a special case of Veinott's general multi-facility system in that each facility may have any number of predecessors but at most a single successor. This paper presents two algorithms for computing optimal lot sizes in such systems with known time-varying demand. The first is a dynamic programming algorithm for which solution time increases exponentially with the number of time periods, but only linearly with the number of stages, irrespective of assembly structure. The second is a branch and bound algorithm intended for cases where the number of time periods is large but the structure is close to serial. Computational results are given and extensions considered.