Online Order Fulfillment with Replenishment

Abstract

In modern e-commerce and service operations, firms jointly manage inventory replenishment and real-time order fulfillment under demand uncertainty. We study their interaction in a single-resource lost-sales system with heterogeneous rewards, positive lead times, and replenishment cycles of length $T$. A central difficulty is that low regret in one fulfillment cycle need not imply a small profit gap under repeated replenishment, since fulfillment decisions change inventory and, under base-stock replenishment, subsequent orders. We consider base-stock and constant-order replenishment and compare online fulfillment with a myopic offline benchmark that knows current-cycle demand but not future demand. We give conditions under which $O(T^{\alpha })$ one-cycle regret yields an $O(T^{\alpha })$ upper bound on the expected average profit gap, uniformly over all finite horizons $N$. For base stock, the bound remains valid when the online and offline targets are optimized separately. For constant orders, a uniform quadratic count-loss bound gives an unrestricted two-sided comparison between separately optimized systems. For the cycle-restarted Bayes Selector, the finite-horizon bounds are $O(1)$. The optimized long-run constant-order profit gap is also $O(1)$. We use these results to compare optimized base stock with greedy fulfillment against optimized constant order with the Bayes Selector and decompose the profit difference into replenishment and fulfillment components. A representative finite-horizon simulation shows that the ranking of the two policy combinations can change with cycle length. We also extend the transfer analysis to multiple resources. Under single-resource base-stock replenishment, a mean-LP quota policy has uniform $O(\sqrt{T})$ regret against full-information benchmark.