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.     

On the GI/M/∞ queue with batch arrivals of constant size

In this note, the GI/M/ queue with batch arrivals of constant sizek is investigated. It is shown that the stationary probabilities that an arriving batch findsi customers in the system can be computed in terms of the corresponding binomial moments (Jordan's formula), which are determined by a recursive relation. This generalizes well-known results by Takács [12] for GI/M/. Furthermore, relations between batch arrival- and time-stationary probabilities are given.     

Asymptotic behavior of the stationary distributions in the GI/PH/c queue with heterogeneous servers

Summary This paper deals with the stablec-server queue with renewal input. The service time distributions may be different for the various servers. They are however all probability distributions of phase type. It is shown that the stationary distribution of the queue length at arrivals has an exact geometric tail of rate , 0<<1. It is further shown that the stationary waiting time distribution at arrivals has an exact exponential tail of decay parameter >0. The quantities and may be evaluated together by an elementary algorithm. For both distributions, the multiplicative constants which arise in the asymptotic forms may be fully characterized. These constants are however difficult to compute in general.This research was supported by the National Science Foundation under Grant Nr. ENG-7908351 and by the Air Force Office of Scientific Research under Grant Nr. AFOSR-77-3236.     

Wiener-Hopf analysis of an M/G/1 queue with negative customers and of a related class of random walks

Two variants of an M/G/1 queue with negative customers lead to the study of a random walkX _n+1=[X _n + _n ]⁺ where the integer-valued _n are not bounded from below or from above, and are distributed differently in the interior of the state-space and on the boundary. Their generating functions are assumed to be rational. We give a simple closed-form formula for , corresponding to a representation of the data which is suitable for the queueing model. Alternative representations and derivations are discussed. With this formula, we calculate the queue length generating function of an M/G/1 queue with negative customers, in which the negative customers can remove ordinary customers only at the end of a service. If the service is exponential, the arbitrarytime queue length distribution is a mixture of two geometrical distributions.Supported by the European grant BRA-QMIPS of CEC DG XIII.     

A sample path analysis of the M t /M t /c queue

The exact transient distribution of the queue length of the M _t /M _t /1 single server queue with timedependent Poisson arrival rate and timedependent exponential service rate was recently obtained by Zhang and Coyle [63] in terms of a solution to a Volterra equation. Their method involved the use of generating functions and complex analysis. In this paper, we present an approach that ties the computation of these transient distributions directly to the random sample path behavior of the M _t /M _t /1 queue. We show the versatility of this method by applying it to the M _t /M _t /c multiserver queue, and indicating how it can be applied to queues with timedependent phase arrivals or timedependent phase service.     

Exact Convergence Rate for the Distributions of GI/M/c/K Queue as K Tends to Infinity

We obtain the exact convergence rate of the stationary distribution ^(K) of the embedded Markov chain in GI/M/c/K queue to the stationary distribution of the embedded Markov chain in GI/M/c queue as K. Similar result for the time-stationary distributions of queue size is also included. These generalize Choi and Kim's results of the case c=1 by nontrivial ways. Our results also strengthen the Simonot's results [5].     

Large Scale and Heavy Traffic Asymptotics for Systems with Unreliable Servers

The asymptotic behaviour of the M/M/n queue, with servers subject to independent breakdowns and repairs, is examined in the limit where the number of servers tends to infinity and the repair rate tends to 0, such that their product remains finite. It is shown that the limiting two-dimensional Markov process corresponds to a queue where the number of servers has the same stationary distribution as the number of jobs in an M/M/ queue. Hence, the limiting model is referred to as the M/M/[M/M/] queue. Its numerical solution is discussed.Next, the behaviour of the M/M/[M/M/] queue is analysed in heavy traffic when the traffic intensity approaches 1. The convergence of the (suitably normalized) process of the number of jobs to a diffusion is proved.     

The M/M/1 queue with inventory, lost sale, and general lead times

We consider an M/M/1 queueing system with inventory under the $(r,Q)$ policy and with lost sales, in which demands occur according to a Poisson process and service times are exponentially distributed. All arriving customers during stockout are lost. We derive the stationary distributions of the joint queue length (number of customers in the system) and on-hand inventory when lead times are random variables and can take various distributions. The derived stationary distributions are used to formulate long-run average performance measures and cost functions in some numerical examples.     

Vacation policies in an M/G/1 type queueing system with finite capacity

This paper deals with a queueing system with finite capacity in which the server passes from the active state to the inactive state each time a service terminates withv customers left in the system. During the active (inactive) phases, the arrival process is Poisson with parameter (₀). Denoting byu _n the duration of thenth inactive phase and byx _n the number of customers present at the end of thenth inactive phase, we assume that the bivariate random vectors {(v _n ,x _n ),n 1} are i.i.d. withx _n v+l a.s. The stationary queue length distributions immediately after a departure and at an arbitrary instant are related to the corresponding distributions in the classical model.     

Flow equivalence and stochastic equivalence in G-networks

G-networks are novel product form queuing networks that, in addition to ordinary customers, contain unusual entities such as negative customers which eliminate normal customers, and triggers that move other customers from some queue to another. Recently we introduced one more special type of customer, a reset, which may be sent out by any server at the end of a service epoch, and that will reset the queue to which it arrives into its steady state when that queue is empty. A reset which arrives to a non-empty queue has no effect at all. The sample paths of a system with resets is significantly different from that of a system without resets, because the arrival of a reset to an empty queue will provoke a finite positive jump in queue length which may be arbitrarily large, while without resets positive jumps are only of size + 1 and they occur only when a positive customer arrives to a queue. In this paper we review this novel model, and then discuss its traffic equations. We introduce the concept of stationary equivalence for queueing models, and of flow equivalence for distinct queueing models. We show that the flow equivalence of two G-networks implies that they are also stationary equivalent. We then show that the stationary probability distribution of a G-network with resets is identical to that of a G-network without resets whose transition probabilities for positive (ordinary) customers has been increased in a specific manner. Our results show that a G-network with resets has the same form of traffic equations and the same joint stationary probability distribution of queue length as that of a G-network without resets.     

On stationary queue length distributions for G/M/s/r queues

Consider aG/M/s/r queue, where the sequence{A _n } _n=– of nonnegative interarrival times is stationary and ergodic, and the service timesS _n are i.i.d. exponentially distributed. (SinceA _n =0 is possible for somen, batch arrivals are included.) In caser < , a uniquely determined stationary process of the number of customers in the system is constructed. This extends corresponding results by Loynes [12] and Brandt [4] forr= (with=ES₀/EA₀<s) and Franken et al. [9], Borovkov [2] forr=0 ors=. Furthermore, we give a proof of the relation min(i, s)¯p(i)=p(i–1), 1ir + s, between the time- and arrival-stationary probabilities¯p(i) andp(i), respectively. This extends earlier results of Franken [7], Franken et al. [9].     

Isometries of symmetric operator spaces associated with AFD factors of typeII and symmetric vector-valued spaces

If is a surjective isometry of the separable symmetric operator spaceE(M, ) associated with the approximately finite-dimensional semifinite factorM and if · _E(M,) is not proportional to · _{L 2}, then there exist a unitary operatorUM and a Jordan automorphismJ ofM such that(x)=UJ(x) for allxME(M, ). We characterize also surjective isometries of vector-valued symmetric spacesF((0, 1), E(M, )).Research supported by the Australian Research Council     

Positive Solutions for a Singular Nonlinear Problem on a Bounded Domain in R 2

For a bounded regular Jordan domain in R ², we introduce and study a new class of functions K() related on its Green function G. We exploit the properties of this class to prove the existence and the uniqueness of a positive solution for the singular nonlinear elliptic equation u+(x,u)=0, in D(), with u=0 on and uC(), where is a nonnegative Borel measurable function in ×(0,) that belongs to a convex cone which contains, in particular, all functions (x,t)=q(x)t ^–,>0 with nonnegative functions qK(). Some estimates on the solution are also given.     

Abstract Bott periodicity inKK-theory

We show that the universalC*-algebras KqA and K²A are homotopy equivalent and define abstract analogues of the Bott elements inKK-theory.     

An asymptotic definition of K-groups of automorphisms and a non-Bernoullian counter-example

Summary Let GZⁿ be a group of measure preserving transformations of a Lebesgue space. J. P. Conze [1] has developed an entropy theory for such groups and described a class of groups obeying a form of the Kolmogorov zero-one law called K-groups. A Bernoulli group is a group isomorphic to the group of translates (shifts) of elements of the space with product measure where X _g =X is a probability space. Bernoulli groups are also K-groups. Katznelson and Weiss [3] have shown entropy is a complete invariant for isomorphism classes of Bernoulli groups. We give an asymptotic definition of K-groups in terms of finite -algebras and justify this definition in terms of entropy and Conze's formulation. This definition s used to help us construct a K-group GZ ⁿ that is completely non-Bernoulli, that is one that contains no Bernoulli subgroup.     

A tandem Jackson network with feedback to the first node

AnN-node tandem queueing network with Bernoulli feedback to the end of the queue of thefirst node is considered. We first revisit the single-nodeM/G/1 queue with Bernoulli feedback, and derive a formula forEL(n), the expected queue length seen by a customer at his nth feedback. We show that, asn becomes large,EL(n) tends to /(l ), being the effective traffic intensity. We then treat the entire queueing network and calculate the mean value ofS, the total sojourn time of a customer in theN-node system. Based on these results we study the problem ofoptimally ordering the nodes so as to minimize ES. We show that this is a special case of a general sequencing problem and derive sufficient conditions for an optimal ordering. A few extensions of the serial queueing model are also analyzed. We conclude with an appendix in which we derive an explicit formula for the correlation coefficient between the number of customers seen by an arbitrary arrival to anM/G/1 queue, and the number of customers he leaves behind him upon departure. For theM/M/1 queue this coefficient simply equals the traffic intensity .     

Applications of the zero–one law to problems connected with Cauchy's functional equation

Summary Marek Kuczma's book, entitled An Introduction To The Theory Of Functional Equations And Inequalities, mentions a certain setV ₀ in several places and presents references as to where this set is discussed in the literature. The main result of this paper is a proof of the fact that the setA _M (V ₀)={xV ₀ f(x)>M} is saturated non-measurable for each additive discontinuous functionf and each real numberM. Other results aboutV ₀ are also presented. Connections between measure and category are stressed. The main tool in our proofs is a certain so-called zero–one law and its topological analogue. In addition it is shown that the zero–one law is equivalent to Smital's lemma.     

Calculation of the Steady State Waiting Time Distribution in GI/PH/c and MAP/PH/c Queues

We consider the waiting time (delay) W in a FCFS c-server queue with arrivals which are either renewal or governed by Neuts' Markovian arrival process, and (possibly heterogeneous) service time distributions of general phase-type F _i , with m _i phases for the ith server. The distribution of W is then again phase-type, with m ₁m _c phases for the general heterogeneous renewal case and phases for the homogeneous case F _i =F, m _i =m. We derive the phase-type representation in a form which is explicit up to the solution of a matrix fixed point problem; the key new ingredient is a careful study of the not-all-busy period where some or all servers are idle. Numerical examples are presented as well.     

A Single Server Poisson Input Queue with a Second Optional Channel

Consider an M/G/1 queue such that over and above the first essential service having a general service time distribution, a unit may need a second optional service with another independent general service time. A unit may depart from the system either after the first essential service with probability (1–r) or at the end of the first service may immediately go for a second service with probability r (0r1). This is a generalization of a recent paper considered by Madan [5].     

Boundary Functionals for the Difference of Nonordinary Renewal Processes with Discrete Time

For the difference of nonordinary renewal processes, we find the distribution of the main boundary functionals. For the queuing system D |D |1, we determine the distribution of the number of calls in transient and stationary modes.