General Arrival or Service Patterns

4.1 M/G/1 Queue (Markovian arrivals, General service, Single server)

Core Assumptions:

• Arrival Process: Poisson (rate $\lambda$)
• Service Time: General distribution with PDF $B(t)$, mean $1/\mu$, and variance $\sigma^2$
• Queue Discipline: First-Come-First-Served (FCFS)
• Single Server

Why Generalization?

Unlike the M/M/1 model (where service is exponential), the M/G/1 queue relaxes the memoryless assumption of service times. This allows the model to capture:

• Batch services
• Deterministic services
• Phased/step services

Mathematical Tools Used:

• Embedded Markov chains (observed at departure epochs)
• Laplace-Stieltjes transforms for solving time distributions
• Renewal theory for modeling residual service time

Pollaczek–Khinchine (P-K) Formula:

A foundational result that connects mean queue length with the first two moments of the service time distribution:

• Expected number in system:

  $$L = \rho + \frac{\lambda^2 \sigma^2}{2(1 - \rho)}$$

• Expected waiting time in system:

  $$W = \frac{1}{\mu} + \frac{\lambda \sigma^2}{2(1 - \rho)}$$

• Where: $\rho = \lambda / \mu$

Observations:

• Even for the same mean service time, systems with larger variance ($\sigma^2$) in service time experience higher waiting time.
• If service is deterministic ($\sigma^2 = 0$), the queue behaves optimally.

Real-Life Examples:

• Customer support desks where issue resolution time varies significantly.
• Clinics with random arrivals but service time determined by patient complexity.

---

4.2 M/G/c and M/G/∞ Queues

---

(a) M/G/c (Multiple servers, General service)

Assumptions:

• Arrival: Poisson with rate $\lambda$
• Service: General with mean $1/\mu$ and variance $\sigma^2$
• c identical parallel servers

Challenge:

No general closed-form solution for steady-state probabilities due to lack of memorylessness in service.

Analysis Approaches:

• Approximation using Allen–Cunneen method
• Simulation or numerical methods
• Diffusion approximations (for large c and high traffic)

Allen–Cunneen Approximation (for waiting time in queue):

$$W_q \approx \frac{C_s^2 + 1}{2} \cdot \frac{\rho^{\sqrt{2(c + 1)} - 1}}{c(1 - \rho)} \cdot \frac{1}{\mu}$$

Where:

• $\rho = \frac{\lambda}{c \mu}$
• $C_s^2$ is the squared coefficient of variation of service time

Real-Life Examples:

• Large banks with variable service durations
• Hospital OPDs where service time depends on case severity

---

(b) M/G/∞ (Infinite-server model)

Assumptions:

• Arrivals: Poisson (rate $\lambda$)
• Service: General
• Servers: Infinite — every customer is served immediately

Important Property:

• The number of customers in the system is Poisson distributed:

  $$P_n(t) = \frac{(\lambda E[S])^n}{n!} e^{-\lambda E[S]}$$

Why It’s Special:

• No queuing or delays
• Analysis simplifies to calculating number of concurrent services

Real-Life Examples:

• Cloud computing with serverless architecture (each user gets a fresh container)
• Video rendering tasks distributed across infinite processors

---

4.3 G/M/1 and G/M/c Queues

---

(a) G/M/1 (General arrivals, Markovian service, Single server)

Core Assumptions:

• Arrival Process: General (not necessarily exponential)
• Service Time: Exponential (rate $\mu$)
• Queue Discipline: FCFS
• Server: Single

Why It’s Interesting:

• Interarrival times can be deterministic, Erlang, or completely irregular
• Requires embedded Markov chain analysis at departure instants

Waiting Time (via Residual Life Theory):

If $E[A] = 1/\lambda$ and $E[A^2]$ is the second moment of interarrival time:

$$W_q = \frac{\lambda E[A^2]}{2(1 - \rho)}$$

• More variability in interarrival times leads to higher waiting times

Real-Life Examples:

• Toll booths with timed vehicle entry (non-random arrivals)
• Manufacturing lines with batch item delivery

---

(b) G/M/c (General arrivals, exponential service, multiple servers)

Key Features:

• Combines general interarrival patterns with exponential service and multiple servers
• Difficult to model due to interaction between irregular arrivals and multiple parallel services

Analysis Tools:

• Simulations or approximations using queueing tables
• In some cases, phase-type distributions can approximate arrival patterns

Real-Life Examples:

• Emergency medical services with uneven call times and multiple ambulances
• Help desks receiving traffic from international time zones

---

📌 Summary Table

Model	Input Type	Service Type	Servers	Key Insight	Example
M/G/1	Poisson	General	1	Variability in service dominates queue	Tech support, variable case durations
M/G/c	Poisson	General	c	No closed form; approximations used	Hospital with multiple doctors
M/G/∞	Poisson	General	∞	No queue; instant service	Cloud-based serverless apps
G/M/1	General	Exponential	1	Arrival irregularity impacts waiting	Toll booth with scheduled inflows
G/M/c	General	Exponential	c	Complex behavior, requires simulation	Multi-agent emergency dispatch system