Performance bounds for queueing networks and scheduling policies
Conference Paper
Overview
Research
Identity
Additional Document Info
Other
View All
Overview
abstract
Except when a product form solution holds, little is known about performance of queueing networks. 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. 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. 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, we plot a bound on the mean delay 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 [1]. 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 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. Finally, we illustrate the application of our method to GI/GI/1 queues. We obtain an analytic bound which improves upon Kingman's bound for E2/M/1 queues.
name of conference
Proceedings of 32nd IEEE Conference on Decision and Control
