Polling systems and multitype branching processes

The joint queue length process in polling systems with and without switchover times is studied. If the service discipline in each queue satisfies a certain property it is shown that the joint queue length process at polling instants of a fixed queue is a multitype branching process (MTBP) with immigration. In the case of polling models with switchover times, it turns out that we are dealing with an MTBP with immigration in each state, whereas in the case of polling models without switchover times we are dealing with an MTBP with immigration in state zero. The theory of MTBPs leads to expressions for the generating function of the joint queue length process at polling instants. Sufficient conditions for ergodicity and moment calculations are also given.This work was done while the author was at the Centre for Mathematics and Computer Science (CWI) in Amsterdam, The Netherlands.     

On the stability of retrial queues

We consider the following Type of problems. Calls arrive at a queue of capacity K (which is called the primary queue), and attempt to get served by a single server. If upon arrival, the queue is full and the server is busy, the new arriving call moves into an infinite capacity orbit, from which it makes new attempts to reach the primary queue, until it finds it non-full (or it finds the server idle). If the queue is not full upon arrival, then the call (customer) waits in line, and will be served according to the FIFO order. If λ is the arrival rate (average number per time unit) of calls and μ is one over the expected service time in the facility, it is well known that μ > λ is not always sufficient for stability. The aim of this paper is to provide general conditions under which it is a sufficient condition. In particular, (i) we derive conditions for Harris ergodicity and obtain bounds for the rate of convergence to the steady state and large deviations results, in the case that the inter-arrival times, retrial times and service times are independent i.i.d. sequences and the retrial times are exponentially distributed; (ii) we establish conditions for strong coupling convergence to a stationary regime when either service times are general stationary ergodic (no independence assumption), and inter-arrival and retrial times are i.i.d. exponentially distributed; or when inter-arrival times are general stationary ergodic, and service and retrial times are i.i.d. exponentially distributed; (iii) we obtain conditions for the existence of uniform exponential bounds of the queue length process under some rather broad conditions on the retrial process. We finally present conditions for boundedness in distribution for the case of nonpatient (or non persistent) customers. This revised version was published online in June 2006 with corrections to the Cover Date.     

IPP+M/M／C排队的遍历性(英文)

The IP P＋M/M/c queueing system has been extensively used in the modern communication system.The existence and uniqueness of stationary distribution of the queue length L（t）for IP P＋M/M/1 queue has been proved in[10].In this paper,we shall give the su？cient and necessary conditions of l-ergodicity,geometric ergodicity,and prove that they are neither uniformly polynomial ergodicity nor strong ergodicity.     

一般形式的连续时间拟生灭过程各种遍历性判定准则

侯振挺、李晓花在 [1]已经讨论了具有某些特殊形式的拟生灭过程各种遍历性 ,我们将在此基础讨论一般形式连续时间拟生灭过程各种遍历性 ,并给出 [1]中连续时间拟生灭过程的指数遍历及多项式遍历的一个新证明 ,该证明给出了具有某些特殊条件下连续时间拟生灭过程遍历性与离散时间拟生灭过程遍历性之间关系 .     

Ergodicity of a polling network with an infinite number of stations

A Markov polling system with infinitely many stations is studied. The topic is the ergodicity of the infinite-dimensional process of queue lengths. For the infinite-dimensional process, the usual type of ergodicity cannot prevail in general and we introduce a modified concept of ergodicity, namely, weak ergodicity. It means the convergence of finite-dimensional distributions of the process. We give necessary and sufficient conditions for weak ergodicity. Also, the “usual” ergodicity of the system is studied, as well as convergence of functionals which are continuous in some norm. This revised version was published online in June 2006 with corrections to the Cover Date.     

Analysis of a dynamic assignment of impatient customers to parallel queues

