An M/G/1 Queueing Model with Gated Random Order of Service

We analyse an M/G/1 queueing model with gated random order of service. In this service discipline there are a waiting room, in which arriving customers are collected, and a service queue. Each time the service queue becomes empty, all customers in the waiting room are put instantaneously and in random order into the service queue. The service times of customers are generally distributed with finite mean. We derive various bivariate steady-state probabilities and the bivariate Laplace–Stieltjes transform (LST) of the joint distribution of the sojourn times in the waiting room and the service queue. The derivation follows the line of reasoning of Avi-Itzhak and Halfin [4]. As a by-product, we obtain the joint sojourn times LST for several other gated service disciplines.     

Software package for the queueing system Mx/G/1

A user-friendly software package, which should be found useful be researchers, practitioners and students alike, for the bulk-arrival single-server queueing system M^x/G/1 is discussed. It finds numerically the steady-state probabilities and moments for the number in the system at each of the three time epochs (pre-arrival, post-departure and random), as well as moments for waiting time in queue and busy and idle periods.     

On the optimal control problem of a single-server queueing system

For a single-server queueing system (with a finite waiting room) with phase type arrivals and exponential service times, an optimal control for the service rate is derived. This generalizes the result of Scott and Jefferson for theM/M/1/1 queueing model.     

Waiting Time Asymptotics in the Single Server Queue with Service in Random Order

We consider the single server queue with service in random order. For a large class of heavy-tailed service time distributions, we determine the asymptotic behavior of the waiting time distribution. For the special case of Poisson arrivals and regularly varying service time distribution with index ?ν, it is shown that the waiting time distribution is also regularly varying, with index 1?ν, and the pre-factor is determined explicitly. Another contribution of the paper is the heavy-traffic analysis of the waiting time distribution in the M/G/1 case. We consider not only the case of finite service time variance, but also the case of regularly varying service time distribution with infinite variance.     

Heavy-traffic limits for many-server queues with service interruptions

We establish many-server heavy-traffic limits for G/M/n+M queueing models, allowing customer abandonment (the +M), subject to exogenous regenerative service interruptions. With unscaled service interruption times, we obtain a FWLLN for the queue-length process, where the limit is an ordinary differential equation in a two-state random environment. With asymptotically negligible service interruptions, we obtain a FCLT for the queue-length process, where the limit is characterized as the pathwise unique solution to a stochastic integral equation with jumps. When the arrivals are renewal and the interruption cycle time is exponential, the limit is a Markov process, being a jump-diffusion process in the QED regime and an O–U process driven by a Levy process in the ED regime (and for infinite-server queues). A stochastic-decomposition property of the steady-state distribution of the limit process in the ED regime (and for infinite-server queues) is obtained.     

Mean Waiting Time Approximations in the G/G/1 Queue

It is known that correlations in an arrival stream offered to a single-server queue profoundly affect mean waiting times as compared to a corresponding renewal stream offered to the same server. Nonetheless, this paper uses appropriately constructed GI/G/1 models to create viable approximations for queues with correlated arrivals. The constructed renewal arrival process, called PMRS (Peakedness Matched Renewal Stream), preserves the peakedness of the original stream and its arrival rate; furthermore, the squared coefficient of variation of the constructed PMRS equals the index of dispersion of the original stream. Accordingly, the GI/G/1 approximation is termed PMRQ (Peakedness Matched Renewal Queue). To test the efficacy of the PMRQ approximation, we employed a simple variant of the TES⁺ process as the autocorrelated arrival stream, and simulated the corresponding TES ⁺/G/1 queue for several service distributions and traffic intensities. Extensive experimentation showed that the proposed PMRQ approximations produced mean waiting times that compared favorably with simulation results of the original systems. Markov-modulated Poisson process (MMPP) is also discussed as a special case.     

Two new heuristics for the <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/<Emphasis Type="Italic">n</Emphasis>/0 queueing loss system with examples based on the two-phase Coxian distribution

In this paper, we introduce a new heuristic approach for the numerical analysis of queueing systems. In particular, we study the general, multi-server queueing loss system, the GI/G/n/0 queue, with an emphasis on the calculation of steady-state loss probabilities. Two new heuristics are developed, called the GM Heuristic and the MG Heuristic, both of which make use of an exact analysis of the corresponding single-server GI/G/1/0 queue. The GM Heuristic also uses an exact analysis of the GI/M/n/0 queue, while the MG Heuristic uses an exact analysis of the M/G/n/0 queue. Experimental results are based on the use of two-phase Coxian distributions for both the inter-arrival time and the service time; these include an error analysis for each heuristic and the derivation of experimental probability bounds for the loss probability. For the class of problems studied, it is concluded that there are likely to be many situations where the accuracy of the GM Heuristic is adequate for practical purposes. Methods are also developed for combining the GM and MG Heuristics. In some cases, this leads to approximations that are significantly more accurate than those obtained by the individual heuristics.     

