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 \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).[3]: 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)).[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
\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.[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]
References
- ^ Adan, I.; Boxma, O.; Perry, D. (2005). "The G/M/1 queue revisited". Mathematical Methods of Operations Research. 62 (3): 437. doi:10.1007/s00186-005-0032-6
- ^ Taylor, P. G. & Van Houdt, B. (2010). "On the dual relationship between Markov chains of GI/M/1 and M/G/1 type". Advances in Applied Probability. 42: 210. doi:10.1239/aap/1269611150
- ^ Grimmett, G. R. & Stirzaker, D. R. (1992). Probability and Random Processes. second ed. Oxford University Press. ISBN 0198572220.
- ^ Perry, D.; Stadje, W.; Zacks, S. (2000). "Busy period analysis for M/G/1 and G/M/1 type queues with restricted accessibility". Operations Research Letters. 27 (4): 163. doi:10.1016/S0167-6377(00)00043-2
- ^ Chu, Y. K. & Ke, J. C. (2007). "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. doi:10.1002/mma.806