Sampling-Based Approximation for Series Inventory Systems

We study inventory management of an infinite-horizon, series system with multiple stages. Each stage orders from its immediate upstream stage, and the most upstream stage orders from an external supplier. Random demand with unknown distribution occurs at the most downstream stage. Each stage incurs inventory holding cost while the most downstream stage also incurs demand backlogging cost when it experiences inventory shortage. The objective is to minimize the expected total discounted cost over the planning horizon. We apply the sample average approximation (SAA) method to obtain a heuristic policy (SAA policy) using the empirical distribution function constructed from a demand sample (of the underlying demand distribution). We derive an upper bound of sample size (viz., distribution-free bound) that guarantees that the performance of the SAA policy be close (i.e., with arbitrarily small relative error) to the optimal policy under known demand distribution with high probability. This result is obtained by first deriving a separable and tight cost upper bound of the whole system that depends on (given) echelon base-stock levels and then showing that the cost difference between the SAA and optimal policies can be measured by the distance between the empirical and the underlying demand distribution functions. We also provide a lower bound of sample size that matches the upper bound (in the order of relative error). Furthermore, when the demand distribution is continuous and has an increasing failure rate (IFR), we derive a tighter sample size upper bound (viz., distribution-dependent bound). Both distribution-free and distribution-dependent bounds for the newsvendor problem, a special case of our series system, improve the previous results. In addition, we show that both bounds increase polynomially as the number of stages increases. The performance of SAA policy and the sample size bounds are illustrated numerically. Finally, we extend the results to finite-horizon series systems.