Dynamic safety-stocks for asymptotic optimality in stochastic networks

Sean Meyn

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 policy is fluid-scale optimal, and approximately average-cost optimal: The steady-state cost η satisfies the bound

η_* < η < η_* + k_0 log( η_* ) , 0< ρ <1,

where η_* is the optimal steady-state cost. These results are based on the construction of an approximate solution to the average-cost dynamic programming equations via the one-dimensional relaxation and an associated fluid model.

Example: Routing model

This work has been extended to general network models in Stability and Asymptotic Optimality of Generalized MaxWeight Policies and in the networks monograph, Control Techniques for Complex Networks

Reference
@article{mey05a,
Author = {Meyn, S. P.},
Journal = QS,
Pages = {255--297},
Title = {Dynamic safety-stocks for asymptotic optimality in stochastic networks},
Volume = {50},
Year = {2005}}

@article{mey09a,
Author = {Meyn, S.},
Journal = SICON,
Number = {6},
Pages = {3259-3294},
Title = {Stability and Asymptotic Optimality of Generalized {MaxWeight} Policies},
Volume = {47},
Year = {2009}}

@book{CTCN,
Address = {Cambridge},
Author = {Meyn, S. P.},
Publisher = {Cambridge University Press},
Title = {Control Techniques for Complex Networks},
Year = {2007}}