Uniform approximations for the M/G/1 queue with subexponential processing times

This paper studies the asymptotic behavior of the steady-state waiting time, W _∞, of the M/G/1 queue with Subexponential processing times for different combinations of traffic intensities and overflow levels. In particular, we provide insights into the regions of large deviations where the so-called heavy-traffic approximation and heavy-tail asymptotic hold. For queues whose service time distribution decays slower than \(e^{-\sqrt{t}}\) we identify a third region of asymptotics where neither the heavy-traffic nor the heavy-tail approximations are valid. These results are obtained by deriving approximations for P(W _∞>x) that are either uniform in the traffic intensity as the tail value goes to infinity or uniform on the positive axis as the traffic intensity converges to one. Our approach makes clear the connection between the asymptotic behavior of the steady-state waiting time distribution and that of an associated random walk.     

Comparison conjectures about the M/G/s queue

We conjecture that the equilibrium waiting-time distribution in an M/G/s queue increases stochastically when the service-time distribution becomes more variable. We discuss evidence in support of this conjecture and others based partly on light-traffic and heavy-traffic limits. We also establish an insensitivity property for the case of many servers in light traffic.     

A first passage time problem for spectrally positive Lévy processes and its application to a dynamic priority queue

We study a first passage time problem for a class of spectrally positive Lévy processes. By considering the special case where the Lévy process is a compound Poisson process with negative drift, we obtain the Laplace–Stieltjes transform of the steady-state waiting time distribution of low-priority customers in a two-class M/GI/1$M/GI/1$ queue operating under a dynamic non-preemptive priority discipline. This allows us to observe how the waiting time of customers is affected as the policy parameter varies.     

Approximations for the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">N</Emphasis>+<Emphasis Type="Italic">GI</Emphasis> type call center

In this paper, we propose approximations to compute the steady-state performance measures of the M/GI/N+GI queue receiving Poisson arrivals with N identical servers, and general service and abandonment-time distributions. The approximations are based on scaling a single server M/GI/1+GI queue. For problems involving deterministic and exponential abandon times distributions, we suggest a practical way to compute the waiting time distributions and their moments using the Laplace transform of the workload density function. Our first contribution is numerically computing the workload density function in the M/GI/1+GI queue when the abandon times follow general distributions different from the deterministic and exponential distributions. Then we compute the waiting time distributions and their moments. Next, we scale-up the M/GI/1+GI queue giving rise to our approximations to capture the behavior of the multi-server system. We conduct extensive numerical experiments to test the speed and performance of the approximations, which prove the accuracy of their predictions.      

On the fluid limit of the M/G/∞ queue

The paper deals with the fluid limits of some generalized M/G/∞ queues under heavy-traffic scaling. The target application is the modeling of Internet traffic at the flow level. Our paper first gives a simplified approach in the case of Poisson arrivals. Expressing the state process as a functional of some Poisson point process, an elementary proof for limit theorems based on martingales techniques and weak convergence results is given. The paper illustrates in the special Poisson arrivals case the classical heavy-traffic limit theorems for the G/G/∞ queue developed earlier by Borovkov and by Iglehart, and later by Krichagina and Puhalskii. In addition, asymptotics for the covariance of the limit Gaussian processes are obtained for some classes of service time distributions, which are useful to derive in practice the key parameters of these distributions.     

Asymptotic analysis for loss probability of queues with finite <Emphasis Type="Italic">GI</Emphasis>/<Emphasis Type="Italic">M</Emphasis>/1 type structure

This paper discusses the asymptotic behavior of the loss probability for general queues with finite GI/M/1 type structure such as GI/M/c/K, SM/M/1/K and GI/MSP/1/K queues. We find an explicit expression for the asymptotic behavior of the loss probability as K tends to infinity. With the result, it is shown that the loss probability tends to 0 at a geometric rate. This research was supported by the MIC (Ministry of Information and Communication), Korea, under the ITRC (Information Technology Research Center) support program supervised by the IITA (Institute of Information Technology Assessment).     

