Title
A matrix geometric representation for the queue length distribution of multitype semi-Markovian queues
Author
Faculty/Department
Faculty of Sciences. Mathematics and Computer Science
Publication type
article
Publication
Amsterdam ,
Subject
Computer. Automation
Source (journal)
Performance evaluation. - Amsterdam
Volume/pages
69(2012) :7-8 , p. 299-314
ISSN
0166-5316
ISI
000308059000002
Carrier
E
Target language
English (eng)
Full text (Publishers DOI)
Affiliation
University of Antwerp
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.
E-info
https://repository.uantwerpen.be/docman/iruaauth/72dfa9/edf3452.pdf
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000308059000002&DestLinkType=RelatedRecords&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
http://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcApp=PARTNER_APP&SrcAuth=LinksAMR&KeyUT=WOS:000308059000002&DestLinkType=FullRecord&DestApp=ALL_WOS&UsrCustomerID=ef845e08c439e550330acc77c7d2d848
Handle