A tandem of discrete-time queues with arrivals and departures at each stage

A discrete-time system of a tandem of queues with exogenous arrivals and departures at each stage is considered. A customer leaving queuek–1 departs the system with probability 1– ^[k] and continues to queuek with probability ^[k] . Exogenous arrivals to each stage are i.i.d. at each time slot. An approximate analysis of the occupancy and busy-period distributions of each stage based on a General Busy-period with batches and Memoryless (geometric) Idle period renewal Process (GBMIP) provides improved performance over two-state Markov approximations and gives exact results when there are no interstage departures.This research was supported in part by NSF grant NCR-8708282.     

Product form in networks of queues with batch arrivals and batch services

A product form equilibrium distribution is derived for a class of queueing networks in either discrete or continuous time, in which multiple customers arrive simultaneously and batches of customers complete service simultaneously.     

Triggered batch movement in queueing networks

A product form equilibrium distribution is derived for a class of queueing networks, in either discrete or continuous time, in which multiple customers arrive simultaneously, multiple customers complete service simultaneously, and any event occurring in the network can force/trigger the release of multiple customers to be routed through the network.     

Geometric stable distributions in Banach spaces

Geometric stable laws have become an object of attention in recent publications dealing with heavy tailed modeling. Many applications require understanding geometric stable laws on infinite dimensional spaces. This paper studies geometric stable laws on Banach spaces, and their place in the more general family of geometric infinitely divisible laws. Furthermore, we discuss rates of convergence in the domains of attraction of geometric stable laws in Banach spaces.Research was supported by NSF Grant DMS-9103452 and a NATO Scientific Affairs Division Grant CRG 900798. University of California, at Santa Barbara, Santa Barbara, California 93102.Research was supported by ONR Grant N00014-90-J-1287 and United States Israel Binational Science Foundation. School of Operations Research, and Industrial Engineering, Cornell University, Ithaca, New York 14853.     

Autocorrelations in infinite server batch arrival queues

This paper studies an important aspect of queueing theory, autocorrelation properties of system processes. A general infinite server queue with batch arrivals is considered. There areM different types of customers and their arrivals are regulated by a Markov renewal input process. Batch sizes and service times depend on the relevant customer types. With a conditional approach, closed form expressions are obtained for the autocovariance of the continuous time and prearrival system sizes. Some special models are also discussed, giving insights into steady state system behaviour. Autocorrelation functions have a wide range of applications. We highlight one area of application by using autocovariances to derive variances of sample means for a number of special models.This work has been supported by the Natural Sciences and Engineering Council of Canada through Grant A5639 and by the National Natural Science Foundation of China through Grant 19001015.     

On the distributions of infinite server queues with batch arrivals

Queues that feature multiple entities arriving simultaneously are among the oldest models in queueing theory, and are often referred to as “batch” (or, in some cases, “bulk”) arrival queueing systems. In this work, we study the effect of batch arrivals on infinite server queues. We assume that the arrival epochs occur according to a Poisson process, with treatment of both stationary and non-stationary arrival rates. We consider both exponentially and generally distributed service durations, and we analyze both fixed and random arrival batch sizes. In addition to deriving the transient mean, variance, and moment-generating function for time-varying arrival rates, we also find that the steady-state distribution of the queue is equivalent to the sum of scaled Poisson random variables with rates proportional to the order statistics of its service distribution. We do so through viewing the batch arrival system as a collection of correlated sub-queues. Furthermore, we investigate the limiting behavior of the process through a batch scaling of the queue and through fluid and diffusion limits of the arrival rate. In the course of our analysis, we make important connections between our model and the harmonic numbers, generalized Hermite distributions, and truncated polylogarithms.

     

Insensitivity in discrete time queues with a moving server

Queues in which customers request service consisting of an integral number of segments and in which the server moves from service station to service station are of considerable interest to practitioners working on digital communications networks. In this paper, we present insensitivity theorems and thereby equilibrium distributions for two discrete time queueing models in which the server may change from one customer to another after completion of each segment of service. In the first model, exactly one segment of service is provided at each time point whether or not an arrival occurs, while in the second model, at most one arrival or service occurs at each time point. In each model, customers of typet request a service time which consists ofl segments in succession with probabilityb _t(l). Examples are given which illustrate the application of the theorems to round robin queues, to queues with a persistent server, and to queues in which server transition probabilities do not depend on the server's previous position. In addition, for models in which the probability that the server moves from one position to another depends only on the distance between the positions, an amalgamation procedure is proposed which gives an insensitive model on a coarse state space even though a queue may not be insensitive on the original state space. A model of Daduna and Schassberger is discussed in this context.This work was supported by the Australian Research Council.     

An Alternative Model for Queueing Systems with Single Arrivals,Batch Services and Customer Coalescence

In this paper we consider a queueing system with single arrivals, batch services and customer coalescence and we use it as a building block for constructing queueing networks that incorporate such characteristics. Chao et al. (1996) considered a similar model and they proved that it possesses a geometric product form stationary distribution, under the assumption that if the number of units present at a service completion epoch is less than the required number of units, then all the units coalesce into an incomplete (defective) batch which leaves the system. We drop this assumption and we study a model without incomplete batches. We prove that the stationary distribution of such a queue has a nearly geometric form. Using quasi-reversibility arguments we construct a network model with such queues which provides relevant bounds and approximations for the behaviour of assembly processes. Several issues about the validity of these bounds and approximations are also discussed.     

几何分布可靠度的估计

本对几何分布,在可靠度的先验分布为幂分布和截尾幂分布时,给出了可靠度的多层Bayes估计,并给出了数值例。     

几何分布的几个性质

本文给出几何分布与指数分布相同及相异的几个性质．     

On the characterization of departure rules for discrete-time queueing networks with batch movements and its applications

This paper supplements and generalizes the results of sawa [11] in this special issue from the viewpoint of discrete-time networks of queues with batch arrivals and batch departures, due to Henderson and Taylor [7]. We first note that the D-rule of sawa [11] is equivalent to the specific form for the release rate function, introduced in [7]. Such forms have widely appeared in the literature, too. sawa [11] found that the D-rule can be characterized in terms of the reversed-time process of a certain vector-valued process. He obtained this characterization for a single node model. We generalize this result for networks of queues with batch arrivals and batch departures. This reveals why the specific form of the release rate function is common in the literature. Furthermore, the characterization is useful to consider traffic flows in a discrete-time queueing network.This research is partially supported by NEC C&C Laboratories.     

Limit distributions for the bivariate geometric maxima

Limit laws are established for the behavior of (max X _i , max Y _i ) when (X _i , Y _i ) are independent and distributed according to a bivariate geometric distribution.     

Optimal control for parallel queues with a single batch server

We consider a queueing system with multiple Poisson arrival queues and a single batch server that has infinite capacity and a fixed service time. The problem is to allocate the server at each moment to minimize the long-run average waiting cost. We propose a Cost-Arrival Weighted (CAW) policy for this problem based on the structure of the optimal policy of a corresponding fluid model. We show that this simple policy enjoys a superior performance by numerical experiments.     

基于共形几何代数的几何分解及程序实现

本文主要讨论了利用共形几何代数来进行几何定理中的几何构型进行几何分解的算法以及它的程序实现问题.利用这个算法可以给出几何量之间的定量依赖关系.所实现的程序能够给出一些较为复杂的几何命题的自动分解的结果.     

A Characterization of Geometric Distributions Through Conditional Independence

ＡＣｈａｒａｃｔｅｒｉｚａｔｉｏｎｏｆＧｅｏｍｅｔｒｉｃＤｉｓｔｒｉｂｕｔｉｏｎｓＴｈｒｏｕｇｈＣｏｎｄｉｔｉｏｎａｌＩｎｄｅｐｅｎｄｅｎｃｅ黄任燕ＡＣｈａｒａｃｔｅｒｉｚａｔｉｏｎｏｆＧｅｏｍｅｔｒｉｃＤｉｓｔｒｉｂｕｔｉｏｎｓＴｈｒｏｕｇｈＣｏｎ...     

A single machine batch scheduling problem with bounded batch size

We address a single-machine batch scheduling problem to minimize total flow time. Processing times are assumed to be identical for all jobs. Setup times are assumed to be identical for all batches. As in many practical situations, batch sizes may be bounded. In the first setting studied in this paper, all batch sizes cannot exceed a common upper bound. In the second setting, all batch sizes share a common lower bound. An optimal solution consists of the number of batches and their (integer) size. We introduce an efficient solution for both problems.     

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].     

On discrete distributions of orderk

Summary This paper gives some results on calculation of probabilities and moments of the discrete distributions of orderk. Further, a new distribution of orderk, which is called the logarithmic series distribution of orderk, is investigated. Finally, we discuss the meaning of theorder of the distributions. The Institute of Statistical Mathematics