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.     

A Polynomial Factorization Approach for the Discrete Time GIX/>G/1/K Queue

This paper proposes a polynomial factorization approach for queue length distribution of discrete time GI ^X /G/1 and GI _X /G/1/K queues. They are analyzed by using a two-component state model at the arrival and departure instants of customers. The equilibrium state-transition equations of state probabilities are solved by a polynomial factorization method. Finally, the queue length distributions are then obtained as linear combinations of geometric series, whose parameters are evaluated from roots of a characteristic polynomial.     

A duality relation for busy cycles inGI/G/1 queues

Using a generalization of the classical ballot theorem, Niu and Cooper [7] established a duality relation between the joint distribution of several variables associated with the busy cycle inM/G/1 (with a modified first service) and the corresponding joint distribution of several related variables in its dualGI/M/1. In this note, we generalize this duality relation toGI/G/1 queues with modified first services; this clarifies the original result, and shows that the generalized ballot theorem is superfluous for the duality relation.     

Conditional and unconditional distributions forM/G/1 type queues with server vacations

M/G/1 queues with server vacations have been studied extensively over the last two decades. Recent surveys by Boxma [3], Doshi [5] and Teghem [14] provide extensive summary of literature on this subject. More recently, Shanthikumar [11] has generalized some of the results toM/G/1 type queues in which the arrival pattern during the vacations may be different from that during the time the server is actually working. In particular, the queue length at the departure epoch is shown to decompose into two independent random variables, one of which is the queue length at the departure epoch (arrival epoch, steady state) in the correspondingM/G/1 queue without vacations. Such generalizations are important in the analysis of situations involving reneging, balking and finite buffer cyclic server queues. In this paper we consider models similar to the one in Shanthikumar [11] but use the work in the system as the starting point of our investigation. We analyze the busy and idle periods separately and get conditional distributions of work in the system, queue length and, in some cases, waiting time. We then remove the conditioning to get the steady state distributions. Besides deriving the new steady state results and conditional waiting time and queue length distributions, we demonstrate that the results of Boxma and Groenendijk [2] follow as special cases. We also provide an alternative approach to deriving Shanthikumar's [11] results for queue length at departure epochs.     

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.     

Busy Periods of Poisson Arrival Queues with Loss

We consider two queues with loss, one is the finite dam with Poisson arrivals and the other is the M/G/1 queue with impatient customers. We use the method of Kolmogorov's backward differential equation and construct a type of renewal equation to obtain the Laplace transform of busy(or wet) period in both queues. As a consequence, we provide the explicit forms of expected busy periods.     

A sample path relation for the sojourn times in G/G/1−PS systems and its applications

For the single server system under processor sharing (PS) a sample path result for the sojourn times in a busy period is proved, which yields a sample path relation between the sojourn times under PS and FCFS discipline. This relation provides a corresponding one between the mean stationary sojourn times in G/G/1 under PS and FCFS. In particular, the mean stationary sojourn time in G/D/1 under PS is given in terms of the mean stationary sojourn time under FCFS, generalizing known results for GI/M/1 and M/GI/1. Extensions of these results suggest an approximation of the mean stationary sojourn time in G/GI/1 under PS in terms of the mean stationary sojourn time under FCFS. Mathematics Subject Classification (MSC 2000) 60K25· 68M20· 60G17· 60G10 This work was supported by a grant from the Siemens AG.     

Using state reduction for computing steady state vectors in Markov chains ofM/G/1 type

This paper presents a state reduction based algorithm for computing the steady state probability vectors of the embedded Markov chains ofM/G/1 type. The algorithm is based on the use of the notion of a state reduction box for streamlining compution. The computational details are linked directly to the theoretical results developed recently by Grassmann and Heyman [6]. Exploiting these connections and a method given in Neuts [18] for finding theG matrix forPH/PH/1 queues, we also propose an hybrid approach for solvingPH/PH/1 queues. Using several numerical examples, we report our computational experiences and present some observations about the relative merits of these approaches.     

Three Cases of Light-Traffic Insensitivity of the Loss Probability in a GI/G/m/0 Loss System to the Shape of the Service Time Distribution

A GI/G/m/0 loss system is considered. Three cases of light-traffic insensitivity of the loss probability to the shape of the service time distribution, given its first moment, are investigated in a triangle array setting.     

Martingale Methods for Analysing Single-Server Queues

In this paper we presents a martingale method for analysing queues of M/G/1 type, which have been generalised so that the system passes through a series of phases on which the service behaviour may differ. The analysis uses the process embedded at departures to create a martingale, which makes possible the calculation of the probability generating function of the stationary occupancy distribution. Specific examples are given, for instance, a model of an unreliable queueing system, and an example of a queue-length-threshold overload-control system.     

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).     

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.     

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.     

Second moment relationships for waiting times in queueing systems with poisson input

For theM/G/1 queue there are well-known and simple relationships among the second moments of waiting time under the first-in-first-out, last-in-first-out, and random-order-of-service disciplines. This paper points out that these relationships hold in considerably more general settings. In particular, it is shown that these relationships hold forM/G/1 queues with exceptional first service,M/G/1 queues with server vacations, andM/G/1 queues with static priorities.     

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     

A note on the optimality of the N- and D-policies for the M/G/1 queue

This note considers the N- and D-policies for the M/G/1 queue. We concentrate on the true relationship between the optimal N- and D-policies when the cost function is based on the expected number of customers in the system.     

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.     

Cycles through a prescribed vertex set in N-connected graphs

A well-known result of Dirac (Math. Nachr. 22 (1960) 61) says that given n vertices in an n-connected G, G has a cycle through all of them. In this paper, we generalize Dirac's result as follows:Given at most vertices in an n-connected graph G when n3 and , then G has a cycle through exactly n vertices of them.This improves the previous known bound given by Kaneko and Saito (J. Graph Theory 15(6) (1991) 655).     

Busy period analysis of queue: Lattice path approach

In this paper, we find the busy period density of queues in explicit computational form, through lattice path (LP) approach. Both the arrival and service time distributions are approximated by 2-phase Cox distribution C₂, which has a Markovian property enabling us to use LP combinatorics. Since any distribution with rational Laplace–Stieltjes transform (LST) and square coefficient of variation (CV²) lying in [1/2,∞) can be approximated by a C₂([M. Agarwal, K. Sen, B. Borkakaty, Busy period density of queueing system C₃/M/1, Journal of Combinatorics, Information and Systems Sciences 31 (1–4) (2006) 127–161]), the results obtained would be applicable to a very wide class of distributions occurring in real life.