Queueing Theory (M/M/1)

Queueing Theory (M/M/1)

Mathematical Definition

In Kendall's notation, the M/M/1 model signifies:

• M (Markovian or Memoryless): Arrivals follow a Poisson process with rate λ. Equivalently, the inter-arrival times are exponentially distributed.
• M (Markovian or Memoryless): Service times are exponentially distributed with rate μ.
• 1: There is a single server processing the jobs.

The stability of the system is determined by the traffic intensity (or utilization), denoted by ρ:

If ρ < 1, the system is stable, and the queue length has a stationary distribution. If ρ ≥ 1, the system is unstable, meaning the queue length will grow to infinity over time.

Key Concepts

Steady-State Probabilities

When the system is stable (ρ < 1), the probability of finding exactly n customers in the system (in the queue plus being served) is given by:

Expected Values (Little's Law)

The expected number of customers in the system (L) and the expected waiting time in the system (W) can be derived using Little's Law (L = λW):

Memoryless Property

The exponential distribution is the only continuous probability distribution with the memoryless property. This means the probability of an event (arrival or service completion) occurring in the next time instant is independent of how much time has already elapsed.

Historical Context

Agner Krarup Erlang, a Danish mathematician and engineer, created the field of queueing theory in the early 20th century. He was working for the Copenhagen Telephone Exchange and wanted to determine the optimal number of telephone operators needed to handle a given volume of calls without causing unacceptable delays. The M/M/1 queue is the simplest formulation in Kendall's notation, which was introduced by David G. Kendall in 1953 to classify different queueing models.

Real-world Applications

• Telecommunications: Analyzing delays in data transmission networks and designing optimal router buffers.
• Operations Management: Modeling checkout lines in retail stores or wait times in banks and post offices.
• Computer Science: Evaluating the performance of single-processor computer systems managing tasks from a job queue.
• Healthcare: Estimating patient wait times for a single specialized medical machine or a specific doctor.
• Transportation: Analyzing traffic flow at toll booths or intersections.

Related Concepts

• Poisson Process — The mathematical foundation describing the arrivals in the M/M/1 model.
• Exponential Distribution — The probability distribution used for the time between arrivals and the service times.
• Markov Chains — The M/M/1 queue is often modeled as a continuous-time Markov chain.