8.1 Basic queueing models

Queueing models are essential tools for analyzing systems where customers or jobs arrive, wait for service, and depart. They help predict system performance and optimize resource allocation. Basic queueing models focus on arrival processes, service time distributions, and system configurations.

These models use mathematical techniques to calculate key performance measures like average queue length, waiting times, and system utilization. Understanding basic queueing models provides a foundation for analyzing more complex real-world systems and making informed decisions about capacity planning and resource management.

Arrival processes in queueing models

• Arrival processes describe the pattern and rate at which customers or jobs enter a queueing system
• Understanding arrival processes is crucial for analyzing queueing systems and predicting system performance
• Different types of arrival processes can be modeled using probability distributions and stochastic processes

Poisson process for arrivals

Top images from around the web for Poisson process for arrivals

• 

  Probability distribution - wikidoc View original

  Is this image relevant?

• 

  Poisson distribution - Wikipedia View original

  Is this image relevant?

• 

  Probability distribution - wikidoc View original

  Is this image relevant?

• 

  Poisson distribution - Wikipedia View original

  Is this image relevant?

1 of 2

Top images from around the web for Poisson process for arrivals

• 

  Probability distribution - wikidoc View original

  Is this image relevant?

• 

  Poisson distribution - Wikipedia View original

  Is this image relevant?

• 

  Probability distribution - wikidoc View original

  Is this image relevant?

• 

  Poisson distribution - Wikipedia View original

  Is this image relevant?

1 of 2

• Poisson process is a common model for describing arrivals in queueing systems
• Assumes that arrivals occur independently and at a constant average rate (λ)
• Inter-arrival times between customers follow an exponential distribution with parameter λ
• Memoryless property: the time until the next arrival is independent of the time since the last arrival
• Poisson arrivals are often used when customers arrive randomly and independently (call centers, web servers)

Batch arrivals

• Batch arrivals occur when customers or jobs arrive in groups rather than individually
• The size of each batch can be fixed or follow a probability distribution (geometric, Poisson)
• Batch arrival processes can be modeled using compound Poisson processes
• Relevant in situations where customers arrive together (families at a restaurant, bulk job submissions)
• Analyzing batch arrival systems requires considering both the arrival rate of batches and the distribution of batch sizes

Time-dependent arrival rates

• In some queueing systems, the arrival rate may vary over time
• Time-dependent arrival rates can be modeled using non-homogeneous Poisson processes
• The arrival rate λ(t) is a function of time, allowing for different intensities throughout the day or season
• Examples include rush hours in transportation systems, peak hours in call centers, and seasonal demand fluctuations
• Analyzing time-dependent arrival rates requires considering the time-varying nature of the arrival process and its impact on system performance

Service time distributions

• Service time distributions describe the amount of time required to serve a customer or complete a job
• The choice of service time distribution depends on the characteristics of the service process and the system being modeled
• Different service time distributions lead to different queueing models and analysis techniques

Exponential service times

• Exponential service times are commonly assumed in queueing models due to their memoryless property
• The service time of each customer is exponentially distributed with parameter μ (service rate)
• Memoryless property: the remaining service time is independent of the time already spent in service
• Exponential service times are often used when service durations are highly variable and unpredictable (call centers, repair facilities)
• Models with exponential service times (M/M/1, M/M/c) have tractable analytical solutions

General service time distributions

• General service time distributions allow for more flexibility in modeling service processes
• The service time can follow any probability distribution (Erlang, hyperexponential, lognormal)
• General distributions capture more realistic service time behaviors, such as high variability or heavy tails
• Models with general service times (M/G/1) require more advanced analysis techniques (Pollaczek-Khinchine formula)
• Approximations and numerical methods are often used to analyze systems with general service times

Deterministic service times

• Deterministic service times assume that each customer or job takes a fixed, constant amount of time to be served
• The service time is denoted by $D$ and is the same for all customers
• Deterministic service times are applicable in systems with highly standardized and predictable service processes (assembly lines, automated systems)
• Models with deterministic service times (M/D/1) have unique characteristics and analysis methods
• Deterministic service times can lead to more predictable system behavior and performance compared to variable service times

Notation and terminology

• Queueing theory uses a standardized notation and terminology to describe and analyze queueing systems
• Understanding the common notation and terminology is essential for communicating and interpreting queueing models and results
• Consistent notation facilitates the comparison and integration of different queueing models and techniques

Kendall's notation

• Kendall's notation is a shorthand way to describe the characteristics of a queueing system
• It has the form A/S/c/K/N/D, where:
  • A: arrival process (M for Markov or Poisson, G for general, D for deterministic)
  • S: service time distribution (M for exponential, G for general, D for deterministic)
  • c: number of servers
  • K: system capacity (maximum number of customers allowed in the system, including those being served)
  • N: calling population (number of potential customers, often assumed to be infinite)
  • D: queue discipline (FIFO, LIFO, priority)
