A Survey on Queueing Systems with Mathematical Models and Applications
3. Components of Queueing System
3.6. Kendall's Notations
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
where ' ' denotes inter-arrival time distribution, ' ' is the service time distribution, ' ' represents the number of servers, and ' ' 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, denotes the traffic intensity which is defined by
Assuming an infinite population system with arrival intensity , which is reciprocal of the mean inter-arrival time, let the mean service time be denoted by , then we have
arrival intensity mean service time
If , then the system is overloaded since the requests arrive faster than they are served. It shows that more servers are needed. Let (A) denotes the characteristic function of the event A, that is
Furthermore, let denotes the event that at time the server is idle having no customers in the system. Therefore, utilization of the server during time is defined by
where is a long interval of time. As , we get the utilization of the server denoted by and the following relations holds with probability 1
where 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 be an ergodic Markov chain and is a subset of its state space. denotes the ergodic (stationary, steady-state distribution) of . Then with probability 1
where and respectively denote the mean sojourn times of the chain in and during a cycle.
In an m-server system, the mean number of arrivals to a given server during time is , provided that the arrivals are uniformly distributed over the servers. Thus the utilization of a given server is
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
However, if we consider a tagged customer, the waiting and response times are more important than the measures defined above. Let and denote waiting time and response time of the 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
where denotes service time; and are random variables and their means denoted by and , 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 and are the number of customers in the queue and in the system at time respectively. Clearly, in an m-server system we have
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.