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.     

Fluid queue driven by anM/M/1 queue

A fluid queue receiving its input from the output of a precedingM/M/1 queue is considered. The input can be characterized as a Markov modulated rate process and the well known spectral decomposition technique can be applied. The novel features in this system relate to the nature of the spectrum, which is shown to be composed of a continuous part and one or two discrete points depending on whether the load of the fluid queue is less or greater than the output to input rate ratio. Explicit expressions of the generalized eigenvectors are given in terms of Chebyshev polynomials of the second kind, and the resolution of unity is determined. The solution for the buffer content distribution is obtained as a simple integral expression. Numerical examples are given.     

A markov-modulated M/M/1 queue with group arrivals

We study anM/M/1 group arrival queue in which the arrival rate, service time distributions and the size of each group arrival depend on the state of an underlying finite-state Markov chain. Using Laplace transforms and matrix analysis, we derive the results for the queue length process, its limit distribution and the departure process. In some special cases, explicit results are obtained which are analogous to known classic results.     

On the area swept under the occupation process of an M/M/1 queue in a busy period

We compute in this paper the distribution of the area swept under the occupation process of an M/M/1 queue during a busy period. For this purpose, we use the expression of the Laplace transform of the random variable established in earlier studies as a fraction of Bessel functions. To get information on the poles and the residues of , we take benefit of the fact that this function can be represented by a continued fraction. We then show that this continued fraction is the even part of an S fraction and we identify its successive denominators by means of Lommel polynomials. This allows us to numerically evaluate the poles and the residues. Numerical evidence shows that the poles are very close to the numbers as . This motivated us to formulate some conjectures, which lead to the derivation of the asymptotic behaviour of the poles and the residues. This is finally used to derive the asymptotic behaviour of the probability survivor function . The outstanding property of the random variable is that the poles accumulate at 0 and its tail does not exhibit a nice exponential decay but a decay of the form for some positive constants c and , which indicates that the random variable has a Weibull-like tail. This revised version was published online in June 2006 with corrections to the Cover Date.     

Fluid model driven by an M/G/1 queue with multiple exponential vacations

This paper studies a fluid model driven by an M/G/1 queue with multiple exponential vacations. By introducing various vacation strategies to the fluid model, we can provide greater flexibility for the design and control of input rate and output rate. The Laplace transform of the steady-state distribution of the buffer content is expressed through the minimal positive solution to a crucial equation. Then the performance measure-mean buffer content, which is independent of the vacation parameter, is obtained. Finally, with some numerical examples, the parameter effect on the mean buffer content is presented.     

Stationary distribution of queue length in G / M / 1 queue with two-stage service policy

We consider a G / M / 1 queue with two-stage service policy. The server starts to serve with rate of μ₁ customers per unit time until the number of customers in the system reaches λ. At this moment, the service rate is changed to that of μ₂ customers per unit time and this rate continues until the system is empty. We obtain the stationary distribution of the number of customers in the system.     

A fluid queue driven by a Markovian queue

We consider an infinite buffer fluid queue receiving its input from the output of a Markovian queue with finite or infinite waiting room. The input is characterized by a Markov modulated rate process. We derive a new approach for the computation of the stationary buffer content. This approach leads to a numerically stable algorithm for which the precision of the result can be given in advance. This revised version was published online in June 2006 with corrections to the Cover Date.     

Asymptotic analysis of the M/G/1 queue with a time‐dependent arrival rate

We consider the M/G/1 queue with an arrival rate λ that depends weakly upon time, as λ = λ(εt) where ε is a small parameter. In the asymptotic limit ε → 0, we construct approximations to the probability p _n(t)that η customers are present at time t. We show that the asymptotics are different for several ranges of the (slow) time scale Τ= εt. We employ singular perturbation techniques and relate the various time scales by asymptotic matching. This revised version was published online in June 2006 with corrections to the Cover Date.     

A direct approach to sojourn times in a busy period of an M/M/1 queue

In this paper we present a direct approach to obtaining joint distributions of various quantities of interest in a busy period in an M/M/1 queue. These quantities are: the sojourn times and waiting times of all the customers in the busy period, the busy period length and the number of customers served in a busy period. Since the evolution of the total workload process between two successive customer arrivals is deterministic, this work gives statistic of the complete evolution of the workload process within a busy period. This work was done when the author was post doctoral fellow with the MAESTRO group at INRIA, Sophia Antipolis, France, and was supported by project no. 2900-IT-1 from the Centre Franco-Indien pour la Promotion de la Recherche Avancee (CEFIPRA).     

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.     

