A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

An Arrival Time Approach to M/G/1-type Queues with Generalized Vacations

We propose a simple way, called the arrival time approach, of finding the queue length distributions for M/G/1-type queues with generalized server vacations. The proposed approach serves as a useful alternative to understanding complicated queueing processes such as priority queues with server vacations and MAP/G/1 queues with server vacations.     

A mean value formula for the M/G/1 queues controlled by workload

We present a mean value formula for the M/G/1 queues controlled by workload (such as the D-policy queues). We first prove the formula and then demonstrate its application. This formula also works for the conventional vacation systems which are controlled by number of customers (such as the N-policy queues).     

Optimal incentive-compatible pricing for M/G/1 queues

This paper extends the applicability of the pricing results of Mendelson and Whang (Oper. Res. 38 (5) (1990) 870) and Balachandran and Radhakrishnan (Management Sci. 40 (10) (1994) 353) for congested service facilities by considering general, class-dependent, service time distributions. Two theorems for nonpreemptive M/G/1 queues and preemptive-resume M/G/1 queues are presented.     

THE TRANSIENT SOLUTION FOR M/G/1 QUEUEWITH SERVER VACATIONS

1IntroductionDuringrecentseveraldecadesqueueingmodelswitllservervacationshavebeenstudiedin'anumberofpapers(seethecitedreferences).Inthesepaperstwoofthemostremarkableresultsconcernsthestochasticdecompositionpropertiesofqueuelengthandwaitingtimeatarandompointinequilibrium.Butthetransientpropertyoftilequeuelengthforanyqueueingsystemwithservervacationsisnotdiscussedyet.InthispaperwefirstlystlldytheproblemforM/G/1queuewithservervacations.Andthequeueingmodelsconsideredarethefollowing.Model1Conside…     

Computation of the quasi-stationary distributions inM(n)/GI/1/K andGI/M(n)/1/K queues

In this paper, we provide numerical means to compute the quasi-stationary (QS) distributions inM/GI/1/K queues with state-dependent arrivals andGI/M/1/K queues with state-dependent services. These queues are described as finite quasi-birth-death processes by approximating the general distributions in terms of phase-type distributions. Then, we reduce the problem of obtaining the QS distribution to determining the Perron-Frobenius eigenvalue of some Hessenberg matrix. Based on these arguments, we develop a numerical algorithm to compute the QS distributions. The doubly-limiting conditional distribution is also obtained by following this approach. Since the results obtained are free of phase-type representations, they are applicable for general distributions. Finally, numerical examples are given to demonstrate the power of our method.     

Strategic behavior and optimization in a hybrid M/M/1 queue with retrials

Queueing Systems - In standard queues, when there are waiting customers, service completions are followed by service commencements. In retrial queues, this is not the case. In such systems,...     

M/M/1 Queue with Impatient Customers of Higher Priority

We introduce a simple approach for the analysis of the M/M/c queues with a single class of customers and constant impatience time by finding simple Markov processes (see (2.1) and (2.15) below), and then by applying this approach we analyze the M/M/1 queues with two classes of customers in which class 1 customers have impatience of constant duration, and class 2 customers have no impatience and lower priority than class 1 customers.     

On the complete monotonicity of the waiting time density in some GI/G/k systems

In this note the complete monotonicity of the waiting time density in GI/G/k queues is proved under the assumption that the service time density is completely monotone. This is an extension of Keilson's [3] result for M/G/1 queues. We also provide another proof of the result that complete monotonicity is preserved by geometric compounding.     

Tables of Waiting Times for <Emphasis Type="Italic">M/M/n</Emphasis>, <Emphasis Type="Italic">M/D/n</Emphasis> and <Emphasis Type="Italic">D/M/n</Emphasis> and their Use to Give Approximate Waiting Times in More General Queues

An approximation formula for average waiting time in multiserver queues is considered using tables for the queues M/M/n, M/D/n and D/M/n. The approximation is compared with that proposed by Sakasegawa. Both approximations predominantly overestimate the waiting time, the first being more accurate, but the Sakasegawa approximation is simpler to apply.     

M/G/1/MLPS compared to M/G/1/PS

Multilevel processor sharing scheduling disciplines have recently been resurrected in papers that focus on the differentiation between short and long TCP flows in the Internet. We prove that, for M/G/1 queues, such disciplines are better than the processor sharing discipline with respect to the mean delay whenever the hazard rate of the service time distribution is decreasing.     

Empirical Bayesian analysis for traffic intensity:M/M/1 queues with covariates

In this paper, we consider a set of individualM/M/1 queues in which variations in both arrival rates and service rates are partly explained by some covariates representing associated characteristics of individual queues. The random error that takes into account the remaining variation is assumed to follow a gamma distribution. Bayes and empirical Bayes procedures are suggested to make inferences concerning individual traffic intensity parameters that can be applied to several industrial queueing problems.     

On the distribution of the number stranded in bulk-arrival, bulk-service queues of the M/G/1 form

