G/M/1 queue

In queueing theory, a discipline within the mathematical theory of probability, the G/M/1 queue represents the queue length in a system where interarrival times have a general (meaning arbitrary) distribution and service times for each job have an exponential distribution. The system is described in Kendall's notation where the G denotes a general distribution, M the exponential distribution for service times and the 1 that the model has a single server.

The arrivals of a G/M/1 queue are given by a renewal process. It is an extension of an M/M/1 queue, where this renewal process must specifically be a Poisson process (so that interarrival times have exponential distribution).

Models of this type can be solved by considering one of two M/G/1 queue dual systems, one proposed by Ramaswami and one by Bright.

Queue size at arrival times

Let $(X_t,t\ge 0)$ be a $G/M(\mu )/1$ queue with arrival times $(A_n,n\in \mathbb{N})$ that have interarrival distribution A. Define the size of the queue immediately before the nth arrival by the process $U_n=X_{A_n-}$. This is a discrete-time Markov chain with stochastic matrix:

$P=\left(\begin{array}{cccccc}1-a_0& a_0& 0& 0& 0& \cdots \\ 1-(a_0+a_1)& a_1& a_0& 0& 0& \cdots \\ 1-(a_0+a_1+a_2)& a_2& a_1& a_0& 0& \cdots \\ 1-(a_0+a_1+a_2+a_3)& a_3& a_2& a_1& a_0& \cdots \\ ⋮& ⋮& ⋮& ⋮& ⋮& \ddots \end{array}\right)$

where $a_v=𝔼\left(\frac{(\mu X{)}^v{e}^{-\mu A}}{v!}\right)$.

The Markov chain $U_n$ has a stationary distribution if and only if the traffic intensity $\rho =(\mu 𝔼(A){)}^{-1}$ is less than 1, in which case the unique such distribution is the geometric distribution with probability $\eta$ of failure, where $\eta$ is the smallest root of the equation $𝔼(\exp (\mu (\eta -1)A))$.

In this case, under the assumption that the queue is first-in first-out (FIFO), a customer's waiting time W is distributed by:

$\mathbb{P}(W\le x)=1-\eta \exp (-\mu (1-\eta )x)\text{ for }x\ge 0$

Busy period

The busy period can be computed by using a duality between the G/M/1 model and M/G/1 queue generated by the Christmas tree transformation.

Response time

The response time is the amount of time a job spends in the system from the instant of arrival to the time they leave the system. A consistent and asymptotically normal estimator for the mean response time, can be computed as the fixed point of an empirical Laplace transform.