Queuing theory 2: Unterschied zwischen den Versionen

Aus Operations-Research-Wiki
Wechseln zu: Navigation, Suche
[unmarkierte Version][unmarkierte Version]
(→‎Introduction)
(→‎The M/M/1 Queuing System)
Zeile 19: Zeile 19:
 
==  The M/M/1 Queuing System ==
 
==  The M/M/1 Queuing System ==
  
−
The M/M/1 system is made of a Poisson arrival, one exponential (Poisson) server, FIFO (or not specified) queue of unlimited capacity and unlimited customer population. Note that these assumptions are very strong, not satisfied for practical systems (the worst assumption is the exponential distribution of service duration - hardly satisfied by real servers). Nevertheless the M/M/1 model shows clearly the basic ideas and methods of Queuing Theory. Next two chapters summarize the basic properties of the Poisson process and give derivation of the M/M/1 theoretical model.
+
M/M/1: (∞, FIFO)
  
−
It is considered a fixed time interval T.
+
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.
  
−
λ = the average number of arrivals in T
+
λ = the average number of arrivals
−
μ = the average number of clearances in T
+
1/λ = the average distance between the arrivals
−
Interesting appears the average queue length, and average waiting time of a person.
+
μ = the average number of clearances
 +
1/μ = the average time for clearance
  
−
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.
+
The system is stable, if  <math>\rho =\frac{\lambda }{\mu }\leq</math>    the number  of operator stations.
−
 
+
−
P0 = P0 (1-λΔt) + P1 (1-λΔt) μΔt
+
−
                  = P0 (1-λΔt) + P1μΔt - P1λΔtμΔt
+
−
= P0 (1-λΔt) + P1μΔt (At ² is negligible)
+
−
Thus, there is the probability that a person in the system is to be
+
−
P1 = (λ / μ) P0
+
−
This formula can be generalized to:
+
−
 
+
−
 
+
−
The sum of all probabilities is equal to 1
+
−
 
+
−
 
+
−
The term can be replaced by Grafik3.png Grafik4.png
+
−
 
+
−
since λ is smaller than μ (geometric series).
+
−
So we obtain:
+
−
 
+
−
P0 = 1 - (λ / μ)
+
  
 
==  Example ==
 
==  Example ==

Version vom 25. Juni 2013, 15:26 Uhr


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.

λ = 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.

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 /EA= number of expected arrivals in the whole time The working rate is m = 1/EB = 1/5 = 02 /EB= needed time for 1 element

The relation between the arrivals and the clearance is: 

                            p = l/m = 5/6 < 1 (the number of operate points)

so the system is stable.

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

The arrival rate is l = 1/EA = 1/6 /EA= number of expected arrivals in the whole time The working rate is m = 1/EB = 1/5 = 02 /EB= needed time for 1 element

The relation between the arrivals and the clearance is: 

                                              p = l/m = 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}= p^{2}/1-p= l^{2}/m(m-1)=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{1/m*p}{1-p}=l/m(m-l)=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=P/1-P=l/m-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/m-l=1/(0,2-1/6)=30min

Von „https://www.wiwi.uni-kl.de/bisor-orwiki/index.php?title=Queuing_theory_2&oldid=4190“