Markovian arrivals in stochastic modellinga survey and some new results

  1. Artalejo Rodríguez, Jesús Manuel
  2. Gómez-Corral, Antonio
  3. He, Qi-Ming
Revista:
Sort: Statistics and Operations Research Transactions

ISSN: 1696-2281

Año de publicación: 2010

Volumen: 34

Número: 2

Páginas: 101-156

Tipo: Artículo

DIALNET GOOGLE SCHOLAR lock_openAcceso abierto editor

Otras publicaciones en: Sort: Statistics and Operations Research Transactions

Resumen

This paper aims to provide a comprehensive review on Markovian arrival processes (MAPs), which constitute a rich class of point processes used extensively in stochastic modelling. Our starting point is the versatile process introduced by Neuts (1979) which, under some simplified notation, was coined as the batch Markovian arrival process (BMAP). On the one hand, a general point process can be approximated by appropriate MAPs and, on the other hand, the MAPs provide a versatile, yet tractable option for modelling a bursty flow by preserving the Markovian formalism. While a number of well-known arrival processes are subsumed under a BMAP as special cases, the literature also shows generalizations to model arrival streams with marks, nonhomogeneous settings or even spatial arrivals. We survey on the main aspects of the BMAP, discuss on some of its variants and generalizations, and give a few new results in the context of a recent state-dependent extension.

