M/G/k queue

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

In queueing theory, a discipline within the mathematical theory of probability, an M/G/k queue is a queue model where arrivals are Markovian (modulated by a Poisson process), service times have a General distribution and there are k servers. The model name is written in Kendall's notation, and is an extension of the M/M/c queue, where service times must be exponentially distributed and of the M/G/1 queue with a single server. Most performance metrics for this queueing system are not known and remain an open problem.[1]

Model definition[edit]

A queue represented by a M/G/k queue is a stochastic process whose state space is the set {0,1,2,3...}, where the value corresponds to the number of customers in the queue, including any being served. Transitions from state i to i + 1 represent the arrival of a new customer: the times between such arrivals have an exponential distribution with parameter λ. Transitions from state i to i − 1 represent the departure of a customer who has just finished being served: the length of time required for serving an individual customer has a general distribution function. The lengths of times between arrivals and of service periods are random variables which are assumed to be statistically independent.

Steady state distribution[edit]

Tijms et al. believe it is "not likely that computationally tractable methods can be developed to compute the exact numerical values of the steady-state probability in the M/G/k queue."[2]

Various approximations for the average queue size,[3] stationary distribution[4][5] and approximation by a reflected Brownian motion[6][7] have been offered by different authors. Recently a new approximate approach based on Laplace transform for steady state probabilities has been proposed by Hamzeh Khazaei et al..[8][9] This new approach is yet accurate enough in cases of large number of servers and when the distribution of service time has a Coefficient of variation more than one.

Average delay/waiting time[edit]

There are numerous approximations for the average delay a job experiences.[5][7][10][11][12][13] The first such was given in 1959 using a factor to adjust the mean waiting time in an M/M/c queue[14][15] This result is sometimes known as Kingman's law of congestion.[16]

E[W^{\text{M/G/}k}] = \frac{C^2+1}{2} \mathbb E [ W^{\text{M/M/}c}]

where C2 is the coefficient of variation of the service time distribution. Ward Whitt described this approximation as “usually an excellent approximation, even given extra information about the service-time distribution."[17]

However, it is known that no approximation using only the first two moments can be accurate in all cases.[14]

A Markov–Krein characterisation has been shown to produce tight bounds on the mean waiting time.[18]

Inter-departure times[edit]

It is conjectured that the times between departures, given a departure leaves n customers in a queue, has a mean which as n tends to infinity is different from the intuitive 1/μ result.[19]

Two servers[edit]

For an M/G/2 queue (the model with two servers) the problem of determining marginal probabilities can be reduced to solving a pair of integral equations[20] or the Laplace transform of the distribution when the service time distribution is a mixture of exponential distributions.[21] The Laplace transform of queue length[22] and waiting time distributions[23] can be computed when the waiting time distribution has a rational Laplace transform.

