Approximations for multi-server queues: System interpolations

This paper provides a unifying method of generating and/or evaluating approximations for the principal congestion measures in aGI/G/s queueing system. The main focus is on the mean waiting time, but approximations are also developed for the queue-length distribution, the waiting-time distribution and the delay probability for the Poisson arrival case. The approximations have closed forms that combine analytical solutions of simpler systems, and hence they are referred to as system-interpolation approximations or, simply, system interpolations. The method in this paper is consistent with and generalizes system interpolations previously presented for the mean waiting time in theGI/G/s queue.     

M x /G/1 Queue with Multiple Vacations

Abstract

In this article, we study a queueing system M ^x /G/1 with multiple vacations. The probability generating function (P.G.F.) of stationary queue length and its expectation expression are deduced by using an embedded Markov chain of the queueing process. The P.G.F. of stationary system busy period and the probability of system in service state and vacation state also are obtained by the same method. At last we deduce the LST and mean of stationary waiting time in the service order FCFS and LCFS, respectively.     

An investigation of phase-distribution moment-matching algorithms for use in queueing models

Algorithms for matching moments to phase-type distributions are evaluated on the basis of their performance in their intended application, queueing models. The moment-matching algorithms under consideration match two moments to a hyperexponential distribution with balanced means and three moments to a mixture of two Erlang distributions of common order. These algorithms are used to approximate an interarrival-time distribution for a queueing model, and the accuracy of associated performance-measure approximations is then used to evaluate the moment-matching algorithms. Three performance measures are considered, and attention is focussed on the steady-state mean queue length (number in system) of theGI/M/1 queue. Performance-measure approximations are compared to three-moment bounds and performance-measure values arising from hypothetical approximated distributions.     

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 modified vacation model M[x]/G/1 system

This paper studies the operating characteristics of an M^[x]/G/1 queueing system under a modified vacation policy, where the server leaves for a vacation as soon as the system is empty. The server takes at most J vacations repeatedly until at least one customer is found waiting in the queue when the server returns from a vacation. We derive the system size distribution at different points in time, as well as the waiting time distribution in the queue. Further, we derive some important characteristics including the expected length of the busy period and idle period. This shows that the results generalize those of the multiple vacation policy and the single vacation policy M^[x]/G/1 queueing system. Finally, a cost model is developed to determine the optimum of J at a minimum cost. Copyright © 2006 John Wiley & Sons, Ltd.     

Comparative analysis for the N policy M/G/1 queueing system with a removable and unreliable server

In this paper we analyze a single removable and unreliable server in the N policy M/G/1 queueing system in which the server breaks down according to a Poisson process and the repair time obeys an arbitrary distribution. The method of maximum entropy is used to develop the approximate steady-state probability distributions of the queue length in the M/G(G)/1 queueing system, where the second and the third symbols denote service time and repair time distributions, respectively. A study of the derived approximate results, compared to the exact results for the M/M(M)/1, M/E₂(E₃)/1, M/H₂(H₃)/1 and M/D(D)/1 queueing systems, suggest that the maximum entropy principle provides a useful method for solving complex queueing systems. Based on the simulation results, we demonstrate that the N policy M/G(G)/1 queueing model is sufficiently robust to the variations of service time and repair time distributions.     

The discrete-time single-server queue

In this paper we consider the discrete-time single server queueing model with exceptional first service. For this model we cannot define the steady-state waiting-time distribution simply as the limiting distribution of the waiting times, since this limit does not always exist. Instead, we use the Cesaro limit to define the limiting waiting-time distribution. We give an exact relation between the generating functions of the steady-state waiting-time distribution and of the idle-time distribution in the case of general interarrival-time and service-time distributions. Once we have this relation, we can give more explicit results when the generating function of either the interarrival-time distribution or the service-time distribution is rational. We also derive some results on the asymptotic behaviour of the waiting-time distribution.     

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.     

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.     

Delay analysis of extended rtPS for VoIP service in IEEE 802.16e by matrix analytic method

Extended real time polling service (ErtPS) is added to IEEE 802.16e-2005 standards in order for VoIP service to use uplink resources efficiently by considering on/off characteristic of voice source. Recently average queueing delay of ErtPS algorithm for VoIP service was investigated, and it was shown that ErtPS allows to admit more users than UGS algorithm. But we need the probability distribution of queueing delay rather than average queueing delay in order to provide a necessary information for QoS. In this paper we obtain the probability distribution of queueing delay of ErtPS for VoIP service by using the matrix analytic method for the GI/M/1 type and the M/G/1 type matrices in cases of the service time being exponential and deterministic respectively. By applying the results on deterministic service time we find the maximum allowable number of VoIP users with the required constraint on queueing delay. 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).     

Delay and partial system contents for a discrete-time G-D-c queue

We consider a discrete-time multiserver queueing system with infinite buffer size, constant service times of multiple slots and a first-come-first-served queueing discipline. A relationship between the probability distributions of the partial system contents and the packet delay is established. The relationship is general in the sense that it doesn’t require knowledge of the exact nature of the arrival process. By means of the relationship, results for the distribution of the partial system contents for a wide variety of discrete-time queueing models can be transformed into corresponding results for the delay distribution. As a result, a separate full analysis of the packet delay becomes unnecessary.      

Performance analysis of a batch service queue arising out of manufacturing system modelling

