Computational schemes for two exponential servers where the first has a finite buffer

Moshe Haviv; Rita Zlotnikov

RAIRO - Operations Research - Recherche Opérationnelle (2011)

  • Volume: 45, Issue: 1, page 17-36
  • ISSN: 0399-0559

Abstract

top
We consider a system consisting of two not necessarily identical exponential servers having a common Poisson arrival process. Upon arrival, customers inspect the first queue and join it if it is shorter than some threshold n. Otherwise, they join the second queue. This model was dealt with, among others, by Altman et al. [Stochastic Models20 (2004) 149–172]. We first derive an explicit expression for the Laplace-Stieltjes transform of the distribution underlying the arrival (renewal) process to the second queue. Second, we observe that given that the second server is busy, the two queue lengths are independent. Third, we develop two computational schemes for the stationary distribution of the two-dimensional Markov process underlying this model, one with a complexity of O ( n log δ - 1 ) , the other with a complexity of O ( log n log 2 δ - 1 ) , whereδ is the tolerance criterion.

How to cite

top

Haviv, Moshe, and Zlotnikov, Rita. "Computational schemes for two exponential servers where the first has a finite buffer." RAIRO - Operations Research - Recherche Opérationnelle 45.1 (2011): 17-36. <http://eudml.org/doc/275090>.

@article{Haviv2011,
abstract = {We consider a system consisting of two not necessarily identical exponential servers having a common Poisson arrival process. Upon arrival, customers inspect the first queue and join it if it is shorter than some threshold n. Otherwise, they join the second queue. This model was dealt with, among others, by Altman et al. [Stochastic Models20 (2004) 149–172]. We first derive an explicit expression for the Laplace-Stieltjes transform of the distribution underlying the arrival (renewal) process to the second queue. Second, we observe that given that the second server is busy, the two queue lengths are independent. Third, we develop two computational schemes for the stationary distribution of the two-dimensional Markov process underlying this model, one with a complexity of $O(n \log \delta ^\{-1\})$, the other with a complexity of $O(\log n \log ^2\delta ^\{-1\})$, whereδ is the tolerance criterion.},
author = {Haviv, Moshe, Zlotnikov, Rita},
journal = {RAIRO - Operations Research - Recherche Opérationnelle},
keywords = {memoryless queues; quasi birth and death processes; matrix geometric; queueing; performance evaluation; scheduling; queues and service},
language = {eng},
number = {1},
pages = {17-36},
publisher = {EDP-Sciences},
title = {Computational schemes for two exponential servers where the first has a finite buffer},
url = {http://eudml.org/doc/275090},
volume = {45},
year = {2011},
}

TY - JOUR
AU - Haviv, Moshe
AU - Zlotnikov, Rita
TI - Computational schemes for two exponential servers where the first has a finite buffer
JO - RAIRO - Operations Research - Recherche Opérationnelle
PY - 2011
PB - EDP-Sciences
VL - 45
IS - 1
SP - 17
EP - 36
AB - We consider a system consisting of two not necessarily identical exponential servers having a common Poisson arrival process. Upon arrival, customers inspect the first queue and join it if it is shorter than some threshold n. Otherwise, they join the second queue. This model was dealt with, among others, by Altman et al. [Stochastic Models20 (2004) 149–172]. We first derive an explicit expression for the Laplace-Stieltjes transform of the distribution underlying the arrival (renewal) process to the second queue. Second, we observe that given that the second server is busy, the two queue lengths are independent. Third, we develop two computational schemes for the stationary distribution of the two-dimensional Markov process underlying this model, one with a complexity of $O(n \log \delta ^{-1})$, the other with a complexity of $O(\log n \log ^2\delta ^{-1})$, whereδ is the tolerance criterion.
LA - eng
KW - memoryless queues; quasi birth and death processes; matrix geometric; queueing; performance evaluation; scheduling; queues and service
UR - http://eudml.org/doc/275090
ER -

References

top
  1. [1] E. Altman, T. Jimenez, R. Nunez Queija and U. Yechiali, Optimal routing among · /M/1 queues with partial information. Stochastic Models20 (2004) 149–172 Zbl1060.60087MR2048250
  2. [2] E. Altman, T. Jimenez, R. Nunez Queija and U. Yechiali, A correction to Optimal routing among · /M/1 queues with partial information. Stochastic Models 21 (2005) 981 Zbl1060.60087MR2178352
  3. [3] F. Avram, Analytic solutions for some QBD models (2010) 
  4. [4] R. Hassin, On the advantage of being the first server. Management Sci.42 (1996) 618–623 Zbl0880.90049
  5. [5] M. Haviv and Y. Kerner, The age of the arrival process in the G/M/1 and M/G/1 queues. Math. Methods Oper. Res.73 (2011) 139–152 Zbl1209.93141MR2772598
  6. [6] A. Kopzon, Y. Nazarathy and G. Weiss, A push-pull network with infinite supply of work. Queueing Systems: Theory and Application 62 (2009) 75–111 Zbl1166.60333MR2520744
  7. [7] S. Karlin and J.L. McGregor, The differential equations of birth-and-death processes, and the Stieltjes moment problem. Trans. Am. Math. Soc.85 (1957) 589–646 Zbl0091.13801MR91566
  8. [8] W. Keller-Gehring, Fast algorithm for the characteristic polynomial. Theor. Comput. Sci.36 (1985) 309–317 Zbl0565.68041MR796306
  9. [9] L. Kleinrock, Queueing Systems 2. John Wiley and Sons, New York (1976) Zbl0334.60045
  10. [10] D.P. Kroese, W.R.W. Scheinhardt and P.G. Taylor, Spectral properties of the tandem Jackson network, seen as a quisi-birth-and-death process, Ann. Appl. Prob.14 (2004) 2057–2089 Zbl1078.60078MR2099663
  11. [11] D. Liu and Y.Q. Zhao, Determination of explict solutions for a general class of Markov processes, in Matrix-Analytic Methods in Stochastic Models, edited by S. Charvarthy and A.S. Alfa, Marcel Dekker (1996) 343–357 Zbl0872.60075MR1427280
  12. [12] M. NeutsMatrix-Geometric Solutions in Stochastic Models. The John Hopkins University Press, Baltimore (1981) Zbl0469.60002MR618123
  13. [13] V. Ramaswami and G. Latouch, A general class of Markov processes with explicit matrix-geometric solutions. OR Spektrum8 (1986) 209–218 Zbl0612.60057MR869006
  14. [14] S.M. RossStochastic Processes, 2nd edition, John Wiley and Sons, New York (1996) Zbl0555.60002MR1373653

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.