A Survey on Queueing Systems with Mathematical Models and Applications

To represent the behaviours discussed above, there is a standard method, called Kendall's notation to classify different queueing systems. This is the method proposed by an English statistician D. G. Kendall (1918-2007) and is denoted by

$\mathrm{a} / \mathrm{b} / \mathrm{c}: \mathrm{d} / \mathrm{e} / \mathrm{f}$

where ' $a$ ' denotes inter-arrival time distribution, ' $b$ ' is the service time distribution, ' $c$ ' represents the number of servers, and ' $\mathrm{d}$ ' denotes the maximum number of jobs that can be occupied in the system (waiting and in service) with infinite number of waiting positions for default. Likewise, 'e' indicates queueing discipline (FCFS, LCFS, SIRO, RR etc.) having FCFS for default, and the last notation 'f' is for population size from which customers rush to the system.

For a single server queueing system, $\rho$ denotes the traffic intensity which is defined by

$\rho=\frac{\text { mean service time }}{\text { mean inter-arrival times }}$

Assuming an infinite population system with arrival intensity $\lambda$, which is reciprocal of the mean inter-arrival time, let the mean service time be denoted by $1 / \mu$, then we have

$\rho=$ arrival intensity $\times$ mean service time $=\frac{\lambda}{\mu}$

If $\rho>1$, then the system is overloaded since the requests arrive faster than they are served. It shows that more servers are needed. Let $\chi$ (A) denotes the characteristic function of the event A, that is

$\chi(\mathrm{A})= \begin{cases}1 & \text { if } \mathrm{A} \text { occurs } \\ 0 & \text { if } \mathrm{A} \text { does not }\end{cases}$

Furthermore, let $N(t)=0$ denotes the event that at time $T$ the server is idle having no customers in the system. Therefore, utilization of the server during time $T$ is defined by

$\frac{1}{\mathrm{~T}} \int_{0}^{\mathrm{T}} \chi(\mathrm{N}(\mathrm{t}) \neq 0) \mathrm{dt}$

where $\mathrm{T}$ is a long interval of time. As $\mathrm{T} \rightarrow \infty$, we get the utilization of the server denoted by $\mathrm{U}_{5}$ and the following relations holds with probability 1

$\mathrm{U}_{\mathrm{s}}=\lim \limits_{\mathrm{T} \rightarrow \infty} \frac{1}{\mathrm{~T}} \int_{0}^{\mathrm{T}} \chi(\mathrm{N}(\mathrm{t}) \neq 0) \mathrm{dt}=1-\mathrm{P}_{0}=\frac{\mathrm{E} \delta}{\mathrm{E} \delta+\mathrm{E} \mathrm{i}}$

where $P_{0}$ is the steady-state probability that the server is idle. E\delta and Ei denote the mean busy period and mean idle period of the server respectively.

Theorem 1: Let $X(t)$ be an ergodic Markov chain and $A$ is a subset of its state space. $P_{i}$ denotes the ergodic (stationary, steady-state distribution) of $X(t)$. Then with probability 1

$\lim \limits_{\mathrm{T} \rightarrow \infty}\left(\frac{1}{\mathrm{~T}} \int_{0}^{\mathrm{T}} \chi(\mathrm{X}(\mathrm{t}) \in \mathrm{A}) \mathrm{dt}\right)=\sum\limits_{\mathrm{i} \in \mathrm{A}} \mathrm{P}_{\mathrm{i}}=\frac{\mathrm{m}(\mathrm{A})}{\mathrm{m}(\mathrm{A})+\mathrm{m}(\overline{\mathrm{A}})}$

where $m(A)$ and $m(\bar{A})$ respectively denote the mean sojourn times of the chain in $A$ and $\bar{A}$ during a cycle.

In an m-server system, the mean number of arrivals to a given server during time $\mathrm{T}$ is $\lambda \mathrm{T} / \mathrm{m}$, provided that the arrivals are uniformly distributed over the servers. Thus the utilization of a given server is

$\mathrm{U}_{\mathrm{s}}=\frac{\lambda}{m \mu}$

The other important measure of the system is the throughput of the system which is defined as the mean number of requests serviced during a time unit. In an m-server system, the mean number of completed services is mp\mu and thus

throughput $=\mathrm{mU}_{s} \mu$

However, if we consider a tagged customer, the waiting and response times are more important than the measures defined above. Let $\mathrm{W}_{j}$ and $\mathrm{T}_{j}$ denote waiting time and response time of the $j$ th customer respectively. Clearly, the waiting time is the time a customer spends in the queue waiting for service, and response time is the time a customer spends in the system, that is

$\mathrm{T}_{\mathrm{j}}=\mathrm{W}_{\mathrm{j}}+\mathrm{S}_{\mathrm{j}}$

where $\mathrm{S}_{\mathrm{j}}$ denotes service time; $\mathrm{W}_{\mathrm{j}}$ and $\mathrm{T}_{\mathrm{j}}$ are random variables and their means denoted by $\overline{\mathrm{W}}_{\mathrm{j}}$ and $\overline{\mathrm{T}}_{\mathrm{j}}$, are appropriate for measuring the efficiency of the system. It is not easy in general to obtain their distribution function.

Other characteristics of the system are the queue length and the number of customers in the system. Let the random variables $Q(t)$ and $N(t)$ are the number of customers in the queue and in the system at time $t$ respectively. Clearly, in an m-server system we have

$\mathrm{Q}(\mathrm{t}) \max \{0 ; \mathrm{N}(\mathrm{t})-\mathrm{m}\}$

The primary aim is to get their distributions which always may not be possible. In many of the situations, we have only their mean values or their generating function.