The impact of production time variability on make-to-stock queue performance

In this paper, we exploit the distributional Little’s law to obtain the steady-state distribution of the number of customers in a GI/G/1 make-to-stock queueing system. Non-exponential service times in make-to-stock queue modeling are usually avoided or at best, considered in approximations due to difficulties in developing an exact method. By providing a numerical solution of the GI/G/1 make-to-stock queue, we observed the impact of production time variability on optimal inventory control policies. The numerical results prove the degree of errors in the results if an exponential service time distribution were assumed instead of the actual distribution.     

A simple method for computing state probabilities of theM/G/1 andGI/M/1 finite waiting space queues

This paper presents a simple method for computing steady state probabilities at arbitrary and departure epochs of theM/G/1/K queue. The method is recursive and works efficiently for all service time distributions. The only input required for exact evaluation of state probabilities is the Laplace transform of the probability density function of service time. Results for theGI/M/1/K –1 queue have also been obtained from those ofM/G/1/K queue.     

An M/G/1 queue with two phases of service subject to the server breakdown and delayed repair

This paper deals with the steady-state behaviour of an M/G/1 queue with an additional second phase of optional service subject to breakdowns occurring randomly at any instant while serving the customers and delayed repair. This model generalizes both the classical M/G/1 queue subject to random breakdown and delayed repair as well as M/G/1 queue with second optional service and server breakdowns. For this model, we first derive the joint distributions of state of the server and queue size, which is one of chief objectives of the paper. Secondly, we derive the probability generating function of the stationary queue size distribution at a departure epoch as a classical generalization of Pollaczek–Khinchin formula. Next, we derive Laplace Stieltjes transform of busy period distribution and waiting time distribution. Finally, we obtain some important performance measures and reliability indices of this model.     

Equivalence relations in the approximations for the M/G/s/s + r queue

This paper investigates some equivalence relations among previously established approximations for the steady-state distribution in an M/G/s queue with finite waiting spaces. The focus is on four approximations developed by Hokstad [1], Tijms and van Hoorn [2], Miyazawa [3] and Kimura [4]. These approximations have been obtained by completely different approaches and they have different expressions. Equivalence theorems show conditions under which some of the approximations coincide.     

On the GI/M/1/N queue with multiple working vacations—analytic analysis and computation

We consider finite buffer single server GI/M/1 queue with exhaustive service discipline and multiple working vacations. Service times during a service period, service times during a vacation period and vacation times are exponentially distributed random variables. System size distributions at pre-arrival and arbitrary epoch with some important performance measures such as, probability of blocking, mean waiting time in the system etc. have been obtained. The model has potential application in the area of communication network, computer systems etc. where a single channel is allotted for more than one source.     

The N threshold policy for the GI/M/1 queue

We study a GI/M/1 queue with an N threshold policy. In this system, the server stops attending the queue when the system becomes empty and resumes serving the queue when the number of customers reaches a threshold value N. Using the embeded Markov chain method, we obtain the stationary distributions of queue length and waiting time and prove the stochastic decomposition properties.     

An overview of Brownian and non-Brownian FCLTs for the single-server queue

We review functional central limit theorems (FCLTs) for the queue-content process in a single-server queue with finite waiting room and the first-come first-served service discipline. We emphasize alternatives to the familiar heavy-traffic FCLTs with reflected Brownian motion (RBM) limit process that arise with heavy-tailed probability distributions and strong dependence. Just as for the familiar convergence to RBM, the alternative FCLTs are obtained by applying the continuous mapping theorem with the reflection map to previously established FCLTs for partial sums. We consider a discrete-time model and first assume that the cumulative net-input process has stationary and independent increments, with jumps up allowed to have infinite variance or even infinite mean. For essentially a single model, the queue must be in heavy traffic and the limit is a reflected stable process, whose steady-state distribution can be calculated by numerically inverting its Laplace transform. For a sequence of models, the queue need not be in heavy traffic, and the limit can be a general reflected Lévy process. When the Lévy process representing the net input has no negative jumps, the steady-state distribution of the reflected Lévy process again can be calculated by numerically inverting its Laplace transform. We also establish FCLTs for the queue-content process when the input process is a superposition of many independent component arrival processes, each of which may exhibit complex dependence. Then the limiting input process is a Gaussian process. When the limiting net-input process is also a Gaussian process and there is unlimited waiting room, the steady-state distribution of the limiting reflected Gaussian process can be conveniently approximated. This revised version was published online in June 2006 with corrections to the Cover Date.