Performance bounds for queueing networks and scheduling policies
Academic Article
Overview
Identity
Additional Document Info
Other
View All
Overview
abstract
Except for the class of queueing networks and scheduling policies admitting a product form solution for the steady-state distribution, little is known about the performance of such systems. For example, if the priority of a part depends on its class (e.g., the buffer that the part is located in), then there are no existing results on performance, or even stability. In most applications such as manufacturing systems, however, one has to choose a control or scheduling policy, i.e., a priority discipline, that optimizes a performance objective. In this paper we introduce a new technique for obtaining upper and lower bounds on the performance of Markovian queueing networks and scheduling policies. Assuming stability, and examining the consequence of a steady state for general quadratic forms, we obtain a set of linear equality constraints on the mean values of certain random variables that determine the performance of the system. Further, the conservation of time and material gives an augmenting set of linear equality and inequality constraints. Together, these allow us to bound the performance, either above or below, by solving a linear program. We illustrate this technique on several typical problems of interest in manufacturing systems. For an open re-entrant line modeling a semiconductor plant, we plot a bound on the mean delay (called cycle-time) as a function of line loading. We show that the last buffer first serve policy is almost optimal in light traffic. For another such line, we show that it dominates the first buffer first serve policy. For a set of open queueing networks, we compare our lower bounds with those obtained by another method of Ou and Wein. For a closed queueing network, we bracket the performance of all buffer priority policies, including the suggested priority policy of Harrison and Wein. We also study the asymptotic heavy traffic limits of the lower and upper bounds. For a manufacturing system with machine failures, we show how the performance changes with failure and repair rates. For systems with finite buffers, we show how to bound the throughput. Finally, we illustrate the application of our method to GI/GI/1 queues. We obtain analytic bounds which improve upon Kingman's bound for E2/1//1 queues. 1994 IEEE
