On the steady-state queue size distribution of the discrete-timeGeo/G/1 queue with repeated customers

In this paper, we study the steady-state queue size distribution of the discrete-timeGeo/G/1 retrial queue. We derive analytic formulas for the probability generating function of the number of customers in the system in steady-state. It is shown that the stochastic decomposition law holds for theGeo/G/1 retrial queue. Recursive formulas for the steady-state probabilities are developed. Computations based on these recursive formulas are numerically stable because the recursions involve only nonnegative terms. Since the regularGeo/G/1 queue is a special case of theGeo/G/1 retrial queue, the recursive formulas can also be used to compute the steady-state queue size distribution of the regularGeo/G/1 queue. Furthermore, it is shown that a continuous-timeM/G/1 retrial queue can be approximated by a discrete-timeGeo/G/1 retrial queue by dividing the time into small intervals of equal length and the approximation approaches the exact when the length of the interval tends to zero. This relationship allows us to apply the recursive formulas derived in this paper to compute the approximate steady-state queue size distribution of the continuous-timeM/G/1 retrial queue and the regularM/G/1 queue.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0046415.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0105828.     

M/G/1 queue with controllable vacations and optimization of vacation policy

We introduce the control parameterN in a common queue M/G/1 with vacations; the end of a global vacation period is controlled by the parameterN. This extension for a queue with vacations is of significance in certain practical cases. In this paper, we find various transient and steady-state results for the queue size, the delay times and the waiting times for the M/G/1 queue with controllable vacations. Finally, we also discuss optimal selection of the control parameter.     

Analysis of a Discrete-Time Finite-Capacity Single-Server Queue with Markovian-Arrival Process and Random-Bulk-Service: D-MAP/G Y /1/M

In this article, we consider a single-server, finite-capacity queue with random bulk service rule where customers arrive according to a discrete-time Markovian arrival process (D-MAP). The model is denoted by D-MAP/G ^Y /1/M where server capacity (bulk size for service) is determined by a random variable Y at the starting point of services. A simple analysis of this model is given using the embedded Markov chain technique and the concept of the mean sojourn time of the phase of underlying Markov chain of D-MAP. A complete solution to the distribution of the number of customers in the D-MAP/G ^Y /1/M queue, some computational results, and performance measures such as the average number of customers in the queue and the loss probability are presented.     

Fluid queue driven by aGI/GI/1 queue

Consider a model consisting of two phases: the GI/GI/1 queue and a buffer which is fed by a fluid arriving from a single-server queue. The fluid output from the GI/GI/1 queue is of the on/off type with on- and off-periods distributed as successive busy and idle periods in the GI/GI/1 queue. The fluid pours out of the buffer at a constant rate. The steady-state performance of this model is studied. We derive the Laplace-Stieltjes transform of the stationary distribution function of the buffer content in the case of the M/GI/1 queue in the first phase. It is shown that this distribution depends on the form of the service-time distribution. Therefore, the replacement of an M/GI/1 queue by an M/M/1 queue is not correct, in general. Continuity estimates are derived in the cast where the buffer is fed from the GI/GI/1 queue. Proceedings of the Seminar on Stability Problems for Stochastic Models, Moscow Russia, 1996, Part II.     

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.     

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.     

Transient solution of anM/M/1 queue with balking

An infinite capacityM/M/1 queue with balking is discussed. Defining the generating function in an unusual and direct way, the time-dependent solution for the system size is obtained elegantly.     

AnM/M/c queue with impatient customers

This paper considers theM/M/c queue in which a customer leaves when its service has not begun within a fixed interval after its arrival. The loss probability can be expressed in a simple formula involving the waiting time probabilities in the standardM/M/c queue. The purpose of this paper is to give a probabilistic derivation of this formula and to outline a possible use of this general formula in theM/M/c retrial queue with impatient customers. This research was supported by the INTAS 96-0828 research project and was presented at the First International Workshop on Retrial Queues, Universidad Complutense de Madrid, Madrid, September 22–24, 1998.     

Maximum Likelihood Estimates and Confidence Intervals of an M/M/R Queue with Heterogeneous Servers

This paper studies maximum likelihood estimates as well as confidence intervals of an M/M/R queue with heterogeneous servers under steady-state conditions. We derive the maximum likelihood estimates of the mean arrival rate and the three unequal mean service rates for an M/M/3 queue with heterogeneous servers, and then extend the results to an M/M/R queue with heterogeneous servers. We also develop the confidence interval formula for the parameter ρ, the probability of empty system P ₀, and the expected number of customers in the system E[N], of an M/M/R queue with heterogeneous servers     

On the Transient Behavior of the M/M/1 and M/M/1/M Queues

This paper gives a transient analysis of the classic M/M/1 and M/M/1/K queues. Our results are asymptotic as time and queue length become simultaneously large for the infinite capacity queue, and as the system’s storage capacity K becomes large for the finite capacity queue. We give asymptotic expansions for p_n(t), which is the probability that the system contains n customers at time t. We treat several cases of initial conditions and different traffic intensities. The results are based on (i) asymptotic expansion of an exact integral representation for p_n(t) and (ii) applying the ray method to a scaled form of the forward Kolmogorov equation which describes the time evolution of p_n(t).     

Asymptotic behaviour of the loss probability of theM/G/1/K andG/M/1/K queues

This paper investigates the asymptotic behaviour of the loss probability of theM / G/1/K and G/M/1/K queues as the buffer size increases. It is shown that the loss probability approaches its limiting value, which depends on the offered load, with an exponential decay in essentially all cases. The value of the decay rate can be easily computed from the main queue parameters. Moreover, the close relation existing between the loss behaviour of the two examined queueing systems is highlighted and a duality concept is introduced. Finally some numerical examples are given to illustrate on the usefulness of the asymptotic approximation.     

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.     

