Queues with service times and interarrival times depending linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queue with unlimited 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. We determine when the waiting-time distributions converge to a proper limit and we develop approximations for this steady-state limit, primarily by applying previous results of Vervaat [21] and Brandt [4] for the unrestricted recursionY _n+1=C _n Y _n +X _n . Particularly appealing for applications is a normal approximation for the stationary waiting time distribution in the case when the queue only rarely becomes empty. We also consider the problem of scheduling successive interarrival times at arrival epochs, with the objective of achieving nearly maximal throughput with nearly bounded waiting times, while making the interarrival time sequence relatively smooth. We identify policies depending linearly and deterministically upon the work in the system which meet these objectives reasonably well; with these policies the waiting times are approximately contained in a specified interval a specified fraction of time.     

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.     

The waiting time distribution for a correlated queue with exponential interarrival and service times

We are concerned with the analysis of the waiting time distribution in an $M∕M∕1$ queue in which the interarrival time between the $n$th and the $(n+1)$th customers and the service time of the $n$th customer are correlated random variables with Downton’s bivariate exponential distribution. In this paper we show that the conditional waiting time distribution, given that the waiting time is positive, is exponential.     

A queueing model with dependence between service and interarrival times

We consider a storage model that can be either interpreted as a certain queueing model with dependence between a service request and the subsequent interarrival time, or as a fluid production/inventory model with a two-state random environment. We establish a direct link between the workload distributions of the queueing model and the production/inventory model, and we present a detailed analysis of the workload and waiting time process of the queueing system.     

On the probability of abandonment in queues with limited sojourn and waiting times

Consider the Geo/Geo/1 queue with impatient customers and let X reflect the patience distribution. We show that systems with a smaller patience distribution X in the convex-ordering sense give rise to fewer abandonments (due to impatience), irrespective of whether customers become patient when entering the service facility.     

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.     

Little laws for utility processes and waiting times in queues

Little's law for queueing systems isL=W: the average queue length equals the average arrival rate times the average waiting time in the system. This study gives further insights into techniques for establishing such laws (i.e. establishing the existence of the terms as limiting averages or expectations) and it presents several basic laws for systems with special structures. The main results concern (1) general necessary and sufficient conditions for Little laws for utility processes as well as queueing systems, (2) Little laws for systems that empty out periodically or, more generally, have regular departures and (3) Little laws tailored to regenerative, Markovian and stationary systems.This research was supported in part by the Air Force Office of Scientific Research under contract 91-0013 and NSF grant DDM-9224520.     

Virtual waiting times in priority-M/G/1 queues with vacations

In this paper exhaustive-service priority-M/G/1 queueing systems with multiple vacations, single vacation and setup times are studied under the nonpreemptive and preemptive resume priority disciplines. For each of the six models analysed, the Laplace-Stieltjes transform of the virtual waiting timeW _k(t) at timet of classk is derived by the method of collective marks. A sufficient condition for , whereU has the standard normal distribution, is also given.     

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.     

Analytic approximations of queues with lightly- and heavily-correlated autoregressive service times

We consider a single-server queueing system. The arrival process is modelled as a Poisson process while the service times of the consecutive customers constitute a sequence of autoregressive random variables. Our interest into autoregressive service times comes from the need to capture temporal correlation of the channel conditions on wireless network links. If these fluctuations are slow in comparison with the transmission times of the packets, transmission times of consecutive packets are correlated. Such correlation needs to be taken into account for an accurate performance assessment. By means of a transform approach, we obtain a functional equation for the joint transform of the queue content and the current service time at departure epochs in steady state. To the best of our knowledge, this functional equation cannot be solved by exact mathematical techniques, despite its simplicity. However, by means of a Taylor series expansion in the parameter of the autoregressive process, a “light-correlation” approximation is obtained for performance measures such as moments of the queue content and packet delay. We illustrate our approach by some numerical examples, thereby assessing the accuracy of our approximations by simulation. For the heavy correlation case, we give differential equation approximations based on the time-scale separation technique, and present numerical examples in support of this approximation.     

Delayed renewal process with uncertain interarrival times

Delayed renewal process is a special type of renewal process in which the first interarrival time is quite different from the others. This paper first proposes an uncertain delayed renewal process whose interarrival times are regarded as uncertain variables. Then it gives an uncertainty distribution of delayed renewal process and an elementary delayed renewal theorem.     

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.     

Optimal design of multi‐server Markovian queues with polynomial waiting and service costs

This paper is concerned with the optimal design of queueing systems. The main decisions in the design of such systems are the number of servers, the appropriate control to have on the arrival rates, and the appropriate service rate these servers should possess. In the formulation of the objective function to this problem, most publications use only linear cost rates. The linear rates, especially for the waiting cost, do not accurately reflect reality. Although there are papers involving nonlinear cost functions, no paper has ever considered using polynomial cost functions of degree higher than two. This is because simple formulas for computing the higher moments are not available in the literature. This paper is an attempt to fill this gap in the literature. Thus, the main contributions of our work are as follows: (i) the derivation of a very simple formula for the higher moments of the waiting time for the M/M/s queueing system, which requires only the knowledge of the expected waiting time; (ii) proving their convexity with respect to the design variables; and (iii) modeling and solving more realistic design problems involving general polynomial cost functions. We also focus on simultaneous optimization of the staffing level, arrival rate and service rate. Copyright © 2013 John Wiley & Sons, Ltd.     

Conditions for finite moments of waiting times inG/G/1 queues

We find conditions for E(W ) to be finite whereW is the stationary waiting time random variable in a stableG/G/1 queue with dependent service and inter-arrival times.Supported in part by KBN under grant 640/2/9, and at the Center for Stochastic Processes, Department of Statistics at the University of North Carolina Chapel Hill by the Air Force Office of Scientific Research Grant No. 91-0030 and the Army Research Office Grant No. DAAL09-92-G-0008.     

Control charts with random interarrival times between successive samplings

In the classical setup used in process monitoring, the times between the collection of successive plotted samples are considered as nonrandom. However, in several real‐life applications, it seems plausible to assume that the time needed to collect the necessary information for plotting a point in the control chart has a stochastic nature. Under this scenario, instead of focusing on the number of points plotted on the chart until an out‐of‐control signal is initiated, the appropriate statistic to look at is the total time until a signal is generated. If we denote by L the run length of a control chart and by Y_t,t = 1,2,…, the times between successive plotted points, then the compound random variable expresses the time to signal of a monitoring scheme, under a particular sampling policy. In this paper, we illustrate how S_L can be exploited to study various charts that are suitable for monitoring Poisson observations. We provide some results for the exact distribution of S_L that may facilitate the task of the performance assessment of a control chart with random plotting times; illustrations and several numerical comparisons that are useful for quality control experts who wish to practice them are presented, and finally, an illustrative example elucidating the implementation of the proposed model is also provided.     

Sojourn and waiting times in a single-server system with state-dependent mean service rate

A birth-death queueing system with asingle server, first-come first-served discipline, Poisson arrivals and state-dependent mean service rate is considered. The problem of determining the equilibrium densities of the sojourn and waiting times is formulated, in general. The particular case in which the mean service rate has one of two values, depending on whether or not the number of customers in the system exceeds a prescribed threshold, is then investigated. A generating function is derived for the Laplace transforms of the densities of the sojourn and waiting times, leading to explicit expressions for these quantities. Explicit expressions for the second moments of the sojourn and waiting times are also obtained.