8.4 M/G/1 and G/M/1 queues

M/G/1 queue

The M/G/1 queue models a single-server system where arrivals are Poisson (Markovian) but service times can follow any distribution. This flexibility makes it one of the most widely used queueing models, since real service processes rarely have neat exponential distributions. The "M/G/1" notation follows Kendall's convention: Markovian arrivals / General service / 1 server.

Poisson arrivals

Customers arrive according to a Poisson process with rate $\lambda$. This means inter-arrival times are i.i.d. exponential random variables with mean $1/\lambda$. The memoryless property of exponential inter-arrivals is what makes the arrival side tractable: the future arrival process doesn't depend on how long you've been waiting since the last arrival.

General service times

Service times are i.i.d. random variables drawn from a general distribution with:

• Mean $E[S] = 1/\mu$
• Second moment $E[S^2]$
• Variance $\sigma_S^2 = E[S^2] - (1/\mu)^2$

The distribution can be anything: exponential, deterministic, Erlang, hyperexponential, Pareto, etc. This generality is the whole point of the model. The key requirement for stability is that the traffic intensity satisfies $\rho = \lambda / \mu < 1$.

Embedded Markov chain

Because service times are general, the system state doesn't form a continuous-time Markov chain. The standard trick is to observe the system only at service completion epochs. Let $Q_n$ be the number of customers left behind by the $n$-th departing customer. Then:

$Q_{n+1} = (Q_n - 1)^+ + A_{n+1}$

where $(x)^+ = \max(x, 0)$ and $A_{n+1}$ is the number of Poisson arrivals during the $(n+1)$-th service time. Since arrivals are Poisson and service times are i.i.d., $\{Q_n\}$ forms a Markov chain. Steady-state probabilities are found by solving the resulting balance equations, typically via generating functions.

Pollaczek-Khinchine (P-K) formula

This is the central result for M/G/1. It gives the mean number of customers in the system in closed form:

$E[L] = \rho + \frac{\rho^2 + \lambda^2 \sigma_S^2}{2(1 - \rho)}$

An equivalent form, written in terms of $E[S^2]$:

$E[L] = \rho + \frac{\lambda^2 E[S^2]}{2(1 - \rho)}$

Notice that the mean queue length depends not just on the mean service time but also on its second moment (or equivalently, its variance). Two service distributions with the same mean but different variances will produce different queue lengths. Higher variance means longer queues.

Mean waiting time (P-K mean value formula)

The average time a customer waits in the queue (before service begins) is:

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

You can derive this from $E[L_q] = \lambda E[W_q]$ (Little's law applied to the queue portion) combined with the P-K formula. The total time in the system (waiting plus service) is:

$E[W] = E[W_q] + E[S] = \frac{\lambda E[S^2]}{2(1 - \rho)} + \frac{1}{\mu}$

And by Little's law for the whole system, $E[L] = \lambda E[W]$, which is consistent with the P-K formula above.

Busy period

A busy period starts when an arriving customer finds the server idle and ends when the server next becomes idle. Let $E[B]$ denote the mean busy period. By a renewal argument:

$E[B] = \frac{1/\mu}{1 - \rho} = \frac{E[S]}{1 - \rho}$

The full distribution of the busy period can be characterized through its Laplace-Stieltjes transform (LST), which satisfies a functional equation involving the LST of the service time distribution.

G/M/1 queue

The G/M/1 queue flips the generality: inter-arrival times follow a general distribution, while service times are exponential. The notation is General arrivals / Markovian service / 1 server.

General inter-arrival times

Consecutive inter-arrival times are i.i.d. with a general distribution:

• Mean $E[A] = 1/\lambda$
• The distribution can be deterministic, Erlang, hyperexponential, etc.

Exponential service times

Service times are exponentially distributed with rate $\mu$ (mean $1/\mu$). The memoryless property of exponential service is what makes the service side tractable here, just as memoryless arrivals made the arrival side tractable in M/G/1.

Stability again requires $\rho = \lambda/\mu < 1$.

Embedded Markov chain

For G/M/1, the natural embedding points are arrival epochs (not departure epochs as in M/G/1). Let $Q_n$ be the number of customers found in the system by the $n$-th arriving customer. Because service times are exponential, the number of service completions during a general inter-arrival time depends only on how many customers are present and the inter-arrival duration. This makes $\{Q_n\}$ a Markov chain.

The root $\sigma$ and steady-state distribution

The steady-state distribution of the number of customers seen by an arriving customer has a geometric-like form:

$\pi_k = (1 - \sigma)\sigma^k, \quad k = 0, 1, 2, \ldots$

where $\sigma$ is the unique root in $(0, 1)$ of the equation:

$\sigma = \tilde{A}(\mu - \mu\sigma)$

Here $\tilde{A}(s)$ is the Laplace-Stieltjes transform of the inter-arrival time distribution, i.e., $\tilde{A}(s) = E[e^{-sA}]$. Finding $\sigma$ is typically done numerically.

Waiting time distribution

The waiting time in queue (before service begins) for a customer who arrives to find the system in steady state is:

$P(W_q = 0) = 1 - \sigma$

$P(W_q > t) = \sigma \, e^{-\mu(1-\sigma)t}, \quad t > 0$

So the conditional waiting time (given that you do wait) is exponential with rate $\mu(1 - \sigma)$. The mean waiting time in queue is:

$E[W_q] = \frac{\sigma}{\mu(1 - \sigma)}$

M/G/1 vs G/M/1 queues

Why the analysis techniques differ

In M/G/1, the exponential (memoryless) arrivals let you embed at departures: the number of arrivals during a service time depends only on the service duration, not on history. In G/M/1, the exponential (memoryless) service lets you embed at arrivals: the number of completions during an inter-arrival gap depends only on the current queue size and the gap length. Each model exploits the memoryless property on whichever side has it.

Role of higher moments

For M/G/1, performance depends on the variance (or second moment) of service times. Two systems with the same mean service time but different variances will behave very differently. For G/M/1, the entire inter-arrival distribution enters through its LST, but the key summary is the single parameter $\sigma$. In both cases, the mean alone is not enough to determine system performance.

Applications of M/G/1 and G/M/1 queues

Computer systems

• M/G/1 for CPU scheduling: Job processing times are often heavy-tailed or multi-modal, not exponential. The M/G/1 model captures this while keeping Poisson job submissions.
• G/M/1 for bursty traffic: When request arrivals are correlated or non-Poisson (e.g., web server traffic with heavy-tailed inter-request times), G/M/1 with exponential processing is a reasonable first model.

Manufacturing

Production lines where machine processing times are deterministic or Erlang-distributed fit naturally into M/G/1 (with Poisson order arrivals). The P-K formula directly shows how service time variability affects work-in-process inventory.

Telecommunications

Packet switches and routers often have fixed or bimodal packet sizes (general service), with Poisson packet arrivals as a first approximation. M/G/1 is the standard model for analyzing packet delay in such systems. G/M/1 applies when the arrival process is the non-standard part, e.g., scheduled or periodic transmissions with exponential processing.

Service operations

Call centers, bank tellers, and hospital triage all involve service times that are clearly not exponential (some calls are quick, others take much longer). M/G/1 captures this heterogeneity. The P-K formula quantifies exactly how much the variability in service times costs you in terms of longer waits.