Response times in gated M/G/1 queues: The processor-sharing case

A class of single server queues with Poisson arrivals and a gated server is considered. Whenever the server becomes idle the gate separating it from the waiting line opens, admitting all the waiting customers into service, and then closes again. The batch admitted into service may be served according to some arbitrary scheme. The equilibrium waiting time distribution is provided for the subclass of conservative schemes with arbitrary service times and the processor-sharing case is treated in some detail to produce the equilibrium time-in-service and response time distributions, conditional on the length of required service. The LIFO and random order of service schemes and the case of compound Poisson arrivals are treated briefly as examples of the effectiveness of the proposed method of analysis. All distributions are provided in terms of their Laplace transforms except for the case of exponential service times where the L.T. of the waiting time distribution is inverted. The first two moments of the equilibrium waiting and response times are provided for most treated cases and in the exponential service times case the batch size distribution is also presented.     

GI~X/M~b/1/N排队系统

本文主要研究了顾客一般独立批到达、指数批服务、缓冲器容量有限的单个服务器的排队系统，本文首先使用补充变量和嵌入马氏链的方法，在部分拒绝和全部拒绝情形下，得到系统排队队长的稳态分布，进而得到相应的性能指标，如系统的平均排队长、平均等待时间、损失概率等．其次对等待时间进行了分析．     

Analysis of a buffer queueing problem in discrete time

We consider a queueing system with bulk arrivals entering a finite waiting room. Service is provided by a single server according to the limited service discipline with server vacation times. We determine the distributions of the time-dependent and stationary queue length in terms of generating functions by a symbolic operator method.     

Vacations in GI X/M Y/1 systems and Riemann boundary value problems

We consider systems of GI/M/1 type with bulk arrivals, bulk service and exponential server vacations. The generating functions of the steady-state probabilities of the embedded Markov chain are found in terms of Riemann boundary value problems, a necessary and sufficient condition of ergodicity is proved. Explicit formulas are obtained for the case where the generating function of the arrival group size is rational. Resonance between the vacation rate and the system is studied. Complete formulas are given for the cases of single and geometric arrivals. This revised version was published online in June 2006 with corrections to the Cover Date.     

Concavity of the conditional mean sojourn time in the <Emphasis Type="Italic">M</Emphasis>/<Emphasis Type="Italic">G</Emphasis>/1 processor-sharing queue with batch arrivals

Avrachenkov et al. (Queueing Syst. 50:459–480, [2005]) conjectured that in an M/G/1 processor-sharing queue with batch arrivals, the conditional mean sojourn time is concave. In this paper, we show that this conjecture is generally not true. This work was supported by the Korea Research Foundation Grant funded by the Korean Government (MOEHRD) (KRF-2006-312-C00470).     

Analysis of the MAP/G a ,b /1/N Queue

The Markovian arrival process (MAP) is used to represent the bursty and correlated traffic arising in modern telecommunication network. In this paper, we consider a single server finite capacity queue with general bulk service rule in which arrivals are governed by MAP and service times are arbitrarily distributed. The distributions of the number of customers in the queue at arbitrary, post-departure and pre-arrival epochs have been obtained using the supplementary variable and the embedded Markov chain techniques. Computational procedure has been given when the service time distribution is of phase type.     

Analysis of finite-buffer multi-server queues with group arrivals: GIX/M/c/N

In this paper, we analyse a multi-server queue with bulk arrivals and finite-buffer space. The interarrival and service times are arbitrarily and exponentially distributed, respectively. The model is discussed with partial and total batch rejections and the distributions of the numbers of customers in the system at prearrival and arbitrary epochs are obtained. In addition, blocking probabilities and waiting time analyses of the first, an arbitrary and the last customer of a batch are discussed. Finally, some numerical results are presented. This revised version was published online in June 2006 with corrections to the Cover Date.     

Processor-sharing queues: Some progress in analysis

