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

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.

It is considered a fixed time interval T.

λ = the average number of arrivals in T μ = the average number of clearances in T 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

= 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

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