Queuing theory 3

Authors: Ebru Vurgun, Damla Yigitoglu and Özlem Özyurt

Introduction

It is a common phenomenon in everyday life to see a large number of persons waiting in front of a booking counter, in a railway station or in a theatre or in a ration shop to have some service carried out. This waiting problem leads the Danish engineer A.K. (Agner Krarup) Erlang, who worked for the Copenhagen Telephone Exchange to find a solution. He developed in 1903 the Queuing theory. Queuing theory analyze the shared facility needs to be accesed for service by a large number of jobs or customers. Examples for the queuing theory are waiting lines in cafeterias, hospitals, banks, airports and so on. In the following you can find more detailled informations for this topic.

Queueing models and Kendall's notation

The basic queueing model (show figure 1)

Fig. 1

A queueing model is characterized by:

a) The arrival process of customers. b) The behaviour of customers. c) The service times. d) The service discipline. e) The service capacity. f) The waiting room.

A special notation, called Kendall's notation, is used to describe a queueing system. The notation has the form A/B/c/K.

->A describes the interarrival time distribution

->B the service time distribution

->c the number of servers

->K the size of the system capacity (including the servers).

The symbols traditionally used for A and B are

->M for exponential distribution (M stands for Markov)

->D for deterministic distribution

->G for general distribution.

When the system capacity is infinite (K = 1) one simply uses the symbol A/B/c. For instance, M/M/1, M/M/c, M/G/1 and G/M/1 are very common queueing systems.

M/M/1 Queuing system

M/M/1 queue represents the queue length in a system having a single server, where arrivals are determined by a Poisson process and job service times have an exponential distribution.The model is the most elementary of queueing models[1] and an attractive object of study as closed-form expressions can be obtained for many metrics of interest in this model. Here is the arrival population unlimited and all arrivals wait to be served. λ is constant and μ >λ (average service rate > average arrival rate).

Operating characteristics:

1. Average server utilization					
p=λ / μ						

2. Average number of customers waiting 					
Lq= λ 2 / μ ( μ - λ )			

3. Average number in system
L = Lq + λ / μ 						

4. Average waiting time:
Wq=Lq=  λ / μ  ( μ - λ )

5. Average time in the system 
W= Wq + 1/ μ 

6. Probability of 0 customers in system
P0= 1 - λ / μ 

7. Probability of exactly n customers in system
Pn = ( λ / μ )*n*P0

An example of M/M/1 Queue

We are in a train station and we see, that a arriving train join a single queue for the runway. We have an exponentially distributed service time with a rate μ= 30 arrivals / hour ( as we computed that in 5 minutes 1 train arrived the station) and we have poisson arrivals with a rate λ= 25 arrivals / hour.

Now we want to calculate W, L, Wq and Lq.

W= 1 / μ - λ= 1/ ( 30-25)= 0,20 hours ≈ 12 min

L= λW = λ / (μ - λ)= 25/ (30-25)= 5 trains

Wq = W- (1/μ)= 1/ (μ - λ) - 1/μ= 1/ ( 30-25) - (1/30)= 0.167 hours≈ 10 min

Lq= λW= λ^2 / μ ( μ - λ )= 25 ^ 2 / 30 ( 30-25) ≈4,167 trains