M/G/k queue

Add links
Source: Wikipedia, the free encyclopedia.

In

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

A queue represented by a M/G/k queue is a stochastic process whose

statistically independent
.

Steady state distribution

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

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]

where C 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 characterization has been shown to produce tight bounds on the mean waiting time.[18]

Inter-departure times

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

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

  1. S2CID 38588726
    .
  2. S2CID 222335724
    .
  3. JSTOR 171768
    .
  4. S2CID 2345317
    .
  5. ^
    JSTOR 169760
    .
  6. JSTOR 170802
    .
  7. ^
    JSTOR 170637
    .
  8. S2CID 16934438
    .
  9. S2CID 16067523
    .
  10. S2CID 124883099
    .
  11. JSTOR 3212698
    .
  12. S2CID 32476285
    .
  13. JSTOR 172087
    .
  14. ^
    S2CID 16755599
    .
  15. doi:10.1057/jors.1959.5
    .
  16. doi:10.1287/msom.5.2.79.16071
    .
  17. doi:10.1111/j.1937-5956.1993.tb00094.x
    .
  18. S2CID 35061112
    .
  19. S2CID 19382087
    .
  20. JSTOR 171363
    .
  21. doi:10.1016/0304-4149(82)90046-1
    .
  22. S2CID 125014523
    .
  23. S2CID 2513624
    .
Retrieved from "https://en.wikipedia.org/w/index.php?title=M/G/k_queue&oldid=1276619399"