A novel decomposition-based method for solving general-product structure assemble-to-order systems

Mohsen ElHafsi*, Jianxin Fang, Essia Hamouda

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)


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.

Original languageEnglish
Pages (from-to)233-249
Number of pages17
JournalEuropean Journal of Operational Research
Issue number1
Publication statusPublished - 1 Oct 2020
Externally publishedYes
Event32nd Annual POMS conference -
Duration: 21 Apr 202225 Apr 2022


  • Approximate policy
  • Assemble-to-order
  • Information relaxation lower bound
  • Inventory control
  • Markov decision process
  • Production


Dive into the research topics of 'A novel decomposition-based method for solving general-product structure assemble-to-order systems'. Together they form a unique fingerprint.

Cite this