Home
Speakers
Schedule
Location and Directions
Hotel Information
Sean Meyn
University of Illinois at Urbana Champaign
Title: Stability and Asymptotic Optimality of Generalized MaxWeight Policies
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.