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.     

Markov-modulated infinite-server queues with general service times

This paper analyzes several aspects of the Markov-modulated infinite-server queue. In the system considered (i) particles arrive according to a Poisson process with rate $\lambda _i$ when an external Markov process (“background process”) is in state $i$ , (ii) service times are drawn from a distribution with distribution function $F_i(\cdot )$ when the state of the background process (as seen at arrival) is $i$ , (iii) there are infinitely many servers. We start by setting up explicit formulas for the mean and variance of the number of particles in the system at time $t\ge 0$ , given the system started empty. The special case of exponential service times is studied in detail, resulting in a recursive scheme to compute the moments of the number of particles at an exponentially distributed time, as well as their steady-state counterparts. Then we consider an asymptotic regime in which the arrival rates are sped up by a factor $N$ , and the transition times by a factor $N^{1+\varepsilon }$ (for some $\varepsilon >0$ ). Under this scaling it turns out that the number of customers at time $t\ge 0$ obeys a central limit theorem; the convergence of the finite-dimensional distributions is proven.     

On queues with service and interarrival times depending on waiting times

We consider an extension of the standard G/G/1 queue, described by the equation $W\stackrel{ \mathcal {D}}{=}\max\mathrm{max}\,\{0,B-A+YW\}$ , where ?[Y=1]=p and ?[Y=?1]=1?p. For p=1 this model reduces to the classical Lindley equation for the waiting time in the G/G/1 queue, whereas for p=0 it describes the waiting time of the server in an alternating service model. For all other values of p, this model describes a FCFS queue in which the service times and interarrival times depend linearly and randomly on the waiting times. We derive the distribution of W when A is generally distributed and B follows a phase-type distribution, and when A is exponentially distributed and B deterministic.     

A simple policy for multiple queues with size-independent service times

We consider a service system with two Poisson arrival queues. A server chooses which queue to serve at each moment. Once a queue is served, all the customers will be served within a fixed amount of time. This model is useful in studying airport shuttling or certain online computing systems. We propose a simple yet optimal state-independent policy for this problem which is not only easy to implement, but also performs very well.     

Two-parameter heavy-traffic limits for infinite-server queues with dependent service times

This paper is a sequel to our 2010 paper in this journal in which we established heavy-traffic limits for two-parameter processes in infinite-server queues with an arrival process that satisfies an FCLT and i.i.d. service times with a general distribution. The arrival process can have a time-varying arrival rate. In particular, an FWLLN and an FCLT were established for the two-parameter process describing the number of customers in the system at time t that have been so for a duration y. The present paper extends the previous results to cover the case in which the successive service times are weakly dependent. The deterministic fluid limit obtained from the new FWLLN is unaffected by the dependence, whereas the Gaussian process limit (random field) obtained from the FCLT has a term resulting from the dependence. Explicit expressions are derived for the time-dependent means, variances, and covariances for the common case in which the limit process for the arrival process is a (possibly time scaled) Brownian motion.     

Calculation of delay characteristics for multiserver queues with constant service times

We consider a discrete-time infinite-capacity queueing system with a general uncorrelated arrival process, constant-length service times of multiple slots, multiple servers and a first-come-first-served queueing discipline. Under the assumption that the queueing system can reach a steady state, we first establish a relationship between the steady-state probability distributions of the system content and the customer delay. Next, by means of this relationship, an explicit expression for the probability generating function of the customer delay is obtained from the known generating function of the system content, derived in previous work. In addition, several characteristics of the customer delay, namely the mean value, the variance and the tail distribution of the delay, are derived through some mathematical manipulations. The analysis is illustrated by means of some numerical examples.     

Scheduling in a multi-class series of queues with deterministic service times

We consider a problem of scheduling in a multi-class network of single-server queues in series, in which service times at the nodes are constant and equal. Such a model has potential application to automated manufacturing systems or packet-switched communication networks, where a message is divided into packets (or cells) of fixed lengths. The network is a series-type assembly or transfer line, with the exception that there is an additional class of jobs that requires processing only at the first node (class 0). There is a holding cost per unit time that is proportional to the total number of customers in the system. The objective is to minimize the (expected) total discounted holding cost over a finite or an infinite horizon. We show that an optimal policy gives priority to class-0 jobs at node 1 when at least one of a set ofm–1 inequalities on partial sums of the components of the state vector is satisfied. We solve the problem by two methods. The first involves formulating the problem as a (discrete-time) Markov decision process and using induction on the horizon length. The second is a sample-path approach using an interchange argument to establish optimality.The research of this author was supported by the National Science Foundation under Grant No. DDM-8719825. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.     

Departures from queues with changeover times

We consider the M/M ^ij /1 queue as a model of queues with changeover times, i.e., the service is exponential with parameter _ij depending on the previous job type (i) and the current job type (j). It is shown that the departure process is renewal and Poisson iff _ij = (constant). In this case, types of departures are dependent renewal processes. Crosscovariance and crosscorrelations are given.     

On Whitt's conjecture for queues in which service times and interarrival times depend linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queueing system with infinite waiting space and the first-in-first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. When the waiting-time distributions converge to a proper limit, Whitt [10] proposed a normal approximation for this steady-state limit. In this paper we prove a limit theorem for the steady-state limit of the system. Thus, our result provides a solid foundation for Whitt's normal approximation of the steady-state distribution of the system.Supported in part by a grant from the National Natural Science Foundation of China.     

