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

Assemble-to-order (ATO) strategies are common to industries such as computers, automotive, and online retailing. Despite their popularity, ATO systems remain challenging to analyze. We consider a multi-component, general-product structure ATO problem which we model 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 the proposed heuristic policy possesses many properties similar to those encountered in special-product structure ATO systems. Extensive numerical experiments show that the heuristic policy is very efficient and compares favorably to other proposed heuristics in the literature. In particular, we show that the proposed policy requires less than 10−5 the time required to obtain the optimal policy, with an average percentage cost gap of less than 4%, for systems with up to 5 components and 6 products. 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 proposed heuristic 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 proposed heuristic can handle systems with a large number of components and products