Matrix-analytic methods in queuing theory

This review describes the development during the past decade of a number of matrix-analytic methods for the study of a variety of stochastic models, primarily queues but also certain models for dams and inventories. This work originated in the search for algorithmic methods and has led to results that are well-suited for computer implementation. It has also required a reexamination of the theoretical approaches to these stochastic models, which may now be analyzed by purely probabilistic methods rather than by techniques from complex analysis.The author also argues the case for an algorithmic optic on the problems of applied probability and sketches the main steps in the construction of computer codes for the evaluation of stationary distributions of interest. The approach is built on certain nonlinear matrix equations that arise naturally in the study of structured Markov chains which are generalizations of the chains embedded in the classical GI/M/1 and M/G/1 queues.     

On simulating arbitrary events

In simulation studies, the distributional properties of random variables associated witharbitrary events in point processes, queues, and other stochastic models are to be understood as appropriate averages over long simulation runs. We caution against trying to generate arbitrary events explicitly by some randomized selection. Because of the likelihood of hidden selection biases, that easily results in significant errors. The point is illustrated by an example for which explicit formulas yield computational results that allow comparisons with the simulation estimates. This work was supported by the Australian Research Council and was done at the ARC Special Research Centre for Ultra-Broadband Information Networks (CUBIN), Department of Electrical and Electronic Engineering, The University of Melbourne, Victoria 3010, Australia. The research of M.F. Neuts was supported in part by NSF Grant Nr. DMI-9988749.     

A single server queue with platooned arrivals and phase type services

A semi-Markovian point process which qualitatively models platooned arrivals is introduced. This process is used as the input to a single server queue in which the service times are independent and have a common distribution of phase type.It is shown that this queue has an embedded Markov chain of a particular block-partitioned type, whose invariant probability vector in the stable case is of matrix-geometric form. Detailed algorithms for the computation of the steady-state features of the queue are obtained and a representative numerical example is discussed.     

Numerical investigation of a multiserver retrial model

We consider a queueing model in which customers arrive in a Poisson stream to be served by one ofc servers. Each arriving customer enters a pool of active customers and starts generating requests for service at exponentially distributed time intervals at rate until he finds a free server and begins service. An analytical solution of this model is difficult and does not lend itself to numerical implementation. In this paper, we make a simplifying approximation, based on understanding of the physical behavior of the system, which yields an infinitesimal generator with a modified matrix-geometric equilibrium probability vector. That vector can be very efficiently computed even for high congestion levels. Illustrative numerical examples demonstrate the effectiveness of the approximation as well as the effect of the retrial rate on the system behavior for various levels of congestion. This study shows how numerical results for analytically intractable systems can be obtained by combining intuition with efficient algorithmic methods.This author's research was supported in part by Grants Nos. ECS-88-03061 from the National Science Foundation and AFOSR-88-0076 from the Air Force Office of Scientific Research.     

An annoted bibliography on computational probability: Part 1

This is the first part of a bibliography on computational probability. It lists over five hundred reference to published papers, technical reports and theses, which deal with algorithmic solutions to probability problems or which contain useful information on the computational aspects of such problems.     

Statistical group testing with queueing involved

We consider a queueing model in which items wait to undergo group testing in batches of sizem. However, if fewer thanm items are present at the beginning of a service, items are tested singly. Ifm or more items are waiting at such an epoch, a group of sizem is tested and, if the group passes the test, allm items leave the system. When a group is found to contain at least one defective item, them items in it are retested individually. An algorithm is developed to compute many steady-state probabilities related to this queue. Comparisons of these probabilities are used to assess the effect of the group sizem on the behavior of the queue of items waiting for testing.This research was supported in part by Grant Nr. ECS-8601203 from the National Science Foundation.     

Convexity of the bounds induced by Markov's inequality

X is a nonnegative random variable such that EX^t < ∞ for 0≤ t < λ ≤ ∞. The (l??) quantile of the distribution of X is bounded above by [?^?1 EX^t]^1?t. We show that there exist positive ?₁ ≥ ?₂ such that for all 0 <?≤?₁ the function g(t) = [?^-1EX^t]^1?t is log-convex in [0, c] and such that for all 0 < ? ≤ ?₂ the function log g(t) is nonincreasing in [0, c].     

Asymptotic behavior of the stationary distributions in the GI/PH/c queue with heterogeneous servers

Summary This paper deals with the stablec-server queue with renewal input. The service time distributions may be different for the various servers. They are however all probability distributions of phase type. It is shown that the stationary distribution of the queue length at arrivals has an exact geometric tail of rate , 0<<1. It is further shown that the stationary waiting time distribution at arrivals has an exact exponential tail of decay parameter >0. The quantities and may be evaluated together by an elementary algorithm. For both distributions, the multiplicative constants which arise in the asymptotic forms may be fully characterized. These constants are however difficult to compute in general.This research was supported by the National Science Foundation under Grant Nr. ENG-7908351 and by the Air Force Office of Scientific Research under Grant Nr. AFOSR-77-3236.