×

Approximate solution for multi-server queueing systems with Erlangian service times. (English) Zbl 0994.90046

Summary: Multi-server queueing systems with Poisson arrivals and Erlangian service times are among the most applicable of what are considered ”easy” systems in queueing theory. By selecting the proper order, Erlangian service times can be used to approximate reasonably well many general types of service times which have a unimodal distribution and a coefficient of variation less than or equal to 1. In view of their practical importance, it may be surprising that the existing literature on these systems is quite sparse. The probable reason is that, while it is indeed possible to represent these systems through a Markov process, serious difficulties arise because of (1) the very large number of system states that may be present with increasing Erlang order and/or number of servers, and (2) the complex state transition probabilities that one has to consider. Using a standard numerical approach, solutions of the balance equations describing systems with even a modest Erlang order and number of servers require extensive computational effort and become impractical for larger systems. In this paper we illustrate these difficulties and present the Equally Likely Combinations (ELC) heuristic which provides excellent approximations to typical equilibrium behavior measures of interest for a wide range of stationary multiserver systems with Poisson arrivals and Erlangian service. As system size grows, ELC computational times can be more than 1000 times faster than those for the exact approach. We also illustrate this heuristic’s ability to estimate accurately system response under transient and/or dynamic conditions.

MSC:

90B22 Queues and service in operations research
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Shapiro, S., The M-server queue with Poisson input and gamma-distributed service of order two, Journal of the Operations Research Society of America, 14, 685-694 (1966) · Zbl 0143.20302
[2] Mayhugh, J.; McCormick, R., Steady state solution of the queue \(M/E_k/r\), Management Science, 14, 692-712 (1968) · Zbl 0167.17103
[3] Murray, J.; Kelton, W., The transient behavior of the \(M/E_k/2\) queue in steady state simulation, Computers and Operations Research, 15, 4, 357-367 (1988) · Zbl 0642.60087
[4] Maaløe, E., Approximation formulae for estimation of waiting-time in multiple-channel queueing systems, Management Science, 19, 703-710 (1973) · Zbl 0252.60043
[5] Smith, V., Distribution of customers in \(M/E_T/m\) queues using Hokstad’s approximation, Applied Statistics (Royal Statistics Society), 36, 394-401 (1987) · Zbl 0645.60099
[6] Hokstad, P., Approximations for the \(M/G/m\) queue, Operations Research, 26, 3, 510-523 (1978) · Zbl 0379.60092
[7] Cosmetatos, G., Some approximate equilibrium results for the multi-server queue \((M/G/r)\)., Operational Research Quarterly, 27, 615-620 (1976) · Zbl 0332.60067
[8] Takahashi, Y., An approximation formula for the mean waiting time of an \(M/G/c\) queue, Journal of the Operations Research Society of Japan, 20, 3, 150-163 (1977) · Zbl 0373.60117
[9] Nozaki, S.; Ross, S., Approximations in finite-capacity multi-server queues with Poisson arrivals, Journal of Applied Probability, 15, 826-834 (1978) · Zbl 0398.60094
[10] Boxma, O.; Cohen, J.; Huffels, N., Approximations of the mean waiting time in an \(M/G/s\) queueing system, Operations Research, 27, 1115-1127 (1979) · Zbl 0439.60090
[11] Tijms, H.; van Hoorn, M.; Federgruen, A., Approximations for the steady-state probabilities in the \(M/G/c\) queue, Advance Applied Probability, 13, 186-206 (1981) · Zbl 0446.60079
[12] Yao, D., Refining the diffusion approximation for the \(M/G/m\) queue, Operations Research, 33, 1266-1277 (1985) · Zbl 0649.60101
[13] Miyazawa, M., Approximation of queue-length distribution of an \(M/ GI /s\) queue by the basic equations, Journal of Applied Probability, 23, 443-458 (1986) · Zbl 0599.60084
[14] Ma, B.; Mark, J., Approximation of the mean queue length of an \(M/G/c\) queueing system, Operations Research, 43, 1, 158-165 (1995) · Zbl 0830.90058
[15] Kimura, T., Diffusion approximation for an \(M/G/s\) queue, Operations Research, 31, 2, 304-319 (1983) · Zbl 0507.90033
[16] Kimura, T., A transform-free approximation for the finite capacity \(M/G/s\) queue, Operations Research, 44, 6, 984-988 (1996) · Zbl 0879.90098
[17] Escobar M. Approximate solutions for multi-server queueing systems with Erlangian service times and applications to air traffic management. PhD thesis, 1998, Massachusetts Institute of Technology.; Escobar M. Approximate solutions for multi-server queueing systems with Erlangian service times and applications to air traffic management. PhD thesis, 1998, Massachusetts Institute of Technology.
[18] Lee D. \(ME_3NNQME_KNNQ\); Lee D. \(ME_3NNQME_KNNQ\)
[19] Green, L.; Kolesar, P.; Svoronos, A., Some effects of nonstationarity on multi-server Markovian systems, Operations Research, 39, 3, 502-511 (1991) · Zbl 0729.60100
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.