D.3 Non-Markovian Queues and Approximations
So far, the queueing models that have been analyzed all assume a Poisson arrival process and exponential service times. For other arrival and service processes only limited or approximate results are readily available. There are two cases worth mentioning here. The first case is the M/G/1 queue and the second case is an approximation for the GI/G/c queueing system. Recall that G represents any general distribution. In other words the results will hold regardless of the distribution. Also, GI refers to an arrival process which has the time between arrivals as independent and identically distributed random variables with any distribution. Table D.4 presents the basic results for the M/G/1 and M/D/1 queueing systems.
| Model | Parameters | \(L_q\) |
|---|---|---|
| M/G/1 | \(E[ST] = \dfrac{1}{\mu}\); \(Var[ST] = \sigma^2\); \(r = \lambda/\mu\) | \(L_q = \dfrac{\lambda^2 \sigma^2 + r^2}{2(1 - r)}\) |
| M/D/1 | \(E[ST] = \dfrac{1}{\mu}\); \(Var[ST] = 0\); \(r = \lambda/\mu\) | \(L_q = \dfrac{r^2}{2(1 - r)}\) |
For the M/G/1 model with a service distribution having a mean \(E[ST] = 1/\mu\) and variance \(\sigma^2\), the expected number in the system is:
\[L_q = \dfrac{\lambda^2 \sigma^2 + r^2}{2(1 - r)} + r\]
From this formula for the expected number in the system, the other performance measures can be obtained via Little’s formula. Notice that only the mean and the variance of the service time distribution are necessary in this case.
For the case of the GI/G/c queue a number of approximations have been influenced by an approximation for the GI/G/1 queue that first appeared in (Kingman 1964). His single-server approximation is shown below:
\[W_q(GI/G/1) \approx \Biggl(\dfrac{c_a^2 + c_s^2}{2}\Biggr) W_q(M/M/1)\]
In this equation, \(W_q\)(M/M/1) denotes the expected waiting time in the queue for the M/M/1 model \(c_a^2\) and \(c_s^2\) and represent the squared coefficient of variation for the inter-arrival time and service time distributions. Recall that for a random variable, \(X\), the squared coefficient of variation is given by \(c_X^2 = Var[X]/(E[X])^2\). (Whitt 1983) used a very similar approximation for the GI/G/c queue to compute the traffic congestion at each node in a queueing network for his Queueing Network Analyzer:
\[W_q(GI/G/c) \approx \Biggl(\dfrac{c_a^2 + c_s^2}{2}\Biggr) W_q(M/M/c)\]
A discussion of queuing approximations of this form as well as additional references can be found in (Whitt 1993).
Thus, to approximate the performance of a GI/G/c queue, you need only the first two moments of the inter-arrival and service time distributions and a way to compute the waiting time in the queue for a M/M/c queueing system. These results are useful when trying to verify and validate a simulation model of a queueing system, especially in the case of a system that consists of more than one queueing system organized into a network. Before examining that more complicated case, some of the issues related to using to simulate single queue systems should be examined.
The following section summarizes the formulas for the previously mentioned queueing systems. The appendis is finished off with some example exercises that can be used to test your understanding of the application of these formulas.