nach oben

Erschienen in:

2013 | OriginalPaper | Buchkapitel

12. Two-Dimensional Markov Processes and Their Applications to Memoryless Queues

verfasst von : Moshe Haviv

Erschienen in: Queues

Verlag: Springer New York

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We have already seen Markov processes in which each state is represented by a vector. These Markov processes offer a convenient way to refer to a state (in fact, this was nothing more than giving names to states). Such was the case, for example, when we dealt with open and closed networks of queues, and with multiclass single-server queues. In this respect there is nothing new in this chapter where the states will be represented by two-dimensional vectors; that is, a state will be referred to by the pair of nonnegative integers (i, j). However, in an attempt to generalize some results from one-dimensional birth-and-death precesses, we will impose the following restrictions on the model:

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Insensitivity and Product-Form Queueing Models

This regime implies that the only option is in fact T + 1.

We do not consider the case where T = 0 as the resulting system is that of an M/M/1 queue.

The case where n = 0 makes the first server always idle and the second line becomes an M/M/1 queue. Thus, we ignore this option of the value for the threshold n.

The other solution x = 1 is immaterial here.

Note that \(A_{0} + A_{1} + A_{2}\) is a stochastic matrix. Moreover, its corresponding discrete-time Markov chain is a uniformization of the original continuous-time Markov process as defined in Sect. 8.5. In particular, it shares its limit probabilities with those of the original process.

The derivation given here is due to Binyamin Oz.

Note that for this not to be the case, s consecutive service stage completions prior to an arrival must take place.

In [40] it is shown that the property that leads to a more explicit solution here is the fact that Q ₀ is a rank-one matrix, i.e., a matrix that is the product of a column vector and a row vector. Of course, the Q ₀ under consideration here is a special case of such a matrix: the column vector is (0, ⋯ , 0, 1)^t and the row vector is (0, ⋯ , 0, λ).

The model \(M/E_{r}/1\) is dual to the one given here in the sense that now the level can go down by one only from a single value for the phase. Nevertheless, an explicit solution for the limit probabilities can be derived (even without the need to solve for the root of a polynomial as is required here). See [40] for details.

An alternative proof for this “almost” independence property is given in [40] and [24].

Broadly speaking, we can say that the first queue evolves “independently” of the second queue. Yet, the two queues are not (statistically) independent.

It is interesting to observe that \(\underline{\pi }_{j+1} = \underline{\pi }_{j}R_{1}\), j ≥ 1, where R ₁ is a diagonal matrix with all its diagonal entries equal to w _n. This does not refute the claim that the rate matrix R is the unique matrix where \(\underline{\pi }_{j+1} = \underline{\pi }_{j}R\), j ≥ 0.

The latter reference states an expression due to Yoav Kerner.

Part of this proof was communicated by Binyamin Oz.

Note that Eqs. (12.55) are obeys for any A and B.

This subsection calls for the previous knowledge of the subject of eigenvectors and of the spectral decomposition and can be skipped.

This model was introduced in Sect. 4.7.3. What follows below is based on [10].

Adan, I. J. B. F., Wessels, J., & Zijm, W. H. M. (1993). Matrix-geometric analysis of the shortest queue problem with threshold jockeying. Operations Research Letters, 13, 107–112.CrossRef

Adan, I. J. B. F., Wessels, J., & Zijm, W. H. M. (1993). A compensation approach for two-dimensional Markov processes. Advance Applied Probability, 25, 783–817.CrossRef

Altman, E., Jimenez, T., Nunez Queija, R., & Yechiali, U. (2004). Optimal routing among ⋅/M/1 queues with partial information. Stochastic Models, 20, 149–172.CrossRef

Altman, E., Jimenez, T., Nunez Queija, R., & Yechiali, U. (2005). Correction to ‘Optimal routing among ⋅/M/1 queues with partial information. Stochastic Models, 21, 981.CrossRef

10.

Brunetas, A., & Economou, A. (2007). Equililbrium customer strategies in a single Markovian queue with setup times. Queueing Systems: Theorey and Applications, 56, 213–228.CrossRef

14.

Cohen, J. W., & Boxma, O. J. (1983). Boundary values problems in queueing systems analysis. Amsterdam: North Holland.

18.

Fayolle, G., King, P. J. B., & Mitrani, I. (1982). The solution of certain two-dimensional Markov models. Advences in Applied Probability, 14, 295–308.CrossRef

21.

Hassin, R. (1996). On the advantage of being the first server. Management Science, 41, 163–173.CrossRef

24.

Haviv, M., & Kerner, Y. (2010). The age of the arrival process in the G/M/1 and M/G/1 queues. Mathematical Methods of Operations Research, 73, 139–152.CrossRef

27.

Haviv, M., & Zlotnikov, R. (2011). Computational schemes for two exponential servers where the first has a finite buffer. RAIRO – Operations Research, 45, 17–66.

29.

Kopzon, A., Nazarathy, Y., & Weiss, G. (2009). A push pull queueing with infinite supply of work. Queueing Systems: Theory and Applications, 66, 75–111.CrossRef

34.

Kingman, J. F. C. (1961). Two similar queues in parallel. Annals of Mathematical Statistics, 32, 1314–1323.CrossRef

38.

Neuts, M. F. (1981). Matrix-geometric solutions in stochastic models. Baltimore: The John Hopkins University Press.

40.

Ramaswamy, V., & Latouch, G. (1986). A general class of Markov processes with explicit matrix-geometric solutions. OR Spectrum, 8, 209–218.CrossRef

42.

Seneta, E. (2006). Non-negative matrices and Markov Chains: revised prinitng. New York: Springer.

Titel: Two-Dimensional Markov Processes and Their Applications to Memoryless Queues
verfasst von: Moshe Haviv
Verlag: Springer New York
Buch: Queues
Print ISBN: 978-1-4614-6764-9

Electronic ISBN: 978-1-4614-6765-6

Copyright-Jahr: 2013
DOI: https://doi.org/10.1007/978-1-4614-6765-6_12

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner