# Stability and Asymptotic Optimality of Generalized MaxWeight Policies

Sean Meyn

See also Hamilton Institute 2007 presentation

The perturbed cost function. The figure shows level sets of the function h obtained through the perturbation of a linear cost function. The concave region is the resulting policy obtained for the tandem queues - a generalized threshold policy in this example. |
||

**Abstract:**

It is shown that stability of the celebrated MaxWeight or back pressure policies is a consequence of the following interpretation: either policy is myopic with respect to a surrogate value function of a very special form, in which the "marginal disutility" at a buffer vanishes for vanishingly small buffer population. This observation motivates the *h*-*MaxWeight policy*, defined for a wide class of functions *h*. These policies share many of the attractive properties of the MaxWeight policy:

- Arrival rate data is not required in the policy.
- Under a variety of general conditions, the policy is stabilizing when
*h*is a perturbation of a monotone linear function, a monotone quadratic, or a monotone Lyapunov function for the fluid model. - A perturbation of the relative value function for a workload relaxation gives rise to a myopic policy that is approximately average-cost optimal in heavy traffic, with logarithmic regret.

The first results are obtained for a general Markovian network model. Asymptotic optimality is established for a general Markovian scheduling model with a single bottleneck, and homogeneous servers.

*Logarithmic regret*:

References

@article{mey09a,

Author = {Meyn, S.},

Doi = {10.1137/06067746X},

Journal = SICON,

Keywords = {queueing networks; routing; scheduling; optimal control},

Number = {6},

Pages = {3259-3294},

Publisher = {SIAM},

Title = {*Stability and Asymptotic Optimality of Generalized {MaxWeight} Policies*},

Url = {http://link.aip.org/link/?SJC/47/3259/1},

Volume = {47},

Year = {2009}} @inproceedings{mey07b,

Author = {Meyn, Sean},

Title = {Myopic policies and {MaxWeight} policies for stochastic networks},

Booktitle = {Proc.~of the 46th IEEE Conference on Decision and Control},

Month = {Dec. 12-14 },

Pages = {639-646},

Year = {2007}}

See also

@book{CTCN, Title = {*Control Techniques for Complex Networks*},

Address = {Cambridge},

Author = {Meyn, S. P.},

Isbn = {978-0-521-88441-9},

Mrclass = {90-01 (90B10 90B22 90B35 90C35 91D30 93E20)},

Mrnumber = {MR2372453},

Pages = {xx+562},

Publisher = {Cambridge University Press},

Year = {2007}}

@article{mey05a,

Author = {Meyn, S. P.},

Journal = {Queueing Systems},

Pages = {255--297},

Title = {*Dynamic safety-stocks for asymptotic optimality in stochastic networks*},

Volume = {50},

Year = {2005}}