Queueing Theory

Queueing Theory is a mathematical framework used to analyze and optimize the flow of work or customer service in various settings, such as business, manufacturing, and healthcare. Developed initially by Agner Krarup Erlang, the theory focuses on understanding the arrival rates of customers or tasks and the service capacity of systems, aiming to balance efficiency with customer satisfaction. The most commonly used model is the single queue model, which simplifies the complexities of service dynamics and is perceived as fairer in terms of social justice, as it adheres to a first-come-first-serve principle.

Queueing models can vary significantly, addressing different scenarios and requirements. For instance, the M/G/1 model considers general service times, while more complex variations like M/M/1 and G/G/1 cater to specific needs in multi-service environments. The application of queueing theory extends beyond traditional businesses; it plays a vital role in hospital management by analyzing patient flow and wait times, as well as in urban planning for traffic management, where vehicle arrival patterns can be modeled using similar principles.

Key concepts within queueing theory include the trade-offs between service costs and wait times, emphasizing the importance of effective queue management for maximizing profit and enhancing customer experience. Overall, understanding queueing theory provides valuable insights into improving operational efficiency and customer interactions across diverse fields.

Published in: 2021

By:

Subject Terms

Queueing Theory

Abstract

In business, manufacturing, and industrial engineering, determining the correct flow of work or customer service for optimum profit while ensuring customer satisfaction requires a specific approach found in queueing theory. Queueing theory encompasses a group of mathematical models developed over time to route work or customers in a manner that balances resources and service capacity with productivity and customer satisfaction. While there are no perfect models for a given scenario or need, the most common models selected are variations of the single queue model. Multiple queue models exist and are used, but less frequently than the single queue model.

Overview

Queueing models are mathematical models that address the arrival times and service capacity within a system. Agner Krarup Erlang was the originator of queueing theory that addressed single queues, but later advanced the model to handle multiple service nodes and more dynamic movement within and around the queue. Though many variations of the single queue model M/G/1 have been produced as the result of industrial systems or business management needs, the single queue is often the model of choice. This is, in part, due to the perception that the single queue is simplified and ideal. In business, the greatest concerns when choosing a model is minimizing waiting times while promoting social justice. In manufacturing, balancing the job flow while minimizing manufacturing costs is the most desirable outcome. There is no perfect model for a given system, but with careful planning, and flexibility in design, most issues can be overcome.

Early Models. Queueing theory is defined as the mathematical study of queues or waiting lines. Early models of queueing theory were formulated by Agner Krarup Erlang, a Danish mathematician and engineer, to explain the Copenhagen telephone exchange (telephone networks analysis). Briefly, in 1909 he applied the concepts of probability to determine the number of circuits that were required to provide quality telephone service, and how many telephone operators would be required to handle a certain volume of callers. He used a Poisson process to model the quantity of telephone calls that arrived in the exchange. This model was based on the earlier work of Andrey Markov for single queues (Markov chains), which states that in a sequence of events each event is dependent upon the state of a previous event.

There are several types of queueing models. The earliest type, the model Erlang used for the Copenhagen exchange (1917), is the M/D/1 type (Kendall notation). In this equation, M represents Markov, or the arrivals that occur using a Poisson process; D represents deterministic, or the fixed amount of service required by number of jobs arriving at the queue. Three years later, Erlang produced the M/D/k model, where k represents the number of servers stationed at a queueing node. This allows for the case where there are more jobs at one node than servers to meet the need and funnels all jobs into one queue until service is available.

