Stability and Asymptotic Optimality of Generalized MaxWeight Policies

Sean Meyn


See also Hamilton Institute 2007 presentation


fmmpPlots.gif   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.



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:

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:

Logarithmic Regret


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 = {},
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}}

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