Approximating the Mean Waiting Time in the <Emphasis Type="Italic">GI/G/s</Emphasis> Queue

We provide two distribution-dependent approximations for the mean waiting time in a GI/G/s queue. Both approximations are weighted combinations of the exact mean waiting times for the GI/M/s and M/D/s queues each of which has the same mean service time and traffic intensity as in the approximating GI/G/s queue. The weights in the approximations are expressed by the service-time c.d.f. and the first two moments of interarrival and service times. To examine the performance of our approximations, they are numerically compared with exact solutions and previous two-moment approximations for various cases. Extensive numerical comparisons indicate that the relative percentage errors of the approximations are of the order of 5% in moderate traffic and 1% in heavy traffic, except for extreme cases.     

A consistent diffusion approximation for finite-capacity multiserver queues

A diffusion approximation is developed for general multiserver queues with finite waiting spaces, which are typical models of manufacturing systems as well as computer and communication systems. The model is the standard GI/G/s/s + r queue with s identical servers in parallel, r extra waiting spaces, and the first-come, first-served discipline. The main focus is on the steady-state distribution of the number of customers in the system. The process of the number of customers is approximated by a time-homogeneous diffusion process on a closed interval in the nonnegative real line. A conservation law plus some heuristics standing on solid theoretical ground generate approximation formulas for the steady-state distribution and other congestion measures. These formulas are consistent with the exact results for the M/G/s/s and M/M/s/s + r queues. The accuracy of approximations for principal congestion measures are numerically examined for some particular cases.     

On some relations between stationary time and customer state probabilities for qneueing systems G/GI/s/r

By means of a general formula for stochastic processes with imbedded marked point processes (PMP) some necessary and sufficient condition is given for the validity of a relationship, which is well-known in the case of exponentially distributed service times, between stationary time and customer state probabilities for loss systems G/GI/s/O (Theorem 3). A result of Miyazawa for the GI/GI/l/∞ queue is generalized to the case of non-recurrent interarrival times (Theorem 4)-. Furthermore, bounds are derived for the mean increment of the waiting time process at arrival epochs and for the mean actual waiting time in multi-server queues.     

AnM/M/s-consistent diffusion model for theGI/G/s queue

This paper develops a diffusion-approximation model for a stableGI/G/s queue: The queue-length process in theGI/G/s queue is approximated by a diffusion process on the nonnegative real line. Some heuristics on the state space and the infinitesimal parameters of the approximating diffusion process are introduced to obtain an approximation formula for the steady-state queue-length distribution. It is shown that the formula is consistent with the exact results for theM/M/s andM/G/ queues. The accuracy of the approximations for principal congestion measures are numerically examined for some particular cases.     

Nonstationary queues with Interrrupted Poisson arrivals and unreliable/repairable servers

