Publication
Title
A matrix geometric representation for the queue length distribution of multitype semi-Markovian queues
Author
Abstract
In this paper we study a broad class of semi-Markovian queues introduced by Sengupta. This class contains many classical queues such as the GI/M/1 queue, SM/MAP/1 queue and others, as well as queues with correlated inter-arrival and service times. Queues belonging to this class are characterized by a set of matrices of size m and Sengupta showed that its waiting time distribution can be represented as a phase-type distribution of order m. For the special case of the SM/MAP/1 queue without correlated service and inter-arrival times the queue length distribution was also shown to be phase-type of order m, but no derivation for the queue length was provided in the general case. This paper introduces an order m(2) phase-type representation (K, K) for the queue length distribution in the general case and proves that the order m(2) of the distribution cannot be further reduced in general. A matrix geometric representation (kappa, K, nu) is also established for the number of type tau subset of (1, . . . , m) customers in the system, where a customer is of type tau if the phase in which it completes service belongs to tau. We derive these results in both discrete and continuous time and also discuss the numerical procedure to compute (kappa, K, nu). When the arrivals have a Markovian structure, the numerical procedure is reduced to solving a Quasi-Birth-Death (for the discrete time case) or fluid queue (for the continuous time case). Finally, by combining a result of Sengupta and Ozawa, we provide a simple formula to compute the order m phase-type representation of the waiting time in a MAP/MAP/1 queue without correlated service and inter-arrival times, using the R matrix of a Quasi-Birth-Death Markov chain. (C) 2012 Elsevier B.V. All rights reserved.
Language
English
Source (journal)
Performance evaluation. - Amsterdam
Publication
Amsterdam : 2012
ISSN
0166-5316
Volume/pages
69:7-8(2012), p. 299-314
ISI
000308059000002
Full text (Publisher's DOI)
Full text (publisher's version - intranet only)
UAntwerpen
Faculty/Department
Research group
Publication type
Subject
Affiliation
Publications with a UAntwerp address
External links
Web of Science
Record
Identification
Creation 22.11.2012
Last edited 07.09.2017
To cite this reference