高负荷情形批处理排队网络的扩散极限理论

在标准排队网络极限理论的基础上，本定义并研究了一类批处理排队网络。利用随机分析的方法，证明了高负荷情形下，各服务台队长的极限扩散存在，并给出了极限扩散的具体形式。     

多类顾客多服务台队列网络的高负荷极限定理

多类顾客多服务台队列网络广泛地应用到计算机网络、通讯网络和交通网络 .由于系统的复杂性 ,其数量指标的精确解很难求出 .为了寻求逼近解 ,本文用概率测度弱收敛理论对进行了研究 ,在高负荷的条件下 ,我们获得了网输入过程、闲时过程和负荷过程的极限定理 .     

一类极限循环连分式的加速收敛因子

本文获得了一类极限循环连分式的加速收敛因子,证明了它们具有良好的加速收敛性质.     

GI／G／1系统队长的极限分布

关于GI／G／1排队系统队长的极限分布存在的一个充分条件被建立．     

半鞅序列积分误差的极限过程的收敛定理

Jacod, Jakubowski和M\'emin讨论了与单个独立增量过程$X$的误差过程$^n\!X =X_t-X_{[nt]/n}$相关的积分误差过程$Y^n(X)$和$Z^{n,p}(X)$, 研究了半鞅序列$\{(nY^n(X),nZ^{n,p}(X))\}_{n\ge 1}$的极限定理. 记半鞅序列$\{(nY^n(X),nZ^{n,p}(X))\}_{n\ge1}$的极限过程为$(Y(X),Z^p(X))$, Jacod等给出了其极限过程$(Y(X)$, $Z^p(X))$的表达式. 本文将研究半鞅序列$\{X^n\}_{n\ge1}$积分误差的极限过程$Y(X^n)$和$Z^{p}(X^n)$的收敛定理, 主要研究半鞅序列$\{(X^n,Y(X^n),Z^p(X^n))\}_{n\ge1}$的依分布弱收敛和依分布稳定收敛.     

GI/G/1排队系统队长的强大数定律和中心极限定理

本文首先证明当服务强度小于1时,GI/G/1排队系统的队长是一个特殊的马尔可夫骨架过程——正常返的Doob骨架过程,然后运用马尔可夫骨架过程的强大数定律和中心极限定理等重要结果,给出了队长的累积过程的期望和方差,并给出了该累积过程满足强大数定律和中心极限定理的充分条件。     

从Riemann积分的定义看推广变量收敛理论的必要性

指出了R iem ann积分定义中积分和的极限已超出了数学分析中变量极限理论的范围,由此看出推广变量极限理论是必要的;简要地介绍了更一般的收敛理论,即网的Moore-Sm ith收敛理论,并通过这种收敛理论给出了定积分的严格定义.     

State space collapse with application to heavy traffic limits for multiclass queueing networks

Heavy traffic limits for multiclass queueing networks are a topic of continuing interest. Presently, the class of networks for which these limits have been rigorously derived is restricted. An important ingredient in such work is the demonstration of state space collapse. Here, we demonstrate state space collapse for two families of networks, first-in first-out (FIFO) queueing networks of Kelly type and head-of-the-line proportional processor sharing (HLPPS) queueing networks. We then apply our techniques to more general networks. To demonstrate state space collapse for FIFO networks of Kelly type and HLPPS networks, we employ law of large number estimates to show a form of compactness for appropriately scaled solutions. The limits of these solutions are next shown to satisfy fluid model equations corresponding to the above queueing networks. Results from Bramson [4,5] on the asymptotic behavior of these limits then imply state space collapse. The desired heavy traffic limits for FIFO networks of Kelly type and HLPPS networks follow from this and the general criteria set forth in the companion paper Williams [41]. State space collapse and the ensuing heavy traffic limits also hold for more general queueing networks, provided the solutions of their fluid model equations converge. Partial results are given for such networks, which include the static priority disciplines. This revised version was published online in June 2006 with corrections to the Cover Date.     

Convergence of a queueing system in heavy traffic with general patience-time distributions

We analyze a sequence of single-server queueing systems with impatient customers in heavy traffic. Our state process is the offered waiting time, and the customer arrival process has a state dependent intensity. Service times and customer patient-times are independent; i.i.d. with general distributions subject to mild constraints. We establish the heavy traffic approximation for the scaled offered waiting time process and obtain a diffusion process as the heavy traffic limit. The drift coefficient of this limiting diffusion is influenced by the sequence of patience-time distributions in a non-linear fashion. We also establish an asymptotic relationship between the scaled version of offered waiting time and queue-length. As a consequence, we obtain the heavy traffic limit of the scaled queue-length. We introduce an infinite-horizon discounted cost functional whose running cost depends on the offered waiting time and server idle time processes. Under mild assumptions, we show that the expected value of this cost functional for the n-th system converges to that of the limiting diffusion process as n tends to infinity.     

