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

This paper establishes new criteria for stability and for instability of multiclass network models under a given stationary policy. It also extends previous results on the approximation of the solution to the average cost optimality equations through an associated fluid model: It is shown that an optimized 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 queueing networks is proposed based on these general results. Network sequencing and routing problems are considered as special cases. The following aspects of the resulting feedback regulation policies are developed in the paper: (i) The policies are stabilizing and are, in fact, geometrically ergodic for a Markovian model. (ii) Numerical examples are given. In each case it is shown that the feedback regulation policy closely resembles the average-cost optimal policy. (iii) A method is proposed for reducing variance in simulation for a network controlled using a feedback regulation policy.