Performance analysis of MAP/G/1 queue with working vacations and vacation interruption

We consider the MAP/G/1 queue with working vacations and vacation interruption. We obtain the queue length distribution with the method of supplementary variable, combined with the matrix-analytic method and censoring technique. We also obtain the system size distribution at pre-arrival epoch and the Laplace–Stieltjes transform (LST) of waiting time.     

基于最大熵的延迟启动/关闭N策略M/G/1可修排队稳态队长分布

研究具有延迟启动-关闭的N策略M/G/1可修排队系统,利用最大熵方法导出稳态队长分布的解析解,进一步得到基于最大熵的顾客平均等待时间.通过比较顾客的平均等待时间来检验最大熵方法的精度,结果表明基于最大熵方法得到的稳态队长分布是相当精确的.     

N-策略单重休假M/G/1排队系统的队长分布

本文考虑N-策略单重休假M/G/1排队系统,通过引进"服务员忙期"和使用全概率分解技术,从任意初始状态出发,研究了队长的瞬态分布和稳态分布,首次导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式,以及平稳队长的随机分解.特别地,通过本文可直接获得一些特殊排队系统相应的结果.     

On the Queue Length Distribution for the GI/G/1/K/VM Queue

Abstract

We present a transform-free distribution of the steady-state queue length for the GI/G/1/K queueing system with multiple vacations under exhaustive FIFO service discipline. The method we use is a modified supplementary variable technique and the result we obtain is expressed in terms of conditional expectations of the remaining service time, the remaining interarrival time, and the remaining vacation, conditional on the queue length at the embedded points. The case K → ∞ is also considered.     

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.     

Stationary tail probabilities in exponential server tandems with renewal arrivals

The problem considered is that of estimating the tail stationary probability for two exponential server queues in series fed by renewal arrivals. We compute the tail of the marginal queue length distribution at the second queue. The marginal at the first queue is known by the classical result for the GI/M/1 queue. The approach involves deriving necessary and sufficient conditions on the paths of the arrival and virtual service processes in order to get a large queue size at the second queue. We then use large deviations estimates of the probabilities of these paths, and solve a constrained convex optimization problem to find the most likely path leading to a large queue size. We find that the stationary queue length distribution at the second queue has an exponentially decaying tail, and obtain the exact rate of decay.Research supported in part by NSF grant NCR 88-57731 and the AT & T Foundation.     

对M/T-SPH/1排队平稳指标的进一步研究—数值计算与渐近分析

讨论M/T-SPH/1排队平稳队长分布的数值计算,以及平稳队长和逗留时间分布各阶矩的数值计算及渐近分析.其中T-SPH表示可数状态吸收生灭链吸收时间的分布.在分布PGF和LST的基础上,首先给出了计算平稳队长分布,平稳队长以及逗留时间分布各阶矩的数值结果的递推公式.其次还讨论了平稳队长及平稳逗留时间分布各阶矩的尾部渐近...     

带有Bernoulli反馈的多级适应性休假的Geo/G/1排队系统分析

考虑带有Bernoulli反馈的多级适应性休假的Geo/G/1离散时间排队系统.通过引入服务员忙期和使用一种简洁的分解方法,讨论了队长的瞬时分布,得到了在任意时刻n队长为j的概率关于时刻n的z-变换的递推式,及队长平稳分布的递推式,且证明了稳态队长的随机分解性质.最后,给出了在特殊情形下相应的一些结果和数值计算实例.     

A MAP/G/1 Queue with Negative Customers

In this paper, we consider a MAP/G/1 queue with MAP arrivals of negative customers, where there are two types of service times and two classes of removal rules: the RCA and RCH, as introduced in section 2. We provide an approach for analyzing the system. This approach is based on the classical supplementary variable method, combined with the matrix-analytic method and the censoring technique. By using this approach, we are able to relate the boundary conditions of the system of differential equations to a Markov chain of GI/G/1 type or a Markov renewal process of GI/G/1 type. This leads to a solution of the boundary equations, which is crucial for solving the system of differential equations. We also provide expressions for the distributions of stationary queue length and virtual sojourn time, and the Laplace transform of the busy period. Moreover, we provide an analysis for the asymptotics of the stationary queue length of the MAP/G/1 queues with and without negative customers.     

Performance of an ATM multiplexer queue in the fluid approximation using the Beneš approach

This paper describes a new method for evaluating the queue length distribution in an ATM multiplexer assuming the cell arrival process can be assimilated to a variable rate fluid input. The method is based on a result due initially to Bene allowing the analysis of queues with general input. Its extension to fluid input systems is considered here in the case of a superposition of on/off sources. We derive an upper bound on the complementary queue length distribution. The method is most easily applied in the case of Poisson burst arrivals (infinite sources model). In this case, we derive analytic expressions for the tail of the queue length distribution. A corrective factor is deduced to convert the upper bounds to good approximations. Numerical results justify the accuracy of the method and demonstrate the impact of certain traffic characteristics on queue performance.     

