M/G/1 retrial queueing systems with two types of calls and finite capacity

We consider anM/G/1 priority retrial queueing system with two types of calls which models a telephone switching system and a cellular mobile communication system. In the case that arriving calls are blocked due to the server being busy, type I calls are queued in a priority queue of finite capacityK whereas type II calls enter the retrial group in order to try service again after a random amount of time. In this paper we find the joint generating function of the numbers of calls in the priority queue and the retrial group in closed form. When ₁=0, it is shown that our results are consistent with the known results for a classical retrial queueing system.     

Optimal prices for finite capacity queueing systems

We prove a lower bound on the optimal price for a fairly large class of blocking systems with general arrival and service processes, determine optimal price expressions for M/M/1/m and M/GI/s/s systems, and investigate how optimal prices change with changes in the size of the waiting room and service capacity.     

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.     

An analytic finite capacity queueing network model capturing the propagation of congestion and blocking

Analytic queueing network models often assume infinite capacity queues due to the difficulty of grasping the between-queue correlation. This correlation can help to explain the propagation of congestion. We present an analytic queueing network model which preserves the finite capacity of the queues and uses structural parameters to grasp the between-queue correlation. Unlike pre-existing models it maintains the network topology and the queue capacities exogenous. Additionally, congestion is directly modeled via a novel formulation of the state space of the queues which explicitly captures the blocking phase. The model can therefore describe the sources and effects of congestion.     

半群的拟紧性和不可约性

利用算子半群生成元的边界扰动方法,给出了Banach格上C0半群的拟紧性和不可约性的充分条件.并利用该结果对一串联可修复系统的拟紧性和不可约性进行了研究.     

Two classes of operators with irreducibility and the small and compact perturbations of them

This paper gives the concepts of finite dimensional irreducible operators((FDI) operators)and infinite dimensional irreducible operators((IDI) operators). Discusses the relationships of(FDI)operators,(IDI) operators and strongly irreducible operators((SI) operators) and illustrates some properties of the three classes of operators. Some sufficient conditions for the finite-dimensional irreducibility of operators which have the forms of upper triangular operator matrices are given. This paper proves that every operator with a singleton spectrum is a small compact perturbation of an(FDI) operator on separable Banach spaces and shows that every bounded linear operator T can be approximated by operators in(Σ FDI)(X) with respect to the strong-operator topology and every compact operator K can be approximated by operators in(Σ FDI)(X) with respect to the norm topology on a Banach space X with a Schauder basis, where(ΣFDI)(X) := {T∈B(X) : T=Σki=1Ti, Ti ∈(FDI), k ∈ N}.     

A finite capacity multi-queueing system with priorities and with repeated server vacations

In this paper, we study an M/G/1 multi-queueing system consisting ofM finite capacity queues, at which customers arrive according to independent Poisson processes. The customers require service times according to a queue-dependent general distribution. Each queue has a different priority. The queues are attended by a single server according to their priority and are served in a non-preemptive way. If there are no customers present, the server takes repeated vacations. The length of each vacation is a random variable with a general distribution function. We derive steady state formulas for the queue length distribution and the Laplace transform of the queueing time distribution for each queue.     

对一类等待空间有限的抢占优先权排队的分析

讨论M/M/1抢占优先权排队模型, 且假设低优先权顾客的等待空间有限. 该模型可以用有限位相拟生灭过程来描述. 由矩阵解析方法, 对该拟生灭过程进行了分析, 并得到排队模型平稳队长的计算公式, 最后还用数值 结果说明了方法的有效性.     

A heavy traffic limit theorem for a class of open queueing networks with finite buffers

We consider a queueing network of d single server stations. Each station has a finite capacity waiting buffer, and all customers served at a station are homogeneous in terms of service requirements and routing. The routing is assumed to be deterministic and hence feedforward. A server stops working when the downstream buffer is full. We show that a properly normalized d-dimensional queue length process converges in distribution to a fd-dimensional semimartingale reflecting Brownian motion (RBM) in a d-dimensional box under a heavy traffic condition. The conventional continuous mapping approach does not apply here because the solution to our Skorohod problem may not be unique. Our proof relies heavily on a uniform oscillation result for solutions to a family of Skorohod problems. The oscillation result is proved in a general form that may be of independent interest. It has the potential to be used as an important ingredient in establishing heavy traffic limit theorems for general finite buffer networks. This revised version was published online in June 2006 with corrections to the Cover Date.     