• Commonly used notations include M/M/1, M/G/1, M/M/c, and M/M/∞

Traffic intensity and stability

• Traffic intensity (ρ) is a measure of the load on the queueing system
• It is defined as the ratio of the arrival rate (λ) to the service rate (μ) multiplied by the number of servers (c): $\rho = \frac{\lambda}{c\mu}$
• For a stable queueing system, the traffic intensity must be less than 1 ($\rho < 1$)
• If $\rho \geq 1$, the queue will grow indefinitely over time, and the system is considered unstable
• Stability condition ensures that the service capacity is sufficient to handle the incoming arrivals in the long run

Little's law

• Little's law is a fundamental relationship in queueing theory that connects the average number of customers in the system (L), the average arrival rate (λ), and the average time a customer spends in the system (W)
• It states that $L = \lambda W$
• Little's law holds for any stable queueing system, regardless of the arrival process, service time distribution, or queue discipline
• It provides a simple way to calculate one of the three quantities (L, λ, W) if the other two are known
• Little's law is useful for performance analysis and capacity planning in queueing systems

Birth-death processes

• Birth-death processes are a class of continuous-time Markov chains used to model the evolution of a queueing system over time
• They describe the transitions between different states of the system, where each state represents the number of customers in the system
• Birth-death processes are characterized by birth rates (λ) and death rates (μ) that govern the transitions between states

Balance equations

• Balance equations, also known as steady-state equations, are used to determine the steady-state probabilities of a birth-death process
• They express the relationship between the rates at which the system enters and leaves each state
• For a birth-death process with states {0, 1, 2, ...}, the balance equations are:
  • $\lambda_0 P_0 = \mu_1 P_1$
  • $(\lambda_n + \mu_n) P_n = \lambda_{n-1} P_{n-1} + \mu_{n+1} P_{n+1}$, for $n \geq 1$
• Solving the balance equations, along with the normalization condition $\sum_{n=0}^{\infty} P_n = 1$, yields the steady-state probabilities $P_n$

Steady-state probabilities

• Steady-state probabilities ($P_n$) represent the long-term proportion of time the queueing system spends in each state $n$
• They are obtained by solving the balance equations and the normalization condition
• Steady-state probabilities provide insights into the long-run behavior and performance of the queueing system
• They are used to calculate various performance measures, such as the average number of customers in the system and the average waiting time

Performance measures

• Performance measures quantify the efficiency and effectiveness of a queueing system
• Common performance measures include:
  • Average number of customers in the system (L)
  • Average number of customers in the queue (Lq)
  • Average time a customer spends in the system (W)
  • Average time a customer spends in the queue (Wq)
  • Probability of the system being empty (P0)
  • Probability of the system being full (PK for finite capacity systems)
• Performance measures are calculated using the steady-state probabilities and other system parameters
• They provide valuable information for system design, capacity planning, and resource allocation decisions

Single-server models

• Single-server models are queueing systems with a single server that serves customers one at a time
• They are the simplest and most fundamental queueing models and form the basis for more complex multi-server and network models
• Single-server models are characterized by the arrival process, service time distribution, and queue discipline

M/M/1 queue

• M/M/1 queue is a single-server model with Poisson arrivals (M), exponential service times (M), and a single server (1)
• Customers arrive according to a Poisson process with rate λ and are served by a single server with exponential service times with rate μ
• The queue discipline is typically assumed to be First-Come, First-Served (FCFS)
• The steady-state probabilities $P_n$ for the M/M/1 queue are given by $P_n = (1 - \rho) \rho^n$, where $\rho = \frac{\lambda}{\mu}$
• Performance measures for the M/M/1 queue include:
  • Average number of customers in the system: $L = \frac{\rho}{1 - \rho}$
  • Average number of customers in the queue: $L_q = \frac{\rho^2}{1 - \rho}$
  • Average time in the system: $W = \frac{1}{\mu - \lambda}$
  • Average time in the queue: $W_q = \frac{\rho}{\mu - \lambda}$

M/G/1 queue

• M/G/1 queue is a single-server model with Poisson arrivals (M), general service time distribution (G), and a single server (1)
• The service time distribution can be any arbitrary probability distribution
• The Pollaczek-Khinchine formula is used to analyze the M/G/1 queue and obtain performance measures
• The average number of customers in the system (L) for the M/G/1 queue is given by $L = \rho + \frac{\lambda^2 E[S^2]}{2(1 - \rho)}$, where $E[S^2]$ is the second moment of the service time distribution
• Other performance measures, such as average waiting time and queue length, can be derived from the Pollaczek-Khinchine formula
• M/G/1 queue is more general and flexible than the M/M/1 queue but requires more complex analysis techniques

M/D/1 queue

