Tandem Brownian queues

We analyze a two-node tandem queue with Brownian input. We first derive an explicit expression for the joint distribution function of the workloads of the first and second queue, which also allows us to calculate their exact large-buffer asymptotics. The nature of these asymptotics depends on the model parameters, i.e., there are different regimes. By using sample-path large-deviations (Schilder’s theorem) these regimes can be interpreted: we explicitly characterize the most likely way the buffers fill. This research has been funded by the Dutch BSIK/BRICKS (Basic Research in Informatics for Creating the Knowledge Society) project. M. Mandjes is also affiliated with the Korteweg-de Vries Institute, University of Amsterdam, The Netherlands, and EURANDOM, Eindhoven, The Netherlands.     

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.     

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.     

Tandem queues with deterministic service times

In this paper we consider a tandem queueing model for a sequence of multiplexers at the edge of an ATM network. All queues of the tandem queueing model have unit service times. Each successive queue receives the output of the previous queue plus some external arrivals. For the case of two queues in series, we study the end-to-end delay of a cell (customer) arriving at the first queue, and the covariance of its delays at both queues. The joint queue length process at all queues is studied in detail for the 2-queue and 3-queue cases, and we outline an approach to the case of an arbitrary number of queues in series.Part of the research of this author has been supported by the European Grant BRA-QMIPS of CEC DG XIII.The research of this author was done during the time that he was affiliated with CWI, in a joint project with PTT Research.     

On bounds for bulk arrival queues

This paper gives a simple and effective approach pf deriving bounds for bulk arrival queues by making use of the bounds for single arrival queues. With this approach, upper bounds of mean actual/virtual waiting times and mean queue length at random epochs can be derived for the bulk arrival queues GI^X/G/1 and GI^X/G/c (lower bounds can be derived in a similar way). The merit of this approach is shown by comparing the bounds obtained with some existing results in the literature.     

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.     

Increasing convex ordering of queue length in bulk queues

This paper considers single-server bulk queues M^(X)/G^(Y)/1 and G^(X)/M^(Y)/1. In the former queue, service times and service capacity are dependent, while in the latter queue, inter-arriving times and arriving group size are dependent. We show that stronger dependence between those leads to shorter queue lengths in the increasing convex ordering sense.     

Parametric nonlinear programming approach to fuzzy queues with bulk service

This paper proposes a procedure to construct the membership functions of the performance measures in bulk service queuing systems with the arrival rate and service rate are fuzzy numbers. The basic idea is to transform a fuzzy queue with bulk service to a family of conventional crisp queues with bulk service by applying the α-cut approach. On the basis of α-cut representation and the extension principle, a pair of parametric nonlinear programs is formulated to describe that family of crisp bulk service queues, via which the membership functions of the performance measures are derived. To demonstrate the validity of the proposed procedure, two fuzzy queues often encountered in transportation management are exemplified. Since the performance measures are expressed by membership functions rather than by crisp values, they completely conserve the fuzziness of input information when some data of bulk-service queuing systems are ambiguous. Thus the proposed approach for vague systems can represent the system more accurately, and more information is provided for designing queuing systems in real life. By extending to fuzzy environment, the bulk service queuing models would have wider applications.     

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.     

Applications of bulk queues to group testing models with incomplete identification

A population of items is said to be “group-testable”, (i) if the items can be classified as “good” and “bad”, and (ii) if it is possible to carry out a simultaneous test on a batch of items with two possible outcomes: “Success” (indicating that all items in the batch are good) or “failure” (indicating a contaminated batch). In this paper, we assume that the items to be tested arrive at the group-testing centre according to a Poisson process and are served (i.e., group-tested) in batches by one server. The service time distribution is general but it depends on the batch size being tested. These assumptions give rise to the bulk queueing model M/G^(m,M)/1, where m and M(>m) are the decision variables where each batch size can be between m and M. We develop the generating function for the steady-state probabilities of the embedded Markov chain. We then consider a more realistic finite state version of the problem where the testing centre has a finite capacity and present an expected profit objective function. We compute the optimal values of the decision variables (m, M) that maximize the expected profit. For a special case of the problem, we determine the optimal decision explicitly in terms of the Lambert function.     

Order restoration in queues

We examine a class of problems in queueing networks which arise when customers enter a bank of parallel servers in a given order and lose their place in the sequence due to passing resulting from variations in service times. The original sequence is required before service can take place at the next station in the network. These problems arise naturally in flexible manufacturing systems. The result is that the next station beyond the parallel bank of servers can be approximated by a non-Markovian bulk arrival system. This station sees batch arrivals of customers that are eligible to receive service. The size of the arriving batches is shown to depend on the inter-arrival times. Several fundamental results are established for this class of problems including the distribution of batch inter-arrival times, batch sizes, and an approximate method for determining the distribution of the number of eligible and an exact method for determining the distribution of the number of ineligible customers in the system.     

Two queues in tandem

A system consisting of two queues in series, the output of one queue being the input of the other, is described. General distributions are discussed, but the exponential distribution is given particular consideration.     

Regeneration and renovation in queues

Regenerative events for different queueing models are considered. The aim of this paper is to construct these events for continuous-time processes if they are given for the corresponding discrete-time model. The construction uses so-called renovative events revealing the property of the state at timen of the discrete-time model to be independent (in an algebraic sense) of the states referring to epochs not later thann −L (whereL is some constant) given that there are some restrictions on the “governing sequence”. Different types of multi-server and multi-phase queues are considered.     

Interacting queues in heavy traffic

We consider a system of parallel queues with Poisson arrivals and exponentially distributed service requirements. The various queues are coupled through their service rates, causing a complex dynamic interaction. Specifically, the system consists of one primary queue and several secondary queues whose service rates depend on whether the primary queue is empty or not. Conversely, the service rate of the primary queue depends on which of the secondary queues are empty.     

Bayesian inference in Markovian queues

This paper is concerned with the Bayesian analysis of general queues with Poisson input and exponential service times. Joint posterior distribution of the arrival rate and the individual service rate is obtained from a sample consisting inn observations of the interarrival process andm complete service times. Posterior distribution of traffic intensity inM/M/c is also obtained and the statistical analysis of the ergodic condition from a decision point of view is discussed.     

Cascades of queues

This paper presents results from a bulk service queueing system, where the main service takes place at fixed time intervals, but where back-up (or relief) services may be introduced in times of heavy demand on the system. On occasions the back-up service itself may receive further back-up services, thus leading to the concept of a cascade of queues flowing from the original main service. Analytic expressions are derived for the mean queue lengths at the points of delivery of service, and the computational requirements are discussed in detail. Sample numerical results and a simple cost analysis are provided.