Analysis of the stationary \(E_ k/C_ 2/s\) queueing system. (English) Zbl 0654.60088
Summary: Erlang’s method of stages is exploited to solve the queue \(E_ k/C_ 2/s\), i.e. with service-time pdf of the versatile Coxian type of order 2. The general solution strategy is purely real arithmetic, leading first to explicit forms (for the probabilities of states with all servers busy) and then, through an algorithmic scheme, to an easily solved linear system of only \(s+1\) equations.
In comparison to other established methods, the present approach (a) seems simpler to grasp and easier to implement, (b) provides closed form expressions offering more qualitative insight, (c) has a much lower order of computational complexity, (d) has the potential to lead to an exact FCFS waiting-time analysis and (e) can be extended to even more general systems.
In comparison to other established methods, the present approach (a) seems simpler to grasp and easier to implement, (b) provides closed form expressions offering more qualitative insight, (c) has a much lower order of computational complexity, (d) has the potential to lead to an exact FCFS waiting-time analysis and (e) can be extended to even more general systems.
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 90B22 | Queues and service in operations research |
References:
| [1] | Allen, B.; Anderssen, R. S.; Seneta, E., Computation of stationary measures for infinite Markov chains, (Neuts, M. F., Algorithmic Methods in Probability. Algorithmic Methods in Probability, TIMS Studies in the Management Sciences, 7 (1977), North-Holland: North-Holland Amsterdam) · Zbl 0386.60048 |
| [2] | Ancker, C. J.; Cafarian, A. V., Queueing with multiple Poisson inputs and exponential service times, Operations Research, 9, 321-327 (1961) · Zbl 0108.31402 |
| [3] | Avis, D. M., Computing waiting times in GI/\(E_k/c\) queueing systems, (Neuts, M. F., Algorithmic Methods in Probability. Algorithmic Methods in Probability, TIMS Studies in the Management Sciences, 7 (1977), North-Holland: North-Holland Amsterdam) · Zbl 0395.60088 |
| [4] | Botta, R. F.; Harris, C. M.; Marchal, W. G., Characterizations of generalized hyperexponential distribution functions, Communications in Statistics—Stochastic Models, 3, 115-148 (1987) · Zbl 0616.62016 |
| [5] | Cohen, J. W., Certain delay problems for a full availability trunk group loaded by two traffic sources, Communication News, 16, 105-113 (1956) |
| [6] | Cohen, J. W., The Single Server Queue (1982), North-Holland: North-Holland Amsterdam · Zbl 0481.60003 |
| [7] | Cohen, J. W., On the M/G/2 queueing model, Stochastic Processes and their Applications, 12, 231-248 (1982) · Zbl 0482.60088 |
| [8] | Cox, D. R., A use of complex probabilities in the theory of stochastic processes, (Proceedings of the Cambridge Philosophical Society, 51 (1955)), 313-319 · Zbl 0066.37703 |
| [9] | Grassman, W. K.; Chaudhry, M. L., A new method to solve steady state equations, Naval Research Logistics Quarterly, 29, 461-473 (1982) · Zbl 0512.60088 |
| [10] | Grassman, W. K.; Taksar, M. I.; Heyman, D. P., Regenerative analysis and steady-state distributions for Markov chains, Operations Research, 33, 1107-1116 (1985) · Zbl 0576.60083 |
| [11] | Greenberg, I., Single server queues with hyperexponential service times, Naval Research Logistics Quarterly, 24, 451-455 (1977) · Zbl 0374.60132 |
| [12] | Groenevelt, H.; Hoorn, M. H.van; Tijms, H. C., Tables for M/G/\(c\) queueing systems with phase-type service, European Journal of Operational Research, 16, 257-269 (1984) · Zbl 0529.60097 |
| [13] | Gupta, S. K.; Goyal, J. K., Queues with Poisson input and hyperexponential output with finite waiting space, Operations Research, 12, 75-81 (1964) · Zbl 0124.09101 |
| [14] | Harris, R., The expected number of idle servers in a queueing system, Operations Research, 22, 1258-1259 (1974) · Zbl 0294.60073 |
| [15] | Hillier, F. S.; Yu, O. S., Queueing Tables and Graphs, (Publications in OR Series (ORSA), Vol. 3 (1981), North-Holland: North-Holland New York) · Zbl 0461.90021 |
| [16] | Hokstad, P., Approximations for the M/G/\(m\) queue, Operations Research, 26, 510-523 (1978) · Zbl 0379.60092 |
| [17] | Hokstad, P., On the steady-state solution of the M/G/2 queue, Advances in Applied Probability, 11, 240-255 (1979) · Zbl 0392.60073 |
| [18] | Hokstad, P., The steady-state solution of the M/\(K_2/m\) queue, Advances in Applied Probability, 12, 799-823 (1980) · Zbl 0451.60091 |
| [19] | Hokstad, P., Some numerical results and approximations for the many server queue with non-exponential service time (1982), Dept. of Mathematics, University of Trondheim |
| [20] | Hokstad, P., Bounds for the mean queue length of the M/\(K_2/m\) queue, European Journal of Operational Research, 23, 108-117 (1986) · Zbl 0585.60091 |
| [21] | Hoorn, M. H.van, Algorithms and Approximations for Queueing Systems (1983), Mathematical Center: Mathematical Center Amsterdam |
| [22] | Hoorn, M. H.van, Numerical analysis of multi-server queues with deterministic service and special phase-type arrivals, Zeitschrift für Operations Research, A, 29 (1985) |
| [23] | Hoorn, M. H.van; Seelen, L. P., Approximations for the GI/G/\(c\) queue, Journal of Applied Probability, 23, 484-494 (1986) · Zbl 0602.60082 |
| [24] | Ishikawa, A., On the equilibrium solution for the queueing system GI/\(E_k\)/m, TRU Mathematics, 15, 47-66 (1979) · Zbl 0434.60096 |
| [25] | Ishikawa, A., Stationary waiting-time distribution in a GI/\(E_k/m\) queue, Journal of Operations Research Society of Japan, 27, 130-149 (1984) · Zbl 0541.60097 |
| [26] | Kleinrock, L., (Queueing systems; Vol. I: Theory (1975), Wiley: Wiley New York) · Zbl 0334.60045 |
| [27] | Kobayashi, H., Modeling and Analysis; an Introduction to System Performance Evaluation Methodology (1981), Addison-Wesley: Addison-Wesley London |
| [28] | Kühn, P., Tables on delay systems (1976), Institute of Switching and Data Technics, University of Stuttgart |
| [29] | Morse, P. M., Queues, Inventories and Maintenance (1958), Wiley: Wiley New York |
| [30] | Neuts, M. F., Matrix Geometric Solutions in Stochastic models: an Algorithmic Approach (1981), The Johns Hopkins University Press · Zbl 0469.60002 |
| [31] | Neuts, M. F.; Takahashi, Y., Asymptotic behavior of the stationary distributions in the GI/PH/\(c\) queue with heterogeneous servers, Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 57, 441-452 (1981) · Zbl 0451.60085 |
| [32] | Ovuworie, G. C., Multi-channel queues: A survey and bibliography, International Statistical Review, 48, 49-71 (1980) · Zbl 0422.60070 |
| [33] | Page, F., Queueing Theory in OR (1972), Butterworths: Butterworths London · Zbl 0253.90002 |
| [34] | Ramaswami, V.; Lucantoni, D. M., Stationary waiting time distribution in queues with phase-type service and in quasi-birth-and-death processes, Communications in Statistics—Stochastic Models, 1, 125-136 (1985) · Zbl 0602.60086 |
| [35] | Sahin, I.; Perrakis, S., Moment inequalities for a class of single server queues, INFOR, 14, 144-152 (1976) · Zbl 0357.60028 |
| [36] | Sakasegawa, H., Numerical Tables of the Queueing Systems \(I; E_k/E_2/s\), (Computer Science Monographs No. 10 (1978), The Institute of Statistical Mathematics) |
| [37] | Seelen, L. P., An algorithm for PH/PH/\(c\) queues, European Journal of Operational Research, 23, 118-127 (1986) · Zbl 0584.90028 |
| [38] | Seneta, E., Finite approximations to infinite non-negative matrices, (Proceedings of the Cambridge Philosophical Society, 63 (1967)), 983-992 · Zbl 0178.20602 |
| [39] | Seneta, E., Finite approximations to infinite non-negative matrices, II: Refinements and applications, (Proceedings of the Cambridge Philosophical Society, 64 (1968)), 465-470 · Zbl 0197.02802 |
| [40] | Shapiro, S., The \(M\)-server queue with Poisson input and gamma-distributed service of order two, Operations Research, 14, 685-694 (1966) · Zbl 0143.20302 |
| [41] | Smit, J. H.A.de, The queue GI/M/\(s\) with customers of different types or the queueGI/\(H_m/s\), Advances in Applied Probability, 15, 392-419 (1983) · Zbl 0512.60086 |
| [42] | Smit, J. H.A.de, A numerical solution for the multi-server queue with hyper-exponential service times, Operations Research Letters, 2, 217-224 (1983) · Zbl 0532.60096 |
| [43] | Smit, J. H.A.de, The queue GI/\(H_m/s\) in continuous time, (Memorandum, 432 (1983), Dept of Mathematics, Twente University of Technology) |
| [44] | Stoyan, D., Comparison Methods for Queues and other Stochastic Models (1983), Wiley: Wiley New York · Zbl 0536.60085 |
| [45] | Sze, D. Y., A queueing model for telephone operation staffing, Operations Research, 32, 229-249 (1984) |
| [46] | Takahashi, Y., Asymptotic exponentiality of the tail of the waiting-time distribution in a PH/PH/\(c\) queue, Advances in Applied Probability, 13, 619-630 (1981) · Zbl 0463.60083 |
| [47] | Takahashi, Y.; Takami, Y., A numerical method for the steady-state probabilities of a GI/G/\(c\) qeueing system in a general class, Journal of the Operations Research Society of Japan, 19, 147-157 (1976) · Zbl 0348.60127 |
| [48] | Tijms, H. C., Stochastic Modeling and Analysis; a Computational Approach (1986), Wiley: Wiley New York · Zbl 0606.90128 |
| [49] | Tijms, H. C.; Hoorn, M. H.van; Federgruen, A., Approximations or the steady-state probabilities in the M/G/\(c\) queue, Advances in Applied Probability, 13, 515-522 (1981) · Zbl 0446.60079 |
| [50] | Whitt, W., Approximating a point process by a renewal process, I: Two basic methods, Operations Research, 30, 125-147 (1982) · Zbl 0481.90025 |
| [51] | Whitt, W., On the heavy-traffic limit theorem for GI/G/∞ queues, Advances in Applied Probability, 14, 171-190 (1982) · Zbl 0479.60090 |
| [52] | Xerocostas, D. A.; Demertzes, C., Steady state solution of the \(E_k\)/D/\(r\) queueing model, OR Spektrum, 4, 47-51 (1982) · Zbl 0479.60092 |
| [53] | Yao, D. D.W.; Buzacott, J. A., Queueing models for a flexible machining station; Part II: The method of Coxian phases, European Journal of Operations Research, 19, 241-252 (1985) · Zbl 0553.90050 |
| [54] | Yu, O., The steady-state solution of a heterogeneous-server queue with Erlang service times, (Neuts, M. F., Algorithmic Methods in Probability. Algorithmic Methods in Probability, TIMS Studies in the Management Sciences, 7 (1977)), 199-213 · Zbl 0395.60083 |
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.
