Queuing theory 2
Authors: Tanja Gutsch and Gökcen Özcetin
Inhaltsverzeichnis
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 how the formulas that is widely used was developed.
At first we calculated a equation (1), which will help us to proof the following formulas (2) , (3) , (4) , (5) directly or indirectly.
We look at a time interval, which is so small, that only one element can be added or dispatched. The probability (P0) that there is no element in the queue is equal to the probability that none is in the queue and within Δt no new will be added (P0 (1-λΔt)), plus the probability that an element is in the queue (P1 (1-λΔt)) and this is dealt with (*μΔt).
P0 = P0 (1-λΔt) + P1 (1-λΔt) μΔt = P0 (1-λΔt) + P1μΔt - P1λΔtμΔt
The term (- P1λΔtμΔt) can be leaved off, because Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \Delta t^{2}
is very small. The remaining term is:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): P_{0} = P_{0}-P_{0}\lambda \Delta t+P_{1}\mu \Delta t
and can be reformulated:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): P_{0}-P_{0}+P_{0}\lambda \Delta t = P_{1}\mu \Delta t
So , the probability P1 that an element is in the system is:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): P_{1} = P_{0} \frac{\lambda \Delta t}{\mu \Delta t} = P_{0}\frac{\lambda }{\mu }
This formula can be generalized to :
Because the sum of all probabilities is equal to 1, we obtain for (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
The geometrical series says, for is:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \sum_{i=0}^{\infty }a_{0}q^{i}= \frac{a_{0}}{1-q}
With the help of the geometrical series the 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 by Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): \frac{1}{1-\lambda /\mu }
since λ the average number of arrivals is smaller than μ the average number of clearance, else we would not have a queue.
So we obtain:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): P_{0}=1-\lambda /{\mu }
The expected number of element in the system 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.): EL=\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 :
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EL=\frac{\frac{\lambda }{\mu }}{1-\lambda/\mu }=\frac{\lambda }{\mu-\lambda }
The average length of the queue is the expected number of elements in the queue minus the degree of occupying:
Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EL_{q}= \frac{\lambda }{\mu -\lambda }-\frac{\lambda }{\mu }= \frac{\lambda \mu }{\mu \left ( \mu -\lambda \right )}-\frac{\lambda \mu -\lambda ^{2}}{\mu \left ( \mu -\lambda \right )}= \frac{\lambda ^{2}}{\mu \left ( \mu -\lambda \right )}
The average time spent on an element 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.): EW=\frac{EL_{q}}{\lambda }=\frac{1}{\mu -\lambda }
The average waiting time 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.): EW_{q}=\frac{1}{\mu -\lambda }-\frac{1}{\mu }=\frac{\mu }{\mu \left ( \mu -\lambda \right )}-\frac{\mu -\lambda }{\mu \left ( \mu -\lambda \right )}=\frac{\lambda }{\mu \left ( \mu -\lambda \right )}
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 average distance between the arrivals is 1/λ = 6 minutes , so the arrival rate is λ = 1/6 aeroplanes in a minute.
Analogouse: The working rate is μ = 1/5 = 0,2 aeroplanes in a minute.
The relation between the arrivals and the clearance is: (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 average number of aeroplanes on approach is 25/6.
The expected waiting period is in average: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EW_{q}=\frac{{1/\mu *p}}{1-p}=\frac{\lambda }{\mu (\mu -\lambda )}=25
An aeroplane has to wait in average 25 minutes until it lands in the airport.
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=\frac{p}{1-p}=\frac{\lambda }{\mu -\lambda }=\frac{5}{1}=5
The expected number of aeroplanes in the whole system is 5.
The expected staying period is in average: Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): EW=\frac{1}{\mu -\lambda }=\frac{1}{0,2-1/6}=30
An aeroplane spends in average 30 minutes in the system. (For waiting and landing)
Sources
http://www.rz.rwth-aachen.de/global/show_document.asp?id=aaaaaaaaaaavhwr
http://www.wirtschaftslexikon24.com/d/warteschlangentheorie/warteschlangentheorie.htm
