Value iteration and optimization of multiclass queueing networks

Value iteration and optimization of multiclass queueing networks

0.00 Avg rating0 Votes
Article ID: iaor20003194
Country: Netherlands
Volume: 32
Issue: 1/3
Start Page Number: 65
End Page Number: 97
Publication Date: Jan 1999
Journal: Queueing Systems
Authors: ,
Keywords: networks: path, programming: markov decision, scheduling
Abstract:

This paper considers in parallel the scheduling problem for multiclass queueing networks, and optimization of Markov decision processes. It is shown that the value iteration algorithm may perform poorly when the algorithm is not initialized properly. The most typical case where the initial value function is taken to be zero may be a particularly bad choice. In contrast, if the value iteration algorithm is initialized with a stochastic Lyapunov function, then the following hold: (i) a stochastic Lyapunov function exists for each intermediate policy, and hence each policy is regular (a strong stability condition), (ii) intermediate costs converge to the optimal costs, and (iii) any limiting policy is average cost optimal. It is argued that a natural choice for the initial value function is the value function for the associated deterministic control problem based upon a fluid model, or the approximate solution to Poisson’s equation obtained from the linear programming of Kumar and Meyn. Numerical studies show that either choice may lead to fast convergence to an optimal policy.

Reviews

Required fields are marked *. Your email address will not be published.