Prediction in Markovian bulk arrival queues

This paper deals with the statistical analysis of bulk arrival queues from a Bayesian point of view. The focus is on prediction of the usual measures of performance of the system in equilibrium. Posterior predictive distribution of the number of customers in the system is obtained through its probability generating function. Posterior distribution of the waiting time, in the queue and in the system, of the first customer of an arriving group is expressed in terms of their Laplace and Laplace–Stieltjes transform. Discussion of numerical inversion of these transforms is addressed.     

Inference and prediction in bulk arrival queues and queues with service in stages

This paper deals with the statistical analysis from a Bayesian point of view, of bulk arrival queues where the batch size is considered as a fixed constant. The focus is on prediction of the usual measures of performance of the system in the steady state. The probability generating function of the posterior predictive distribution of the number of customers in the system and the Laplace transform of the posterior predictive distribution of the waiting time in the system are obtained. Numerical inversion of these transforms is considered. Inference and prediction of its equivalent single queue with service in stages is also discussed. © 1998 John Wiley & Sons, Ltd.     

On a bulk arrival bulk service infinite service queue

This paper considers an infinite server queue in continuous time in which arrivals are in batches of variable size X and service is provided in groups of fixed size R. We obtain analytical results for the number of busy servers and waiting customers at arbitrary time points. For the number of busy servers, we obtain a recursive relation for the partial binomial moments both in transient and steady states. Special cases are also discussed     

On finite capacity queues with time dependent arrival rates

We consider the finite capacity M/M/1−K$M/M/1-K$ queue with a time dependent arrival rate λ(t)$\lambda \left(t\right)$. Assuming that the capacity K$K$ is large and that the arrival rate varies slowly with time (as t/K$t/K$), we construct asymptotic approximations to the probability of finding n$n$ customers in the system at time t$t$, as well as the mean number. We consider various time ranges, where the system is nearly empty, nearly full, or is filled to a fraction of its capacity. Extensive numerical studies are used to back up the asymptotic analysis.     

Stochastic comparisons for bulk queues

We consider two important classes of single-server bulk queueing models: M^(X)/G^(Y)/1 with Poisson arrivals of customer groups, and G^(X)/m^(Y)1 with batch service times having exponential density. In each class we compare two systems and prove that one is more congested than the other if their basic random variables are stochastically ordered in an appropriate manner. However, it must be recognized that a system that appears congested to customers might be working efficiently from the system manager's point of view. We apply the results of this comparison to (i) the family {M/G^(s)/1,s 1} of systems with Poisson input of customers and batch service times with varying service capacity; (ii) the family {G^(s)/1,s 1} of systems with exponential customer service time density and group arrivals with varying group size; and (iii) the family {M/D/s,s 1} of systems with Poisson arrivals, constant service time and varying number of servers. Within each family, we find the system that is the best for customers, but this turns out to be the worst for the manager (or vice versa). We also establish upper (or lower) bounds for the expected queue length in steady state and the expected number of batches (or groups) served during a busy period. The approach of the paper is based on the stochastic comparison of random walks underlying the models.This research was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.     

Improved bounds for queues with delayed arrivals

Improved bounds are developed for a queue where arrivals are delayed by a fixed time. For moderate to heavy traffic, a simple improved upper bound is obtained which only uses the first two moments of the service time distribution. We show that our approach can be extended to obtain bounds for other types of delayed arrival queues. For very light traffic, asymptotically tight bounds can be obtained using more information about the service time distribution. While an improved upper bound can be obtained for light to moderate traffic it is not particularly easy to apply. This revised version was published online in June 2006 with corrections to the Cover Date.     

Exponential bounds for queues with Markovian arrivals

Exponential bounds [queueb]e ^b are found for queues whose increments are described by Markov Additive Processes. This is done by application of maximal inequalities to exponential martingales for such processes. Through a thermodynamic approach the constant is shown to be the decay rate for an asymptotic lower bound for the queue length distribution. The class of arrival processes considered includes a wide variety of Markovian multiplexer models, and a general treatment of these is given, along with that of Markov modulated arrivals. Particular attention is paid to the calculation of the prefactor .     

Autocorrelations in infinite server batch arrival queues

This paper studies an important aspect of queueing theory, autocorrelation properties of system processes. A general infinite server queue with batch arrivals is considered. There areM different types of customers and their arrivals are regulated by a Markov renewal input process. Batch sizes and service times depend on the relevant customer types. With a conditional approach, closed form expressions are obtained for the autocovariance of the continuous time and prearrival system sizes. Some special models are also discussed, giving insights into steady state system behaviour. Autocorrelation functions have a wide range of applications. We highlight one area of application by using autocovariances to derive variances of sample means for a number of special models.This work has been supported by the Natural Sciences and Engineering Council of Canada through Grant A5639 and by the National Natural Science Foundation of China through Grant 19001015.     

