Assemble-to-Order Systems with Exogenous Lead Times

We study a single-product assemble-to-order (ATO) system with exogenous lead times operated under a component base stock policy. The challenge of evaluating a base stock policy in an ATO system with random lead times is due to the fact that one needs to compute the distribution of the minimum of n correlated random variables, where n is the number of components. The correlation arises because the replenishment quantities of different components are all contingent on the demand for the final product. We first develop two algorithms for performance evaluation in the special case of i.i.d. lead times. The first algorithm is exponential in the number of components, but polynomial in the maximum lead time, and the second algorithm is polynomial in the number of components but exponential in the maximum lead time. We then study sequential lead times, another special case. For this case, we provide an efficient algorithm with polynomial complexity. This is the first efficient algorithm for the performance evaluation of base stock policies in an assemble-to-order system with random lead times. By using the method as an evaluation oracle in a steepest descent algorithm, we also obtain a polynomial time algorithm for base stock optimization for the case of sequential lead times. We then proceed to develop efficiently computable upper and lower bounds for the general case of exogenous lead times, which includes i.i.d. and sequential lead times as special cases. One of the two methods produces tight bounds for performance evaluation, and both bounds perform well as part of an optimization algorithm to optimize base stock levels.