Queuing theory 2

Authors: Tanja Gutsch and Gökcen Özcetin

Introduction

A queue is a waiting line (like customers waiting at a supermarket checkout counter);queueing theory is the mathematical theory of waiting lines.More generally,queueing theory is concerned with the mathematical modeling and analysis of systems that provide service to random demands. A queueing model is an abstract description of such a system.Typically, a queueing model represents:

1) the system's physical configuration, by specifying the number and arrangement of the servers, which provide service to the customers 2) the stochastic (that is, probabilistic or statistical) nature of the demands, by specifying the variability in the arrival process and in the service process.

History

Queueing theory was born in the early 1900s with the work of A. K. Erlang of the Copenhagen Telephone Company, who derived several important formulas for teletraffic engineering that today bear his name. The range of applications has grown to include not only telecommunications and computer science, but also manufacturing, air traffic control, military logistics, design of theme parks, and many other areas that involve service systems whose demands are random. Queueing theory is considered to be one of the standard methodologies (together with linear programming, simulation, etc.) of operations research and management science, and is standard fare in academic programs in industrial engineering, manufacturing engineering, etc., as well as in programs in telecommunications, computer engineering, and computer science. There are dozens of books and thousands of papers on queueing theory, and they continue to be published at an ever-increasing rate. But, despite its apparent simplicity (customers arrive, request service, and leave or wait until they get it), the subject is one of some depth and subtlety. We will illustrate this by briefly visiting some of the most important models, and describing along the way some of the obvious features and some of the subtletie.

The M/M/1 Queuing System

M/M/1: (∞, FIFO)

The first term M/M/1 describes a Markov process of arrivals and of processing. The notion Markov is used to honor the russian probability theorist Markov and means, that the events are Poisson- and the distances between the events are exponentially distributed. That implies that the arrival processes are random and independent of each other. The "1" denotes that there is one operator station. The term (∞, FIFO) describes that there is no restriction on the size of the queue, else a element loss could happen, and that it is operates on a first-in-first-out principle.

Related Formulas

λ = the average number of arrivals

1/λ = the average distance between the arrivals

μ = the average number of clearances

1/μ = the average time for clearance

The system is stable, if Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \rho =\frac{\lambda }{\mu }\leq

   the  number  of operator stations.

For the system M/M/1 formular can be derived , for example describing the avarage lenght of the queue.

Expected avarege lenght of the queue : 
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.):  EL_{q}=\frac{\lambda ^{2}}{\mu(\mu -\lambda )}

Expected avarage waiting period :
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EW_{q}=\frac{\lambda}{\mu(\mu -\lambda )}

Average number of  elements in system :
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EL=\frac{\lambda}{\mu -\lambda }

Avarage residence time in system :
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EW=\frac{1}{\mu -\lambda }

---

Proof

The following is proof of the formulas. It will show you how the formulas that is widely used was developed.

Interesting appears the average queue length, and average waiting time of a person.

The starting point is a very small time interval At in the added only one person or can be dispatched. The probability (P) that there is no element in the queue is equal to the probability that none is in the queue and within DELTA.t no new matters worse, plus the probability that an element is in the queue and this is dealt with, However, no new added

P0 = P0 (1-λΔt) + P1 (1-λΔt) μΔt = P0 (1-λΔt) + P1μΔt - P1λΔtμΔt

Thus , there is the probability that a person in the system is to be

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): P_{1}=\frac{\lambda }{\mu }P_{0}

This formula can be generalized to :

$P_{i}=P_{0}\left({\frac {\lambda }{\mu }}\right)^{i}$

The sum of all probabilities is equal to 1

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{\infty }P_{i}=1=P_{0}\sum_{i=0}^{\infty }\left (\frac{\lambda}{\mu }\right)^i

This term Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{\infty }\left (\frac{ \lambda }{\mu} \right )^i

can be replaced Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{1}{1-\lambda /\mu }
since λ is smaller than μ (geometric series).

So we obtain:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): P_{0}=1-\lambda /{\mu }

The average lenght of the queue (expected value )is equal to the probaility that the queue lenght i occurs multiplied by i, summe over all i.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): n=\sum_{i=0}^{\infty }iP_{i}=P_{0}\sum_{i=0}^{\infty }i\left (\frac{\lambda}{\mu }\right)^i=\left ( 1-\frac{\lambda }{\mu } \right)\sum_{i=0}^{\infty }i\left ( \frac{\lambda }{\mu } \right )^i

The term Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{\infty }i\frac{\lambda }{\mu }^{i}

can be replaced by  Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{\lambda /\mu }{(1-\lambda /\mu )^2}

We obtain for n:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): n=\frac{\frac{\lambda }{\mu }}{1-\lambda/\mu }=\frac{\lambda }{\mu-\lambda }

The average time spent on tv sn eşement in the system is derived from the average lenght ofthe queue divided by the average arrivals per time unit.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): t_{v}=\frac{n}{\lambda }=\frac{1}{\mu -\lambda }

The average waiting time tw is equal to the average residence time minus the average turnaround time.

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): t_{w}=\frac{1}{\mu -\lambda }-\frac{1}{\mu }

Example

On average, every 6 minutes, an aeroplane arrives in an airport with only one runway. The aeroplanes need 5 minutes to land. Whilst one aeroplane is landing, other incoming aircraft must wait. The required time for the landing and the number of aeroplanes arriving are exponentially distributed.

It is a (M/M/1)- queue without limit of the waiting room.

The arrival rate is l = 1/EA = 1/6

The working rate is m = 1/EB = 1/5 = 0,2

The relation between the arrivals and the clearance is: p = l/μ = 5/6 < 1 (the number of operate points) so the system is stable.

The expected length of the queue is: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EL_{q}=\frac{\lambda ^{2}}{\mu(\mu -\lambda )}=5^{2}/6(6-5)=4,16

The expected waiting period is in average: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EW_{q}=\frac{\lambda}{\mu(\mu-\lambda)}=25min

The expected number of airplanes in the system is in average: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EL=l/μ-l=5/1=5

The expected staying period is in average: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EW=1/μ-l=1/(0,2-1/6)=30min