Decay rate for a PH/M/2 queue with shortest queue discipline

In this paper, we consider a PH/M/2 queue in which each server has its own queue and arriving customers join the shortest queue. For this model, it has been conjectured that the decay rate of the tail probabilities for the shortest queue length in the steady state is equal to the square of the decay rate for the queue length in the corresponding PH/M/2 model with a single queue. We prove this fact in the sense that the tail probabilities are asymptotically geometric when the difference of the queue sizes and the arrival phase are fixed. Our proof is based on the matrix analytic approach pioneered by Neuts and recent results on the decay rates. AMS subject classifications: 60K25 · 60K20 · 60F10 · 90B22     

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.     

N-策略M/G/1/∞排队系统的队长分布表达式

本文考虑N-策略M／G／1／∞排队系统，研究了队长的瞬态和稳态性质。通过引进“服务员忙期”和使用全概率分解技术，我们导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式，以及平稳队长的随机分解。特别地，通过本文可直接获得一些特殊排队系统相应的结果。     

On the steady-state queue size distribution of the discrete-timeGeo/G/1 queue with repeated customers

In this paper, we study the steady-state queue size distribution of the discrete-timeGeo/G/1 retrial queue. We derive analytic formulas for the probability generating function of the number of customers in the system in steady-state. It is shown that the stochastic decomposition law holds for theGeo/G/1 retrial queue. Recursive formulas for the steady-state probabilities are developed. Computations based on these recursive formulas are numerically stable because the recursions involve only nonnegative terms. Since the regularGeo/G/1 queue is a special case of theGeo/G/1 retrial queue, the recursive formulas can also be used to compute the steady-state queue size distribution of the regularGeo/G/1 queue. Furthermore, it is shown that a continuous-timeM/G/1 retrial queue can be approximated by a discrete-timeGeo/G/1 retrial queue by dividing the time into small intervals of equal length and the approximation approaches the exact when the length of the interval tends to zero. This relationship allows us to apply the recursive formulas derived in this paper to compute the approximate steady-state queue size distribution of the continuous-timeM/G/1 retrial queue and the regularM/G/1 queue.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0046415.Partially supported by the Natural Sciences and Engineering Research Council of Canada through grant OGP0105828.     

A BMAP/G/1 Retrial Queue with a Server Subject to Breakdowns and Repairs

In this paper, we consider a BMAP/G/1 retrial queue with a server subject to breakdowns and repairs, where the life time of the server is exponential and the repair time is general. We use the supplementary variable method, which combines with the matrix-analytic method and the censoring technique, to study the system. We apply the RG-factorization of a level-dependent continuous-time Markov chain of M/G/1 type to provide the stationary performance measures of the system, for example, the stationary availability, failure frequency and queue length. Furthermore, we use the RG-factorization of a level-dependent Markov renewal process of M/G/1 type to express the Laplace transform of the distribution of a first passage time such as the reliability function and the busy period.     

推广的单重休假M~x/G/1排队系统

研究了服务前需要重新调整机器的单重休假Mx/G/1排队系统,在LS变换和L变换下得到了服务员忙期中队长的瞬态分布和队长稳态分布的概率母函数.     

The M/G-G/1 Oscillating Queueing System

In this paper oscillating queueing system is studied. Oscillating queueing systems are interesting practical objects and researches in this subject are a natural continuation of previous studies on oscillating stochastic processes. It is shown a powerful method for finding characteristic quantities of queuing systems (potential method). Using this method the steady-state distribution of the length of the queue in the M/G-G/1 oscillating system is found and presented in explicit formula. In addition, a numerical example is given.     

对M/T-SPH/1排队平稳队长的分析

研究了M/T-SPH/l排队模型,利用拟生灭过程和算子几何解的方法给出了平稳队长分布的概率母函数.在此基础上,指出该分布不是一个离散PH分布,但在一定条件下却是一个几何尾部分布.     

推广的多重休假$M^X/G/1$排队系统

在平稳状态下,Baba利用补充变量方法研究了多重休假的MX/G/1排队,但作者假定了休假时间和服务时间都有概率密度函数.本文考虑推广的多重休假MX/G/1排队,在假定休假时间和服务时间都是一般概率分布函数下,我们研究了队长的瞬态和稳态性质.通过引进"服务员忙期"和使用不同于Baba文中使用的分析技术,我们导出了在任意时刻t瞬态队长分布的L变换的递推表达式和稳态队长分布的递推表达式,以及平稳队长的随机分解.特别地,通过本文可直接获得多重休假的M/G/1与标准的MX/G/1排队系统相应的结果.     

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.