G/M/1 queue explained

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]

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 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 & … \\ 1- (a _{0+a} _{1)} & a _{1} & a _{0} & 0 & 0 & … \\ 1- (a _{0+a} _{1+a} _{2)} & a _{2} & a _{1} & a _{0} & 0 & … \\ 1- (a _{0+a} _{1+a} _{2+a} _{3)} & a _{3} & a _{2} & a _{1} & a _{0} & … \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix}

where

a _{v = E \left( ((\mu X) ^{v} e ^{-\mu})/(v!)} \right) .

The Markov chain

U _{n} has a stationary distribution if and only if the traffic intensity \rho = (\mu E (A)) ^{-1} is less than 1, in which case the unique such distribution is the geometric distribution with probability η of failure, where η is the smallest root of the equation E (\exp(\mu( η-1 )A)) .^[3]

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]

P (W\le x) =1-η \exp( - \mu( 1-η )x) ~ 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.^[4]

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

Notes and References

1. Adan . I. . Boxma . O. . Onno Boxma. Perry . D. . 10.1007/s00186-005-0032-6 . The G/M/1 queue revisited . Mathematical Methods of Operations Research . 62 . 3 . 437 . 2005 .
2. 10.1239/aap/1269611150. On the dual relationship between Markov chains of GI/M/1 and M/G/1 type. Advances in Applied Probability. 42. 210. 2010. Taylor . P. G.. Van Houdt . B.. free.
3. Book: Probability and Random Processes . D. R. . Stirzaker . G. R. . Grimmett . Geoffrey Grimmett . 1992 . second . Oxford University Press. 0198572220.
4. Perry . D. . Stadje . W. . Zacks . S. . 10.1016/S0167-6377(00)00043-2 . Busy period analysis for M/G/1 and G/M/1 type queues with restricted accessibility . Operations Research Letters . 27 . 4 . 163 . 2000 .
5. 10.1002/mma.806. Interval estimation of mean response time for a G/M/1 queueing system: Empirical Laplace function approach. Mathematical Methods in the Applied Sciences. 30. 6. 707. 2007. Chu . Y. K. . Ke . J. C. .