The M/M/1 queue model is formulated to handle a single server that receives jobs that follow a Poisson process and have service requirements that are exponentially distributed. As industrial methods for processing jobs advanced, so did the need for a mathematical model to handle more complex queues of jobs. In 1930, Felix Pollaszek solved the model M/G/1, where G (general) represents arbitrary probability distribution of jobs. John Kingman produced a formula (Kingman's formula) for mean waiting time: G/G/1, based from the queueing model Pollaszek advanced. Phase-type queues are solved using matrix geometric methods and matrix analytic methods. These approaches allow for inter-arrival and service time distributions to be factored into a queue flow.

Reasons for Queueing Theory. There are typically three decisions to be made when designing a queueing system: the number of servers at a service node, efficiency of the servers, and number of service nodes. Intertwined in these three decisions is the determination of the appropriate level of service needed for the queueing system. Decisions regarding the service capacity are normally based on two components: costs resulting from providing service and time waiting for the service. These concepts put pressure on decision makers; reducing service costs demands providing minimal service, but to offset waiting requires greater service.

To strike a balance between these two factors, it is useful to evaluate their impact via cost, primarily the cost of waiting. The reason for this is that the cost of waiting is related to a loss of profit. If this involves queues for humans being provided a service, it is more difficult to measure cost than for a job being performed by a machine. In the latter case, costs are straightforward, but the human factor introduces unknown variables that result in a miss for accurately calculating cost, which results in loss of profit. Hence, the current solution is to balance wait times with cost of providing service, though no perfect solution exists.

Further Insights

Some important factors that are involved with queueing include queueing networks and network algorithms. Both concepts highlight the complexity of queues in modern day usage, most commonly, but not limited to, customer service. A queueing network represents a system of queues that are connected to a customer router. Nodes can be connected so that after a customer is serviced at one node, they can proceed to the next node, and so forth, or leave the network entirely. Mathematically, these networks can be described as: for networks of m nodes, m-dimensional vectors (x1, x2,….xm) describe the state of the system, and x denotes the number of customers at each node.

Many different scenarios can present when effectively managing the flow of a queue, and routing algorithms, or algorithms that allow a network scheduler to optimally guide a customer queue, are key. The general scenario that presents is when backpressure occurs from customers visiting more than one node. Several concepts are related to routing algorithms: mean field limits, fluid limits, and heavy traffic/diffusion approximations. Mean field limits represent the limits of the proportion of queues in different states. The effect of one queue upon many queues is approximated by a differential equation that allows the convergence of one model to that of the original model. This mathematical approach stems from mean field theory, which evaluates the interaction of complex stochastic models using a simpler model, by averaging the effect of many individual effects from a complex system.

When a process is scaled by time and space, fluid models provide a scaled trajectory of a complex system that allows a system's stability to be proven. This model was produced from the central limit theorem for Markov chains and a law of large numbers, by Thomas G. Kurtz. Heavy traffic/diffusion approximations use Brownian motion/Ornsteil-Ulenbeck process, or the concept that molecules are in random motion due to collision with other molecules in the surrounding environment, to approximate the behavior of individuals (how they diffuse) in a queue system. Both fluid models and heavy traffic/diffusion approximations help to direct dynamic situations within a model to reduce mathematically to the single queue model.

Some examples of queueing theory include hospital management and traffic flow design. In the field of health care, queueing theory is used to address waiting time, utilization analysis, and appointment systems. Though the processes that must be managed are varied, common issues to be addressed include patient arrival times, waiting for service, obtaining service, and discharge from service. Reneging, or when a patient decides to stop waiting due to prolonged waiting, is of importance to health care institutions. This factor is a sign of demand exceeding capacity and creates a dysfunctional equilibrium.

Determining the appropriate approach to the queue (i.e., first-come-first-serve vs. triage) is a constant problem. Presetting specific utilization levels or creating fixed patient-to-resource ratios produce reduced service quality because of congestion. Due to the high level of variability in many factors in health care, identifying one ideal model has proved challenging, but common models are variations of the single M/G/1 queue model.

Queueing theory is also used in city planning, specifically in designing optimum traffic flow. In a typical queueing model for traffic (Poisson process), the interarrival times are distributed exponentially. In a conventional model, the arriving vehicles form a queue in front of the server (light, stop sign). Each vehicle in the queue advances at specific speed to the stop line (imaginary line between queue and server). This stationary model is considered a M/G/1 queueing model with a first-come-first-serve priority (service). The queue is in statistical equilibrium, and queue lengths do not change with time. However, in nonequilibrium conditions, transient queueing models should be used, which can address issues such as speed-flow-density. The model can be applied to multilane and unidirectional roads.

Issues

Queue models are present in many different types of industries and businesses. For example, industrial engineering uses queue theory to manage work flows for machines and employees, informational technologists use queue theory to manage iterative drives or web-based customer service, as do banks, stores, and health care institutions. Employing the correct queue model to a system is imperative for many reasons, including efficiency in both time and productivity, customer satisfaction, and to maximize profit. One can see the differences in queue models between retail institutions, which use multiple lines with many check stands, and banks that utilize one queue with only a few tellers.

Companies that prioritize queueing properly tend to achieve the best customer satisfaction with the least expense. A properly selected queue will reduce the negative effect of a customer's wait. Waiting presents a significant problem from the customer standpoint. Waiting produces a lack of activity, and this can lead to irritation for many people. Queue type can affect the amount of wait time a customer experiences. The main question is whether a single queue or a multiple queue will be the most effective.

Both types of queues have advantages. The single queue minimizes wait time variation because the differences of the arrival rate and service time are nullified. Multiple queues lead to shorter waiting times by reducing the distance to the server. The multiple queue is also beneficial when service capacity is faster than the speed that customers move through the queue, compared with a single queue. Also, customers can choose their server (e.g., because one server is moving faster than the other). This concept of choosing a server is a key difference between the single queue and multiple queue. This gives the customer a sense of control, which in turn has a positive effect on customer attitude.

Central to achieving the goals of customer satisfaction while maximizing profit is the concept of social justice, or perceived understanding of queue models in the context of personal experience from the customer's viewpoint. This stems from wait times for the customer while in the queue. Two interesting aspects of waiting are connected to social and procedural justice. Social justice of waiting is related to the fairness of the queue and service being offered, while procedural justice is related to the perceived fairness of the procedures used to conduct the queue.

Interestingly, single queues are considered fairer than multiple queues from a social justice perspective. This is because in a single queue, the random factor of first-come-first-serve reduces the likelihood of bias on the server's part. Also, all customers in the queue are subject to the same rules and regulations. However, in a multiple queue structure, the first-come-first-serve rule does not apply, because customers can move from one queue to the next, regardless of when they arrived on site.

Furthermore, the rate that one queue moves compared with another can vary, leading to a lack of what is called distributive justice. For these reasons, the single queue model has gained popularity to solve the social, procedural, and distributive justice issues, but leaves the issue of wait times. The ideal scenario would be to balance wait times with minimizing the perceptions of bias or lack of social justice.

Terms & Concepts

Brownian Motion: The most important stochastic process, first observed by Robert Brown, to describe the random motion of particles through a fluid, moving because of collision with other molecules in the surrounding medium.

Distributive Justice: Socially just apportionment of goods or services.

Kendall's Notation: Standard system of classifying queueing nodes. In 1953, D. C. Kendall presented a queueing model with the notation: A/S/c, where A is the time between intervals in a queue, S is the quantity of jobs, and c is the number of servers at a node.

Markov Chain: First described by Andrey Markov, a type of queuing process that uses a discrete state space or discrete index set (time variables). Each event occurring in the chain is dependent upon the conditions set by a previous event.

Poisson Process: A stochastic modeling process for accounting for random arrival times in a system. It bears similarities to the Bernoulli process.

Procedural Justice: Concept of fairness in processes that involves allocation of resources.

Social Justice: Concept of fairness between the individual and society. This includes equal distribution of material goods, prospects, and privileges among individuals in a society.

Stochastic Model: Discrete or continuous random variables categorized by time.

Bibliography

Boxma, O., & Walraevens, J. (2017). Computational methods and applications in queueing theory. Annals of Operations Research, 1–2. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=122574688&site=ehost-live

Bramson, M. (1999). A stable queueing network with unstable fluid model. The Annals of Applied Probability, 9(3), 818. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=10589417&site=ehost-live

Chen, X., Li, Z., Li, L. & Shi, Q. (2014). A traffic breakdown model based on queueing theory. Networks & Spatial Economics, 14(3/4), 485–504. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=99841352&site=ehost-live

Gilliam, R. R. (1979). An application of queueing theory to airport passenger security screening. Interfaces, 9(4), 117–122. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=6694096&site=ehost-live

Heidemann, D. (2001). A queueing theory model of nonstationary traffic flow. Transportation Science, 35(4), 405. Retrieved January 28, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=5716820&site=ehost-live

Kendall, D. G. (1953). Stoichastic processes occuring in the theory of queues and their analysis by the method of the imbedded Markov chain. The Annals of Mathematical Statistics, 24(3), 338.

Larson, R. C. (1987). Perspective on queues: Social justice and the psychology of queueing. Operations Research, 35(6), 895–905. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=4481017&site=ehost-live

Lu Y., Musalem A., Olivares M., & Schikrut A. (2013). Measuring the effect of queues on customer purchases. Management Science, 59(8), 1743–1763. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=89598210&site=ehost-live

Pakdaman, K., Thieullen, M., Wainrib, G. (2010). Fluid limit theorems for stochastic hybrid systems with application to neuron models. Advances in Applied Probability, 42(3), 761. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=54905735&site=ehost-live

Rafeli, A., Barron, G., & Haber, K. (2002). The effects of queue structure on attitudes. Journal of Service Research, 5(2), 125–140. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=7917480&site=ehost-live

Yamada, K. (1995). Diffusion approximation for open state-dependent queuing networks under heavy traffic situation. The Annals of Applied Probability, 5(4), 958. Retrieved January 21, 2018 from EBSCO Online Database Business Source Ultimate. http://search.ebscohost.com/login.aspx?direct=true&db=bsu&AN=10545612&site=ehost-live

Queueing Theory

On this Page

Subject Terms

Queueing Theory

Abstract

Overview

Further Insights

Issues

Terms & Concepts

Bibliography

Suggested Reading