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.{{Cite journal | last1 = Adan | first1 = I. | last2 = Boxma | first2 = O. | author-link2 = Onno Boxma| last3 = Perry | first3 = D. | doi = 10.1007/s00186-005-0032-6 | title = The G/M/1 queue revisited | journal = Mathematical Methods of Operations Research | volume = 62 | issue = 3 | pages = 437 | year = 2005 | url = https://www.researchgate.net/publication/226557847_The_GM1queue_revisited/file/3deec51a74f2dc8b2a.pdf}} 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.{{Cite journal | doi = 10.1239/aap/1269611150| title = On the dual relationship between Markov chains of GI/M/1 and M/G/1 type| journal = Advances in Applied Probability| volume = 42| pages = 210| year = 2010| last1 = Taylor | first1 = P. G.| last2 = Van Houdt | first2 = B.| url = http://pats.ua.ac.be/publications/content/publications/2010/TaylorVanHoudtRevision.pdf| doi-access = free}}

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 = \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 $a_v=\mathbb{E}\left(\frac{(\mu X)^v e^{-\mu A}}{v!}\right)$ .{{rp|427–428}}

The Markov chain $U_n$ has a stationary distribution if and only if the traffic intensity $\rho=(\mu \mathbb{E}(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 $\mathbb{E}(\exp(\mu(\eta-1)A))$ .{{cite book | title=Probability and Random Processes | first2=D. R. | last2=Stirzaker | first1=G. R. | last1=Grimmett | author-link=Geoffrey Grimmett | year=1992 |edition=second | publisher=Oxford University Press|ISBN=0198572220}}{{rp|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:{{rp|430}}

: $\mathbb{P}(W\le x)=1-\eta \exp(-\mu(1-\eta)x) ~\text{ for } x \geq 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.{{Cite journal | last1 = Perry | first1 = D. | last2 = Stadje | first2 = W. | last3 = Zacks | first3 = S. | doi = 10.1016/S0167-6377(00)00043-2 | title = Busy period analysis for M/G/1 and G/M/1 type queues with restricted accessibility | journal = Operations Research Letters | volume = 27 | issue = 4 | pages = 163 | year = 2000 }}

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.{{Cite journal | doi = 10.1002/mma.806| title = Interval estimation of mean response time for a G/M/1 queueing system: Empirical Laplace function approach| journal = Mathematical Methods in the Applied Sciences| volume = 30| issue = 6| pages = 707| year = 2007| last1 = Chu | first1 = Y. K. | last2 = Ke | first2 = J. C. }}

References

Category:Single queueing nodes