G/M/1 queue

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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.

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]

Busy period[edit]

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.[3]

Response time[edit]

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


  1. ^ Adan, I.; Boxma, O.; Perry, D. (2005). "The G/M/1 queue revisited" (PDF). Mathematical Methods of Operations Research. 62 (3): 437. doi:10.1007/s00186-005-0032-6. 
  2. ^ Taylor, P. G.; Van Houdt, B. (2010). "On the dual relationship between Markov chains of GI/M/1 and M/G/1 type" (PDF). Advances in Applied Probability. 42: 210. doi:10.1239/aap/1269611150. 
  3. ^ 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. 
  4. ^ 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.