Approximations for waiting time in GI/G/1 systems

The Sokolov procedure is described and used to obtain an explicit and easily applied approximation for the waiting time distribution in the FIFO GI/G/1 queue.     

Representing workloads in GI/G/1 queues through the preemptive-resume LIFO queue discipline

We give in this paper a detailed sample-average analysis of GI/G/1 queues with the preemptive-resume LIFO (last-in-first-out) queue discipline: we study the long-run state behavior of the system by averaging over arrival epochs, departure epochs, as well as time, and obtain relations that express the resulting averages in terms of basic characteristics within busy cycles. These relations, together with the fact that the preemptive-resume LIFO queue discipline is work-conserving, imply new representations for both actual and virtual delays in standard GI/G/1 queues with the FIFO (first-in-first-out) queue discipline. The arguments by which our results are obtained unveil the underlying structural explanations for many classical and somewhat mysterious results relating to queue lengths and/or delays in standard GI/G/1 queues, including the well-known Bene's formula for the delay distribution in M/G/l. We also discuss how to extend our results to settings more general than GI/G/1.     

On a Two-Queue Priority System with Impatience and its Application to a Call Center*

We consider an s-server priority system with a protected and an unprotected queue. The arrival rates at the queues and the service rate may depend on the number n of customers being in service or in the protected queue, but the service rate is assumed to be constant for n > s. As soon as any server is idle, a customer from the protected queue will be served according to the FCFS discipline. However, the customers in the protected queue are impatient. If the offered waiting time exceeds a random maximal waiting time I, then the customer leaves the protected queue after time I. If I is less than a given deterministic time, then he leaves the system, else he will be transferred by the system to the unprotected queue. The service of a customer from the unprotected queue will be started if the protected queue is empty and more than a given number of servers become idle. The model is a generalization of the many-server queue with impatient customers. The global balance conditions seem to have no explicit solution. However, the balance conditions for the density of the stationary state process for the subsystem of customers being in service or in the protected queue can be solved. This yields the stability conditions and the probabilities that precisely n customers are in service or in the protected queue. For obtaining performance measures for the unprotected queue, a system approximation based on fitting impatience intensities is constructed. The results are applied to the performance analysis of a call center with an integrated voice-mail-server.     

Design of a production system with a feedback buffer

In this paper, we deal with an M/G/1 Bernoulli feedback queue and apply it to the design of a production system. New arrivals enter a “main queue” before processing. Processed items leave the system with probability 1-p or are fed back with probability p into an intermediate finite “feedback queue”. As soon as the feedback queue is fully occupied, the items in the feedback queue are released, all at a time, into the main queue for another processing. Using transform methods, various performance measures are derived such as the joint distribution of the number of items in each queue and the dispatching rate. We then derive the optimal buffer size which minimizes the overall operating cost under a cost structure. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotics for M/G/1 low-priority waiting-time tail probabilities

We consider the classical M/G/1 queue with two priority classes and the nonpreemptive and preemptive-resume disciplines. We show that the low-priority steady-state waiting-time can be expressed as a geometric random sum of i.i.d. random variables, just like the M/G/1 FIFO waiting-time distribution. We exploit this structures to determine the asymptotic behavior of the tail probabilities. Unlike the FIFO case, there is routinely a region of the parameters such that the tail probabilities have non-exponential asymptotics. This phenomenon even occurs when both service-time distributions are exponential. When non-exponential asymptotics holds, the asymptotic form tends to be determined by the non-exponential asymptotics for the high-priority busy-period distribution. We obtain asymptotic expansions for the low-priority waiting-time distribution by obtaining an asymptotic expansion for the busy-period transform from Kendall's functional equation. We identify the boundary between the exponential and non-exponential asymptotic regions. For the special cases of an exponential high-priority service-time distribution and of common general service-time distributions, we obtain convenient explicit forms for the low-priority waiting-time transform. We also establish asymptotic results for cases with long-tail service-time distributions. As with FIFO, the exponential asymptotics tend to provide excellent approximations, while the non-exponential asymptotics do not, but the asymptotic relations indicate the general form. In all cases, exact results can be obtained by numerically inverting the waiting-time transform. This revised version was published online in June 2006 with corrections to the Cover Date.     

The serial correlation coefficients for waiting times in the stationary GI/M/m queue

Serial correlation coefficients are useful measures of the interdependence of successive waiting times. Potential applications include the development of linear predictors and determining simulation run lengths. This paper presents the algorithm for calculating such correlations in the multiserver exponential service queue, and relates it to known results for single server queues.     

Some aspects of an<Emphasis Type="Italic">M/G/1</Emphasis> queueing system with optional second service

This paper examines the steady state behaviour of anM/G/1 queue with a second optional service in which the server may provide two phases of heterogeneous service to incoming units. We derive the queue size distribution at stationary point of time and waiting time distribution. Moreover we derive the queue size distribution at the departure point of time as a classical generalization of the well knownPollaczek Khinchin formula. This is a generalization of the result obtained by Madan (2000). This work is supported by Department of Atomic Energy, Govt. of India, NBHM Project No. 88/2/2001/R&D II/2001.     

TheM/G/1 queue with processor sharing and its relation to a feedback queue

The central model of this paper is anM/M/1 queue with a general probabilistic feedback mechanism. When a customer completes his ith service, he departs from the system with probability 1–p(i) and he cycles back with probabilityp(i). The mean service time of each customer is the same for each cycle. We determine the joint distribution of the successive sojourn times of a tagged customer at his loops through the system. Subsequently we let the mean service time at each loop shrink to zero and the feedback probabilities approach one in such a way that the mean total required service time remains constant. The behaviour of the feedback queue then approaches that of anM/G/1 processor sharing queue, different choices of the feedback probabilities leading to different service time distributions in the processor sharing model. This is exploited to analyse the sojourn time distribution in theM/G/1 queue with processor sharing.Some variants are also considered, viz., anM/M/1 feedback queue with additional customers who are always present, and anM/G/1 processor sharing queue with feedback.     

