Dynamic safety-stocks for asymptotic optimality in stochastic networks

This paper concerns control of stochastic networks using state-dependent safety-stocks. Three examples are considered: a pair of tandem queues; a simple routing model; and the Dai-Wang re-entrant line. In each case, a single policy is proposed that is independent of network load ρ_·. The following conclusions are obtained for the controlled network, where the finite constant K₀ is independent of load. (i) An optimal policy for a one-dimensional relaxation stores all inventory in a single buffer i*. The policy for the (unrelaxed) stochastic network maintains for each k ≥ 0, E_i≠i*[Σ Q_i(k)]≤ K₀E[log(1+Q_i*(k))], where Q(k) is the ℓ -dimensional vector of buffer lengths at time k, initialized at Q(0) = 0. (i) The policy is fluid-scale optimal, and approximately average-cost optimal: The steady-state cost η satisfies the bound η_*≤η≤η_* + K₀ log(η_*), 0 < ρ· < 1, where η_* is the optimal steady-state cost.