Hostname: page-component-8448b6f56d-c4f8m Total loading time: 0 Render date: 2024-04-18T01:07:51.313Z Has data issue: false hasContentIssue false
  • English
  • Français

A SUCCESSIVE LUMPING PROCEDURE FOR A CLASS OF MARKOV CHAINS

Published online by Cambridge University Press:  30 July 2012

Michael N. Katehakis  and
Laurens C. Smit
Michael N. Katehakis
Affiliation:
Department of Management Science and Information Systems, Rutgers Business School, Newark and New Brunswick, Newark, NJ 07210 E-mail: mnk@rutgers.edu
Laurens C. Smit
Affiliation:
Mathematisch Instituut, Universiteit Leiden, Niels Bohrweg 1, 2333 CA, The Netherlands E-mail: lsmit@math.leidenuniv.nl
Get access Rights & Permissions [Opens in a new window]

Abstract

A class of Markov chains we call successively lumbaple is specified for which it is shown that the stationary probabilities can be obtained by successively computing the stationary probabilities of a propitiously constructed sequence of Markov chains. Each of the latter chains has a(typically much) smaller state space and this yields significant computational improvements. We discuss how the results for discrete time Markov chains extend to semi-Markov processes and continuous time Markov processes. Finally, we will study applications of successively lumbaple Markov chains to classical reliability and queueing models.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 26 , Issue 4 , October 2012 , pp. 483 - 508
Copyright
Copyright © Cambridge University Press 2012

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.Derman, C., Lieberman, G.J., & Ross, S.M. (1980). On the optimal assignment of servers and a repairman. Journal of Applied Probability 17: 577–581.CrossRefGoogle Scholar
2.Feinberg, B.N., & Chui, S.S. (1987). A method to calculate steady state distributions of large Markov chains. Operations Research 35: 282–290.CrossRefGoogle Scholar
3.Frostig, E. (1999). Jointly optimal allocation of a repairman and optimal control of service rate for machine repairman problem. European Journal of Operational Research 116: 274–280.CrossRefGoogle Scholar
4.Hooghiemstra, G., & Koole, G. (2000). On the convergence of the power series algorithm. Performance Evaluation 42: 21–39.CrossRefGoogle Scholar
5.Katehakis, M.N., & Derman, C. (1984). Optimal repair allocation in a series system. Mathematics of Operations Research 9: 615–623.CrossRefGoogle Scholar
6.Katehakis, M.N., & Derman, C. (1989). On the maintenance of systems composed of highly reliable components. Management Science 35(5): 551–560.CrossRefGoogle Scholar
7.Katehakis, M.N., & Melolidakis, C. (1995). On the optimal maintenance of systems and control of arrivals in queues. Stochastic Analysis and Applications 13: 137–164.CrossRefGoogle Scholar
8.Kemeny, J.G., & Snell, J.L. (1960). Finite Markov chains. Princeton, NJ: D. van Nostrand Company, Inc.Google Scholar
9.Kim, D.S., & Smith, R.L. (1989). An exact aggregation algorithm for a special class of markov chains. Technical Report. University of Michigan.Google Scholar
10.Kim, D.S., & Smith, R.L. (1990), An exact aggregation–disaggregation algortihm for mandatory set decomposable markovchains. Numerical Solution of Markov Chains 89–104.Google Scholar
11.Koole, G.M., & Spieksma, F.M. (2001). On deviation matrices for birth–death processes. Probability in the Engineering and Informational Sciences 15: 239–258.CrossRefGoogle Scholar
12.Miranker, W.L., & Pan, V.Ya. (1980). Methods of aggregation. Linear Algebra and its Application 29: 231–257.CrossRefGoogle Scholar
13.Neuts, M.F. (1981). Matrix-geometric solutions in stochastic models. Baltimore: The Johns Hopkins University Press.Google Scholar
14.Righter, R. (1996). Optimal policies for scheduling repairs and allocating heterogeneous servers. Journal of Applied Probability 436–547.Google Scholar
15.Ross, S.M. (1996). Stochastic processes. New York: John Wiley and Sons.Google Scholar
16.Schweitzer, P.J., Puterman, M.L., & Kindle, W.L. (1984). Iterative aggregation–disaggregation procedures for discounted semi-markov reward processes. Operations Research 33: 589–605.CrossRefGoogle Scholar
17.Ungureanu, V., Melamed, B., Katehakis, M.N., & Bradford, P.G. (2006). Deferred assignment scheduling in cluster-based servers. Cluster Computing 9: 57–65.CrossRefGoogle Scholar
18.Yap, V.B. (2009). Similar states in continuous time Markov chains. Journal of Applied Probability 46: 497–506.CrossRefGoogle Scholar
19.Zhang, Q., Mi, N., Riska, A., & Smirni, E. (2007), Performance-guided load (un) balancing under autocorrelated flows. IEEE Transactions on Parallel and Distributed Systems 652–665.Google Scholar