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.^[1] 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.^[2]

Let ${\displaystyle (X_{t},t\geq 0)}${\displaystyle (X_{t},t\geq 0)} be a ${\displaystyle G/M(\mu )/1}${\displaystyle G/M(\mu )/1} queue with arrival times ${\displaystyle (A_{n},n\in \mathbb {N} )}${\displaystyle (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 ${\displaystyle U_{n}=X_{A_{n}-}}${\displaystyle U_{n}=X_{A_{n}-}}. This is a discrete-time Markov chain with stochastic matrix:

${\displaystyle P={\begin{pmatrix}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 \\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}}${\displaystyle P={\begin{pmatrix}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 \\\vdots &\vdots &\vdots &\vdots &\vdots &\ddots \end{pmatrix}}}

where ${\displaystyle a_{v}=\mathbb {E} \left({\frac {(\mu X)^{v}e^{-\mu A}}{v!}}\right)}${\displaystyle a_{v}=\mathbb {E} \left({\frac {(\mu X)^{v}e^{-\mu A}}{v!}}\right)}.^{[3] : 427–428}

The Markov chain ${\displaystyle U_{n}}${\displaystyle U_{n}} has a stationary distribution if and only if the traffic intensity ${\displaystyle \rho =(\mu \mathbb {E} (A))^{-1}}${\displaystyle \rho =(\mu \mathbb {E} (A))^{-1}} is less than 1, in which case the unique such distribution is the geometric distribution with probability ${\displaystyle \eta }${\displaystyle \eta } of failure, where ${\displaystyle \eta }${\displaystyle \eta } is the smallest root of the equation ${\displaystyle \mathbb {E} (\exp(\mu (\eta -1)A))}${\displaystyle \mathbb {E} (\exp(\mu (\eta -1)A))}.^{[3] : 428}

In this case, under the assumption that the queue is first-in first-out (FIFO), a customer's waiting time W is distributed by:^{[3] : 430}

${\displaystyle \mathbb {P} (W\leq x)=1-\eta \exp(-\mu (1-\eta )x)~{\text{ for }}x\geq 0}${\displaystyle \mathbb {P} (W\leq x)=1-\eta \exp(-\mu (1-\eta )x)~{\text{ for }}x\geq 0}

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.^[4]

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.^[5]

• Single queueing nodes

• Articles with short description
• Short description matches Wikidata