References[edit]

  1. ^ Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems 63: 3–4. doi:10.1007/s11134-009-9147-4.  edit
  2. ^ Tijms, H. C.; Van Hoorn, M. H.; Federgruen, A. (1981). "Approximations for the Steady-State Probabilities in the M/G/c Queue". Advances in Applied Probability 13 (1): 186–206. doi:10.2307/1426474. JSTOR 1426474.  edit
  3. ^ Ma, B. N. W.; Mark, J. W. (1995). "Approximation of the Mean Queue Length of an M/G/c Queueing System". Operations Research 43: 158. doi:10.1287/opre.43.1.158. JSTOR 171768.  edit
  4. ^ Breuer, L. (2008). "Continuity of the M/G/c queue". Queueing Systems 58 (4): 321–331. doi:10.1007/s11134-008-9073-x.  edit
  5. ^ a b Hokstad, Per (1978). "Approximations for the M/G/m Queue". Operations Research (INFORMS) 26 (3): 510–523. doi:10.1287/opre.26.3.510. JSTOR 169760.  edit
  6. ^ Kimura, T. (1983). "Diffusion Approximation for an M/G/m Queue". Operations Research 31 (2): 304–321. doi:10.1287/opre.31.2.304. JSTOR 170802.  edit
  7. ^ a b Yao, D. D. (1985). "Refining the Diffusion Approximation for the M/G/m Queue". Operations Research 33 (6): 1266–1277. doi:10.1287/opre.33.6.1266. JSTOR 170637.  edit
  8. ^ Khazaei, H.; Misic, J.; Misic, V. B. (2012). "Performance Analysis of Cloud Computing Centers Using M/G/m/m+r Queuing Systems". IEEE Transactions on Parallel and Distributed Systems 23 (5): 936. doi:10.1109/TPDS.2011.199.  edit
  9. ^ Khazaei, H.; Misic, J.; Misic, V. B. (2011). "Modelling of Cloud Computing Centers Using M/G/m Queues". 2011 31st International Conference on Distributed Computing Systems Workshops. p. 87. doi:10.1109/ICDCSW.2011.13. ISBN 978-1-4577-0384-3.  edit
  10. ^ Hokstad, Per (1980). "The Steady-State Solution of the M/K2/m Queue". Advances in Applied Probability (Applied Probability Trust) 12 (3): 799–823. JSTOR 1426432.  edit
  11. ^ Köllerström, Julian (1974). "Heavy Traffic Theory for Queues with Several Servers. I". Journal of Applied Probability (Applied Probability Trust) 11 (3): 544–552. JSTOR 3212698.  edit
  12. ^ Nozaki, S. A.; Ross, S. M. (1978). "Approximations in Finite-Capacity Multi-Server Queues with Poisson Arrivals". Journal of Applied Probability 15 (4): 826–834. doi:10.2307/3213437.  edit
  13. ^ Boxma, O. J.; Cohen, J. W.; Huffels, N. (1979). "Approximations of the Mean Waiting Time in an M/G/s Queueing System". Operations Research (INFORMS) 27 (6): 1115–1127. doi:10.1287/opre.27.6.1115. JSTOR 172087.  edit
  14. ^ a b Gupta, V.; Harchol-Balter, M.; Dai, J. G.; Zwart, B. (2009). "On the inapproximability of M/G/K: Why two moments of job size distribution are not enough". Queueing Systems 64: 5. doi:10.1007/s11134-009-9133-x.  edit
  15. ^ Lee, A. M.; Longton, P. A. (1959). "Queueing Processes Associated with Airline Passenger Check-in". Journal of the Operational Research Society 10: 56. doi:10.1057/jors.1959.5.  edit
  16. ^ Gans, N.; Koole, G.; Mandelbaum, A. (2003). "Telephone Call Centers: Tutorial, Review, and Research Prospects". Manufacturing & Service Operations Management 5 (2): 79. doi:10.1287/msom.5.2.79.16071.  edit
  17. ^ Whitt, W. (2009). "Approximations for the GI/G/m Queue". Production and Operations Management 2 (2): 114–161. doi:10.1111/j.1937-5956.1993.tb00094.x.  edit
  18. ^ Gupta, V.; Osogami, T. (2011). "On Markov–Krein characterization of the mean waiting time in M/G/K and other queueing systems". Queueing Systems 68 (3–4): 339. doi:10.1007/s11134-011-9248-8.  edit
  19. ^ Veeger, C.; Kerner, Y.; Etman, P.; Adan, I. (2011). "Conditional inter-departure times from the M/G/s queue". Queueing Systems 68 (3–4): 353. doi:10.1007/s11134-011-9240-3.  edit
  20. ^ Knessl, C.; Matkowsky, B. J.; Schuss, Z.; Tier, C. (1990). "An Integral Equation Approach to the M/G/2 Queue". Operations Research 38 (3): 506. doi:10.1287/opre.38.3.506. JSTOR 171363.  edit
  21. ^ Cohen, J. W. (1982). "On the M/G/2 queueing model". Stochastic Processes and their Applications 12 (3): 231–248. doi:10.1016/0304-4149(82)90046-1.  edit
  22. ^ Hokstad, Per (1979). "On the Steady-State Solution of the M/G/2 Queue". Advances in Applied Probability (Applied Probability Trust) 11 (1): 240–255. JSTOR 1426776.  edit
  23. ^ Boxma, O. J.; Deng, Q.; Zwart, A. P. (2002). "Waiting-Time Asymptotics for the M/G/2 Queue with Heterogeneous Servers". Queueing Systems 40: 5. doi:10.1023/A:1017913826973.  edit