Stability and Asymptotic Optimality of Generalized MaxWeight Policies

S. 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.

Reference:

@unpublished{mey07a,
Title = {Stability and Asymptotic Optimality of Generalized {MaxWeight} Policies},
Author = {Meyn, S.P.},
Note = {Submitted for publication SIAM J. Control and Opt. Preliminary version to appear, 46th IEEE Conference on Decision and Control},
Year = {2006}}

See also
@unpublished{CTCN,
Title = {Control Techniques for Complex Networks},
Author = {Meyn, S. P.},
Note = {To appear, {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}}