Heavy traffic limits for queues with non-stationary path-dependent arrival processes

Queueing Systems - In this paper, we develop a diffusion approximation for the transient distribution of the workload process in a standard single-server queue with a non-stationary Polya arrival...     

Batch arrival queues with vacations and server setup

We study a single server queueing system whose arrival stream is compound Poisson and service times are generally distributed. Three types of idle period are considered: threshold, multiple vacations, and single vacation. For each model, we assume after the idle period, the server needs a random amount of setup time before serving. We obtain the steady-state distributions of system size and waiting time and expected values of the cycle for each model. We also show that the distributions of system size and waiting time of each model are decomposed into two parts, whose interpretations are provided. As for the threshold model, we propose a method to find the optimal value of threshold to minimize the total expected operating cost.     

Tandem queues in bulk port operations

The study is motivated by the operations at the bulk material handling port of Kamsar in Guinea. Bauxite ore is brought to port to load vessels that arrive on a semischeduled basis. Vessels go through several stages of delays due to sailing, tide and due to time in a waiting berth before and after they are loaded. We propose bounds and an approximation for a modified port time which is a significant measure of performance in bulkmaterial port operations.     

Monotonicity and error bounds for networks of Erlang loss queues

Networks of Erlang loss queues naturally arise when modelling finite communication systems without delays, among which, most notably are

1. classical circuit switch telephone networks (loss networks) and
2. present-day wireless mobile networks.

Performance measures of interest such as loss probabilities or throughputs can be obtained from the steady state distribution. However, while this steady state distribution has a closed product form expression in the first case (loss networks), it does not have one in the second case due to blocked (and lost) handovers. Product form approximations are therefore suggested. These approximations are obtained by a combined modification of both the state space (by a hypercubic expansion) and the transition rates (by extra redial rates). It will be shown that these product form approximations lead to

• upper bounds for loss probabilities and
• analytic error bounds for the accuracy of the approximation for various performance measures.

The proofs of these results rely upon both monotonicity results and an analytic error bound method as based on Markov reward theory. This combination and its technicalities are of interest by themselves. The technical conditions are worked out and verified for two specific applications:

• pure loss networks as under (i)
• GSM networks with fixed channel allocation as under (ii).

The results are of practical interest for computational simplifications and, particularly, to guarantee that blocking probabilities do not exceed a given threshold such as for network dimensioning.     

Perturbation bounds and truncations for a class of Markovian queues

We consider time-inhomogeneous Markovian queueing models with batch arrivals and group services. We study the mathematical expectation of the respective queue-length process and obtain the bounds on the rate of convergence and error of truncation of the process. Specific queueing models are shown as examples.     

Simple bounds and monotonicity results for finite multi-server exponential tandem queues

Simple and computationally attractive lower and upper bounds are presented for the call congestion such as those representing multi-server loss or delay stations. Numerical computations indicate a potential usefulness of the bounds for quick engineering purposes. The bounds correspond to product-form modifications and are intuitively appealing. A formal proof of the bounds and related monotonicity results will be presented. The technique of this proof, which is based on Markov reward theory, is of interest in itself and seems promising for further application. The extension to the non-exponential case is discussed. For multiserver loss stations the bounds are argued to be insensitive.     

An algorithm proposed for busy-period subcomponent analysis of bulk queues

This paper presents an algorithmic procedure for a busy-period subcomponent analysis of bulk queues. A component of interest for many server queues is the periodt _k to reduce congestion from a levelk to levelk-1. For anM ^(x)/M/c system with the possibility of total or partial rejection of batches, it is demonstrated that the expected length of busy periods, the proportion of delayed batch and the steady state queue length probabilities can be easily obtained. The procedure is based on the nested partial sums and monotonic properties of expected lengths of the busy periods.Formerly University of Ife.     

Interconnected networks of queues with randomized arrival and departure blocking

In this paper, we study two interconnected multiclass non-exponential queueing networks. Jobs can jump from one cluster to another, but subject to randomized blocking depending on the class occupancies. Such systems naturally arise in communication networks, like Metropolitan Area Networks. We present sufficient conditions for the existence of a product form equilibrium distribution under both the recirculate and the stop blocking protocol. A number of examples are given.     

Optimal arrival rate and service rate control of multi-server queues

We consider the problem of optimal control of a multi-server queue with controllable arrival and service rates. This study is motivated by its potential application to the design and control of data centers. The cost structure includes customer holding cost which is a non-decreasing convex function of the number of customers in the system, server operating cost which is a non-decreasing convex function of the chosen service rate, and system operating reward which is a non-decreasing concave function of the chosen arrival rate. We formulate the problem as a continuous-time Markov decision process and derive structural properties of the optimal control policies under both discounted cost and average cost criterions.