Asymptotic behaviour of the tandem queueing system with identical service times at both queues

Consider a tandem queue consisting of two single-server queues in series, with a Poisson arrival process at the first queue and arbitrarily distributed service times, which for any customer are identical in both queues. For this tandem queue, we relate the tail behaviour of the sojourn time distribution and the workload distribution at the second queue to that of the (residual) service time distribution. As a by-result, we prove that both the sojourn time distribution and the workload distribution at the second queue are regularly varying at infinity of index 1−ν, if the service time distribution is regularly varying at infinity of index −ν (ν>1). Furthermore, in the latter case we derive a heavy-traffic limit theorem for the sojourn time S ⁽²⁾ at the second queue when the traffic load ρ↑ 1. It states that, for a particular contraction factor Δ (ρ), the contracted sojourn time Δ (ρ) S ⁽²⁾ converges in distribution to the limit distribution H(·) as ρ↑ 1 where .     

Moving-average representation of autoregressive approximations

We study the properties of an MA(∞)-representation of an autoregressive approximation for a stationary, real-valued process. In doing so we give an extension of Wiener's theorem in the deterministic approximation setup. When dealing with data, we can use this new key result to obtain insight into the structure of MA(∞)-representations of fitted autoregressive models where the order increases with the sample size. In particular, we give a uniform bound for estimating the moving-average coefficients via autoregressive approximation being uniform over all integers.     

Two fluid approximations for multi-server queues with abandonments

Insight is provided into a previously developed M/M/s/r+M(n) approximation for the M/GI/s/r+GI queueing model by establishing fluid and diffusion limits for the approximating model. Fluid approximations for the two models are compared in the many-server efficiency-driven (overloaded) regime. The two fluid approximations do not coincide, but they are close.     

Priority queues with semi-exhaustive service

This paper studies a new type of multi-class priority queues with semi-exhaustive service and server vacations, which operates as follows: A single server continues serving messages in queuen until the number of messages decreases toone less than that found upon the server's last arrival at queuen, where 1nN. In succession, messages of the highest class present in the system, if any, will be served according to this semi-exhaustive service. Applying the delay cycle analysis and introducing a super-message composed of messages served in a busy period, we derive explicitly the Laplace-Stieltjes transforms (LSTs) and the first two moments of the message waiting time distributions for each class in the M/G/1-type priority queues with multiple and single vacations. We also derive a conversion relationship between the LSTs for waiting times in the multiple and single vacation models.     

Waiting times in queues with relative priorities

This paper determines the mean waiting times for a single server multi-class queueing model with Poisson arrivals and relative priorities. If the server becomes idle, the probability that the next job is from class-i is proportional to the product between the number of class-i jobs present and their priority parameter.     

Validity of heavy-traffic steady-state approximations in many-server queues with abandonment

We consider \(GI/Ph/n+M\) parallel-server systems with a renewal arrival process, a phase-type service time distribution, \(n\) homogenous servers, and an exponential patience time distribution with positive rate. We show that in the Halfin–Whitt regime, the sequence of stationary distributions corresponding to the normalized state processes is tight. As a consequence, we establish an interchange of heavy-traffic and steady-state limits for \(GI/Ph/n+M\) queues.     

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.     

Assembly-like queues with finite capacity: Bounds,asymptotics and approximations

In this paper we study a queueing model of assembly-like manufacturing operations. This study was motivated by an examination of a circuit pack testing procedure in an AT & T factory. However, the model may be representative of many manufacturing assembly operations. We assume that customers fromn classes arrive according to independent Poisson processes with the same arrival rate into a single-server queueing station where the service times are exponentially distributed. The service discipline requires that service be rendered simultaneously to a group of customers consisting of exactly one member from each class. The server is idle if there are not enough customers to form a group. There is a separate waiting area for customers belonging to the same class and the size of the waiting area is the same for all classes. Customers who arrive to find the waiting area for their class full, are lost. Performance measures of interest include blocking probability, throughput, mean queue length and mean sojourn time. Since the state space for this queueing system could be large, exact answers for even reasonable values of the parameters may not be easy to obtain. We have therefore focused on two approaches. First, we find upper and lower bounds for the mean sojourn time. From these bounds we obtain the asymptotic solutions as the arrival rate (waiting room, service rate) approaches zero (infinity). Second, for moderate values of these parameters we suggest an approximate solution method. We compare the results of our approximation against simulation results and report good correspondence.     

Diffusion approximations for double-ended queues with reneging in heavy traffic

We study a double-ended queue consisting of two classes of customers. Whenever there is a pair of customers from both classes, they are matched and leave the system. The matching is instantaneous following the first-come–first-match principle. If a customer cannot be matched immediately, he/she will stay in a queue. We also assume customers are impatient with generally distributed patience times. Under suitable heavy traffic conditions, we establish simple linear asymptotic relationships between the diffusion-scaled queue length process and the diffusion-scaled offered waiting time processes and show that the diffusion-scaled queue length process converges weakly to a diffusion process that admits a unique stationary distribution.