Sequencing and routing in multiclass queueing networks. I: Feedback regulation. (English) Zbl 1060.90043

Meyn, Sean P.

SIAM J. Control Optimization 40, No. 3, 741-776 (2001).

Summary: 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.
For part II see ibid. 42, No. 1, 178–217 (2003; Zbl 1061.90047).

MSC:

90B35	Deterministic scheduling theory in operations research
90B22	Queues and service in operations research
60K20	Applications of Markov renewal processes (reliability, queueing networks, etc.)
68M20	Performance evaluation, queueing, and scheduling in the context of computer systems

Keywords:

queueing networks; routing; scheduling; optimal control

Citations:

Zbl 1061.90047