A Novel Decomposition-Based Method for Solving General-Product Structure Assemble-to-Order Systems

Abstract

Assemble-to-order (ATO) strategies are common to many industries. Despite their popularity, ATO systems remain challenging to analyze. We consider a general-product structure ATO problem modeled as an infinite horizon Markov decision process. As the optimal policy of such a system is computationally intractable, we develop a heuristic policy that is based on a decomposition of the original system, into a series of two-component ATO subsystems. We show that our decomposition heuristic policy (DHP) possesses many properties similar to those encountered in special- product structure ATO systems. Extensive numerical experiments show that the DHP is very efficient. In particular, we show that the DHP requires less than 10−5 the time required to obtain the optimal policy, with an average percentage cost gap less than 4% for systems with up to 5 components and 6 products. We also show that the DHP outperforms the state aggregation heuristic of Nadar et al. (2018), in terms of cost and computational effort. We further develop an information relaxation-based lower bound on the performance of the optimal policy. We show that such a bound is very efficient with an average percentage gap not exceeding 0.5% for systems with up to 5 components and 6 products. Using this lower bound, we further show that the average suboptimality gap of the DHP is within 9% for two special- product structure ATO systems, with up to 9 components and 10 products. Using a sophisticated computing platform, we believe the DHP can handle systems with a large number of components and products.