Deterministic Analysis of Queueing Systems with Heterogeneous Servers
Muhammad El-Taha,
Department of Mathematics and Statistics, University of Southern Maine
Shaler Stidham, Jr.,
Department of Operations Research, University of North Carolina
Abstract
Using deterministic (sample-path) analysis, we generalize and
extend fundamental properties of systems with "stationary
deterministic flows" as introduced by Gelenbe and Gelenbe
and Finkel. Primarily, we provide conditions for stability
and instability for general queueing models, and focus attention
on multi-channel queueing systems with servers that work at
different rates. Stability analysis is important in computer
applications and usually precedes any further investigation of the
system in question. Our results complement and extend those of Gelenbe and
Finkel by making weaker assumptions, allowing multi-channel
facilities with heterogeneous servers, and including more general
queueing disciplines such as processor sharing and LCFS-PR.
A key to our stability analysis
is a deterministic version of the renewal-reward theorem
which we call Y = l X, and a relationship that
shows the "operational analysis" definition of
average service times, when considered as the observation period
t \rightarrow \infty $, coincides with the standard definition
of average service times for all stable queueing systems.
Our analysis is completely deterministic and avoids any
stochastic assumptions about the system under investigation;
thus provides the practioner with a method that often leads to better
and deeper understanding of the system under consideration.
It also gives a powerful tool to determine which properties of
the system are independent of the usually needed probabilistic
assumptions. As an illustration, a sample-path relationship
that gives the long-run average
busy period (cycle) for a general queueing model is
given and utilized to derive several well-known results under
weaker conditions.