Asymptotic behavior of the expansion method for open finite queueing networks. (English) Zbl 0662.60105
The paper presents an approximation technique for the modeling of finite capacity queueing networks.
In the first part, the ‘expansion method’, already discussed in earlier papers, is described. The basic idea behind it is the introduction of ‘holding nodes’ representing the additional waiting times incurred by customers due to blocking. In limiting the analysis to exponential service times and an external Poisson arrival process, an exhaustive set of recursive equations is derived based on mean value computation and well-known approximations [see J. Labetoulle and G. Pujolle, IEEE Trans. Software Eng. SE-6, No.4 (1980)].
In part two, the value of the expansion method with regard to meeting an upper bound throughput criterion [P. C. Bell, Oper. Res. Lett. 1, 230-235 (1982; Zbl 0499.90039)] even for quite ‘unbalanced’ service rates is demonstrated.
In the first part, the ‘expansion method’, already discussed in earlier papers, is described. The basic idea behind it is the introduction of ‘holding nodes’ representing the additional waiting times incurred by customers due to blocking. In limiting the analysis to exponential service times and an external Poisson arrival process, an exhaustive set of recursive equations is derived based on mean value computation and well-known approximations [see J. Labetoulle and G. Pujolle, IEEE Trans. Software Eng. SE-6, No.4 (1980)].
In part two, the value of the expansion method with regard to meeting an upper bound throughput criterion [P. C. Bell, Oper. Res. Lett. 1, 230-235 (1982; Zbl 0499.90039)] even for quite ‘unbalanced’ service rates is demonstrated.
Reviewer: G.Wieber
MSC:
| 60K25 | Queueing theory (aspects of probability theory) |
| 60K20 | Applications of Markov renewal processes (reliability, queueing networks, etc.) |
| 90B22 | Queues and service in operations research |
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
Keywords:
tandem queues; decomposition; approximation technique; finite capacity queueing networks; Poisson arrival processCitations:
Zbl 0499.90039References:
| [1] | Chandy, K. M.; Sauer, C. H., Approximate methods for analyzing queueing network models of computing systems, Comput. Surveys, 10, 281-317 (1978) · Zbl 0385.68039 |
| [2] | Kobayashi, H., Application of the diffusion approximation to queueing networks I: equilibrium queue distributions, J. Assoc. Comput. Machinery, 21, 316-328 (April 1974) · Zbl 0278.60074 |
| [3] | Reiser, M.; Kobayashi, H., Accuracy of the diffusion approximation for some queueing systems, IBM J. Res. Dev., 18 (1974) · Zbl 0275.68014 |
| [4] | Halachimi, B.; Franta, W. R., A diffusion approximation solution the \(G/G/k\) queueing system, Comput. Opns Res., 4, 37-46 (1977) |
| [5] | Gelenbe, E.; Pujolle, G., The behavior of a single queue in a general queueing network, Acta Inform., 7, 123-136 (1976) · Zbl 0349.60091 |
| [6] | Newell, G. F., Approximate Behavior of Tandem Queues (1980), Springer: Springer Berlin · Zbl 0497.90017 |
| [7] | Sauer, C. H.; Chandy, K. M., Computer Systems Performance Modeling (1981), Prentice-Hall: Prentice-Hall Englewood Cliffs, N.J |
| [8] | Jackson, J. R., Networks of waiting lines, Opns Res., 5, 518-521 (1957) · Zbl 1414.90067 |
| [9] | Kuehn, P. J., Approximate analysis of general networks by decomposition, IEEE Transact. Commun., COM-27, 113-126 (January 1979) · Zbl 0392.60070 |
| [10] | Whitt, W., Approximations for Networks of Queues: A Simple Two-Parameter Linear Algorithm (1982), Bell Laboratories Holmdel: Bell Laboratories Holmdel N.J |
| [11] | Buzacott, J.; Shanthikumar, J., Approximate queueing models of dynamic job shops, Mgmt Sci., 31, 870-887 (1985) |
| [12] | Smith, J. M.; Bouanaka, B., Queueing networks decomposition in facilities planning, Comput. Opns Res., 12, 1-16 (1985) |
| [13] | Perros, H. G., Queueing networks with blocking: a bibliography, ACM Sigmet., 12, 8-12 (1984) |
| [14] | Labetoulle, J.; Pujolle, G., Isolation method in a network of queues, IEEE Transact. Software Engng, SE-6, 4 (July 1980) |
| [15] | Boxma, O.; Konheim, A., Approximate analysis of exponential queueing systems with blocking, Acta inform., 15, 19-26 (1981) · Zbl 0442.60091 |
| [16] | Caseau, P.; Pujolle, G., Throughput capacity of a sequence of queues with blocking due to finite waiting room, IEEE Trans. Soft. Engng, SE-5, 631-642 (1979) · Zbl 0428.68002 |
| [17] | Fredericks, A. A.; Reisner, G. A., Approximations to stochastic service systems, with an application to a retrial model, The Bell Syst. Techn. J., 58, 557-576 (1979) · Zbl 0402.90043 |
| [18] | Fredericks, A. A., Congestion in blocking systems—A simple approximation technique, The Bell Syst. Tech. J., 59, 805-827 (1980) · Zbl 0439.90037 |
| [19] | Millier, F. S.; Boling, R. W., Finite queues in series with exponential or Erlang service times—A numerical approach, Opns Res., 15, 286-303 (1967) · Zbl 0171.16302 |
| [20] | Takahashi, Y.; Miyahara, H.; Hasegawa, T., An approximation method for open restricted queueing networks, Opns Res., 28, 594-602 (June 1980), (Part I, May) · Zbl 0442.90025 |
| [21] | Altiok, T., Approximate analysis of exponential tandem queues with blocking, Eur. J. Opns Res., 11, 390-398 (1982) · Zbl 0497.60096 |
| [22] | Altiok, T.; Perros, H. G., Open networks of queues with blocking: split and merge configurations, (Paper presented at the ORSA/TIMS Meeting. Paper presented at the ORSA/TIMS Meeting, San Francisco. Calif. 14-16 May (1984)) |
| [23] | Kerbache, L., Analysis of open finite queueing networks, (Ph.D. thesis (February 1984), Department of Industrial Engineering and Operations Research, University of Massachusetts: Department of Industrial Engineering and Operations Research, University of Massachusetts Amherst, MA 01003) |
| [24] | Suri, R.; Diehl, G. W., A new building block for performance evaluation of queueing networks with finite buffer, (ACM S1GMETRICS Conference Proceedings. ACM S1GMETRICS Conference Proceedings, Cambridge, Mass. (August 1984)) |
| [25] | Kleinrock, L., Theory, (Queueing Systems, Vol. I (1975), Wiley: Wiley New York) · Zbl 0161.13701 |
| [26] | Brown, K. M., A quadratically convergent Newton-like method based upon Gaussian elimination, SIAM J. numer. Anal., 6, 560-569 (1969) · Zbl 0245.65023 |
| [27] | Talebi, K., Stochastic network evacuation models, (Ph.D. dissertation (September 1985), University of Massachusetts, Department of Industrial Engineering and Operations Research: University of Massachusetts, Department of Industrial Engineering and Operations Research Amherst, MA 01003) |
| [28] | Bell, P. C., The use of decomposition techniques for the analysis of open restricted queueing networks, Opns Res. Lett., 1, 230-235 (1982) · Zbl 0499.90039 |
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.
