Queuing theory

from Wikipedia, the free encyclopedia

The queuing theory (or operator theory ) is a branch of probability theory and operations research and thus an example of applied mathematics . It deals with the mathematical analysis of systems in which orders from operator stations are processed and provides answers to questions about the characteristic variables such as the stability of the waiting system , the number of customers in the system, their waiting time, etc. It supports, among other things, management decisions about the deployment of staff and the handling process and helps to develop a system for measuring performance . Their application ranges from computers , telecommunication systems , traffic systems to logistics and manufacturing systems .

Systematics

Basically, a waiting system consists of an operating area in which one or more execution units process orders, and a waiting room in which incoming orders wait for execution when execution units are currently not free but available. Completed orders leave the system.

A waiting system is described with six parameters (here in the order of the Kendall notation ):

Arrival process
The stochastic process that describes the arrival of new orders. A Poisson process is often used for this .
Service time distribution
The stochastic distribution of execution times (the pure processing time of an order without waiting time). In many cases an exponential distribution is assumed for this .
Number of execution units
Number of units that can process orders in parallel. For example, the number of (open) cash registers in a supermarket.
Capacity of the queue
Specifies the maximum number of jobs waiting (the maximum length of the queue). In many cases this is assumed to be infinitely large ( ).
population
The set of all possible orders from which orders enter the system through the arrival process. Is assumed to be infinitely large in many cases ( ).
Handling discipline
Specifies the order in which jobs waiting in the queue are processed. Mostly the FCFS principle is used. This means that the order at the front end of the queue is processed next.

Using these assumptions, the queue theory delivers statements about performance parameters such as the mean queue length, the number of customers in the waiting system, the mean waiting time or the like. By David George Kendall uniform notation to describe the response systems has been developed that Kendall's notation . Waiting systems without a waiting room are called loss systems. Central statements are Little's law , Erlang B and Erlang C as well as the Gordon – Newell theorem.

Areas of application

Queuing theory is used in the analysis of computers, telecommunication systems ( call centers ), transportation systems ( traffic flow ), logistics and manufacturing systems. Depending on the area of ​​application, the abstract terms order and operating station have very different meanings.

computer
Order = task ; Operator station = CPU
telecommunications
Job = phone call; Operator station = telephone line
traffic system
Order = driver; Service station = gas station
production
Order = machine to be assembled; Operator station = fitter

Several such (simple) waiting systems can be combined to form so-called queue networks. Various approaches have been developed for the mathematical analysis of waiting systems. These include Markov chains , Petri nets and discrete event simulation .

history

The queuing theory was first applied by the mathematician Agner Krarup Erlang in 1909 for the dimensioning of telephone exchanges ( The Theory of Probabilities and Telephone Conversations ). In the 1930s, the Pollaczek-Chintschin formula made further simplifications of the theory possible. Later significant contributions came from David George Kendall , Dennis Victor Lindley, James R. Jackson, Gordon, Gordon F. Newell, Felix Pollaczek , Carl Adam Petri , Leonard Kleinrock, and Paul Ehrenfest . With the development of computers and computer networks, research in this area also gained in importance.

See also

literature

  • Natalja N. Amossova: Operation Theory : An Introduction. Teubner, Leipzig 1986, ISBN 3-322-00309-4 .
  • Dieter Baum: Basics of the queuing theory. Springer Spectrum, Berlin / Heidelberg 2013, ISBN 978-3-642-39631-1 .
  • Gunter Bolch, Stefan Greiner, Hermann de Meer, Kishor S. Trivedi: Queuing Networks and Markov Chains. Wiley & Sons, Hoboken, New Jersey, 2006.
  • Donald Gross, Carl M. Harris: Fundamentals of Queuing Theory. Wiley & Sons, New York 1994.
  • Heinz Häfner: A queuing approach for integrated production planning. Physica-Verlag, Heidelberg 1992, ISBN 3-7908-0579-3 . (also dissertation U Mannheim)
  • Uwe Kiencke: Discrete event systems: Modeling and control of distributed systems. 2., revised. and exp. Edition. Oldenbourg Verlag, Munich 2006, ISBN 3-486-58011-6 .
  • Edward D. Lazowska, John Zahorjan, G. Scott Graham, Kenneth C. Sevcik: Quantitative System Performance: Computer System Analysis Using Queuing Network Models. Prentice-Hall, 1984. ( cs.washington.edu )
  • Volker Rausch: Operating systems for maintenance. A combination of mathematical-statistical methods and operating theory. SVH, Saarbrücken 2010, ISBN 978-3-8381-1492-7 .
  • Volker Rausch: Open and closed operating systems in production and process engineering. Grin Verlag, Munich 2015, ISBN 978-3-656-89453-7 .
  • Markus Sommereder: Modeling queuing systems with Markov chains: Basics, concepts, methods. Publishing house Dr. Müller, Saarbrücken 2008, ISBN 978-3-8364-5697-5 .

Web links

Wiktionary: queuing theory  - explanations of meanings, word origins, synonyms, translations