×

Analysis of a continuous time SM[K]/PH[K]/1/FCFS queue: age process, sojourn times, and queue lengths. (English) Zbl 1259.90022

Summary: This paper studies a continuous time queueing system with multiple types of customers and a first-come-first-served service discipline. Customers arrive according to a semi-Markov arrival process and the service times of individual types of customers have PH-distributions. A \(GI/M/1\) type Markov process for a generalized age process of batches of customers is constructed. The stationary distribution of the \(GI/M/1\) type Markov process is found explicitly and, consequently, the distributions of the age of the batch in service, the total workload in the system, waiting times, and sojourn times of different batches and different types of customers are obtained. The paper gives the matrix representations of the PH-distributions of waiting times and sojourn times. Some results are obtained for the distributions of queue lengths at departure epochs and at an arbitrary time. These results can be used to analyze not only the queue length, but also the composition of the queue. Computational methods are developed for calculating steady state distributions related to the queue lengths, sojourn times, and waiting times.

MSC:

90B22 Queues and service in operations research

Software:

Q-MAM
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] E. Cinlar, Queues with semi-Markov arrivals, J. Appl. Prob., 1967, 4: 365–379. · Zbl 0153.20001 · doi:10.2307/3212030
[2] J. W. Cohen, The Single Server Queue, North-Holland, Amsterdam, 1982. · Zbl 0481.60003
[3] Q. M. He, Queues with marked customers, Adv. Appl. Prob., 1996, 28: 567–587. · Zbl 0861.60089 · doi:10.2307/1428072
[4] Q. M. He, The versatility of MMAP[K]_and the MMAP[K]/G[K]/1 queue, Queueing Systems, 2001, 38(4): 397–418. · Zbl 0982.60094 · doi:10.1023/A:1010995827792
[5] G. Latouche and V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modelling, ASA & SIAM, Philadelphia, 1999. · Zbl 0922.60001
[6] D. M. Lucantoni, K. S. Meier-Hellstern, and M. F. Neuts, A single server queue with server vacations and a class of non-renewal arrival processes, Adv. Appl. Prob., 1990, 22: 676–705. · Zbl 0709.60094 · doi:10.2307/1427464
[7] M. F. Neuts, Matrix-Geometric Solutions in Stochastic Models: An algorithmic Approach, The Johns Hopkins University Press, Baltimore, 1981. · Zbl 0469.60002
[8] M. F. Neuts, Generalizations of the Pollaczek-Khinchin integral method in the theory of queues, Adv. Appl. Prob., 1986, 18: 952–990. · Zbl 0634.60087 · doi:10.2307/1427258
[9] M. F. Neuts, Structured Stochastic Matrices of M/G/ 1 type and Their Applications, MarcelDekker, New York, 1989.
[10] V. Ramaswami, The N/G/1 queue and its detailed analysis, Adv. Appl. Prob., 1980, 12: 222–261. · Zbl 0424.60093 · doi:10.2307/1426503
[11] T. Takine, Queue length distribution in an FIFO single-server queue with multiple arrival streams having different service time distributions, Queueing System, 2001a, 39: 349–375. · Zbl 0994.60091 · doi:10.1023/A:1013961710829
[12] T. Takine, A recent progress in algorithmic analysis of FIFO queues with Markovian arrival streams, J. Korean Math. Soc., 2001b, 38(4): 807–842. · Zbl 0983.60088
[13] T. Takine and T. Hasegawa, The workload in an MAP/G/1 queue with state-dependent services: Its applications to a queue with preemptive resume priority, Stochastic Models, 1994, 10(1): 183–204. · Zbl 0791.60088 · doi:10.1080/15326349408807292
[14] S. Asmussen, Phase-type representation in random walk and queueing problems, Annals of Probability, 1992, 20(2): 772–789. · Zbl 0755.60049 · doi:10.1214/aop/1176989805
[15] S. Asmussen and C. O’Cinneide, Representation for matrix-geometric and matrix-exponential steady-state distributions with applications to many-server queues, Stochastic Models, 1998, 14: 369–387. · Zbl 0934.60082 · doi:10.1080/15326349808807477
[16] B. Sengupta, Markov processes whose steady state distribution is matrix-exponential with an application to the GI /PH/1 queue, Adv. Appl. Prob., 1989, 21: 159–180. · Zbl 0672.60090 · doi:10.2307/1427202
[17] B. Sengupta, Phase-type representations for matrix-geometric solutions, Stochastic Models, 1990a, 6: 163–167. · Zbl 0701.60066 · doi:10.1080/15326349908807142
[18] B. Sengupta, The semi-Markovian queue: Theory and applications, Stochastic Models, 1990b, 6: 383–413. · Zbl 0699.60090 · doi:10.1080/15326349908807154
[19] Q. M. He,Workload process, waiting times, and sojourn times in a discrete time MMAP[K]/SM[K]/1/FCFS queue, Stochastic Models, 2004, 20(4): 415–437. · Zbl 1060.60088 · doi:10.1081/STM-200033099
[20] Q. M. He, Age process, total workload, sojourn times, and waiting times in a discrete time SM[K]/PH[K]/1/FCFS queue, Queueing Systems, 2005, 49: 363–403. · Zbl 1080.90028 · doi:10.1007/s11134-005-6972-y
[21] B. Van Houdt and C. Blondia, The delay distribution of a type k customer in an FCFS MMAP[K]/PH[K]/1 queue, Journal of Applied Probability, 2002a, 39(1): 213–222. · Zbl 1006.60092 · doi:10.1239/jap/1019737998
[22] B. Van Houdt and C. Blondia, The waiting time distribution of a type k customer in a discrete-time FCFS MMAP[K]/PH[K]/c (c=1,2) queue using QBDs, Stochastic Models, 2002b, 20(1): 55–69. · Zbl 1054.60098
[23] J. Lambert, B. Van Houdt, and C. Blondia, Queues in DOCSIS cable modem networks, Computer and Operations Research, 2008, 35(8): 2482–2496. · Zbl 1179.90080 · doi:10.1016/j.cor.2006.12.004
[24] S. Asmussen and G. Koole, Marked point processes as limits of Markovian arrival streams, J. Appl. Probab., 1993, 30: 365-372. · Zbl 0778.60035
[25] E. Cinlar, Markov renewal theory, Adv. Appl. Prob., 1969, 1: 123–187. · Zbl 0212.49601 · doi:10.2307/1426216
[26] Q. M. He and M. F. Neuts, Markov chains with marked transitions, Stochastic Processes and Their Applications, 1998, 74(1): 37–52. · Zbl 0932.60078 · doi:10.1016/S0304-4149(97)00109-9
[27] R. M. Loynes, The stability of a queue with non-independent interarrival and service times, Proc. Cambridge Philos. Soc., 1962, 58: 497–520. · Zbl 0203.22303 · doi:10.1017/S0305004100036781
[28] F. R. Gantmacher, The Theory of Matrices, Chelsea, New York, 1959. · Zbl 0085.01001
[29] H. Marcus and H. Minc, A Survey of Matrix Theory and Matrix Inequalities, Allyn and Bacon, Inc., Boston, 1964. · Zbl 0126.02404
[30] J. F. Perez, J. Van Velthoven, and B. Van Houdt, Q-MAM: A tool for solving infinite queues using matrix-analytic methods, Proceedings of SMCtools’08, ACM Press, Athens (Greece), 2008.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.