Queueing theory deals with one of the most unpleasant experiences of life, waiting. Queueing is quite common in many fields, for example, in telephone exchange, in a supermarket, at a petrol station, at computer systems, etc. I have mentioned the telephone exchange first because the first problems of queueing theory was raised by calls and Erlang was the first who treated congestion problems in the beginning of 20th century, see Erlang[ 21 ],[ 22 ].
His works inspired engineers, mathematicians to deal with queueing problems using probabilistic methods. Queueing theory became a field of applied probability and many of its results have been used in operations research, computer science, telecommunication, traffic engineering, reliability theory, just to mention some. It should be emphasized that is a living branch of science where the experts publish a lot of papers and books. The easiest way is to verify this statement one should use the Google Scholar for queueing related items. A Queueing Theory Homepage has been created where readers are informed about relevant sources, for example books, softwares, conferences, journals, etc. I highly recommend to visit it at
There is only a few books and lectures notes published in Hungarian language, I would mention the work of Györfi and Páli [ 33 ], Jereb and Telek [ 43 ], Kleinrock[ 48 ], Lakatos ,Szeidl and Telek [ 55 ] and Sztrik [ 81 ], [ 82 ], [ 83 ], [ 84 ]. However, it should be noted that the Hungarian engineers and mathematicians have effectively contributed to the research and applications. First of all we have to mention Lajos Takács who wrote his pioneer and famous book about queueing theory[ 88 ]. Other researchers are J. Tomkó, M. Arató, L. Györfi, A. Benczúr, L. Lakatos, L. Szeidl, L. Jereb, M. Telek, J. Bíró, T. Do, and J. Sztrik. The Library of Faculty of Informatics, University of Debrecen, Hungary offer a valuable collection of queueing and performance modeling related books in English, and Russian, too. Please visit:
I may draw your attention to the books of Takagi[ 85 ] [ 86 ] [ 87 ].
To characterize a queueing system we have to identify the
probabilistic properties of the incoming flow of requests, service
times and service disciplines. The arrival process can be
characterized by the distribution of the interarrival times of the customers, denoted by
, that is 
.
In queueing theory these interarrival times are usually assumed
to be independent and identically distributed random variables. The
other random variable is the service
time, sometimes it is called service request, work. Its
distribution function is denoted by 
, that is 
.
The service times, and interarrival times are commonly supposed to be independent random variables.
The structure of service and service discipline tell us the number of servers, the capacity of the system, that is the maximum number of customers staying in the system including the ones being under service. The service discipline determines the rule according to the next customer is selected. The most commonly used laws are
FIFO - First In First Out: who comes earlier leaves earlier
LIFO - Last Come First Out: who comes later leaves earlier
RS - Random Service: the customer is selected randomly
Priority.
The aim of all investigations in queueing theory is to get the main performance measures of the system which are the probabilistic properties ( distribution function, density function, mean, variance ) of the following random variables: number of customers in the system, number of waiting customers, utilization of the server/s, response time of a customer, waiting time of a customer, idle time of the server, busy time of a server. Of course, the answers heavily depends on the assumptions concerning the distribution of interarrival times, service times, number of servers, capacity and service discipline. It is quite rare, except for elementary or Markovian systems, that the distributions can be computed. Usually their mean or transforms can be calculated.
For simplicity consider first a single-server system. Let
, called traffic
intensity, be defined as
Assuming an infinity population system with arrival intensity
, which is reciprocal of the mean interarrival
time, and let the mean service denote by 
. Then we have
If 
then the systems is overloaded since the requests
arrive faster than as the are served. It shows that more server are
needed.
Let 
denote the characteristic function of event
, that is
furthermore let 
denote the event that at time 
the server is idle, that is no customer in the
system. Then the 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
where 
is the steady-state probability that the server is
idle 
, 
denote the mean busy period, mean idle period of
the server, respectively.
This formula is a special case of the relationship valid for continuous-time Markov chains and proved in Tomkó [ 93 ].
Theorem 10.1.
Let
be an ergodic Markov chain, and 
is a subset of its state space. Then with
probability 
.
where 
and 
denote the mean sojourn time of the chain in
and 
rduring a cycle,respectively. The ergodic (
stationary, steady-state ) distribution of 
is denoted by 
.
In an 
-server system the mean number of arrivals to a
given server during time 
is 
given 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
- server system the mean number of completed
services is 
and thus
However, if we consider now the customers for a tagged customer
the waiting and response times are
more important than the measures defined above. Let us define by
, 
the waiting, 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 its service time. Of course,
and 
are random variables and their mean, denoted by
and 
, are appropriate for measuring the efficiency of
the system. It is not easy in general to obtain their distribution
function.
Other characteristic of the system is the queue length, and the number of customers in the
system. Let the random variables 
, 
denote the number of customers in the queue, in
the system at time 
, respectively. Clearly, in an 
-server system we have
The primary aim is to get their distributions, but it is not always possible, many times we have only their mean values or their generating function.