On the part inventory model sequencing problem: complexity and Beam Search heuristic

In many industries mixed‐model assembly systems are increasingly supplied out of third‐party consignment stock. This novel trend gives rise to a new short‐term sequencing problem which decides on the succession of models launched down the line and aims at minimizing the cost of in‐process inventory held by the manufacturer. In this work, we investigate the mathematical structure of this part oriented mixed‐model sequencing problem and prove that general instances of the problem are NP‐hard in the strong sense. Moreover, we develop a new Beam Search heuristic, which clearly outperforms existing solution procedures.