Abstract
Rational Arrival Processes (RAPs) form a general class of stochastic processes which include Markovian Arrival Processes (MAPs) as a subclass. In this paper we study RAPs and their representations of different sizes. We show some transformation methods between different representations and present conditions to evaluate the size of the minimal representation. By using some analogous results from linear systems theory, a minimization approach is defined which allows one to transform a RAP (from a redundant high dimension) into one of its minimal representations. An algorithm for computing a minimal representation is also given. Furthermore, we extend the approach to RAPs with batch arrivals (BRAPs) and to RAPs with arrivals of different customer types (MRAPs).
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akar, N. (2006). Solving the ME/ME/1 queue with state-space methods and the matrix sign function. Performance Evaluation, 63, 131–145.
Asmussen, S., & Bladt, M. (1997). Renewal theory and queueing algorithms for matrix-exponential distributions. In Lecture notes in pure and appl. math.: Vol. 183. Matrix-analytic methods in stochastic models (pp. 313–341).
Asmussen, S., & Bladt, M. (1999). Point processes with finite-dimensional conditional probabilities. Stochastic Processes and Their Applications, 82, 127–142.
Bean, N. G., & Nielsen, B. F. (2010). Quasi-birth-and-death processes with rational arrival process components. Stochastic Models, 26(3), 309–334.
Bodrog, L., Horvath, A., & Telek, M. (2008). Moment characterization of matrix exponential and Markovian arrival processes. Annals of Operations Research, 160, 51–58.
Buchholz, P., & Telek, M. (2010). Stochastic Petri nets with matrix exponentially distributed firing times. Performance Evaluation, 67(12), 1373–1385.
Commault, C., & Mocanu, S. (2003). Phase-type distributions and representations: some open problems for system theory. International Journal of Control, 76(6), 566–580.
Davis, J. M., Gravagne, I. A., Jackson, B. J., & Marks, R. J. II (2009). Controllability, observability, realizability and stability of dynamic linear systems. Electronic Journal of Differential Equations, 37, 1–32.
de Schutter, B. (2000). Minimal state-space realization in linear system theory: An overview. Journal of Computational and Applied Mathematics, 121(1–2), 331–354.
Golub, G. H., & Van Loan, C. F. (1996). Matrix computations (3rd ed.). Baltimore: Johns Hopkins University Press
He, Q. M., & Neuts, M. (1998). Markov arrival processes with marked transitions. Stochastic Processes and Their Applications, 74, 37–52.
He, Q. M., & Zhang, H. (2007). On matrix exponential distributions. Advances in Applied Probability, 39, 271–292.
Heindl, A., Zhang, Q., & Smirni, E. (2004). ETAQA truncation models for the MAP/MAP/1 departure process. In QEST (pp. 100–109).
Lipsky, L. (2008). Queueing theory: a linear algebraic approach. Berlin: Springer.
Lucantoni, D. M. (1991). New results on the single server queue with a batch Markovian arrival process. Stochastic Models, 7, 1–46.
Mitchell, K. (2001). Constructing a correlated sequence of matrix exponentials with invariant first order properties. Operations Research Letters, 28, 27–34.
Neuts, M. F. (1979). A versatile Markovian point process. Journal of Applied Probability, 16, 764–779.
O’Cinneide, C. A. (1999). Phase-type distributions: Open problems and a few properties. Stochastic Models, 15(4), 731–757.
Telek, M., & Horváth, G. (2007). A minimal representation of Markov arrival processes and a moments matching method. Performance Evaluation, 64(9–12), 1153–1168.
Van Dooren, P. M. (1981). The generalized eigenstructure on linear system theory. IEEE Transactions on Automatic Control, 26(1), 111–129.
Varga, A. (1991). Minimal realization procedures based on balancing and related techniques. In F. Pichler & R. Moreno-Díaz (Eds.), Lecture notes in computer science: Vol. 585. EUROCAST (pp. 733–761). Berlin: Springer.
Zhang, Q., Heindl, A., & Smirni, E. (2005). Characterizing the BMAP/MAP/1 departure process via the ETAQA truncation. Stochastic Models, 21(2–3), 821–846.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Buchholz, P., Telek, M. On minimal representations of Rational Arrival Processes. Ann Oper Res 202, 35–58 (2013). https://doi.org/10.1007/s10479-011-1001-5
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-011-1001-5