Markovian arrivals in stochastic modelling: a survey and some new results

• Autores: Jesús Manuel Artalejo Rodríguez, Antonio Gómez-Corral, Qi-Ming He
• Localización: Sort: Statistics and Operations Research Transactions, ISSN 1696-2281, Vol. 34, Nº. 2, 2010, págs. 101-156
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• 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:...
  • Alfa, A. S. and Neuts, M. F. (1995). Modelling vehicular traffic using the discrete time Markovian arrival process.Transportation Science,...
  • Alfa, A. S., Liu, B. and He, Q.-M. (2003). Discrete-time analysis of MAP/PH/1 multiclass general preemptive priority queue.Naval Research...
  • 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...
  • Artalejo, J. R. and Li, Q.-L. (2010). Performance analysis of a block-structured discrete-time retrial queue with state-dependent arrivals.Discrete...
  • 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,...
  • 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,...
  • Badescu, A. L., Drekic, S. and Landriault, D. (2007). Analysis of a threshold dividend strategy for a MAP risk model.Scandinavian Actuarial...
  • 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...
  • 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...
  • Breuer, L. (2002). An EM algorithm for batch Markovian arrival processes and its comparison to a simpler estimation procedure.Annals of Operations...
  • 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...
  • Chakravarthy, S. R. (2001). The batch Markovian arrival process: A review and future work. InAdvances in Probability & Stochastic Processes,...
  • Chakravarthy, S. R., Krishnamoorthy, A. and Joshua, V. C. (2006). Analysis of a multi-server retrial queue with search of customers from the...
  • Chakravarthy, S. R. and Ǵomez-Corral, A. (2009). The influence of delivery times on repairablek-out-of-N systems with spares.Applied Mathematical...
  • Chakravarthy, S. R. (2010). Markovian arrival process. InWiley Encyclopedia of Operations Research and Management Science, J. J. Cochran (ed.),...
  • Chen, F. and Song, J.-S. (2001). Optimal policies for multiechelon inventory problems with Markov-modulated demand.Operations Research, 49,...
  • Cheung, E. C. K. and Landriault, D. (2009). Perturbed MAP risk models with dividend barrier strategies. Journal of Applied Probability, 46,...
  • Ching, W. K. (1997). Markov-modulated Poisson processes for multi-location inventory problems.International Journal of Production Economics,...
  • 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...
  • Darroch, J. N. and Seneta, E. (1967). On quasi-stationary distributions in absorbing continuous-time finite Markov chains.Journal of Applied...
  • Dudin, A. N. and Nishimura, S. (1999). ABMAP/SM/1 queueing system with Markovian arrival input of disasters.Journal of Applied Probability,...
  • Eckberg, A. E. (1983). Generalized peakedness of teletraffic processes. InProceedings of the Tenth International Teletraffic Congress, Montreal,...
  • Frostig, E. and Kenzin, M. (2009). Availability of inspected systems subject to shocks – A matrix algorithmic approach.European Journal of...
  • 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...
  • 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...
  • 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...
  • 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,...
  • Kim, B. and Kim, J. (2010). Queue size distribution in a discrete-time D − BMAP/G/1 retrial queue. Computers & Operations Research, 37,...
  • 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...
  • 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...
  • 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,...
  • Li, Q.-L. (2010).Constructive Computation in Stochastic Models with Applications: The RG-factorizations. Beijing, Berlin Heidelberg: Tsinghua...
  • 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...
  • 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...
  • 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...
  • 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...
  • Montoro-Cazorla, D. and Ṕerez-Oćon, R. (2008). A maintenance model with failures and inspection following Markovian arrival processes...
  • Narayana, S. and Neuts, M. F. (1992). The first two moment matrices of the counts for the Markovian arrival process.Stochastic Models, 8,...
  • 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,...
  • Nielsen, B. F., Nilsson, L. A. F., Thygesen, U. H. and Beyer, J. E. (2007). Higher order moments and conditional asymptotics of the batch...
  • Norden, R. H. (1982). On the distribution of the time to extinction in the stochastic logistic population model.Advances in Applied Probability,...
  • Okamura, H., Dohi, T. and Trivedi, K. S. (2009). Markovian arrival process parameter estimation with group data.IEEE/ACM Transactions on Networking,...
  • 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....
  • 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...
  • 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...
  • Takine, T. and Hasegawa, T. (1994). The workload in theMAP/G/1 queue with state-dependent services: Its applications to a queue with preemptive...
  • 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,...
  • Tian, N. and Zhang, Z. G. (2006).Vacation Queueing Models: Theory and Applications,International Series in Operations Research & Management,...
  • Tweedie, R. L. (1982). Operator-geometric stationary distributions for Markov chains, with application to queueing models.Advances in Applied...
  • 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...