Departures from queues with changeover times

We consider the M/M ^ij /1 queue as a model of queues with changeover times, i.e., the service is exponential with parameter _ij depending on the previous job type (i) and the current job type (j). It is shown that the departure process is renewal and Poisson iff _ij = (constant). In this case, types of departures are dependent renewal processes. Crosscovariance and crosscorrelations are given.     

Sojourn time problems in feedback queues

A brief survey of the literature on sojourn time problems in single node feedback queueing systems is presented. The derivation of the distribution and moments of the sojourn time of a typical customer in a Markov renewal queue with state dependent feedback is considered in depth. The techniques used relate to the derivation of a first passage time distribution in a particular Markov renewal process. These results are applied to birth-death queues with state dependent feedback. For such models an alternative approach using the theory of Markov chains in continuous time is also examined.     

多重休假GI／G／1排队系统的非统计平衡理论

文献[1]引入了一类具有广泛应用前景的随机过程-Markov骨架过程，文献[2]研究了GI/G/1排队系统，本文对其进行了拓展，研究了多重休假GI/G/1排队模型。求出了此模型的到达过程，等待时间及队长的概率分布。     

GI／G／1单重休假随机服务系统的马氏骨架方法

文献[1]引入一类具有广泛应用前景的随机过程-Markov骨架过程。借助Markov骨架过程的方法研究GI/G/1单重休假服务系统队长，及t时刻到达顾客等待时间的瞬时概率分布。     

The GI/M/1 queue with exponential vacations

In this paper, we give a detailed analysis of the GI/M/1 queue with exhaustive service and multiple exponential vacation. We express the transition matrix of the imbedded Markov chain as a block-Jacobi form and give a matrix-geometric solution. The probability distribution of the queue length at arrival epochs is derived and is shown to decompose into the distribution of the sum of two independent random variables. In addition, we discuss the limiting behavior of the continuous time queue length processes and obtain the probability distributions for the waiting time and the busy period.     

On single-server closed queues with priorities and state dependent parameters

A wide class of closed single-channel queues is considered. The more general model involvesm +w + 1 “permanent” customers that occasionally require service. Them customers are of the first priority and the rest are of the second priority. The input rate and service of customers depend upon the total number of customers waiting for service. Such a system can also be described in terms of servicing machines processes with reserve replacement and multi-channel queues with finite waiting room. Two dual models, with and without idle periods, are treated. An explicit relation between the servicing processes of both models is derived. The semi-regenerative techniques originally developed in the author's earlier work [4] are extended and used to derive the probability distribution of the processes in equilibrium. Applications and examples are discussed. This paper is a part of work supported by the National Science Foundation under Grant No. DMS-8706186.     

Delay moments for FIFO GI/GI/s queues

For stable FIFO GI/GI/s queues, s ≥ 2, we show that finite (k+1)st moment of service time, S, is not in general necessary for finite kth moment of steady-state customer delay, D, thus weakening some classical conditions of Kiefer and Wolfowitz (1956). Further, we demonstrate that the conditions required for E[D ^k]<∞ are closely related to the magnitude of traffic intensity ρ (defined to be the ratio of the expected service time to the expected interarrival time). In particular, if ρ is less than the integer part of s/2, then E[D] < ∞ if E[S^3/2]<∞, and E[D^k]<∞ if E[S^k]<∞, ^k≥ 2. On the other hand, if s-1 < ρ < s, then E[D^k]<∞ if and only if E[S^k+1]<∞, k ≥ 1. Our method of proof involves three key elements: a novel recursion for delay which reduces the problem to that of a reflected random walk with dependent increments, a new theorem for proving the existence of finite moments of the steady-state distribution of reflected random walks with stationary increments, and use of the classic Kiefer and Wolfowitz conditions. This revised version was published online in June 2006 with corrections to the Cover Date.     

Relationships between characteristics in periodic Poisson queues

We study single server periodic queues in the day equilibrium conditions. The following characteristics of interest are considered at time of dayt: V^p(t)-the work load, L^p(t)-the number of customers and u^p(t)-the departure rate. We give relationships between E[V^p(t)], E[L^p(t)] and u^p(t). We also prove that E[V^p(t)] < and E[L^p(t)] < provided the second moment of the service time is finite.     

Monotonicity properties in various retrial queues and their applications

We consider several multi-server retrial queueing models with exponential retrial times that arise in the literature of retrial queues. The effect of retrial rates on the behavior of the queue length process is investigated via sample path approach. We show that the number of customers in orbit and in the system as a whole are monotonically changed if the retrial rates in one system are bounded by the rates in second one. The monotonicity results are applied to show the convergence of generalized truncated systems that have been widely used for approximating the stationary queue length distribution in retrial queues. AMS subject classifications: Primary 60K25     

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.     

Sojourn times in queues with instantaneous tri-route decision process

In this paper, we study the total sojourn time in a queueing system with an instantaneous tri-route decision process. Even though the computations are more difficult, we give here the structure of the sojourn time process for the M/G/1 queue with tri-route decision process. A numerical study is carried out in this paper.     

