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.

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