Optimal buffer size for a stochastic processing network in heavy traffic

We consider a one-dimensional stochastic control problem that arises from queueing network applications. The state process corresponding to the queue-length process is given by a stochastic differential equation which reflects at the origin. The controller can choose the drift coefficient which represents the service rate and the buffer size b>0. When the queue length reaches b, the new customers are rejected and this incurs a penalty. There are three types of costs involved: A “control cost” related to the dynamically controlled service rate, a “congestion cost” which depends on the queue length and a “rejection penalty” for the rejection of the customers. We consider the problem of minimizing long-term average cost, which is also known as the ergodic cost criterion. We obtain an optimal drift rate (i.e. an optimal service rate) as well as the optimal buffer size b ^*>0. When the buffer size b>0 is fixed and where there is no congestion cost, this problem is similar to the work in Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005). Our method is quite different from that of (Ata, Harrison and Shepp (Ann. Appl. Probab. 15, 1145–1160, 2005)). To obtain a solution to the corresponding Hamilton–Jacobi–Bellman (HJB) equation, we analyze a family of ordinary differential equations. We make use of some specific characteristics of this family of solutions to obtain the optimal buffer size b ^*>0. A.P. Weerasinghe’s research supported by US Army Research Office grant W911NF0510032.     

A reflected fBm limit for fluid models with ON/OFF sources under heavy traffic

We consider a family of non-deterministic fluid models that can be approximated under heavy traffic conditions by a multidimensional reflected fractional Brownian motion (rfBm). Specifically, we prove a heavy traffic limit theorem for multi-station fluid models with feedback and non-deterministic arrival process generated by a large enough number of heavy tailed ON/OFF sources, say N$N$. Scaling in time by a factor r$r$ and in state space conveniently, and letting N$N$ and r$r$ approach infinity (in this order) we prove that the scaled immediate workload process converges in some sense to a rfBm.     

A path-based double projection method for solving the asymmetric traffic network equilibrium problem

In this paper we propose a new iterative method for solving the asymmetric traffic equilibrium problem when formulated as a variational inequality whose variables are the path flows. The path formulation leads to a decomposable structure of the constraints set and allows us to obtain highly accurate solutions. The proposed method is a column generation scheme based on a variant of the Khobotov’s extragradient method for solving variational inequalities. Computational experiments have been carried out on several networks of a medium-large scale. The results obtained are promising and show the applicability of the method for solving large-scale equilibrium problems. This work has been supported by the National Research Program FIRB/RBNE01WBBBB on Large Scale Nonlinear Optimization.     

An efficient algorithm for optimal design of area traffic control with network flows

An equilibrium network design (EQND) is a problem of finding the optimal design parameters while taking into account the route choice of users. This problem can be formulated as an optimization by taking the user equilibrium traffic assignment as a constraint. In this paper, the methods solving the EQND problem with signal settings are investigated via numerical calculations on two example road networks. An efficient algorithm is proposed in which improvement on a locally optimal search by combining the technique of parallel tangents with the gradient projection method is presented. As it shows, the method combines the locally optimal search and globally search heuristic achieved substantially better performance than did those other approaches.     

Extreme and high-level sojourns of the single server queue in heavy traffic

This study characterizes the behavior of large queue lengths in heavy traffic. We show that the distribution of the maximum queue length in a random time interval for a queueing systems in heavy traffic converges to a novel extreme value distribution. We also study the processes that record the times that the queue length exceeds a high level and the cumulative time the queue is above the level. We show that these processes converge in distribution to compound Poisson processes. This revised version was published online in June 2006 with corrections to the Cover Date.     

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.     

Convergence for a family of neural network operators in Orlicz spaces

In this paper, we develop the theory for a family of neural network (NN) operators of the Kantorovich type, in the general setting of Orlicz spaces. In particular, a modular convergence theorem is established. In this way, we study the above family of operators in many instances of useful spaces by a unique general approach. The above NN operators provide a constructive approximation process, in which the coefficients, the weights, and the thresholds of the networks needed in order to approximate a given function f , are known. At the end of the paper, several examples of Orlicz spaces, and of sigmoidal activation functions for which the present theory can be applied, are studied in details.