×

Upper bounds on performance measures of heterogeneous \(M/M/c\) queues. (English) Zbl 1235.90042

Summary: In many real-life queueing systems, the servers are often heterogeneous, namely they work at different rates. This paper provides a simple method to compute tight upper bounds on two important performance measures of single-class heterogeneous multi-server Markovian queueing systems, namely the average number in queue and the average waiting time in queue. This method is based on an expansion of the state space that is followed by an approximate reduction of the state space, only considering the most probable states. In most cases tested, we were able to approximate the actual behavior of the system with smaller errors than those obtained from traditional homogeneous multiserver Markovian queues, as shown by GPSS simulations. In addition, we have correlated the quality of the approximation with the degree of heterogeneity of the system, which was evaluated using its Gini index. Finally, we have shown that the bounds are robust and still useful, even considering quite different allocation strategies. A large number of simulation results show the accuracy of the proposed method that is better than that of classical homogeneous multiserver Markovian formulae in many situations.

MSC:

90B22 Queues and service in operations research
60K25 Queueing theory (aspects of probability theory)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. M. Youssef and H. A. ElMaraghy, “Performance analysis of manufacturing systems composed of modular machines using the universal generating function,” Journal of Manufacturing Systems, vol. 27, no. 2, pp. 55-69, 2008.
[2] J. Li, E. Enginarlar, and S. M. Meerkov, “Conservation of filtering in manufacturing systems with unreliable machines and finished goods buffers,” Mathematical Problems in Engineering, vol. 2006, Article ID 27328, 12 pages, 2006. · Zbl 1200.91160
[3] A. B. Hu and S. M. Meerkov, “Lean buffering in serial production lines with Bernoulli machines,” Mathematical Problems in Engineering, Article ID 17105, 24 pages, 2006. · Zbl 1200.91158
[4] I. Dimitriou and C. Langaris, “A repairable queueing model with two-phase service, start-up times and retrial customers,” Computers & Operations Research, vol. 37, no. 7, pp. 1181-1190, 2010. · Zbl 1178.90090
[5] T. van Woensel, L. Kerbache, H. Peremans, and N. Vandaele, “Vehicle routing with dynamic travel times: a queueing approach,” European Journal of Operational Research, vol. 186, no. 3, pp. 990-1007, 2008. · Zbl 1146.90426
[6] N. U. Ahmed and X. H. Ouyang, “Suboptimal RED feedback control for buffered TCP flow dynamics in computer network,” Mathematical Problems in Engineering, Article ID 54683, 17 pages, 2007. · Zbl 1169.68345
[7] J. Chen, C. Hu, and Z. Ji, “An improved ARED algorithm for congestion control of network transmission,” Mathematical Problems in Engineering, vol. 2010, Article ID 329035, 14 pages, 2010. · Zbl 1191.68096
[8] L. Tang, H. S. Xi, J. Zhu, and B. Q. Yin, “Modeling and optimization of M/G/1-type queueing networks: an efficient sensitivity analysis approach,” Mathematical Problems in Engineering, Article ID 130319, 20 pages, 2010. · Zbl 1195.90033
[9] T. van Woensel and F. R. B. Cruz, “A stochastic approach to traffic congestion costs,” Computers and Operations Research, vol. 36, no. 6, pp. 1731-1739, 2009. · Zbl 1179.90086
[10] Q. Wang, S. Lassalle, A. R. Mileham, and G. W. Owen, “Analysis of a linear walking worker line using a combination of computer simulation and mathematical modeling approaches,” Journal of Manufacturing Systems, vol. 28, no. 2-3, pp. 64-70, 2009.
[11] H. Gumbel, “Waiting lines with heterogeneous servers,” Operations Research, vol. 8, pp. 504-511, 1960. · Zbl 0097.13101
[12] V. P. Singh, “Markovian queues with three heterogeneous servers,” AIIE Transactions, vol. 3, no. 1, pp. 45-48, 1971.
[13] V. P. Singh, “Two-server Markovian queues with balking: heterogeneous vs. homogeneous servers,” Operations Research, vol. 18, pp. 145-159, 1970. · Zbl 0186.24703
[14] P. Le Gall, “The stationary G/G/s queue with non-identical servers,” Journal of Applied Mathematics and Stochastic Analysis, vol. 11, no. 2, pp. 163-178, 1998. · Zbl 0922.60085
[15] P. Le Gall, “The stationary G/G/s queue,” Journal of Applied Mathematics and Stochastic Analysis, vol. 11, no. 1, pp. 59-71, 1998. · Zbl 0922.60085
[16] K. W. Grassmann and Q. Y. Zhao, “Heterogeneous multiserver queues with general input,” Tech. Rep., University of Winnipeg, Manitoba, Canada, 2004. · Zbl 0898.60097
[17] O. J. Boxma, Q. Deng, and A. P. Zwart, “Waiting-time asymptotics for the M/G/2 queue with heterogeneous servers,” Queueing Systems, vol. 40, no. 1, pp. 5-31, 2002. · Zbl 0993.60098
[18] X. Chao and H. P. Luh, “A stochastic directional convexity result and its application in comparison of queues,” Queueing Systems, vol. 48, no. 3-4, pp. 399-419, 2004. · Zbl 1125.60312
[19] S. Y. Chiang, A. Hu, and S. M. Meerkov, “Lean buffering in serial production lines with nonidentical exponential machines,” IEEE Transactions on Automation Science and Engineering, vol. 5, no. 2, pp. 298-306, 2008.
[20] S. Biller, S. P. Marin, S. M. Meerkov, and L. Zhang, “Closed bernoulli production lines: analysis, continuous improvement, and leanness,” IEEE Transactions on Automation Science and Engineering, vol. 6, no. 1, pp. 168-180, 2009.
[21] M. Marmony, “Dynamic routing in large-scale service systems with heterogeneous servers,” Queueing Systems, vol. 51, no. 3-4, pp. 287-329, 2005. · Zbl 1094.60058
[22] A. van Harten and A. Sleptchenko, “On Markovian multi-class, multi-server queueing,” Queueing Systems, vol. 43, no. 4, pp. 307-328, 2003. · Zbl 1020.60090
[23] W. Lin and P. R. Kumar, “Optimal control of a queueing system with two heterogeneous servers,” IEEE Transactions on Automatic Control, vol. 29, no. 8, pp. 696-703, 1984. · Zbl 0546.90035
[24] G. Koole, “A simple proof of the optimality of a threshold policy in a two-server queueing system,” Systems & Control Letters, vol. 26, no. 5, pp. 301-303, 1995. · Zbl 0876.90052
[25] J. Walrand, “A note on ‘optimal control of a queuing system with two heterogeneous servers’,” Systems & Control Letters, vol. 4, no. 3, pp. 131-134, 1984. · Zbl 0581.60079
[26] V. Rykov and D. Efrosinin, “Optimal control of queueing systems with heterogeneous servers,” Queueing Systems, vol. 46, no. 3-4, pp. 389-407, 2004. · Zbl 1061.90035
[27] S. Shenker and A. Weinrib, “Asymptotic analysis of large heterogeneous queueing systems,” in Proceedings of the ACMSIGMETRICS Conference on Measurement and Modeling of Computer Systems (SIGMETRICS ’88), pp. 56-62, ACM, New York, NY, USA, 1988.
[28] S. Shenker and A. Weinrib, “The optimal control of heterogeneous queueing systems: a paradigm for load-sharing and routing,” IEEE Transactions on Computers, vol. 38, no. 12, pp. 1724-1735, 1989.
[29] F. R. B. Cruz, T. van Woensel, J. MacGregor Smith, and K. Lieckens, “On the system optimum of traffic assignment in M/G/c/c state-dependent queueing networks,” European Journal of Operational Research, vol. 201, no. 1, pp. 183-193, 2010. · Zbl 1177.90089
[30] T. J. Schriber, An Introduction to Simulation Using GPSS/H, John Wiley and Sons, New York, NY, USA, 1991.
[31] S. Robinson, “A statistical process control approach to selecting a warm-up period for a discrete-event simulation,” European Journal of Operational Research, vol. 176, no. 1, pp. 332-346, 2007. · Zbl 1137.90470
[32] H. Shalit, “Calculating the Gini index of inequality for individual data,” Oxford Bulletin of Economics and Statistics, vol. 47, pp. 185-189, 1985.
[33] N. Al-Matar and J. H. Dshalalow, “Maintenance in single-server queues: a game-theoretic approach,” Mathematical Problems in Engineering, Article ID 857871, 23 pages, 2009. · Zbl 1190.90048
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.