Queueing theory

Assessment | Biopsychology | Comparative | Cognitive | Developmental | Language | Individual differences | Personality | Philosophy | Social |
Methods | Statistics | Clinical | Educational | Industrial | Professional items | World psychology |

Statistics: Scientific method · Research methods · Experimental design · Undergraduate statistics courses · Statistical tests · Game theory · Decision theory

---

This article needs rewriting to enhance its relevance to psychologists..
Please help to improve this page yourself if you can..

Queueing theory is the mathematical study of waiting lines, or queues. The theory enables mathematical analysis of several related processes, including arriving at the (back of the) queue, waiting in the queue (essentially a storage process), and being served at the front of the queue. The theory permits the derivation and calculation of several performance measures including the average waiting time in the queue or the system, the expected number waiting or receiving service, and the probability of encountering the system in certain states, such as empty, full, having an available server or having to wait a certain time to be served.

Queueing theory has applications in diverse fields, including telecommunications, computing and the design of factories, shops, offices and hospitals.

Overview

The word queue comes, via French, from the Latin cauda, meaning tail. The spelling "queueing" over "queuing" is typically encountered in the academic research in the field. In fact, one of the flagship journals of the profession is named "Queueing Systems". "Queueing" - the correct spelling - is the only word in the English language with five consecutive vowels.

Queueing theory is generally considered a branch of operations research because the results are often used when making business decisions about the resources needed to provide service. It is applicable in a wide variety of situations that may be encountered in business, commerce, industry, healthcare, public service and engineering. Applications are frequently encountered in customer service situations as well as transport and telecommunication. Queueing theory is directly applicable to intelligent transportation systems, call centers, PABXs, networks, telecommunications, server queueing, mainframe computer queueing of telecommunications terminals, advanced telecommunications systems, and traffic flow.

Notation for describing the characteristics of a queueing model was first suggested by David G. Kendall in 1953. Kendall's notation introduced an A/B/C queueing notation that can be found in all standard modern works on queueing theory, for example, Tijms.

The A/B/C notation designates a queueing system having A as interarrival time distribution, B as service time distribution, and C as number of servers. For example, "G/D/1" would indicate a General (may be anything) arrival process, a Deterministic (constant time) service process and a single server. More details on this notation are given in the article about queueing models.

History

Agner Krarup Erlang, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on queueing theory in 1909.

David G. Kendall introduced an A/B/C queueing notation in 1953. Important work on queueing theory used in modern packet switching networks was performed in the early 1960s by Leonard Kleinrock.

Queueing networks

Networks of queues are systems which contain an arbitrary, but finite, number m of queues. Customers, sometimes of different classes, travel through the network and are served at the nodes. The state of a network can be described by a vector $\scriptstyle{(k_1,k_2,\ldots,k_m)}$, where k_i is the number of customers at queue i. In open networks, customers can join and leave the system, whereas in closed networks the total number of customers within the system remains fixed.

The first significant result in the area was Jackson networks, for which an efficient product form equilibrium distribution exists.

Role of Poisson process, exponential distributions

A useful queueing model represents a real-life system with sufficient accuracy and is analytically tractable. A queueing model based on the Poisson process and its companion exponential probability distribution often meets these two requirements. A Poisson process models random events (such as a customer arrival, a request for action from a web server, or the completion of the actions requested of a web server) as emanating from a memoryless process. That is, the length of the time interval from the current time to the occurrence of the next event does not depend upon the time of occurrence of the last event. In the Poisson probability distribution, the observer records the number of events that occur in a time interval of fixed length. In the (negative) exponential probability distribution, the observer records the length of the time interval between consecutive events. In both, the underlying physical process is memoryless.

Models based on the Poisson process often respond to inputs from the environment in a manner that mimics the response of the system being modeled to those same inputs. The analytically tractable models that result yield both information about the system being modeled and the form of their solution. Even a queueing model based on the Poisson process that does a relatively poor job of mimicking detailed system performance can be useful. The fact that such models often give "worst-case" scenario evaluations appeals to system designers who prefer to include a safety factor in their designs. Also, the form of the solution of models based on the Poisson process often provides insight into the form of the solution to a queueing problem whose detailed behavior is poorly mimicked. As a result, queueing models are frequently modeled as Poisson processes through the use of the exponential distribution.

Limitations of mathematical approach

Classic queueing theory is often too mathematically restrictive to be able to model real-world situations exactly. This restriction arises because the underlying assumptions of the theory do not always hold in the real world. The complexity of production lines with product-specific characteristics cannot be handled with mathematical models. Therefore special tools like Plant Simulation have been developed to simulate, analyze, visualize and optimize time dynamic queueing line behavior.

For example; the mathematical models often assume infinite numbers of customers, infinite queue capacity, or no bounds on inter-arrival or service times, when it is quite apparent that these bounds must exist in reality. Often, although the bounds do exist, they can be safely ignored because the differences between the real-world and theory is not statistically significant, as the probability that such boundary situations might occur is remote compared to the expected normal situation. In other cases the theoretical solution may either prove intractable or insufficiently informative to be useful.

Alternative means of analysis have thus been devised in order to provide some insight into problems that do not fall under the scope of queueing theory, although they are often scenario-specific because they generally consist of computer simulations or analysis of experimental data. See network traffic simulation.

See also

• BCMP network
• Buzen's algorithm
• Ehrenfest model
• Erlang unit
• Fork-join queue
• Gordon–Newell network
• Industrial engineering
• Jackson network
• Little's law
• Markovian arrival processes
• Network simulation
• Pollaczek-Khinchine formula -- the mean analysis of an M/G/1 queue
• Quasireversibility
• Queue area
• Queueing delay
• Random early detection
• Renewal theory
• Throughput
• Traffic generation model

Further reading

• Gross, Donald; Carl M. Harris (1998). Fundamentals of Queueing Theory, Wiley.
• Deitel, Harvey M. [1982] (1984). An introduction to operating systems, revisited first, 673, Addison-Wesley. chap.15, pp.380–412
• Lazowska, Edward D.; John Zahorjan, G. Scott Graham, Kenneth C. Sevcik (1984). Quantitative System Performance: Computer System Analysis Using Queueing Network Models, Prentice-Hall, Inc.
• Zukerman, Moshe. Introduction to Queueing Theory and Stochastic Teletraffic Models.

External links

• Virtamo's Queueing Theory Course
• Shmula's Queueing Theory Page
• Myron Hlynka's Queueing Theory Page
• Queueing Theory Basics
• Queueing theory calculator