• M/D/1 queue is a single-server model with Poisson arrivals (M), deterministic service times (D), and a single server (1)
• The service time is constant and equal to $\frac{1}{\mu}$ for all customers
• The steady-state probabilities and performance measures for the M/D/1 queue can be obtained using specialized formulas
• The average number of customers in the system (L) for the M/D/1 queue is given by $L = \rho + \frac{\rho^2}{2(1 - \rho)}$
• The M/D/1 queue has a lower average waiting time and queue length compared to the M/M/1 queue with the same traffic intensity
• Deterministic service times lead to more predictable system behavior and performance than variable service times

Multi-server models

• Multi-server models are queueing systems with multiple servers that can serve customers simultaneously
• They are used to model situations where there are multiple resources available to process customer requests or jobs
• Multi-server models are characterized by the arrival process, service time distribution, number of servers, and queue discipline

M/M/c queue

• M/M/c queue is a multi-server model with Poisson arrivals (M), exponential service times (M), and $c$ identical servers
• Customers arrive according to a Poisson process with rate λ and are served by one of the $c$ servers with exponential service times with rate μ
• If all servers are busy, customers wait in a queue until a server becomes available
• The steady-state probabilities $P_n$ for the M/M/c queue can be obtained using the balance equations and the normalization condition
• Performance measures for the M/M/c queue include:
  • Average number of customers in the system: $L = L_q + \rho$
  • Average number of customers in the queue: $L_q = \frac{P_0 (\frac{\lambda}{\mu})^c \rho}{c! (1 - \rho)^2}$
  • Average time in the system: $W = \frac{L}{\lambda}$
  • Average time in the queue: $W_q = \frac{L_q}{\lambda}$
• The M/M/c queue reduces to the M/M/1 queue when $c = 1$

M/M/∞ queue

• M/M/∞ queue is a multi-server model with Poisson arrivals (M), exponential service times (M), and an infinite number of servers
• Customers arrive according to a Poisson process with rate λ and are immediately served by an available server with exponential service times with rate μ
• There is no waiting in the queue since there are always enough servers to handle all arriving customers
• The steady-state probabilities $P_n$ for the M/M/∞ queue follow a Poisson distribution with parameter $\frac{\lambda}{\mu}$
• Performance measures for the M/M/∞ queue include:
  • Average number of customers in the system: $L = \frac{\lambda}{\mu}$
  • Average time in the system: $W = \frac{1}{\mu}$
• The M/M/∞ queue is used to model systems with ample service capacity and no waiting, such as call centers with a large number of operators

Erlang loss system

• Erlang loss system, also known as M/M/c/c queue, is a multi-server model with Poisson arrivals (M), exponential service times (M), $c$ servers, and no waiting room
• Customers arrive according to a Poisson process with rate λ and are served by one of the $c$ servers with exponential service times with rate μ
• If all servers are busy when a customer arrives, the customer is blocked and lost (leaves the system without being served)
• The steady-state probabilities $P_n$ for the Erlang loss system can be obtained using the truncated Poisson distribution
• The main performance measure of interest is the blocking probability ($P_c$), which represents the probability that an arriving customer is blocked and lost
• The blocking probability is given by the Erlang B formula: $P_c = \frac{\frac{(\lambda/\mu)^c}{c!}}{\sum_{n=0}^{c} \frac{(\lambda/\mu)^n}{n!}}$
• Erlang loss systems are used to model systems with limited capacity and no waiting, such as telephone networks and hospital beds

Finite capacity queues

• Finite capacity queues are queueing systems with a limited buffer size or waiting room
• They impose a restriction on the maximum number of customers that can be present in the system, including those being served and those waiting in the queue
• Finite capacity queues are characterized by the arrival process, service time distribution, number of servers, and the system capacity (buffer size)

M/M/1/K queue

• M/M/1/K queue is a single-server model with Poisson arrivals (M), exponential service times (M), a single server (1), and a finite system capacity of $K$ customers
• Customers arrive according to a Poisson process with rate λ and are served by a single server with exponential service times with rate μ
• If the system is full (i.e., there are $K$ customers in the system), any arriving customers are blocked and lost
• The steady-state probabilities $P_n$ for the M/M/1/K queue can be obtained using the balance equations and the normalization condition
• The steady-state probabilities have a geometric distribution: $P_n = \frac{(1 - \rho) \rho^n}{1 - \rho^{K+1}}$, for $n = 0, 1, \ldots, K$
• Performance measures for the M/M/1/K queue include the average number of customers in the system, average waiting time, and blocking probability

Blocking probability and throughput

• Blocking probability ($P_K$) is the probability that an arriving customer finds the system full and is blocked (lost)
• In the M/M/1/K queue, the blocking probability is given by $P_K = \frac{(1 - \rho) \rho^K}{1 - \rho^{K+1}}$
• Throughput ($\lambda_{eff}$) is the effective arrival rate of customers who enter the system and receive service
• In the M/M/1/K queue, the throughput is given by $\lambda_{eff} = \lambda