A Survey on Queueing Systems with Mathematical Models and Applications
Read this paper on waiting line analysis and queues. It provides a good survey of the theory and uses of this type of analysis. Pay particular attention to sections 1 through 3. How might these models be used to balance firm costs with different levels of customer satisfaction?
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.