Referencias bibliográficas

  • Ahn, S. and Badescu, A. L. (2007). On the analysis of the Gerber-Shin discounted penalty function for risk processes with Markovian arrivals.Insurance: Mathematics and Economics, 41, 234-249.
  • Alfa, A. S. and Neuts, M. F. (1995). Modelling vehicular traffic using the discrete time Markovian arrival process.Transportation Science, 29, 109-117.
  • Alfa, A. S., Liu, B. and He, Q.-M. (2003). Discrete-time analysis of MAP/PH/1 multiclass general preemptive priority queue.Naval Research Logistics, 50, 662-682.
  • Allen, L. J. S. (2003).An Introduction to Stochastic Processes with Applicationsto Biology. New Jersey: Prentice Hall.
  • Artalejo, J. R. and Ǵomez-Corral, A. (2008).Retrial Queueing Systems: A Computational Approach. Berlin: Springer-Verlag.
  • Artalejo, J. R. and Ǵomez-Corral, A. (2010). A state-dependent Markov-modulated mechanism for generating events and stochastic models.Mathematical Methods in the Applied Sciences, 33, 1342-1349.
  • Artalejo, J. R. and Li, Q.-L. (2010). Performance analysis of a block-structured discrete-time retrial queue with state-dependent arrivals.Discrete Event Dynamic Systems, 20, 325-347.
  • Asmussen, S. and Koole, G. (1993). Marked point processes aslimits of Markovian arrival streams.Journal of Applied Probability, 30, 365-372.
  • Asmussen, S. and Bladt, M. (1999). Point processes with finite-dimensional conditional probabilities.Stochastic Processes and their Applications, 82, 127-142.
  • Asmussen, S. (2000). Matrix-analytic models and their analysis. Scandinavian Journal of Statistics, 27, 193-226.
  • Asmussen, S. and Møller, J. R. (2001). Calculation of the steady state waiting time distribution inGI/PH/c andMAP/PH/c queues.Queueing Systems, 37, 9-29.
  • Badescu, A. L., Drekic, S. and Landriault, D. (2007). Analysis of a threshold dividend strategy for a MAP risk model.Scandinavian Actuarial Journal, 2007, 227-247.
  • Baek, J. W., Lee, H. W., Lee, S. W. and Ahn, S. (2008). A factorization property forBMAP/G/1 vacation queues under variable service speed.Annals of Operations Research, 160, 19-29.
  • Bini, D. A., Latouche, G. and Meini, B. (2005).Numerical Methods for Structured Markov Chains. Oxford: Oxford University Press.
  • Blondia, C. and Casals, O. (1992). Statistical multiplexing of VBR sources: A matrix-analytic approach. Performance Evaluation, 16, 5-20.
  • Bodrog, L., Horv́ath, A. and Telek, M. (2008). Moment characterization of matrix exponential and Markovian arrival processes.Annals of Operations Research, 160, 51-68.
  • Breuer, L. (2002). An EM algorithm for batch Markovian arrival processes and its comparison to a simpler estimation procedure.Annals of Operations Research, 112, 123-138.
  • Breuer, L. (2003).From Markov Jump Processes to Spatial Queues. Dordrecht: Kluwer Academic Publishers.
  • Breuer, L. and Alfa, A. S. (2005). An EM algorithm for platoonarrival processes in discrete time.Operations Research Letters, 33, 535-543.
  • Breuer, L. and Baum, D. (2005).An Introduction to Queueing Theory and Matrix-Analytic Methods. Dordrecht: Springer.
  • Chakka, R. and Do, T. V. (2007). TheMM ∑Kk=1CPPk/GE/c/L G-queue with heterogenous servers: Steady state solution and an application to performance evaluation. Performance Evaluation, 64, 191-209.
  • Chakravarthy, S. R. (2001). The batch Markovian arrival process: A review and future work. InAdvances in Probability & Stochastic Processes, A. Krishnamoorthy, N. Raju and V. Ramaswami (eds.), Notable Publications, 21-49.
  • Chakravarthy, S. R., Krishnamoorthy, A. and Joshua, V. C. (2006). Analysis of a multi-server retrial queue with search of customers from the orbit.Performance Evaluation, 63, 776-798.
  • Chakravarthy, S. R. and Ǵomez-Corral, A. (2009). The influence of delivery times on repairablek-out-of-N systems with spares.Applied Mathematical Modelling, 33, 2368-2387.
  • Chakravarthy, S. R. (2010). Markovian arrival process. InWiley Encyclopedia of Operations Research and Management Science, J. J. Cochran (ed.), John Wiley and Sons, to appear.
  • Chen, F. and Song, J.-S. (2001). Optimal policies for multiechelon inventory problems with Markov-modulated demand.Operations Research, 49, 226-234.
  • Cheung, E. C. K. and Landriault, D. (2009). Perturbed MAP risk models with dividend barrier strategies. Journal of Applied Probability, 46, 521-541.
  • Ching, W. K. (1997). Markov-modulated Poisson processes for multi-location inventory problems.International Journal of Production Economics, 53, 217-223.
  • Ching, W. K. (2001).Iterative Methods for Queuing and Manufacturing Systems. London: Springer-Verlag.
  • Choi, B. D., Kim, B. and Zhu, D. (2004).MAP/M/c queue with constant impatient time.Mathematics of Operations Research, 29, 309-325.
  • Çinlar, E. (1972a). Markov additive processes. I.Z. Wahrscheinlichkeitstheory verw. Geb., 24, 85-93.
  • Çinlar, E. (1972b). Markov additive processes. II.Z. Wahrscheinlichkeitstheory verw. Geb., 24, 95-121.
  • Cohen, A. M. (2007).Numerical Methods for Laplace Transform Inversion. New York: Springer.
  • Daikoku, K., Masuyama, H., Takine, T. and Takahashi, Y. (2007). Algorithmic computation of the transient queue length distribution in theBMAP/D/c queue.Journal of the Operational Research Society of Japan, 50, 55-72.
  • Darroch, J. N. and Seneta, E. (1967). On quasi-stationary distributions in absorbing continuous-time finite Markov chains.Journal of Applied Probability, 4, 192-196.
  • Dudin, A. N. and Nishimura, S. (1999). ABMAP/SM/1 queueing system with Markovian arrival input of disasters.Journal of Applied Probability, 36, 868-881.
  • Eckberg, A. E. (1983). Generalized peakedness of teletraffic processes. InProceedings of the Tenth International Teletraffic Congress, Montreal, Canada, paper no. 4, 4B3.
  • Frostig, E. and Kenzin, M. (2009). Availability of inspected systems subject to shocks – A matrix algorithmic approach.European Journal of Operational Research, 193, 168-183.
  • He, Q.-M. (1996). Queues with marked customers.Advances in Applied Probability, 28, 567-587.
  • He, Q.-M. and Neuts, M. F. (1998). Markov chains with marked transitions.Stochastic Processes and their Applications, 74, 37-52.
  • He, Q.-M. (2000). Quasi-birth-and-death Markov processeswith a tree structure and theMMAP[K]/PH [K]/N/LCFSnon-preemptive queue.European Journal of Operational Research, 120, 641-656.
  • He, Q.-M. and Alfa, A. S. (2000). Computational analysis ofMMAP[K]/PH[K]/1 queues with a mixed FCFS and LCFS service discipline.Naval Research Logistics, 47, 399-421.
  • He, Q.-M. (2001). The versatility ofMMAP[K] and theMMAP[K]/G[K]/1 queue.Queueing Systems, 38, 397-418.
  • He, Q.-M., Jewkes, E. M. and Buzaccot, J. (2002). Optimal andnear-optimal inventory control policies for a make-to-order inventory-production system.European Journal of Operational Research, 141, 113- 132.
  • He, Q.-M. (2010). Construction of continuous time Markov arrival processes.Journal of Systems Science and Systems Engineering, 19, 351-366.
  • Horváth, A., Horv́ath, G. and Telek, M. (2010). A joint moments based analysis of networks of MAP/ MAP/1 queues.Performance Evaluation, 67, 759-788.
  • Kim, B. and Kim, J. (2010). Queue size distribution in a discrete-time D − BMAP/G/1 retrial queue. Computers & Operations Research, 37, 1220-1227.
  • Kim, C. S., Klimenok, V. I., Mushko, V. and Dudin, A. N. (2010). TheBMAP/PH/N retrial queueing system operating in Markovian random environment.Computers & Operations Research, 37, 1228- 1237.
  • Kulkarni, V. G. (1989). A new class of multivariate phase type distributions.Operations Research, 37, 151- 158.
  • Kulkarni, V. G. (1995).Modelling and Analysis of Stochastic Systems. London: Chapman & Hall.
  • Lambert, J., Van Houdt, B. and Blondia, C. (2006). Queues with correlated service and inter-arrival times and their application to optical buffers.Stochastic Models, 22, 233-251.
  • Latouche, G. and Ramaswami, V. (1999).Introduction to Matrix Analytic Methods in Stochastic Modelling. Philadelphia: ASA-SIAM.
  • Li, Q.-L., Ying, Y. and Zhao, Y. Q. (2006). ABMAP/G/1 retrial queue with a server subject to breakdowns and repairs.Annals of Operations Research, 141, 233-270.
  • Li, Q.-L. (2010).Constructive Computation in Stochastic Models with Applications: The RG-factorizations. Beijing, Berlin Heidelberg: Tsinghua University Press, Springer-Verlag.
  • Lucantoni, D. M., Meier-Hellstern, K. S. and Neuts, M. F. (1990). A single-server queue with server vacations and a class of non-renewal arrival processes.Advances in Applied Probability, 22, 676-705.
  • Lucantoni, D. M. (1991). New results on the single server queue with a batch Markovian arrival process. Stochastic Models, 7, 1-46.
  • Lucantoni, D. M. (1993). TheBMAP/G/1 queue: A tutorial. InPerformance Evaluation of Computer and Communication Systems, L. Donatiello and R. Nelson (eds.), Lecture Notes in Computer Science, Vol. 729, Springer-Verlag, 330-358.
  • Lucantoni, D. M., Choudhury, G. L. and Whitt, W. (1994). The transientBMAP/G/1 queue.Stochastic Models, 10, 145-182.
  • Manuel, P., Sivakumar, B. and Arivarignan, G. (2007). A perishable inventory system with service facilities, MAP arrivals and PH-service times.Journal of Systems Science and Systems Engineering, 16, 62-73.
  • Milne, C. (1982). Transient behaviour of the interrupted Poisson process.Journal of the Royal Statistical Society. Series B, 44, 398-405.
  • Montoro-Cazorla, D. and Ṕerez-Oćon, R. (2006). Reliability of a system under two types of failures using a Markovian arrival process.Operations Research Letters, 34, 525-530.
  • Montoro-Cazorla, D. and Ṕerez-Oćon, R. (2008). A maintenance model with failures and inspection following Markovian arrival processes and two repair modes.European Journal of Operational Research, 186, 694-707.
  • Narayana, S. and Neuts, M. F. (1992). The first two moment matrices of the counts for the Markovian arrival process.Stochastic Models, 8, 459-477.
  • Neuts, M. F. (1979). A versatile Markovian point process.Journal of Applied Probability, 16, 764-779.
  • Neuts, M. F. (1981).Matrix-geometric Solutions in Stochastic Models: An Algorithmic Approach. Baltimore: The Johns Hopkins University Press.
  • Neuts, M. F. (1989).Structured Stochastic Matrices of M/G/1 Type and Their Applications. New York: Marcel Dekker, Inc.
  • Neuts, M. F. (1992). Models based on the Markovian arrival process.IEICE Transactions on Communications, E75-B, 1255-1265.
  • Neuts, M. F., Liu, D. and Narayana, S. (1992). Local poissonification of the Markovian arrival process. Stochastic Models, 8, 87-129.
  • Neuts, M. F. (1993). The burstiness of point processes.Stochastic Models, 9, 445-466.
  • Neuts, M. F. (1995).Algorithmic Probability: A Collection of Problems. London: Chapman & Hall.
  • Neuts, M. F. and Li, J.-M. (1997). An algorithm for theP(n, t) matrices of a continuous BMAP. InMatrixanalytic Methods in Stochastic Models, S.R. Chakravarthy and A.S. Alfa (eds.), Lecture Notes in Pure and Applied Mathematics, Vol. 183, Marcel Dekker, 7-19.
  • Nielsen, B. F., Nilsson, L. A. F., Thygesen, U. H. and Beyer, J. E. (2007). Higher order moments and conditional asymptotics of the batch Markovian arrival process.Stochastic Models, 23, 1-26.
  • Norden, R. H. (1982). On the distribution of the time to extinction in the stochastic logistic population model.Advances in Applied Probability, 14, 687-708.
  • Okamura, H., Dohi, T. and Trivedi, K. S. (2009). Markovian arrival process parameter estimation with group data.IEEE/ACM Transactions on Networking, 17, 1326-1339.
  • Ost, A. (2001).Performance of Communication Systems: A Model-based Approach with Matrix-geometric Methods.Berlin: Springer-Verlag.
  • Pacheco, A. and Prabhu, N. U. (1995). Markov-additive processes of arrivals. InAdvances in Queuing: Theory, Methods and Open Problems, J.H. Dshalalow (ed.), CRC Press, 167-194.
  • Ramaswami, V. (1980). TheN/G/1 queue and its detailed analysis.Advances in Applied Probability, 12, 222-261.
  • Ramaswami, V. (1981). Algorithms for a continuous-review(s,S) inventory system.Journal of Applied Probability, 18, 461-472.
  • Rudemo, M. (1973). Point processes generated by transitions of Markov chains.Advances in Applied Probability, 5, 262-286.
  • Sengupta, B. (1989). Markov processes whose steady state distribution is matrix-exponential with an application to theGI/PH/1 queue.Advances in Applied Probability, 21, 159-180.
  • Shin, Y. W. (2004).BMAP/G/1 queue with correlated arrivals of customers and disasters. Operations Research Letters, 32, 364-373.
  • Squillante, M. S., Zhang, Y., Sivasubramanian, A. and Gautam, N. (2008). Generalized parallel-server forkjoin queues with dynamic task scheduling.Annals of Operations Research, 160, 227-255.
  • Takine, T. and Hasegawa, T. (1994). The workload in theMAP/G/1 queue with state-dependent services: Its applications to a queue with preemptive resume priority. Stochastic Models, 10, 183-204.
  • Takine, T. (1999). The nonpreemptive priorityMAP/G/1 queue.Operations Research, 47, 917-927.
  • Telek, M. and Horv́ath, G. (2007). A minimal representation of Markov arrival processes and a moments matching method.Performance Evaluation, 64, 1153-1168.
  • Tian, N. and Zhang, Z. G. (2006).Vacation Queueing Models: Theory and Applications,International Series in Operations Research & Management, Vol. 93. New York:Springer.
  • Tweedie, R. L. (1982). Operator-geometric stationary distributions for Markov chains, with application to queueing models.Advances in Applied Probability, 14, 368-391.
  • Van Houdt, B. and Blondia, C. (2002). The delay distributionof a typek customer in a first-come-firstservedMMAP[K]/PH[K]/1 queue.Journal of Applied Probability, 39, 213-223.
Fuente de los datos: Dialnet