Simple Markovian Queueing Models

2.1 Birth–Death Processes

Concept: A birth-death process is a continuous-time Markov process where transitions only occur between neighboring states:

• "Birth" (arrival): $n \rightarrow n + 1$ with rate $\lambda_n$
• "Death" (service completion): $n \rightarrow n - 1$ with rate $\mu_n$

Steady-state probabilities: Let $P_n$ be the probability of $n$ customers in the system. The steady-state condition is:

$$\lambda_n P_n = \mu_{n+1} P_{n+1}$$

By recursion:

$$P_n = P_0 \prod_{k=0}^{n-1} \frac{\lambda_k}{\mu_{k+1}}$$

Real-life Example: Hospital ICU beds. Patients arrive (birth), and after treatment, leave (death). Bed availability and service time determine the flow.

2.2 Single-Server Queues (M/M/1)

• Assumptions:

  • Poisson arrival: $\lambda$
  • Exponential service: $\mu$
  • Single server, infinite queue, FCFS discipline

Key results (for $\rho = \frac{\lambda}{\mu} < 1$):

• $L = \frac{\rho}{1 - \rho}$
• $L_q = \frac{\rho^2}{1 - \rho}$
• $W = \frac{1}{\mu - \lambda}$
• $W_q = \frac{\lambda}{\mu(\mu - \lambda)}$

Real-life Example: ATM kiosk with a single machine. Customers arrive randomly and are served one by one.

2.3 Multiserver Queues (M/M/c)

• Assumptions:

  • $c$ servers
  • Same arrival and service assumptions as M/M/1

Utilization:

$$\rho = \frac{\lambda}{c\mu}$$

Let:

$$P_0 = \left[ \sum_{n=0}^{c-1} \frac{(\lambda/\mu)^n}{n!} + \frac{(\lambda/\mu)^c}{c!} \cdot \frac{1}{1 - \rho} \right]^{-1}$$

Then:

• $L_q = \frac{P_0 (\lambda/\mu)^c \cdot \rho}{c!(1 - \rho)^2}$
• $W_q = \frac{L_q}{\lambda}$

Real-life Example: Call centers with multiple agents answering customer calls simultaneously.

2.4 Choosing the Number of Servers

• Trade-off between cost of servers and customer waiting time
• Objective: minimize total cost

Total Cost Function:

$$C = C_s \cdot c + C_w \cdot L_q$$

Where:

• $C_s$ = cost per server per unit time
• $C_w$ = cost per customer waiting

Real-life Example: Bank managers determining the number of tellers needed to avoid excessive queues during peak hours.

2.5 Queues with Truncation (M/M/c/K)

• System capacity is limited to K customers (includes customers in service + queue)
• New arrivals are blocked or lost when system is full

Probability of blocking (Erlang B formula):

$$P_K = \frac{ \frac{(\lambda/\mu)^K}{K!} }{ \sum_{n=0}^K \frac{(\lambda/\mu)^n}{n!} }$$

Real-life Example: Parking lot with fixed capacity—new vehicles are turned away when full.

2.6 Erlang’s Loss Formula (M/M/c/c)

• Also called Erlang B system
• No queue, only $c$ servers
• New arrivals are lost if all servers are busy

Blocking probability (Erlang B):

$$B(c, \rho) = \frac{ \frac{\rho^c}{c!} }{ \sum_{n=0}^c \frac{\rho^n}{n!} }$$

Real-life Example: Telecommunication switch circuits—calls are dropped if all circuits are engaged.

2.7 Queues with Unlimited Service (M/M/∞)

• Infinite number of servers
• No waiting; every arrival is instantly served

Distribution: Poisson with mean $\lambda/\mu$

$$P_n = \frac{(\lambda/\mu)^n e^{-\lambda/\mu}}{n!}$$

Real-life Example: Online web servers where each user session is handled by its own virtual server (cloud-based architecture).

2.8 Finite-Source Queues

• Population of potential customers is limited
• Arrival rate depends on the number of customers not currently in system

Let population = $N$

• $\lambda_n = (N - n) \cdot \lambda$
• $\mu_n = n \cdot \mu$ (if $n \le c$)

Real-life Example: Maintenance system where a fixed number of machines can fail and request repair from a limited pool of repairmen.

2.9 State-Dependent Service

• Service rate changes with the number of customers in the system:

  • $\mu_n$ varies with $n$

Examples:

• Faster service when queue is long
• Slower service due to congestion

Real-life Example: Customer support where more agents join calls when wait times grow.

2.10 Queues with Impatience

• Reneging: customer leaves after waiting too long
• Balking: customer decides not to enter upon seeing queue
• Jockeying: switching between lines

Models include:

• Reneging probability functions
• Average time before a customer leaves

Real-life Example: Retail stores—shoppers abandoning carts if checkout lines are too long.

2.11 Transient Behavior

• Analyzes system behavior before it reaches steady state
• Uses Kolmogorov forward equations (differential equations)

$$\frac{dP_n(t)}{dt} = \lambda_{n-1}P_{n-1}(t) + \mu_{n+1}P_{n+1}(t) - (\lambda_n + \mu_n)P_n(t)$$

Real-life Example: Airport security during opening hours—understanding how queues evolve in the first few minutes.

2.12 Busy-Period Analysis

• Time from when the server becomes busy until it is idle again

For M/M/1:

• Expected busy period = $\frac{1}{\mu - \lambda}$

Real-life Example: Coffee shop—analyzing the duration of continuous customer flow from the first arrival to the moment the barista gets a break.