A queueing model having a nonstationary Interrupted Poisson arrival process (IPP(t)),s time-dependent exponential unreliable/repairable servers and finite capacityc is introduced, and an approximation method for analysis of it is developed and tested. Approximations are developed for the time-dependent queue length moments and the system viewpoint waiting time distributions and moments. The approximation involves state-space partitioning and numerically integrating partial-moment differential equations (PMDEs). Surrogate distribution approximations (SDA's) are used to close the system of PMDEs. The approximations allow for analysis using only (s + 1)(s + 6) differential equations for the queue length moments rather than the 2(c + 1)(s +1) equations required by the classic method of numerically integrating the full set of Kolmogorov-forward equations. Effectively hours of cpu time are reduced to minutes for even modest capacity systems. Approximations for waiting time distributions and moments are developed.This research was partially funded by National Science Foundation grant ECS-8404409.     

Models and Approximations for Call Center Design

A call center is a facility for delivering telephone service, both incoming and outgoing. This paper addresses optimal staffing of call centers, modeled as M/G/n queues whose offered traffic consists of multiple customer streams, each with an individual priority, arrival rate, service distribution and grade of service (GoS) stated in terms of equilibrium tail waiting time probabilities or mean waiting times. The paper proposes a methodology for deriving the approximate minimal number of servers that suffices to guarantee the prescribed GoS of all customer streams. The methodology is based on an analytic approximation, called the Scaling-Erlang (SE) approximation, which maps the M/G/n queue to an approximating, suitably scaled M/G/1 queue, for which waiting time statistics are available via the Pollaczek-Khintchine formula in terms of Laplace transforms. The SE approximation is then generalized to M/G/n queues with multiple types of customers and non-preemptive priorities, yielding the Priority Scaling-Erlang (PSE) approximation. A simple goal-seeking search, utilizing SE/PSE approximations, is presented for the optimal staffing level, subject to GoS constraints. The efficacy of the methodology is demonstrated by comparing the number of servers estimated via the PSE approximation to their counterparts obtained by simulation. A number of case studies confirm that the SE/PSE approximations yield optimal staffing results in excellent agreement with simulation, but at a fraction of simulation time and space.     

Refining diffusion approximations for queues

This note illustrates the need to refine diffusion approximations for queues. Diffusion approximations are developed in several different ways for the mean waiting time in a GI/G/1 queue, yielding different results, all of which fail obvious consistency checks with bounds and exact values.     

Corrected asymptotics for a multi-server queue in the Halfin-Whitt regime

To investigate the quality of heavy-traffic approximations for queues with many servers, we consider the steady-state number of waiting customers in an M/D/s queue as s→∞. In the Halfin-Whitt regime, it is well known that this random variable converges to the supremum of a Gaussian random walk. This paper develops methods that yield more accurate results in terms of series expansions and inequalities for the probability of an empty queue, and the mean and variance of the queue length distribution. This quantifies the relationship between the limiting system and the queue with a small or moderate number of servers. The main idea is to view the M/D/s queue through the prism of the Gaussian random walk: as for the standard Gaussian random walk, we provide scalable series expansions involving terms that include the Riemann zeta function.      

Markov Skeleton Processes and Applications to Queueing Systems

In this paper, we apply the backward equations of Markov skeleton processes to qucueing systems. The transient distribution of the waiting time of a GI/G/1 queueing system, the transient distribution of the length of a GI/G/N queueing system and the transient distribution of the length of queueing networks are obtained.     

Simple Approximations for the GI/G/c Queue-II: The Moments,the Inverse Distribution Function and the Loss Function of the Number in the System and of the Queue Delay

Based on results obtained in part I of this paper, approximations for the first four moments of the number in the system are developed and thence used to approximate the inverse distribution function (IDF) and the loss functions (LF), employing Shore's general approximations. Existing approximations for the first two moments of queueing time in a GI/G/l queue serve to approximate the IDF and the LF of queueing time in the corresponding GI/G/c queue. The accuracy attained is generally satisfactory, while a remarkable algebraic simplicity is preserved. A numerical example demonstrates the applicability of some of the new approximations to solve optimization problems.     

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.     

关于GI/G/1/∞排队系统的平稳等待时间分布的局部尾等价式

关于GI/G/1/∞排队系统的平稳等待时间分布W,已有许多经典的结果描述了其尾分布[AKW-](x)=1-W(x)的等价极限情况.该文结合一些保险与金融领域重要的风险变量,研究了关于分布W的各种局部尾等价式问题.     

An interpolation approximation for the GI/G/1 queue based on multipoint Padé approximation

The performance evaluation of many complex manufacturing, communication and computer systems has been made possible by modeling them as queueing systems. Many approximations used in queueing theory have been drawn from the behavior of queues in light and heavy traffic conditions. In this paper, we propose a new approximation technique, which combines the light and heavy traffic characteristics. This interpolation approximation is based on the theory of multipoint Padé approximation which is applied at two points: light and heavy traffic. We show how this can be applied for estimating the waiting time moments of the ^GI/G/1 queue. The light traffic derivatives of any order can be evaluated using the MacLaurin series analysis procedure. The heavy traffic limits of the ^GI/G/1 queue are well known in the literature. Our technique generalizes the previously developed interpolation approximations and can be used to approximate any order of the waiting time moments. Through numerical examples, we show that the moments of the steady state waiting time can be estimated with extremely high accuracy under all ranges of traffic intensities using low orders of the approximant. We also present a framework for the development of simple analytical approximation formulas. This revised version was published online in June 2006 with corrections to the Cover Date.     

A simple formula for mean multiplexing delay for independent regenerative sources

Simple expressions are given for the mean delay, mean waiting time, and mean busy period length in a multiplexer. Data streams with active periods having a general distribution are permitted, and the data rate during the active periods can be random. Data can also arrive in batches. The key restrictions of the model are that the sources are independent, idle periods are exponentially distributed, and a source generates at least enough data during an active period to keep the server busy throughout the period. The exact formulas allow evaluation of the error in approximations such as a heavy traffic diffusion approximation.Both continuous and discrete time models are considered. The discrete-time model includes that studied by Viterbi and subsequently generalized by Neuts. The Pollaczek-Khinchine formula for the mean amount of work in anM/GI/1 queue is retrieved as a limiting case.Preliminary version presented at IEEE INFOCOM, San Francisco, April 1993.     

Numerical approximations for the steady‐state waiting times in a GI/G/1 queue

This paper focuses on easily computable numerical approximations for the distribution and moments of the steadystate waiting times in a stable GI/G/1 queue. The approximation methodology is based on the theory of Fredholm integral equations and involves solving a linear system of equations. Numerical experimentation for various M/G/1 and GI/M/1 queues reveals that the methodology results in estimates for the mean and variance of waiting times within ±1% of the corresponding exact values. Comparisons with competing approaches establish that our methodology is not only more accurate, but also more amenable to obtaining waiting time approximations from the operational data. Approximations are also obtained for the distributions of steadystate idle times and interdeparture times. The approximations presented in this paper are intended to be useful in roughcut analysis and design of manufacturing, telecommunications, and computer systems as well as in the verification of the accuracies of inequalities, bounds, and approximations.     

On the inapproximability of <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">K</Emphasis>: why two moments of job size distribution are not enough

The M/G/K queueing system is one of the oldest models for multiserver systems and has been the topic of performance papers for almost half a century. However, even now, only coarse approximations exist for its mean waiting time. All the closed-form (nonnumerical) approximations in the literature are based on (at most) the first two moments of the job size distribution. In this paper we prove that no approximation based on only the first two moments can be accurate for all job size distributions, and we provide a lower bound on the inapproximability ratio, which we refer to as “the gap.” This is the first such result in the literature to address “the gap.” The proof technique behind this result is novel as well and combines mean value analysis, sample path techniques, scheduling, regenerative arguments, and asymptotic estimates. Finally, our work provides insight into the effect of higher moments of the job size distribution on the mean waiting time.     

On inference concerning time-dependent queue performance: The M/G/1 example

This paper proposes easily-computed approximations to the finite-time expected waiting time for anM/G/1 system starting from an empty state. Both unsaturated (ρ<1) and saturated (ρ>1) conditions are considered. Numerical evidence is presented to indicate that the quality of the approximations is usefully good, especially when ease of computation is an issue. Further, the methodology is adapted to assess expected waiting time when inference must be made from a random sample of service times, and the decision is made to do so nonparametrically, i.e., without fitting a specific function. The results appear reasonable and potentially useful, and are not burdensome to obtain. The methodology investigated can also be applied to the variety of queueing models that are close siblings ofM/G/1: priority and breakdowns and “vacations” being examples. Of course other approximating and inferential options remain to be investigated.     

Fluid approximations for a processor-sharing queue

In this paper a fluid approximation, also known as a functional strong law of large numbers (FSLLN) for a GI/G/1 queue under a processor-sharing service discipline is established and its properties are analysed. The fluid limit depends on the arrival rate, the service time distribution of the initial customers, and the service time distribution of the arriving customers. This is in contrast to the known result for the GI/G/1 queue under a FIFO service discipline, where the fluid limit is piecewise linear and depends on the service time distribution only through its mean. The piecewise linear form of the limit can be recovered by an equilibrium type choice of the initial service distribution. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analyzing the discrete-timeG (G)/Geo/1 queue using complex contour integration

In this paper, a discrete-time single-server queueing system with an infinite waiting room, referred to as theG ^(G)/Geo/1 model, i.e., a system with general interarrival-time distribution, general arrival bulk-size distribution and geometrical service times, is studied. A method of analysis based on integration along contours in the complex plane is presented. Using this technique, analytical expressions are obtained for the probability generating functions of the system contents at various observation epochs and of the delay and waiting time of an arbitrary customer, assuming a first-come-first-served queueing discipline, under the single restriction that the probability generating function for the interarrival-time distribution be rational. Furthermore, treating several special cases we rediscover a number of well-known results, such as Hunter's result for theG/Geo/1 model. Finally, as an illustration of the generality of the analysis, it is applied to the derivation of the waiting time and the delay of the more generalG ^(G)/G/1 model and the system contents of a multi-server buffer-system with independent arrivals and random output interruptions.Both authors wish to thank the Belgian National Fund for Scientific Research (NFWO) for support of this work.     

多重休假GI／G／1排队系统的非统计平衡理论

文献[1]引入了一类具有广泛应用前景的随机过程-Markov骨架过程，文献[2]研究了GI/G/1排队系统，本文对其进行了拓展，研究了多重休假GI/G/1排队模型。求出了此模型的到达过程，等待时间及队长的概率分布。