Bayesian prediction inM/M/1 queues

Simple queues with Poisson input and exponential service times are considered to illustrate how well-suited Bayesian methods are used to handle the common inferential aims that appear when dealing with queue problems. The emphasis will mainly be placed on prediction; in particular, we study the predictive distribution of usual measures of effectiveness in anM/M/1 queue system, such as the number of customers in the queue and in the system, the waiting time in the queue and in the system, the length of an idle period and the length of a busy period.     

A unified algorithm for computing the stationary queue length distributions inM(k)/G/1/N and GI/M(k)/1/N queues

An iterative algorithm is developed for computing numerically the stationary queue length distributions in M/G/1/N queues with arbitrary state-dependent arrivals, or simply M(k)/G/1/N queues. The only input requirement is the Laplace-Stieltjes transform of the service time distribution.In addition, the algorithm can also be used to obtain the stationary queue length distributions in GI/M/1/N queues with state-dependent services, orGI/M(k)/1/N, after establishing a relationship between the stationary queue length distributions inGI/M(k)/1/N and M(k)/G/1/N+1 queues.Finally, we elaborate on some of the well studied special cases, such asM/G/1/N queues,M/G/1/N queues with distinct arrival rates (which includes the machine interference problems), andGI/M/C/N queues. The discussions lead to a simplified algorithm for each of the three cases.     

Some results on a generalized M/G/1 feedback queue with negative customers

This paper deals with a generalized M/G/1 feedback queue in which customers are either “positive" or “negative". We assume that the service time distribution of a positive customer who initiates a busy period is G _e (x) and all subsequent positive customers in the same busy period have service time drawn independently from the distribution G _b (x). The server is idle until a random number N of positive customers accumulate in the queue. Following the arrival of the N-th positive customer, the server serves exhaustively the positive customers in the queue and then a new idle period commences. This queueing system is a generalization of the conventional N-policy queue with N a constant number. Explicit expressions for the probability generating function and mean of the system size of positive customers are obtained under steady-state condition. Various vacation models are discussed as special cases. The effects of various parameters on the mean system size and the probability that the system is empty are also analysed numerically. AMS Subject Classification: Primary: 60 K 25 · Secondary: 60 K 20, 90 B 22     

The infinite server queue and heuristic approximations to the multi-server queue with and without retrials

In this paper, properties of the time-dependent state probabilities of theM _t /G/∞ queue, when the queue is assumed to start empty are studied. Those results are compared with corresponding time-dependent results for theM/M/1 queue. Approximation to the time-dependent state probabilities of theM/G/m/m queue by means of the corresponding time-dependent state probabilities of theM/G/∞ queue are discussed. Through a decomposition formula it is shown that the main performance characteristics of the ergodicM/M/m/m+d queue are sums of the corresponding random variables for the ergodicM/M/m/m andM/M/1/1+(d−1) queues, respectively, weighted by the 3-rd Erlang formula (stationary probability of waiting or being lost for theM/M/m/m+d queue). Successful exact and approximation extensions of this kind of decomposition formula to theM/M/m/m+d queue with retrials are presented.     

Continuity of the M/G/c queue

Consider an M/G/c queue with homogeneous servers and service time distribution F. It is shown that an approximation of the service time distribution F by stochastically smaller distributions, say F _n , leads to an approximation of the stationary distribution π of the original M/G/c queue by the stationary distributions π _n of the M/G/c queues with service time distributions F _n . Here all approximations are in weak convergence. The argument is based on a representation of M/G/c queues in terms of piecewise deterministic Markov processes as well as some coupling methods.      

Equilibrium properties of the M/G/1 queue

Summary Various aspects of the equilibrium M/G/1 queue at large values are studied subject to a condition on the service time distribution closely related to the tail to decrease exponentially fast. A simple case considered is the supplementary variables (age and residual life of the current service period), the distribution of which conditioned upon queue length n is shown to have a limit as n. Similar results hold when conditioning upon large virtual waiting times. More generally, a number of results are given which describe the input and output streams prior to large values e.g. in the sense of weak convergence of the associated point processes and incremental processes. Typically, the behaviour is shown to be that of a different transient M/G/1 queueing model with a certain stochastically larger service time distribution and a larger arrival intensity. The basis of the asymptotic results is a geometrical approximation for the tail of the equilibrium queue length distribution, pointed out here for the GI/G/1 queue as well.     

Tail asymptotics of the queue size distribution in the M/M/m retrial queue

We consider an M/M/m retrial queue and investigate the tail asymptotics for the joint distribution of the queue size and the number of busy servers in the steady state. The stationary queue size distribution with the number of busy servers being fixed is asymptotically given by a geometric function multiplied by a power function. The decay rate of the geometric function is the offered load and independent of the number of busy servers, whereas the exponent of the power function depends on the number of busy servers. Numerical examples are presented to illustrate the result.     

An M/G/1-type queuing model with service times depending on queue length

A study is made of an M/G/1-type queuing model in which customers receive one type of service until such time as, at the end of a service, the queue size is found to exceed a given value N, N ≥ 1. Then a second type of service is put into effect and remains in use until the queue size is reduced to a fixed value K, 0 ≤ K ≤ N. Equations are derived for the stationary probabilities both at departure times and at general times. An algorithm is developed that allows the rapid computation of the mean queue length and some important probabilities.