On the optimal design of tandem queueing systems with finite buffers

We consider tandem queueing systems that can be formulated as a continuous-time Markov chain, and investigate how to maximize the throughput when the queue capacities are limited. We consider various constrained optimization problems where the decision variables are of one or more of the following types: (1) expected service times, (2) queue capacities, and (3) the number of servers at the respective stations. After surveying our previous studies of this kind, we open up consideration of three new problems by presenting some numerical results that should give some insight into the general form of the optimal design.     

Some algorithms for discrete time queues with finite capacity

We consider a discrete time queue with finite capacity and i.i.d. and Markov modulated arrivals. Efficient algorithms are developed to calculate the moments and the distributions of the first time to overflow and the regeneration length. Results are extended to the multiserver queue. Some illustrative numerical examples are provided. This revised version was published online in June 2006 with corrections to the Cover Date.     

Bounding blocking probabilities and throughput in queueing networks with buffer capacity constraints

We propose a new technique for upper and lower bounding of the throughput and blocking probabilities in queueing networks with buffer capacity constraints, i.e., some buffers in the network have finite capacity. By studying the evolution of multinomials of the state of the system in its assumed steady state, we obtain constraints on the possible behavior of the system. Using these constraints, we obtain linear programs whose values upper and lower bound the performance measures of interest, namely throughputs or blocking probabilities. The main advantages of this new technique are that the computational complexity does not increase with the size of the finite buffers and that the technique is applicable to systems in which some buffers have infinite capacity. The technique is demonstrated on examples taken from both manufacturing systems and communication networks. As a special case, for the M/M/s/s queue, we establish the asymptotic exactness of the bounds, i.e., that the bounds on the blocking probability asymptotically approach the exact value as the degree of the multinomials considered is increased to infinity. This revised version was published online in June 2006 with corrections to the Cover Date.     

Optimal inventory replenishment policy for a queueing system with finite waiting room capacity

We treat an inventory control problem in a facility that provides a single type of service for customers. Items used in service are supplied by an outside supplier. To incorporate lost sales due to service delay into the inventory control, we model a queueing system with finite waiting room and non-instantaneous replenishment process and examine the impact of finite buffer on replenishment policies. Employing a Markov decision process theory, we characterize the optimal replenishment policy as a monotonic threshold function of reorder point under the discounted cost criterion. We present a simple procedure that jointly finds optimal buffer size and order quantity.     

扩散方程保正的有限体积格式

在大变形网格上数值求解多介质扩散方程时, 如何构造具有保正性的扩散格式一直是人们关注的难题. 本文将简要综述与保正性相关的扩散格式的研究历史, 并为解决这一难题提出新的设计途径,构造出新的具有较高精度的单元中心型守恒保正格式, 它们可兼顾网格几何变形和物理量变化. 本文将给出数值实验结果, 验证新格式在变形的网格上保持非负性.     

Massively time-parallel,approximate simulation of loss queueing systems

A time-parallel simulation obtains parallelism by partitioning the time domain of the simulation. An approximate time-parallel simulation algorithm named GG1K is developed for acyclic networks of loss FCFSG/G/1/K queues. The GG1K algorithm requires two phases. In the first phase, a similar system (i.e. aG/G/1/ queue) is simulated using the GLM algorithm. Then the resultant trajectory is transformed into an approximateG/G/1/K trajectory in the second phase. The closeness of the approximation is investigated theoretically and experimentally. Our results show that the approximation is highly accurate except whenK is very small (e.g. 5) in certain models. The algorithm exploits unbounded parallelism and can achieve near-linear speedup when the number of arrivals simulated is sufficiently large.     

On finite capacity queues with time dependent arrival rates

We consider the finite capacity M/M/1−K$M/M/1-K$ queue with a time dependent arrival rate λ(t)$\lambda \left(t\right)$. Assuming that the capacity K$K$ is large and that the arrival rate varies slowly with time (as t/K$t/K$), we construct asymptotic approximations to the probability of finding n$n$ customers in the system at time t$t$, as well as the mean number. We consider various time ranges, where the system is nearly empty, nearly full, or is filled to a fraction of its capacity. Extensive numerical studies are used to back up the asymptotic analysis.