Queuing theory 3: Unterschied zwischen den Versionen

Version vom 30. Juni 2013, 15:54 Uhr

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.

Definition

In computer science, queueing theory is the study of queues as a technique for managing processes and objects in a computer. A queue can be studied in terms of: the source of each queued item, how frequently items arrive on the queue, how long they can or should wait, whether some items should jump ahead in the queue, how multiple queues might be formed and managed, and the rules by which items are enqueued and dequeued.

The queues that a computer manages are sometimes viewed as being in stacks. In most systems, an item is always added to the top of a stack. A process that handles queued items from the bottom of the stack first is known as a first-in first-out (FIFO) process. A process that handles the item at the top of the stack first is known as a last-in first-out (LIFO) process.

Kendall's notation

David George Kendall was an English statistician and mathematician, known for his work on probability, statistical shape analysis, ley lines and queueing theory. Kandall's Notation is the standard system used to describe and classify a queueing node.

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

A mathematical 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