This paper reviews some recent results based on new techniques used in the analysis of main processor-sharing queueing systems. These results include the solutions of the problems of determining the sojourn time distributions and the distributions of the number of jobs in the M/G/1/t8 queue under egalitarian and feedback (foreground-background) processor-sharing disciplines. A brief discussion of some related results is also given.     

Two queues with vastly different arrival rates and processor-sharing factors

We consider a 2-class queueing system, operating under a generalized processor-sharing discipline. The arrival rate to the secondary queue is much smaller than that to the primary queue, while the exponentially distributed service requirements have comparable parameters. The primary queue is assumed to be heavily loaded, so the processor-sharing factor for the secondary queue is assumed to be relatively small. We use singular perturbation analyses in a small parameter measuring the ratio of arrival rates, and the closeness of the system to instability. Two different regimes are analyzed, corresponding to a heavily loaded and a lightly loaded secondary queue, respectively. With suitable scaling of variables, lowest order asymptotic approximations to the joint stationary distribution of the numbers of jobs in the two queues are derived, as well as to the marginal distributions.     

Queue-length and waiting-time distributions of discrete-time GI X/Geom/ 1 queueing systems with early and late arrivals

In this paper, we give a unified approach to solving discrete-time GI ^X/Geom/ 1 queues with batch arrivals. The analysis has been carried out for early- and late-arrival systems using the supplementary variable technique. The distributions of numbers in systems at prearrival epochs have been expressed in terms of roots of associated characteristic equations. Furthermore, distributions at arbitrary as well as outside observer's observation epochs have been obtained using the relation derived in this paper. We also present delay analyses for both the systems. Numerical results are presented for various interarrival-time and batch-size distributions. This revised version was published online in June 2006 with corrections to the Cover Date.     

The conditional sojourn time distribution in the GI/M/1 processor-sharing queue in heavy traffic

We treat the GI/M/1 queue with a processor-sharing server, in the heavy traffic case. Using perturbation methods, we construct asymptotic expansions for the conditional sojourn time distribution of a tagged customer conditioned on the tagged customer's service time. The resulting approximation is simple in form and involves only the first three moments of the interarrival time distribution.     

A General Decomposition Algorithm for Parallel Queues with Correlated Arrivals

Queueing with correlated arrivals occurs when customers arrive at a set of queues simultaneously. The difficulty in analyzing systems with correlated arrivals is due to the fact that the individual queueing systems are stochastically dependent. Exact methods for analyzing these systems are computationally intensive and are limited to only a few special cases. In this paper, we consider a system of parallel queues with bulk service and correlated arrivals. We show how the matrix-geometric approach can be used to obtain the performance measures of the system. We also develop an algorithm for large systems that efficiently approximates the performance measures by decomposing it into individual queueing systems. Finally, we describe how the principles of our decomposition algorithm can be extended to analyze a variety of different parallel queueing systems with correlated arrivals. We then evaluate the accuracy of our algorithm through a numerical study.     

The discrete-time MAP/PH/1 queue with multiple working vacations

We consider a discrete-time single-server queueing model where arrivals are governed by a discrete Markovian arrival process (DMAP), which captures both burstiness and correlation in the interarrival times, and the service times and the vacation duration times are assumed to have a general phase-type distributions. The vacation policy is that of a working vacation policy where the server serves the customers at a lower rate during the vacation period as compared to the rate during the normal busy period. Various performance measures of this queueing system like the stationary queue length distribution, waiting time distribution and the distribution of regular busy period are derived. Through numerical experiments, certain insights are presented based on a comparison of the considered model with an equivalent model with independent arrivals, and the effect of the parameters on the performance measures of this model are analyzed.     

Algorithmic methods for multi-server queues with group arrivals and exponential services

