Queueing theory

[1] 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 a service.

Queueing theory has its origins in research by Agner Krarup Erlang, who created models to describe the system of incoming calls at the Copenhagen Telephone Exchange Company.

[3][4] The spelling "queueing" over "queuing" is typically encountered in the academic research field.

Queueing theory is one of the major areas of study in the discipline of management science.

Through management science, businesses are able to solve a variety of problems using different scientific and mathematical approaches.

[5] The overall goal of queueing analysis is to compute these characteristics for the current system and then test several alternatives that could lead to improvement.

These systems help in the final decision making process by showing ways to increase savings, reduce waiting time, improve efficiency, etc.

The system transitions between values of k by "births" and "deaths", which occur at the arrival rates

Single queueing nodes are usually described using Kendall's notation in the form A/S/c where A describes the distribution of durations between each arrival to the queue, S the distribution of service times for jobs, and c the number of servers at the node.

[6][7] For an example of the notation, the M/M/1 queue is a simple model where a single server serves jobs that arrive according to a Poisson process (where inter-arrival durations are exponentially distributed) and have exponentially distributed service times (the M denotes a Markov process).

In an M/G/1 queue, the G stands for "general" and indicates an arbitrary probability distribution for service times.

A common basic queueing system is attributed to Erlang and is a modification of Little's Law.

In 1909, Agner Krarup Erlang, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on what would now be called queueing theory.

The M/G/1 queue was solved by Felix Pollaczek in 1930,[13] a solution later recast in probabilistic terms by Aleksandr Khinchin and now known as the Pollaczek–Khinchine formula.

His initial contribution to this field was his doctoral thesis at the Massachusetts Institute of Technology in 1962, published in book form in 1964.

His theoretical work published in the early 1970s underpinned the use of packet switching in the ARPANET, a forerunner to the Internet.

[18] Systems with coupled orbits are an important part in queueing theory in the application to wireless networks and signal processing.

[28] The first significant results in this area were Jackson networks,[29][30] for which an efficient product-form stationary distribution exists and the mean value analysis[31] (which allows average metrics such as throughput and sojourn times) can be computed.

[21] In the more general case where jobs can visit more than one node, backpressure routing gives optimal throughput.

Fluid models are continuous deterministic analogs of queueing networks obtained by taking the limit when the process is scaled in time and space, allowing heterogeneous objects.

This scaled trajectory converges to a deterministic equation which allows the stability of the system to be proven.

[42] Queueing theory finds widespread application in computer science and information technology.

By applying queueing theory principles, designers can optimize these systems, ensuring responsive performance and efficient resource utilization.

Beyond the technological realm, queueing theory is relevant to everyday experiences.

Whether waiting in line at a supermarket or for public transportation, understanding the principles of queueing theory provides valuable insights into optimizing these systems for enhanced user satisfaction.

Queueing theory, a discipline rooted in applied mathematics and computer science, is a field dedicated to the study and analysis of queues, or waiting lines, and their implications across a diverse range of applications.

This theoretical framework has proven instrumental in understanding and optimizing the efficiency of systems characterized by the presence of queues.

The study of queues is essential in contexts such as traffic systems, computer networks, telecommunications, and service operations.

The efficiency of queueing systems is gauged through key performance metrics.

These metrics provide insights into the system's functionality, guiding decisions aimed at enhancing performance and reducing wait times.

Queue networks are systems in which single queues are connected by a routing network. In this image, servers are represented by circles, queues by a series of rectangles and the routing network by arrows. In the study of queue networks one typically tries to obtain the equilibrium distribution of the network, although in many applications the study of the transient state is fundamental.

A black box. Jobs arrive to, and depart from, the queue.

A queueing node with 3 servers. Server a is idle, and thus an arrival is given to it to process. Server b is currently busy and will take some time before it can complete service of its job. Server c has just completed service of a job and thus will be next to receive an arriving job.

A birth–death process. The values in the circles represent the state of the system, which evolves based on arrival rates *λ _i* and departure rates *μ _i* .