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}}
