Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-22T17:14:21.739Z Has data issue: false hasContentIssue false
  • English
  • Français

A compensation approach for two-dimensional Markov processes

Part of: Operations research and management science Special processes

Published online by Cambridge University Press:  01 July 2016

I. J. B. F. Adan ,
J. Wessels  and
W. H. M. Zijm
I. J. B. F. Adan*
Affiliation:
Eindhoven University of Technology
J. Wessels*
Affiliation:
Eindhoven University of Technology
W. H. M. Zijm*
Affiliation:
University of Twente
*
* Postal address: Eindhoven University of Technology, Department of Mathematics and Computing Science, PO Box 513, 5600 MB Eindhoven, The Netherlands.
** Postal address: Eindhoven University of Technology, Department of Mathematics and Computing Science, PO Box 513, 5600 MB Eindhoven, The Netherlands. Also affiliated to the International Institute for Applied Systems Analysis, Laxenburg, Austria.
** Postal address: University of Twente, Department of Mechanical Engineering, Enschede, The Netherlands.
Get access Rights & Permissions [Opens in a new window]

Abstract

Several queueing processes may be modeled as random walks on a multidimensional grid. In this paper the equilibrium distribution for the case of a two-dimensional grid is considered. In previous research it has been shown that for some two-dimensional random walks the equilibrium distribution has the form of an infinite series of products of powers which can be constructed with a compensation procedure. The object of the present paper is to investigate under which conditions such an elegant solution exists and may be found with a compensation approach. The conditions can be easily formulated in terms of the random behaviour in the inner area and the drift on the boundaries.

Keywords

EQUILIBRIUM DISTRIBUTIONQUEUESRANDOM WALKS

MSC classification

Primary: 60K25: Queueing theory
Secondary: 90B22: Queues and service
Type
Research Article
Information
Advances in Applied Probability , Volume 25 , Issue 4 , December 1993 , pp. 783 - 817
Copyright
Copyright © Applied Probability Trust 1993 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Adan, I. J. B. F. (1991) A compensation approach for queueing problems. Ph.D. thesis, Eindhoven University of Technology.Google Scholar
[2] Adan, I. J. B. F., Van Houtum, G. J., Wessels, J. and Zijm, W. H. M. (1993) A compensation procedure for multiprogramming queues. OR Spektrum 15, 95–106.CrossRefGoogle Scholar
[3] Adan, I. J. B. F., Van De Waarsenburg, W. A. and Wessels, J. (1992) Analysing Ek/Er/c queues. Submitted for publication.Google Scholar
[4] Adan, I. J. B. F., Wessels, J. and Zijm, W. H. M. (1990) Analysis of the symmetric shortest queue problem. Stoch. Models 6, 691–713.CrossRefGoogle Scholar
[5] Adan, I. J. B. F., Wessels, J. and Zijm, W. H. M. (1991) Analysis of the asymmetric shortest queue problem. QUESTA 8, 1–58.Google Scholar
[6] Adan, I. J. B. F., Wessels, J. and Zijm, W. H. M. (1991) Analysis of the asymmetric shortest queue problem with threshold jockeying. Stoch. Models 7, 615–627.CrossRefGoogle Scholar
[7] Adan, I. J. B. F., Wessels, J. and Zijm, W. H. M. (1993) Analysing multiprogramming queues by generating functions. SIAM J. Appl. Math. 53. To appear.Google Scholar
[8] Baskett, F., Chandy, K. M., Muntz, R. and Palacios-Gomez, F. (1975) Open, closed and mixed networks of queues with different classes of customers. J. Assoc. Comput. Mach. 22, 248–260.CrossRefGoogle Scholar
[9] Blanc, J. P. C. (1987) On a numerical method for calculating state probabilities for queueing systems with more than one waiting line. J. Comput. Appl. Math. 20, 119–125.CrossRefGoogle Scholar
[10] Blanc, J. P. C. (1992) The power-series algorithm applied to the shortest-queue model. Operat. Res. 40, 157–167.CrossRefGoogle Scholar
[11] Boxma, O. J. and Van Houtum, G. J. (1993) The compensation approach applied to a 2 × 2 switch. Prob. Eng. Inf. Sci. To appear.CrossRefGoogle Scholar
[12] Cohen, J. W. (1987) A two-queue, one-server model with priority for the longer queue. QUESTA 2, 261–283.Google Scholar
[13] Cohen, J. W. and Boxma, O. J. (1983) Boundary Value Problems in Queueing System Analysis. North-Holland, Amsterdam.Google Scholar
[14] Fayolle, G. (1979) Méthodes analytiques pour les files d'attente coupleés. Thesis, Université de Paris VI.Google Scholar
[15] Fayolle, G. and Iasnogorodski, R. (1979) Two coupled processors: the reduction to a Riemann-Hilbert problem. Z. Wahrscheinlichkeitsth. 47, 325–351.CrossRefGoogle Scholar
[16] Flatto, L. The longer queue model. Prob. Eng. Inf. Sci. 3, 537–559.CrossRefGoogle Scholar
[17] Flatto, L. and Mckean, H. P. (1977) Two queues in parallel. Comm. Pure Appl. Math. 30, 255–263.CrossRefGoogle Scholar
[18] Foster, F. G. (1953) On the stochastic matrices associated with certain queueing processes. Ann. Math. Statist. 24, 355–360.CrossRefGoogle Scholar
[19] Hofri, M. (1978) A generating-function analysis of multiprogramming queues. Internat. J. Comp. Inf. Sci. 7, 121–155.CrossRefGoogle Scholar
[20] Hooghiemstra, G., Keane, M. and Van De Ree, S. (1988) Power series for stationary distributions of coupled processor models. SIAM J. Appl. Math. 48, 1159–1166.CrossRefGoogle Scholar
[21] Iasnogorodski, R. (1979) Problèmes-frontières dan les files d'attente. Thesis, Université de Paris IV.Google Scholar
[22] Jaffe, S. (1992) Equilibrium results for a pair of coupled discrete-time queues. Prob. Eng. inf. Sci. 6, 425–438.Google Scholar
[23] Kingman, J. F. C. (1961) Two similar queues in parallel. Ann. Math. Statist. 32, 1314–1323.CrossRefGoogle Scholar
[24] Konheim, A. G., Meilijson, J. and Melkman, A. (1981) Processor-sharing of two parallel lines. J. Appl. Prob. 18, 952–956.CrossRefGoogle Scholar
[25] Neuts, M. F. (1981) Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore.Google Scholar
[26] Zheng, Y. S. and Zipkin, P. (1990) A queueing model to analyze the value of centralized inventory information. Operat. Res. 38, 296–307.CrossRefGoogle Scholar