Sequencing and routing in multiclass queueing networks part I: Feedback regulation

This paper establishes new criteria for stability and for instability of mu lticlass network models under a given stationary policy. It also extends pr evious results on the approximation of the solution to the average cost opt imality equations through an associated fluid model: It is shown that an op timized network possesses a fluid limit model which is itself optimal with respect to a total cost criterion. A general framework for constructing control algorithms for multiclass queu eing networks is proposed based on these general results. Network sequencin g and routing problems are considered as special cases. The following aspec ts of the resulting feedback regulation policies are developed in the paper : (i) The policies are stabilizing and are, in fact, geometrically ergodic fo r a Markovian model. (ii) Numerical examples are given. In each case it is shown that the feedba ck regulation policy closely resembles the average-cost optimal policy. (iii) A method is proposed for reducing variance in simulation for a networ k controlled using a feedback regulation policy.