Single-server queues with spatially distributed arrivals

Consider a queueing system where customers arrive at a circle according to a homogeneous Poisson process. After choosing their positions on the circle, according to a uniform distribution, they wait for a single server who travels on the circle. The server's movement is modelled by a Brownian motion with drift. Whenever the server encounters a customer, he stops and serves this customer. The service times are independent, but arbitrarily distributed. The model generalizes the continuous cyclic polling system (the diffusion coefficient of the Brownian motion is zero in this case) and can be interpreted as a continuous version of a Markov polling system. Using Tweedie's lemma for positive recurrence of Markov chains with general state space, we show that the system is stable if and only if the traffic intensity is less than one. Moreover, we derive a stochastic decomposition result which leads to equilibrium equations for the stationary configuration of customers on the circle. Steady-state performance characteristics are determined, in particular the expected number of customers in the system as seen by a travelling server and at an arbitrary point in time.     

空竭服务多重休假的离散时间GI/G/1重试排队系统

考虑带有空竭服务多重休假的离散时间GI/G/1重试排队系统,其中重试空间中顾客的重试时间和服务台的休假时间均服从几何分布.通过矩阵几何方法,给出了该系统的一系列性能分析指标.最终利用逼近的方法得到了部分数值结果,并通过算例说明主要的参数变化对系统人数的影响.     

服务台休假的GI/Geom/1离散时间排队

本文研究了具有位相型休假、位相型启动和单重几何休假的离散时间排队,假定 顾客到达间隔服从一般分布,服务时间服从几何分布,运用矩阵解析方法我们得到了这 些排队系统中顾客在到达时刻稳态队长分布及其随机分解.     

Computational analysis of single-server bulk-arrival queues: GIX/M/1

This paper deals with numerical computations for the bulk-arrival queueing modelGI ^X/M/1. First an algorithm is developed to find the roots inside the unit circle of the characteristic equation for this model. These roots are then used to calculate both the moments and the steady-state distribution of the number of customers in the system at a pre-arrival epoch. These results are used to compute the distribution of the same random variable at post-departure and random epochs. Unifying the method used by Easton [7], we have extended its application to the special cases where the interarrival time distribution is deterministic or uniform, and to cases whereX has a given arbitrary distribution. We also improved on the various root-finding methods used by several previous authors so that high values of the parameters, in particular large batch sizes, can be investigated as well.     

Optimal multithreshold control for a BMAP/G/1 queue with N service modes

This paper deals with the problem of the optimal service rate control in the system with BMAP (Batch Markovian Arrival Process) arrival stream. An algorithm for the computation of the embedded stationary queue length distribution is developed. The procedure for the cost criteria calculation is elaborated for any fixed parameters of the multithreshold control policy. This revised version was published online in June 2006 with corrections to the Cover Date.     

Single-Server Queue with Markov-Dependent Inter-Arrival and Service Times

In this paper we study a single-server queue where the inter-arrival times and the service times depend on a common discrete time Markov chain. This model generalizes the well-known MAP/G/1 queue by allowing dependencies between inter-arrival and service times. The waiting time process is directly analyzed by solving Lindley's equation by transform methods. The Laplace–Stieltjes transforms (LST) of the steady-state waiting time and queue length distribution are both derived, and used to obtain recursive equations for the calculation of the moments. Numerical examples are included to demonstrate the effect of the autocorrelation of and the cross-correlation between the inter-arrival and service times. An erratum to this article is available at .     

Representing workloads in GI/G/1 queues through the preemptive-resume LIFO queue discipline

We give in this paper a detailed sample-average analysis of GI/G/1 queues with the preemptive-resume LIFO (last-in-first-out) queue discipline: we study the long-run state behavior of the system by averaging over arrival epochs, departure epochs, as well as time, and obtain relations that express the resulting averages in terms of basic characteristics within busy cycles. These relations, together with the fact that the preemptive-resume LIFO queue discipline is work-conserving, imply new representations for both actual and virtual delays in standard GI/G/1 queues with the FIFO (first-in-first-out) queue discipline. The arguments by which our results are obtained unveil the underlying structural explanations for many classical and somewhat mysterious results relating to queue lengths and/or delays in standard GI/G/1 queues, including the well-known Bene's formula for the delay distribution in M/G/l. We also discuss how to extend our results to settings more general than GI/G/1.     

M/G1/1型可修排队的强度守恒律分析

用从平稳点过程和Palm分布理论推得的强度守恒律尝试研究了寿命为一般分布的M／G1／1型可修排队系统,在求得模型稳态工作量和拟虚等待时间表达式的基础上,得到了服务台的首次故障前时间,系统可用度,平均失效概率,服务台平均失效次数和系统故障频度等．有趣的是,当寿命分布取其特例指数分布时,与文选中已知的结果完全一致．     

The M/G/1 FIFO Queue with Several Customer Classes

In this note we present short derivations of the joint queue length distribution in the M/G/1 queue with several classes of customers and FIFO service discipline.