19.3 Queueing Theory Framework

There is a standard notation that is used to describe large families of queueing systems: the Kendall-Lee notation [379].

19.3.1 Kendall-Lee Notation

Queuing systems can be described via six characteristics: \[x_1/x_2/x_3/x_4/x_5/x_6.\] The first characteristic \(x_1\) specifies the nature of the arrival process. The following standard abbreviations are used:

\(M\) inter-arrival times are independent identically distributed (iid) exponentials
\(D\) inter-arrival times are iid and deterministic
\(E_{k}\) inter-arrival times are iid Erlangs with shape parameter \(k\)
\(G\) inter-arrival times are iid and governed by some general distribution

The second characteristic \(x_2\) specifies the nature of the service times:

\(M\) service times are iid and exponential
\(D\) service times are iid and deterministic
\(E_{k}\) service times are iid Erlang with shape parameter \(k\)
\(G\) service times are iid and follow some general distribution

The third characteristic \(x_3\) represents the number of parallel servers; it is a positive integer.

The fourth characteristic \(x_4\) describes the queue discipline:

FCFS first come, first served
LCFS last come, first served
SIRO service in random order
GD general queue discipline

The fifth characteristic \(x_5\) specifies the maximum allowable number of customers in the system (including customers who are waiting and customers who are in service).

The sixth characteristic \(x_6\) gives the size of the population from which customers are drawn. Unless the number of potential customers is of the same order of magnitude as the number of servers, the population size is considered to be infinite.

In many important models \(x_4/x_5/x_6\) is \(\textrm{GD}/\infty/\infty\); when this is the case, these characteristics are often omitted. As an example, \(M/M/3/\textrm{FCFS}/20/\infty\) could represent a bank with 3 tellers, exponential arrival times, exponential service times, a “first come, first served” queue discipline, a total capacity of 20 customers, and an infinite population pool from which to draw. The situation is partly illustrated in Figure 19.4.

Single line at bank with three tellers -- $M/M/3/\textrm{FCFS}/20/\infty$.

Figure 19.4: Single line at bank with three tellers – \(M/M/3/\textrm{FCFS}/20/\infty\).

Examples: here are some commonly-used/studied queueing systems:

Name Notation Example
simple system \(M/M/1\) customer service desk in a small store
multi-server system \(M/M/c\) airline ticket counter
constant service \(M/D/1\) automated car wash
general service \(M/G/1\) auto repair shop
limited capacity \(M/M/1/N\) barber shop with \(N\) waiting seats

19.3.2 Birth-Death Processes

The state of a queueing system at time \(t\) is defined to be the number of customers in the queuing system, either waiting in line or in service, at time \(t\). At \(t = 0\), the state of the system is the initial number of customers in the system. This state is worth recording because it clearly affects the state at future times \(t\).

Knowing this, we define \(P_{i,j} (t)\) as the probability that the state at time \(t\) is \(j\), given that the state at \(t = 0\) was \(i\). For large \(t\), \(P_{i,j} (t)\) becomes independent of \(i\) and approaches a limit \(\pi_{j}\). This limit is known as the steady-state of state \(j\).

It is generally quite difficult to determine the steps of arrivals and services that lead to a steady-state \(\pi_j\). Likewise, starting from an early \(t\), it is difficult to determine exactly when a system will reach its steady state \(\pi_j\), if such a state even exists.

For simplicity’s sake, when a queuing system is studied, we begin by assuming that the steady-state has already been reached. A birth-death process is a Markov process in which states are indexed by non-negative integers, and transitions are only permitted between “neighbouring” states. After a “birth”, the state increases from \(n\) to \(n+1\); after a “death”, the state decreases from \(m\) to \(m-1\).

Typically, we denote the set of birth rates and death rates by \(\lambda_n\) and \(\mu_m\), respectively (see Figure 2).

Birth-death process; queueing states indexed by integers; birth rates and death rates indicated by $\lambda_n$ and $\mu_m$, respectively (source unknown).

Figure 19.5: Birth-death process; queueing states indexed by integers; birth rates and death rates indicated by \(\lambda_n\) and \(\mu_m\), respectively (source unknown).

Pure birth processes are those for which \(\mu_m=0\) for all \(m\); pure death processes those for which \(\lambda_n=0\) for all \(n\). The steady-state solution of a birth-death process, i.e., the probability \(\pi_n\) of being in state \(n\), can actually be computed: \[\begin{aligned} \pi_{n} &= \pi_{0}\frac{\lambda_{0} \lambda_{1} \cdots \lambda_{n-1}}{\mu_{1} \mu_{2} \cdots \mu_{n}},\quad \text{for } n=1,2,\cdots \end{aligned}\] where \(\pi_{0}\) is the probability of being in state 0 (i.e., without users). It can further be shown [376] that: \[\pi_{0} = \frac{1}{1+ \displaystyle{\sum^{\infty}_{n=1} \prod^{n-1}_{j=0} \frac{\lambda_{j}}{\mu_{j+1}}}}.\]

19.3.3 Little’s Queuing Formula

It is often the case that clients and end users are interested in determining the amount of time that a typical customer spends in the queuing system. Let \(W\) be the expected waiting time spent in the queuing system, including time in line plus time in service, and \(W_{q}\) be the expected time a customer spends waiting in line.

Both \(W\) and \(W_{q}\) are computed under the assumption that the steady state has been reached. By using a powerful result known as Little’s queuing formula, \(W\) and \(W_{q}\) are easily related to the number of customers in the queue and those waiting in line. For any queuing system (or any subset of a queuing system), consider the following quantities:

  • \(\lambda =\) average number of arrivals entering the system per unit time;

  • \(L =\) average number of customers present in the queuing system;

  • \(L_{q} =\) average number of customers waiting in line;

  • \(L_{s} =\) average number of customers in service;

  • \(W =\) average time a customer spends in the system;

  • \(W_{q} =\) average time a customer spends in line, and

  • \(W_{s} =\) average time a customer spends in service.

Customers in the system can only be found in the queue or being serviced, so that \(L = L_{q} + L_{s}\) and \(W = W_{q} + W_{s}\). In these definitions, all averages are steady-state averages.

Schematics of steady state vs. transient behaviour (source unknown).

Figure 19.6: Schematics of steady state vs. transient behaviour (source unknown).

For most queuing systems in which a steady-state exists, Little’s queuing formula are summarized by: \[\begin{aligned} L &= \lambda W, \quad L_{q} = \lambda W_{q}, \quad\mbox{and} \quad L_{s}= \lambda W_{s}.\end{aligned}\]

Example: if, on average, 46 customers enter a restaurant each hour it is opened, and if they spend, on average, 10 minutes (1/6 hours) waiting to be served, then we should expect \(46\cdot 1/6 \approx 7.7\) customers in the queue at all time (on average).

References

[376]
L. Kleinrock, Queueing Systems, Volume I. Wiley, 1974.
[379]
D. G. Kendall, Stochastic Processes Occurring in the Theory of Queues and their Analysis by the Method of the Imbedded Markov Chain,” The Annals of Mathematical Statistics, vol. 24, no. 3, pp. 338–354, 1953, doi: 10.1214/aoms/1177728975.