Queueing Theory
Introduction
Queueing theory is a 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 is directly applicable to intelligent customer management, logistics, and telecommunications. 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.
History
The origins of the study of queueing theory can be traced back to the early 20th century with the work of A.K. Erlang, a Danish engineer who created the fields of traffic engineering and queueing theory while working for the Copenhagen Telephone Exchange. Erlang sought to understand the randomness and probability involved in call lengths and waiting times, and his work laid the foundation for the field as we know it today.
Mathematical Foundations
Queueing theory is based on mathematical principles and uses models to represent the various aspects of a queue. These models help to describe the behavior of the queue, predict its future behavior, and help to make decisions about how to manage the queue. The most common queueing models are based on the Markov process, a type of stochastic process, and are known as Markovian queueing models.
Markovian Queueing Models
Markovian queueing models are a class of queueing models that assume the Markov property, which states that the probability of moving to the next state depends only on the current state and not on the sequence of events that preceded it. This assumption simplifies the analysis and makes these models particularly tractable.
The most common Markovian queueing models are the M/M/1 and M/M/c queues. The M/M/1 queue is a single-server queue, where arrivals are determined by a Poisson process and job service times have an exponential distribution. The M/M/c queue extends the M/M/1 model to multiple servers.
Applications
Queueing theory has a wide range of applications in various fields. In computer science, it is used to model and analyze the performance of algorithms, particularly those related to job scheduling. In telecommunications, it is used to model and analyze the performance of networks, particularly in relation to traffic intensity and congestion. In operations research, it is used to model and analyze the performance of systems, particularly in relation to customer service and logistics.
Computer Science
In computer science, queueing theory is used to model and analyze the performance of various systems and algorithms. For example, in the study of algorithms for job scheduling, queueing models can be used to predict the performance of different scheduling policies, such as first-come, first-served (FCFS), shortest job first (SJF), and round-robin scheduling.
Telecommunications
In telecommunications, queueing theory is used to model and analyze the performance of networks. For example, in the study of network traffic, queueing models can be used to predict the performance of different traffic management policies, such as traffic shaping and traffic policing.
Operations Research
In operations research, queueing theory is used to model and analyze the performance of various systems. For example, in the study of customer service, queueing models can be used to predict the performance of different service policies, such as first-come, first-served (FCFS), priority service, and reservation service.
Conclusion
Queueing theory is a powerful tool that allows for the analysis and prediction of the behavior of queues. By using mathematical models, it can provide valuable insights into the performance of various systems and policies, making it an essential part of fields such as computer science, telecommunications, and operations research.