Classification of Queuing Systems
David George Kendall in 1953 suggested a notation that is helpful to classify a wide variety of different waiting line.
The simplest form of Kendall's notation consists of 3 letters: a/b/c
a represents the probability distribution of customers arrivals
b represents the probability distribution of service time
c is the number of servers
Commonly used letter in position a or b are
- M to indicate Poisson Process (which means Poisson distribution for arrival and Exponential distribution for service time). Symbol M represents Markovian.
- E to indicate Erlang distribution
- D to indicate Deterministic or constant distribution
- G to indicate General probability distribution with known mean and variance
For example, queuing system M/M/1 means Poisson distribution for arrival and Exponential distribution for service time and one server. Queuing system M/M/2 has customers arrive according to Poisson distribution with Exponential distribution for service time and the system has two servers. Queuing system M/D/3 indicates that the customers arrive according to Poisson distribution while the service time is constant with 3 servers.
More comprehensive Kendall notation consists up to 6 letters: a/b/c/d/e/f
The first three letters are, as before in the simplest Kendall notation, indicates the arrival distribution , service time distribution and number of servers. The fourth letter, d , represents the capacity of the queuing system, which is the maximum number of customers that allowed being in the queue and being served at any time. Some queuing system has certain size of room or capacity on the number of seats, and some other queuing system has limited number of customers . Letter e , represents the size of the source of population, from which customers seek the service. The last letter, f, is an additional letter into the original Kendall's notation to indicate queuing discipline. In most queuing theory, the common assumption of queuing discipline is first in first out or FIFO.
When we use the simplest Kendall notation, the fourth and the fifth letters are assumed to be infinite. In other words, we use more comprehensive Kendall notation only when either the capacity is finite or the calling source is finite. The last letter is assumed to be FIFO
Knowing the Kendal Notation is useful to classify the queuing system and the usage of computer program to compute the measurement of effectiveness of a queuing system often based on the Kendal classification of the queuing system.
Preferable reference for this tutorial is
Teknomo, Kardi. (2014) Queuing Theory Tutorial