Settling time bounds forM/G/1 queues

This paper addresses the question of how long it takes for anM/G/1 queue, starting empty, to approach steady state. A coupling technique is used to derive bounds on the variation distance between the distribution of number in the system at timet and its stationary distribution. The bounds are valid for allt. This research was supported in part by a grant from the AT&T Foundation and NSF grant DCR-8351757.     

Asymptotic expansions for waiting time probabilities in an M/G/1 queue with long-tailed service time

We consider anM/G/1 queue with FCFS queue discipline. We present asymptotic expansions for tail probabilities of the stationary waiting time when the service time distribution is longtailed and we discuss an extension of our methods to theM ^[x]/G/1 queue with batch arrivals.     

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.     

A Markov-modulated M/G/1 queue I: Stationary distribution

We consider an M/G/1 queueing system in which the arrival rate and service time density are functions of a two-state stochastic process. We describe the system by the total unfinished work present and allow the arrival and service rate processes to depend on the current value of the unfinished work. We employ singular perturbation methods to compute asymptotic approximations to the stationary distribution of unfinished work and in particular, compute the stationary probability of an empty queue.This research was supported in part by NSF Grants DMS-84-06110, DMS-85-01535 and DMS-86-20267, and grants from the U.S. Israel Binational Science Foundation and the Israel Academy of Sciences.     

A Markov-modulated M/G/1 queue II: Busy period and time for buffer overflow

We consider an M/G/1 queue where the arrival and service processes are modulated by a two state Markov chain. We assume that the arrival rate, service time density and the rates at which the Markov chain switches its state, are functions of the total unfinished work (buffer content) in the queue. We compute asymptotic approximations to performance measures such as the mean residual busy period, mean length of a busy period, and the mean time to reach capacity.This research was supported in part by NSF Grants DMS-84-06110, DMS-85-01535 and DMS-86-20267, and grants from the U.S. Israel Binational Science Foundation and the Israel Academy of Sciences.     

An Arrival Time Approach to M/G/1-type Queues with Generalized Vacations

We propose a simple way, called the arrival time approach, of finding the queue length distributions for M/G/1-type queues with generalized server vacations. The proposed approach serves as a useful alternative to understanding complicated queueing processes such as priority queues with server vacations and MAP/G/1 queues with server vacations.     

Markov-modulatedPH/G/1 queueing systems

We study a PH/G/1 queue in which the arrival process and the service times depend on the state of an underlying Markov chain J(t) on a countable state spaceE. We derive the busy period process, waiting time and idle time of this queueing system. We also study the Markov modulated E_K/G/1 queueing system as a special case.     

The average virtual waiting time as a measure of performance

Under weak conditions the average virtual waiting time converges exponentially fast to its limit. For this reason this quantity has been suggested as a measure of performance for queueing systems. We consider theM/G/1 queue and provide estimation and limiting behaviour of the index of exponential decay.     

Clearing Models for M/G/1 Queues

We consider M/G/1-type queueing systems with disasters, occurring at certain random times and causing an instantaneous removal of the entire residual workload from the system. After such a clearing, the system is assumed to be ready to start working again immediately. We consider clearings at deterministic equidistant times, at random times and at crossings of some prespecified level, and derive the stationary distribution of the workload process for these clearing times and some of their combinations.     

Multi-Server Queueing Systems with Multiple Priority Classes

We present the first near-exact analysis of an M/PH/k queue with m > 2 preemptive-resume priority classes. Our analysis introduces a new technique, which we refer to as Recursive Dimensionality Reduction (RDR). The key idea in RDR is that the m-dimensionally infinite Markov chain, representing the m class state space, is recursively reduced to a 1-dimensionally infinite Markov chain, that is easily and quickly solved. RDR involves no truncation and results in only small inaccuracy when compared with simulation, for a wide range of loads and variability in the job size distribution. Our analytic methods are then used to derive insights on how multi-server systems with prioritization compare with their single server counterparts with respect to response time. Multi-server systems are also compared with single server systems with respect to the effect of different prioritization schemes—“smart” prioritization (giving priority to the smaller jobs) versus “stupid” prioritization (giving priority to the larger jobs). We also study the effect of approximating m class performance by collapsing the m classes into just two classes. Supported by NSF Career Grant CCR-0133077, NSF Theory CCR-0311383, NSF ITR CCR-0313148, and IBM Corporation via Pittsburgh Digital Greenhouse Grant 2003. AMS subject classification: 60K25, 68M20, 90B22, 90B36     

Approximations for the delay probability in the M/G/s queue

This paper develops approximations for the delay probability in an M/G/s queue. For M/G/s queues, it has been well known that the delay probability in the M/M/s queue, i.e., the Erlang delay formula, is usually a good approximation for other service-time distributions. By using an excellent approximation for the mean waiting time in the M/G/s queue, we provide more accurate approximations of the delay probability for small values of s. To test the quality of our approximations, we compare them with the exact value and the Erlang delay formula for some particular cases.     

Queues with impolite customers

An interesting behavior of customers arriving to a queue for service concerns the manner in which they join the queue. The arrival discipline of the customers may be impolite, in the sense that an arriving customer who finds all servers busy may pick a position which is not necessarily at the end of the line. We introduce and discuss in detail such an arrival discipline of sufficient generality which has interesting applications. In particular, we show that the more impolite an arrival discipline is, the bigger is the variance of the waiting time. We also study a special model in more depth to provide simple computational formulas for several performance measures.