We discuss algorithms for the computation of the steady-state features of the c-server queue with exponential service times and bounded group arrivals. While our methods are valid for general interarrival time distributions, we treat in detail the simplifications obtained by using a distribution of phase type. Oueue length densities at times prior to arrivals and at arbitrary times are obtained in a modified matrix-geometric form. Their means and variances are found in computationally tractable forms. We also present algorithmic methods for the waiting time and the virtual waiting time distributions of a customer in a group and obtain the means and variances of these distributions in tractable forms. Numerical examples show that the effects of changing various parameters of the queuing model may so be examined at a small computational cost.     

Moment inequalities for the discrete-time bulk service queue

For the discrete-time bulk service queueing model, the mean and variance of the steady-state queue length can be expressed in terms of moments of the arrival distribution and series of the zeros of a characteristic equation. In this paper we investigate the behaviour of these series. In particular, we derive bounds on the series, from which bounds on the mean and variance of the queue length follow. We pay considerable attention to the case in which the arrivals follow a Poisson distribution. For this case, additional properties of the series are proved leading to even sharper bounds. The Poisson case serves as a pilot study for a broader range of distributions.     

On the M/G/1 foreground-background processor-sharing queue

We consider the M/G/1 queue under the foreground-background processor-sharing discipline. Using a result on the stationary distribution of the total number of customers we give a direct derivation of the distribution of the random counting measure representing the steady state of the queue in all detail.This work was done during a sabbatical at INRIA, France.     

Sojourn time distribution in a MAP/M/1 processor-sharing queue

This paper considers the sojourn time distribution in a processor-sharing queue with a Markovian arrival process and exponential service times. We show a recursive formula to compute the complementary distribution of the sojourn time in steady state. The formula is simple and numerically feasible, and enables us to control the absolute error in numerical results. Further, we discuss the impact of the arrival process on the sojourn time distribution through some numerical examples.     

Analysis of a finite MAP/G/1 queue with group services

The finite capacity queues, GI/PH/1/N and PH/G/1/N, in which customers are served in groups of varying sizes were recently introduced and studied in detail by the author. In this paper we consider a finite capacity queue in which arrivals are governed by a particular Markov renewal process, called a Markovian arrival process (MAP). With general service times and with the same type of service rule, we study this finite capacity queueing model in detail by obtaining explicit expressions for (a) the steady-state queue length densities at arrivals, at departures and at arbitrary time points, (b) the probability distributions of the busy period and the idle period of the server and (c) the Laplace-Stieltjes transform of the stationary waiting time distribution of an admitted customer at points of arrivals. Efficient algorithmic procedures for computing the steady-state queue length densities and other system performance measures when services are of phase type are discussed. An illustrative numerical example is presented.     

Computation of the quasi-stationary distributions inM(n)/GI/1/K andGI/M(n)/1/K queues

In this paper, we provide numerical means to compute the quasi-stationary (QS) distributions inM/GI/1/K queues with state-dependent arrivals andGI/M/1/K queues with state-dependent services. These queues are described as finite quasi-birth-death processes by approximating the general distributions in terms of phase-type distributions. Then, we reduce the problem of obtaining the QS distribution to determining the Perron-Frobenius eigenvalue of some Hessenberg matrix. Based on these arguments, we develop a numerical algorithm to compute the QS distributions. The doubly-limiting conditional distribution is also obtained by following this approach. Since the results obtained are free of phase-type representations, they are applicable for general distributions. Finally, numerical examples are given to demonstrate the power of our method.     

A recursive method to the optimal control of an M/G/1 queueing system with finite capacity and infinite capacity

We study a single removable server in an infinite and a finite queueing systems with Poisson arrivals and general distribution service times. The server may be turned on at arrival epochs or off at service completion epochs. We present a recursive method, using the supplementary variable technique and treating the supplementary variable as the remaining service time, to obtain the steady state probability distribution of the number of customers in a finite system. The method is illustrated analytically for three different service time distributions: exponential, 3-stage Erlang, and deterministic. Cost models for infinite and finite queueing systems are respectively developed to determine the optimal operating policy at minimum cost.