WorksMathematics
A 5/2 Guarantee for Echelon Stock (s,S) Policies in One-Warehouse Multi-Retailer Systems
Abstract
We study a periodic-review warehouse serving multiple heterogeneous retailers with stochastic demand and fixed costs and lead times at both echelons. We construct a deterministic echelon stock (s,S) policy whose long-run expected average cost is at most 5/2 times the optimum over all nonanticipative policies. The guarantee holds when, as in a retail chain with common service penalties, the uniform backlog penalty and heterogeneous retailer holding rates are at least the warehouse holding rate and heterogeneous retailer setup costs are at most 3/2 times the supplier's. The latter setup-cost condition extends beyond supplier setup-cost dominance: a retailer dispatch may incur a setup cost up to 50 percent higher than a supplier order's. Demand vectors are i.i.d. over periods with finite positive means, and demands of different retailers may be correlated. Each retailer selects the full cycle of its single-location plan or a shifted cycle of half its width, under an inflated setup cost, and the warehouse serves requests in arrival order, allowing partial shipments. The upper bound on the policy's cost includes each retailer's mirror cost, which prices the warehouse imbalance created by that retailer's batching. The upper and lower bounds share a pooled supplier problem and add one problem per retailer, giving a factor independent of all lead times and the number of retailers. For arbitrary nonnegative setup costs and associated retailer demands, a consolidation policy holds allocated stock until a dispatch threshold is met and gives a factor below 4.9. On 864 instances built from Walmart store sales, the simulated cost of an integer-rounded implementation of the FIFO policy averages 1.45 times the lower bound and reaches 1.75, and our analytical upper bound on its cost is below 1.94 times the lower bound; both ratios to the lower bound have nearly the same mean at every supplier lead time.