In this paper, we present an exact analysis of a queueing system with Poisson arrivals and batch service. The system has a finite numberS of waiting places and a batch service capacityb. A service period is initialized when a service starting thresholda of waiting customers has been reached. The model is denoted accordingly byM/G ^[a,b] /1–S. The motivation for this model arises from manufacturing environments with batch service work stations, e.g. in machines for computer components and chip productions. The method of embedded Markov chain is used for the analysis, whereby a representation of the general service time is obtained via a moment matching approach. Numerical results are shown in order to illustrate the dependency of performance measures on special sets of system parameters. Furthermore, attention is devoted to the issues of starting rules, where performance objectives like short waiting time, small blocking probability and minimal amount of work in progress are taken into account.     

An M/G/1 queue under hysteretic vacation policy with an early startup and un-reliable server

This paper considers the bi-level control of an M/G/1 queueing system, in which an un-reliable server operates N policy with a single vacation and an early startup. The server takes a vacation of random length when he finishes serving all customers in the system (i.e., the system is empty). Upon completion of the vacation, the server inspects the number of customers waiting in the queue. If the number of customers is greater than or equal to a predetermined threshold m, the server immediately performs a startup time; otherwise, he remains dormant in the system and waits until m or more customers accumulate in the queue. After the startup, if there are N or more customers waiting for service, the server immediately begins serving the waiting customers. Otherwise the server is stand-by in the system and waits until the accumulated number of customers reaches or exceeds N. Further, it is assumed that the server breaks down according to a Poisson process and his repair time has a general distribution. We obtain the probability generating function in the system through the decomposition property and then derive the system characteristics     

On Whitt's conjecture for queues in which service times and interarrival times depend linearly and randomly upon waiting times

We consider a modification of the standardG/G/1 queueing system with infinite waiting space and the first-in-first-out discipline in which the service times and interarrival times depend linearly and randomly on the waiting times. In this model the waiting times satisfy a modified version of the classical Lindley recursion. When the waiting-time distributions converge to a proper limit, Whitt [10] proposed a normal approximation for this steady-state limit. In this paper we prove a limit theorem for the steady-state limit of the system. Thus, our result provides a solid foundation for Whitt's normal approximation of the steady-state distribution of the system.Supported in part by a grant from the National Natural Science Foundation of China.     

Computing steady-state queueing-time distributions of single-server queues:GI X /M/1

This paper presents a computationally efficient method to find the steady-state distributions of actual queueing times of the first customer, as well as of a randomly selected customer, of an arrival group for the queueing systemGI ^X /M/1, and hence the queueing-time distribution of a customer for the systemGI/E _X /1. The distribution of virtual queueing time is also obtained. Approximate analysis based on one or more roots is also discussed. Though the exact detailed as well as approximate computations for a variety of interarrival-time distributions such as generalized Erlang, mixed generalized Erlang, hyperexponential, generalized hyperexponential, and deterministic have been carried out, only representative results in the form of tables have been appended. The results obtained should prove useful to queueing theorists, practitioners, and others.     

An M/G/1 queue with cyclic service times

In this paper we consider a single server queue with Poisson arrivals and general service distributions in which the service distributions are changed cyclically according to customer sequence number. This model extends a previous study that used cyclic exponential service times to the treatment of general service distributions. First, the stationary probability generating function and the average number of customers in the system are found. Then, a single vacation queueing system with aN-limited service policy, in which the server goes on vacation after servingN consecutive customers is analyzed as a particular case of our model. Also, to increase the flexibility of using theM/G/1 model with cyclic service times in optimization problems, an approximation approach is introduced in order to obtain the average number of customers in the system. Finally, using this approximation, the optimalN-limited service policy for a single vacation queueing system is obtained.On leave from the Department of Industrial Engineering, Iran University of Science and Technology, Narmak, Tehran 16844, Iran.     

Waiting-time tail probabilities in queues with long-tail service-time distributions

We consider the standardGI/G/1 queue with unlimited waiting room and the first-in first-out service discipline. We investigate the steady-state waiting-time tail probabilitiesP(W>x) when the service-time distribution has a long-tail distribution, i.e., when the service-time distribution fails to have a finite moment generating function. We have developed algorithms for computing the waiting-time distribution by Laplace transform inversion when the Laplace transforms of the interarrival-time and service-time distributions are known. One algorithm, exploiting Pollaczek's classical contourintegral representation of the Laplace transform, does not require that either of these transforms be rational. To facilitate such calculations, we introduce a convenient two-parameter family of long-tail distributions on the positive half line with explicit Laplace transforms. This family is a Pareto mixture of exponential (PME) distributions. These PME distributions have monotone densities and Pareto-like tails, i.e., are of orderx ^–r forr>1. We use this family of long-tail distributions to investigate the quality of approximations based on asymptotics forP(W>x) asx. We show that the asymptotic approximations with these long-tail service-time distributions can be remarkably inaccurate for typicalx values of interest. We also derive multi-term asymptotic expansions for the waiting-time tail probabilities in theM/G/1 queue. Even three terms of this expansion can be remarkably inaccurate for typicalx values of interest. Thus, we evidently must rely on numerical algorithms for determining the waiting-time tail probabilities in this case. When working with service-time data, we suggest using empirical Laplace transforms.     

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     

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.     

A note on conservation laws for a multiclass service queueing system with setup times

This paper derives a conservation law for mean waiting times in a single-server multi-class service queueing system (M ^X/G/1 type queue) with setup times which may be dependent on multiple customer classes and its arrival batch size by using the work decomposition property in the queueing system with vacations.