Decompositions of theM/M/1 transition function

Two decompositions are established for the probability transition function of the queue length process in the M/M/1 queue by a simple probabilistic argument. The transition function is expressed in terms of a zero-avoiding probability and a transition probability to zero in two different ways. As a consequence, the M/M/1 transition function can be represented as a positive linear combination of convolutions of the busy-period density. These relations provide insight into the transient behavior and facilitate establishing related results, such as inequalities and asymptotic behavior.     

The PH/PH/1 queue at epochs of queue size change

The PH/PH/1 queue is considered at embedded epochs which form the union of arrival and departure instants. This provides us with a new, compact representation as a quasi-birth-and-death process, where the order of the blocks is the sum of the number of phases in the arrival and service time distributions. It is quite easy to recover, from this new embedded process, the usual distributions at epochs of arrival, or epochs of departure, or at arbitrary instants. The quasi-birth-and-death structure allows for efficient algorithmic procedures. This revised version was published online in June 2006 with corrections to the Cover Date.     

Wiener-Hopf analysis of an M/G/1 queue with negative customers and of a related class of random walks

Two variants of an M/G/1 queue with negative customers lead to the study of a random walkX _n+1=[X _n + _n ]⁺ where the integer-valued _n are not bounded from below or from above, and are distributed differently in the interior of the state-space and on the boundary. Their generating functions are assumed to be rational. We give a simple closed-form formula for , corresponding to a representation of the data which is suitable for the queueing model. Alternative representations and derivations are discussed. With this formula, we calculate the queue length generating function of an M/G/1 queue with negative customers, in which the negative customers can remove ordinary customers only at the end of a service. If the service is exponential, the arbitrarytime queue length distribution is a mixture of two geometrical distributions.Supported by the European grant BRA-QMIPS of CEC DG XIII.     

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 busy period of an M/M/1 queue with balking and reneging

It has been shown by (R.O. Al-Seedy, A.A. El-Sherbiny, S.A. El-Shehawy, S.I. Ammar, Transient solution of the M/M/c queue with balking and reneging, Comput. Math. Appl. 57 (2009) 1280–1285) that a generating function technique can be successfully applied to derive the transient solution for an M/M/c queueing system. In this paper, we further illustrate how this technique can be used to obtain the busy period density function of an M/M/1 queue with balking and reneging. Finally, numerical calculations are presented.     

Busy period analysis of the state dependent M/M/1/K queue

In this paper, we study the transient behavior of a state dependent M/M/1/K queue during the busy period. We derive in closed-form the joint transform of the length of the busy period, the number of customers served during the busy period, and the number of losses during the busy period. For two special cases called the threshold policy and the static policy we determine simple expressions for their joint transform.     

分析M/M/1多重工作休假排队的一种新方法

用一种新方法对经典的M/M/1工作休假排队系统建立模型.对该模型,用无限位相GI/M/1型Markov过程和矩阵解析方法进行分析,不但得到了所讨论排队模型平稳队长分布的具体结果,还给出了平稳状态时服务台具体位于第几次工作休假的概率.这些关于服务台状态更为精确的描述是该排队系统的新结果.     

Analysis of the M/M/1 Queue with Processor Sharing via Spectral Theory

We show in this paper that the computation of the distribution of the sojourn time of an arbitrary customer in a M/M/1 with the processor sharing discipline (abbreviated to M/M/1 PS queue) can be formulated as a spectral problem for a self-adjoint operator. This approach allows us to improve the existing results for this queue in two directions. First, the orthogonal structure underlying the M/M/1 PS queue is revealed. Second, an integral representation of the distribution of the sojourn time of a customer entering the system while there are n customers in service is obtained.     

The GI/M/1 queue with exponential vacations

In this paper, we give a detailed analysis of the GI/M/1 queue with exhaustive service and multiple exponential vacation. We express the transition matrix of the imbedded Markov chain as a block-Jacobi form and give a matrix-geometric solution. The probability distribution of the queue length at arrival epochs is derived and is shown to decompose into the distribution of the sum of two independent random variables. In addition, we discuss the limiting behavior of the continuous time queue length processes and obtain the probability distributions for the waiting time and the busy period.