Consider a number of parallel queues, each with an arbitrary capacity and multiple identical exponential servers. The service discipline in each queue is first-come-first-served (FCFS). Customers arrive according to a state-dependent Poisson process. Upon arrival, a customer joins a queue according to a state-dependent policy or leaves the system immediately if it is full. No jockeying among queues is allowed. An incoming customer to a parallel queue has a general patience time dependent on that queue after which he/she must depart from the system immediately. Parallel queues are of two types: type 1, wherein the impatience mechanism acts on the waiting time; or type 2, a single server queue wherein the impatience acts on the sojourn time. We prove a key result, namely, that the state process of the system in the long run converges in distribution to a well-defined Markov process. Closed-form solutions for the probability density function of the virtual waiting time of a queue of type 1 or the offered sojourn time of a queue of type 2 in a given state are derived which are, interestingly, found to depend only on the local state of the queue. The efficacy of the approach is illustrated by some numerical examples.     

带负顾客和N-策略的Geo^{lambda_1, lambda_2/Geo/1(MWV)排队系统分析及最优控制策略N*

分析了一个带有负顾客、N-策略控制的Geo/Geo/1多重工作休假排队系统, 其中正顾客在工作休假及正规忙期以不同的到达率进入系统. 利用拟生灭过程和矩阵几何解方法, 给出了该模型的稳态队长分布及平均队长, 以及系统分别处于假期和忙期的概率. 同时, 对该系统的忙期进行了分析, 并讨论了稳态队长分布在系统容量的优化设计中的应用. 最后, 在给定的费用结构下, 用数值计算例子确定了使系统长期单位时间内期望费用最小的最优控制策 N*.     

N策略工作休假M/M/1排队

考虑策略工作休假M/M/1排队,简记为M/M/1(N-WV)。在休假期间,服务员并未完全停止工作而是以较低的速率为顾客服务。用拟生灭过程和矩阵几何解方法,我们给出了有直观概率意义的稳态队长和稳态条件等待时间的分布。此外,我们也得到了队长和等待时间的条件随机分解结构及附加队长和附加延迟的分布。     

M/G/1非空竭服务休假排队系统的平衡条件分析

讨论了一般非空竭服务M/G/1型休假排队系统的嵌入更新过程常返的条件,为稳态队长与等待时间的随机分解奠定理论基础.并且在独立休假策略下进一步简化Fuhrman与Cooper(1985)休假排队系统的随机分解的条件,并得到完整的随机分解结构.     

延迟Min(N,D)-策略的M/G/1排队系统的队长分布与数值计算

考虑延迟Min(N, D)-策略的M/G/1排队系统. 运用更新过程理论、全概率分解技术和Laplace变换工具, 从任意初始状态出发, 研究了队长的瞬态和稳态性质, 获得了瞬态队长分布的Laplace变换的递推表达式和稳态队长分布的递推表达式, 同时求出了附加队长分布的显示表达式. 进一步讨论了当N \to \infty, 或D \to \infty, 或N=1且P{Y=0}=1, 或P{Y=0}=1时的特殊情形. 最后通过数值实例, 讨论了稳态队长分布对系统参数的敏感性, 并阐述了稳态队长分布的表达式在系统容量优化设计中的重要价值.     

假期中顾客以概率θ进人的Geo/G/1(E,SV)排队系统的队长分布

考虑单重休假的Geo/G/1离散时间排队系统,其中在服务员休假期间到达的顾客以概率θ(0<θ≤1)进入系统.通过引入"服务员忙期"和使用全概率分解技术,从任意初始状态出发,研究了队长的瞬态和稳态性质,导出了在任意时刻n瞬态队长分布的z-变换的递推表达式和稳态队长分布的递推表达式,以及稳态队长的随机分解.最后,通过数值实例,讨论了稳态队长分布对系统参数的敏感性,并阐述了获得便于计算的稳态队长分布的表达式在系统容量设计中有重要的价值.     

The tightness in the ergodic analysis of regenerative queueing processes

The tightness of some queueing stochastic processes is proved and its role in an ergodic analysis is considered. It is proved that the residual service time process in an open Jackson-type network is tight. The same problem is solved for a closed network, where the basic discrete time process is embedded at the service completion epochs. An extention of Kiefer and Wolfowitz's “key” lemma to a nonhomogeneous multiserver queue with an arbitrary initial state is obtained. These results are applied to get the ergodic theorems for the basic regenerative network processes. This revised version was published online in June 2006 with corrections to the Cover Date.     

Explicit Convergence Rates of the Embedded M/G/1 Queue

This paper investigates the explicit convergence rates to the stationary distribution π of the embedded M/G/1 queue; specifically, for suitable rate functions r（n） which may be polynomial with r（n） = n^l, l 〉 0 or geometric with r（n） = α^n, a 〉 1 and ＂moments＂ f ≥ 1, we find the conditions under which Σ∞n=0 r（n）｜｜P^n（i,·） - π（·）｜｜f ≤ M（i） for all i ∈ E. For the polynomial case, the explicit bounds on M（i） are given in terms of both ＂drift functions＂ and behavior of the first hitting time on the state O; and for the geometric case, the largest geometric convergence rate α＊ is obtained.     

Ergodicity of the BMAP/PH/s/s+K retrial queue with PH-retrial times

Define the traffic intensity as the ratio of the arrival rate to the service rate. This paper shows that the BMAP/PH/s/s+K retrial queue with PH-retrial times is ergodic if and only if its traffic intensity is less than one. The result implies that the BMAP/PH/s/s+K retrial queue with PH-retrial times and the corresponding BMAP/PH/s queue have the same condition for ergodicity, a fact which has been believed for a long time without rigorous proof. This paper also shows that the same condition is necessary and sufficient for two modified retrial queueing systems to be ergodic. In addition, conditions for ergodicity of two BMAP/PH/s/s+K retrial queues with PH-retrial times and impatient customers are obtained. This revised version was published online in June 2006 with corrections to the Cover Date.     

基于矩阵分析方法的具有双阶段休假的排队系统驱动的流模型性能分析

基于矩阵分析方法研究了具有单重工作休假和多重休假策略M/M/1排队系统驱动的流模型.首先建立了控制该流模型的微分方程组,利用矩阵分析方法,得出了系统平稳库存量的laplace变换(LT)的矩阵阶乘表达式.进而利用LaplaceStieltjes变换(LST)得出了平稳库存量的期望.最后,通过数值例子展示了系统性能指标与参数的关系.     

M/G/∞ with alternating renewal breakdowns

We consider an M/G/ queue where the service station is subject to occasional interruptions which form an alternating renewal process ofup anddown periods. We show that under some natural conditions the random measure process associated with the residual service times of the customers is regenerative in the strict sense, and study its steady state characteristics. In particular we show that the steady state distribution of this random measure is a convolution of two distributions of (independent) random measures, one of which is associated with a standard M/G/ queue.     

Steady state analysis of an M/G/1 queue with two phase service and Bernoulli vacation schedule under multiple vacation policy

This paper examines the steady state behaviour of a batch arrival queue with two phases of heterogeneous service along and Bernoulli schedule vacation under multiple vacation policy, where after two successive phases service or first vacation the server may go for further vacations until it finds a new batch of customer in the system. We carry out an extensive stationary analysis of the system, including existence of stationary regime, queue size distribution of idle period process, embedded Markov chain steady state distribution of stationary queue size, busy period distribution along with some system characteristics.     

On the uniqueness of solutions to the Poisson equations for average cost Markov chains with unbounded cost functions

We consider the Poisson equations for denumerable Markov chains with unbounded cost functions. Solutions to the Poisson equations exist in the Banach space of bounded real-valued functions with respect to a weighted supremum norm such that the Markov chain is geometrically ergodic. Under minor additional assumptions the solution is also unique. We give a novel probabilistic proof of this fact using relations between ergodicity and recurrence. The expressions involved in the Poisson equations have many solutions in general. However, the solution that has a finite norm with respect to the weighted supremum norm is the unique solution to the Poisson equations. We illustrate how to determine this solution by considering three queueing examples: a multi-server queue, two independent single server queues, and a priority queue with dependence between the queues.