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.     

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.     

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.     

Operating characteristics of MX/G/1 queue with N-policy

We consider aM ^X/G/1 queueing system withN-policy. The server is turned off as soon as the system empties. When the queue length reaches or exceeds a predetermined valueN (threshold), the server is turned on and begins to serve the customers. We place our emphasis on understanding the operational characteristics of the queueing system. One of our findings is that the system size is the sum of two independent random variables: one has thePGF of the stationary system size of theM ^X/G/1 queueing system withoutN-policy and the other one has the probability generating function _j=0 ^N=1 _j z ^j/ _j=0 ^N=1 _j , in which _j is the probability that the system state stays atj before reaching or exceedingN during an idle period. Using this interpretation of the system size distribution, we determine the optimal thresholdN under a linear cost structure.     

Simple analysis of a fluid queue driven by an M/M/1 queue

In this note we consider the fluid queue driven by anM/M/1 queue as analysed by Virtamo and Norros [Queueing Systems 16 (1994) 373–386]. We show that the stationary buffer content in this model can be easily analysed by looking at embedded time points. This approach gives the stationary buffer content distribution in terms of the modified Bessel function of the first kind of order one. By using a suitable integral representation for this Bessel function we show that our results coincide with the ones of Virtamo and Norros.     

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.     

On the multi-phase M/G/1 queueing system with random feedback

In this paper we consider an M/G/1 queue with k phases of heterogeneous services and random feedback, where the arrival is Poisson and service times has general distribution. After the completion of the i-th phase, with probability θ _i the (i + 1)-th phase starts, with probability p _i the customer feedback to the tail of the queue and with probability 1 − θ _i − p _i  = q _i departs the system if service be successful, for i = 1, 2 , . . . , k. Finally in kth phase with probability p _k feedback to the tail of the queue and with probability 1 − p _k departs the system. We derive the steady-state equations, and PGF’s of the system is obtained. By using them the mean queue size at departure epoch is obtained.     

A GI/Geo/1 queue with negative and positive customers

The arrival of a negative customer to a queueing system causes one positive customer to be removed if any is present. Continuous-time queues with negative and positive customers have been thoroughly investigated over the last two decades. On the other hand, a discrete-time Geo/Geo/1 queue with negative and positive customers appeared only recently in the literature. We extend this Geo/Geo/1 queue to a corresponding GI/Geo/1 queue. We present both the stationary queue length distribution and the sojourn time distribution.     

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.     

Optimality of D-Policies for an M/G/1 Queue with a Removable Server

We consider an M/G/1 queue with a removable server. When a customer arrives, the workload becomes known. The cost structure consists of switching costs, running costs, and holding costs per unit time which is a nonnegative nondecreasing right-continuous function of a current workload in the system. We prove an old conjecture that D-policies are optimal for the average cost per unit time criterion. It means that for this criterion there is an optimal policy that either runs the server all the time or switches the server off when the system becomes empty and switches it on when the workload reaches or exceeds some threshold D.     

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.     

Performance analysis of discrete-time queue GI/G/1 with negative arrivals

In this paper, we consider a discrete-time GI/G/1 queueing model with negative arrivals. By deriving the probability generating function of actual service time of ordinary customers, we reduced the analysis to an equivalent discrete-time GI/G/1 queueing model without negative arrival, and obtained the probability generating function of buffer contents and random customer delay.     

A repairable Geo X /G/1 retrial queue with Bernoulli feedback and impatient customers

Abstract This paper deals with a discrete-time batch arrival retrial queue with the server subject to starting failures.Diferent from standard batch arrival retrial queues with starting failures,we assume that each customer after service either immediately returns to the orbit for another service with probabilityθor leaves the system forever with probability 1θ(0≤θ1).On the other hand,if the server is started unsuccessfully by a customer(external or repeated),the server is sent to repair immediately and the customer either joins the orbit with probability q or leaves the system forever with probability 1 q(0≤q1).Firstly,we introduce an embedded Markov chain and obtain the necessary and sufcient condition for ergodicity of this embedded Markov chain.Secondly,we derive the steady-state joint distribution of the server state and the number of customers in the system/orbit at arbitrary time.We also derive a stochastic decomposition law.In the special case of individual arrivals,we develop recursive formulae for calculating the steady-state distribution of the orbit size.Besides,we investigate the relation between our discrete-time system and its continuous counterpart.Finally,some numerical examples show the influence of the parameters on the mean orbit size.     

The Virtual Waiting Time of the M/G/1 Queue with Impatient Customers

The M/G/1 queue with impatient customers is studied. The complete formula of the limiting distribution of the virtual waiting time is derived explicitly. The expected busy period of the queue is also obtained by using a martingale argument.     

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.     

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.     

The GI/M/1 queue with Bernoulli-schedule-controlled vacation and vacation interruption

Consider a GI/M/1 queue with multiple vacations. As soon as the system becomes empty, the server either begins an ordinary vacation with probability q  (0?q?1)$(0?q?1)$ or takes a working vacation with probability 1-q$1-q$. We assume the vacation interruption is controlled by Bernoulli. If the system is non-empty at a service completion instant in a working vacation period, the server can come back to the normal busy period with probability p  (0?p?1)$(0?p?1)$ or continue the vacation with probability 1-p$1-p$. Using the matrix-analytic method, we obtain the steady-state distributions for the queue length both at arrival and arbitrary epochs. The waiting time and sojourn time are also derived by different methods. Finally, some numerical examples are presented.     

Queue length and waiting time of the M/G/1 queue under the D-policy and multiple vacations

We study the steady-state queue length and waiting time of the M/G/1 queue under the D-policy and multiple server vacations. We derive the queue length PGF and the LSTs of the workload and waiting time. Then, the mean performance measures are derived. Finally, a numerical example is presented and the effects of employing the D-policy are discussed. AMS Subject Classifications 60K25 This work was supported by the SRC/ERC program of MOST/KOSEF grant # R11-2000-073-00000.     

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.     

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.