Exact Simulation for Assemble-To-Order Systems

Ana Busic, Emilie CoupechouxarXiv 2014 · arXiv

Introduction

Assemble-To-Order (ATO) systems are a cornerstone of modern supply chain management, where components are stocked in advance but final products are only assembled upon receiving a customer order. While efficient, these systems are notoriously difficult to analyze due to complex interdependencies: a single missing component can stall the assembly of multiple distinct products. This leads to a "state space explosion," where the number of possible inventory combinations grows exponentially with the variety of items.

Traditional analysis often employs Markov Chain Monte Carlo (MCMC) methods to estimate long-term system behavior. However, MCMC suffers from the "burn-in" problem—the difficulty of determining exactly when a simulation has reached its steady state. This paper introduces the Aggregated Envelope Perfect Sampling Algorithm (AEPSA), which leverages "Coupling From The Past" (CFTP) to provide unbiased, exact samples from the stationary distribution, effectively removing the guesswork of traditional simulations.

Methodology: The AEPSA Algorithm

The authors' framework categorizes ATO systems based on their service protocols—Partial Order Service (POS) versus Total Order Service (TOS)—and replenishment mechanisms.

A conceptual roadmap linking perfect sampling theory to specific ATO system applications.

The AEPSA algorithm overcomes the state space challenge through two primary innovations:

  1. State Aggregation: Instead of tracking the full complexity of every item combination currently in the system, the algorithm projects the state onto a smaller space representing the total count of available items for each type.
  2. Bounding Envelopes: To compensate for the information lost during aggregation, the algorithm maintains "upper" and "lower" bounding chains. When these two bounds meet (couple), the algorithm guarantees that the underlying complex system has converged to its stationary distribution.
Illustration of state transitions in a two-component aggregated inventory model, showing the movement toward boundary states.

Key Insights: Monotonicity and Coupling

The research highlights that monotonicity is a critical factor in simulation efficiency. In POS systems, inventory levels are monotone, making them relatively straightforward to simulate. In contrast, TOS systems—where an entire order is canceled if a single part is missing—are non-monotone and significantly more computationally intensive.

The "aha moment" of the paper is the realization that one does not need to track the full system complexity to prove convergence. By bounding the projected (aggregated) state, researchers can infer the state of the original high-dimensional system. Furthermore, the authors introduce "component-wise coupling," which allows the simulation to terminate as soon as individual component inventory levels align, drastically reducing computation time.

Results and Computational Performance

The authors validated their algorithms using synthetic Markovian models, yielding several key findings:

  • Computational Efficiency: For single-server replenishment, the algorithm's complexity is linear relative to the system's total capacity. For many-server cases, it scales quadratically.
  • Tight Convergence: Numerical results demonstrate that the AEPSA algorithm often couples much faster in practice than pessimistic theoretical upper bounds would suggest.
  • Exactness: Unlike standard MCMC, these algorithms provide a definitive "stopping bit," ensuring the simulation only ends once the exact target distribution is reached.

Conclusion and Future Directions

The AEPSA algorithm provides a powerful tool for the exact simulation of complex ATO systems. While it performs exceptionally well under high service rate assumptions, challenges remain for extremely large systems with joint returns or non-monotone TOS protocols. Future research may explore combining state aggregation with "splitting" techniques to further enhance the scalability of perfect sampling for massive, global supply chain networks.

Summary updated

Abstract

We develop exact simulation (also known as perfect sampling) algorithms for a family of assemble-to-order systems. Due to the finite capacity, and coupling in demands and replenishments, known solving techniques are inefficient for larger problem instances. We first consider the case with individual replenishments of items, and derive an event based representation of the Markov chain that allows applying existing exact simulation techniques, using the monotonicity properties or bounding chains. In the case of joint replenishments, the state space becomes intractable for the existing methods. We propose new exact simulation algorithms, based on aggregation and bounding chains, that allow a significant reduction of the state space of the Markov chain. We also discuss the coupling times of considered models and provide sufficient conditions for linear (in the single server replenishment case) or quadratic (many server case) complexity of our algorithms in terms of the total capacity in the system.
BibTeX
@misc{busic2014exact,
  author = {Ana Busic and Emilie Coupechoux},
  title = {{Exact Simulation for Assemble-To-Order Systems}},
  year = {2014},
  eprint = {1402.5391},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1402.5391},
}
Figure