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.