Bulk-arrival queues with single servers that provide bulk service are widespread in the real world, e.g., elevators in buildings, people-movers in amusement parks, air-cargo delivery planes, and automated guided vehicles. Much of the literature on this topic focusses on the development of the theory for waiting time and number in such queues. We develop the theory for the number stranded, i.e., the number of customers left behind after each service, in queues of the M/G/1 form, where there is single server, the arrival process is Poisson, the service is of a bulk nature, and the service time is a random variable. For the homogenous Poisson case, in our model the service time can have any given distribution. For the non-homogenous Poisson arrivals, due to a technicality, we assume that the service time is a discrete random variable. Our analysis is not only useful for performance analysis of bulk queues but also in designing server capacity when the aim is to reduce the frequency of stranding. Past attempts in the literature to study this problem have been hindered by the use of Laplace transforms, which pose severe numerical difficulties. Our approach is based on using a discrete-time Markov chain, which bypasses the need for Laplace transforms and is numerically tractable. We perform an extensive numerical analysis of our models to demonstrate their usefulness. To the best of our knowledge, this is the first attempt in the literature to study this problem in a comprehensive manner providing numerical solutions.     

Numerical analysis for bulk-arrival queueing systems: Root-finding and steady-state probabilities inGI r /M/1 queues

Queueing theorists have presented, as solutions to many queueing models, probability generating functions in which state probabilities are expressed as functions of the roots of characteristic equations, evaluation of the roots in particular cases being left to the reader. Many users have complained that such solutions are inadequate. Some queueing theorists, in particular Neuts [6], rather than use Rouché's theorem to count roots and an equation-solver to find them, have developed new algorithms to solve queueing problems numerically, without explicit calculation of roots. Powell [7] has shown that in many bulk service queues arising in transportation models, characteristic equations can be solved and state probabilities can be found without serious difficulty, even when the number of roots to be found is large. We have slightly modified Powell's method, and have extended his work to cover a number of bulk-service queues discussed by Chaudhry et al. [1] and a number of bulk-arrival queues discussed in the present paper.     

Approximation of M/M/c retrial queue with PH-retrial times

We consider the M/M/c retrial queues with PH-retrial times. Approximation formulae for the distribution of the number of customers in service facility and the mean number of customers in orbit are presented. Some numerical results are presented.     

Fast simulation of buffer overflows in tandem networks ofGI/GI/1 queues

Simply because of their rarity, the estimation of the statistics of buffer overflows in well-dimensioned queueing networks via direct simulation is extremely costly. One technique that can be used to reduce this cost is importance sampling, and it has been shown previously that large deviations theory can be used in conjunction with importance sampling to minimize the required simulation time. In this paper, we obtain results on the fast simulation of tandem networks of queues, and derive an analytic solution to the problem of finding an optimal simulation system for a class of tandem networks ofGI/GI/1 queues.Work supported by Australian Telecommunications and Electronics Research Board (ATERB). The authors wish to acknowledge the funding of the activities of the Cooperative Research Centre for Robust and Adaptive Systems by the Australian Commonwealth Government under the Cooperative Research Centres Program.     

Computational analysis of steady-state probabilities of M/Ga,b/1 and related nonbulk queues

In their book, Chaudhry and Templeton [6] present a unified approach to many problems on bulk queues. Using their analytical approach, we show how to numerically evaluate steady-state probabilities and moments for number in system (or queue) at each of three time epochs — postdeparture, prearrival and random — for several bulk and nonbulk queues. The approach can be used for other problems in queueing theory, and for similar problems in the theories of dams, inventories, etc. The present study extends the computational results available in tables, such as those produced by Hillier and Yu [12], and has several potential applications. The method proposed is computationally efficient, accurate, and stable. It accommodates high values of the queueing parameters. Sample numerical results and graphs are also presented.     

Using state reduction for computing steady state vectors in Markov chains ofM/G/1 type

This paper presents a state reduction based algorithm for computing the steady state probability vectors of the embedded Markov chains ofM/G/1 type. The algorithm is based on the use of the notion of a state reduction box for streamlining compution. The computational details are linked directly to the theoretical results developed recently by Grassmann and Heyman [6]. Exploiting these connections and a method given in Neuts [18] for finding theG matrix forPH/PH/1 queues, we also propose an hybrid approach for solvingPH/PH/1 queues. Using several numerical examples, we report our computational experiences and present some observations about the relative merits of these approaches.     

Probabilistic proof of the interchangeability of ./M/1 queues in series

Given a finite number of empty ./M/1 queues, let customers arrive according to an arbitrary arrival process and be served at each queue exactly once, in some fixed order. The process of departing customers from the network has the same law, whatever the order in which the queues are visited. This remarkable result, due to R. Weber [4], is given a simple probabilistic proof.     

Quasi-reversible multiclass queues with order independent departure rates

This paper introduces a new class of queues which are quasi-reversible and therefore preserve product form distribution when connected in multinode networks. The essential feature leading to the quasi-reversibility of these queues is the fact that the total departure rate in any queue state is independent of the order of the customers in the queue. We call such queues order independent (OI) queues. The OI class includes a significant part of Kelly's class of symmetric queues, although it does not cover the whole class. A distinguishing feature of the OI class is that, among others, it includes the MSCCC and MSHCC queues but not the LCFS queue. This demonstrates a certain generality of the class of OI queues and shows that the quasi-reversibility of the OI queues derives from causes other than symmetry principles. Finally, we examine OI queues where arrivals to the queue are lost when the number of customers in the queue equals an upper bound. We obtain the stationary distribution for the OI loss queue by normalizing the stationary probabilities of the corresponding OI queue without losses. A teletraffic application for the OI loss queue is presented.