闭排队网络基于并行仿真的灵敏度估计和优化算法

基于Markov性能势理论，对一类闭排队网络的灵敏度估计和优化，建立了一种行之有效的并行仿真算法。采用公共随机数，使所有的处理器使用相同的样本轨道，以减少各个处理器之间的通讯时间。在一台SPMD并行计算机上的仿真实例表明，该并行仿真算法对于闭排队网络的优化能显著地提高运算速度。     

半Markov过程基于性能势的灵敏度分析和性能优化

基于性能势的方法 ,研究了一类半Markov过程 (SMP)的性能灵敏度分析和平均费用下的性能优化问题 .将SMP转化为与之等价的离散时间Markov链 (DTMC) ,利用DTMC的性能势 ,对SMP进行灵敏度分析和性能优化 ,得到了SMP基于DTMC性能势的灵敏度分析公式和最优性方程 .最后给出了一个数值例子以表明该方法的应用 .     

闭排队网络当性能函数与参数相关时的性能灵敏度分析

借助于无穷小矩阵摄动方法, 讨论了一类Markov过程, 其稳态性能关于参数摄动的灵敏度分析问题. 然后研究了闭排队网络的稳态性能灵敏度分析问题, 并在参数相关性能函数的情况下, 给出了网络的几种稳态性能的灵敏度公式. 这些公式表明稳态性能灵敏度很容易通过网络势能进行计算.     

基于分层排队网络模型的分布式系统性能评价

关于并发或分布式系统的性台匕评价是一个广泛研究的课题,提供有效的数学理论工具、直观的模型描述方法和有效的模型分析方法,是系统性能评价所面临的关键问题。传统的性能模型——排队网络模型已很难分析这样复杂的系统,分层排队网络（Layered Queueing Net,LQN）模型是排队网络模型的扩展,可以用来分析相互依赖任务间的冲突。介绍了分层排队网络模型的原理及研究现状,并以DBMS为例,建立了DBMS的分层排队网络模型。     

Benney方程的势对称和不变解

利用微分形式的吴方法计算了Benney方程的势对称及其不变解．由于Benney方程中包含不稳定项和耗散项,使得直接求其不变解较为困难,利用吴一微分特征列算法可大大降低其中确定方程组的计算难度．本文全面讨论了Benney方程不同系数情况下的对称,并且得到了新的势对称,同时利用这些对称求得了相应的不变解,这些解对进一步研究Benney方程所描述的物理现象具有广泛的应用价值．文章表明,对于守恒形式的偏微分方程,可通过其辅助系统求得的势对称来构造其不变解．     

Fokker Planck方程的非古典广义势对称及精确解

分析了Fokker-Planck方程的非古典势对称,通过广义势系统而不是一般势系统求得了这些非古典势对称.文中得到了这些方程的新的对称,同时也得到了伴随系统的新的对称,并用其求出了一些精确解.这些解对进一步研究Fokker-Planck方程所描述的物理现象具有广泛的应用价值.     

基于排队网络的大型网络游戏服务器性能分析

介绍了大型网络游戏的服务器架构,基于架构提出了一个基于闭环排队网络的性能模型.给出了用平均值分析(MVA)求解该模型的算法,以及估计算法所需的性能参数的方法.模拟试验显示出,服务器系统的平均响应时间大致随着用户数量的增多成线性增长.通过模型计算出的结果与实验结果基本一致,从而验证了模型的有效性.     

基于排队网络的网络服务器性能分析与优化

针对网络服务器在用户数量和状态相对复杂情况下无法对服务器性能进行有效分析的问题,提出了一种基于排队网络的服务器性能分析方法。该方法可以有效降低时间复杂度和空间复杂度,使服务器性能分析更加精确,效率更高。实验结果表明,利用该方法对服务器性能进行建模和分析,并根据分析结果对服务器程序进行优化,可以达到合理利用系统资源、提高服务器性能的要求。     

一类具有排队现象的工作流图的性能分析

基于极大代数方法,描述一类具有排队现象的工作流图中AND和XOR的时间逻辑关系.AND逻辑表示输出事件当且仅当输入事件都完成时发生,XOR逻辑表示在数个输入事件中按概率只有一个会发生并导致输出事件的发生.以AND和XOR基本模块构建这类工作流图模型,进行系统的性能分析,并给出顾客输出时间间隔下界的估计方法.通过实例仿真验证了建模、分析方法的可行性和有效性.     

基于离散MMDP信源模型的ATM网络排队性能仿真

该文在建立离散MMDP信源模型的基础上,研究ATM网络排队性能,得出了信元的平均丢失率及平均延迟时间与传输带宽及缓存单元数量的近似关系,从而为连接允许控制（CAC）算法提出了理论依据。     

Characteristics of optimal workload allocation for closed queueing networks

We consider the problem of allocating a given workload among the stations in a multi-server product-form closed queueing network to maximize the throughput. We first investigate properties of the throughput function and prove that it is pseudoconcave for some special cases. Some other characteristics of the optimal workload and its physical interpretation are also provided. We then develop two computational procedures to find the optimum workload allocation under the assumption that the throughput function is pseudoconcave in general. The primary advantage of assuming pseudoconcavity is that, under this assumption, satisfaction of first order necessary conditions is sufficient for optimality. Computational experience with these algorithms provides additional support for the validity of this assumption. Finally, we generalize the solution procedure to accommodate bounds on the workloads at each station.     

Infinitesimal and finite perturbation analysis for queueing networks

The sample-path perturbation analysis technique is extended to include finite (and possibly large) perturbations typically introduced by changes in queue sizes or other parameters. It is shown that there is a natural hierarchy of perturbation analysis which takes care of increasingly large perturbations. Experiments with zero (infinitesimal) and first order (finite) perturbation analysis show that significant accuracy improvement can be obtained with small increase in computational effort.     

Approximation analysis of multi-class closed queueing maintenance networks with a parts inventory system and two-phase Coxian time distributions

We consider a maintenance network where a set of bases is supported by a replacement parts inventory system and a centrally located repair depot. The ordering policy for the parts is the (S, Q) inventory policy. We extended the previous results to the network, where processing times at each node follow a two-phase Coxian distribution. The proposed network was modeled as a multi-class closed queueing network with a synchronization station. To make the analysis of the network computationally tractable, we developed a two-phase approximation method. In the first phase of the method, the proposed network was analyzed with the previous algorithm based on a product-form approximation. In the second phase, a sub-network was again analyzed with the procedure of a product-form approximation method such that the state space of the sub-network was reduced. In the analysis of a sub-network, a recursive method was also used to solve balance equations by exploiting the special structure of the Markov chain. The new algorithm provided a good estimation of the performance measures of interest. In addition to being accurate, the new algorithm is simple and converges rapidly.     

A unified view of product-form approximation techniques for general closed queueing networks

Two major approximate techniques have been proposed for the analysis of general closed queueing networks, namely the aggregation method and Marie's method. The idea of the aggregation technique is to replace a subsystem (a subnetwork) by a flow equivalent single-server with load-dependent service rates. The parameters of the equivalent server are obtained by analyzing the subsystem in isolation as a closed system with different populations. The idea of Marie's method is also to replace a subsystem by an equivalent exponential service station with load-dependent service rates. However, in this case, the parameters of the equivalent server are obtained by analyzing the subsystem in isolation under a load-dependent Poisson arrival process. Moreover, in Marie's case, the procedure is iterative.

In this paper we provide a general and unified view of these two methods. The contributions of this paper are the following. We first show that their common principle is to partition the network into a set of subsystems and then to define an equivalent product-form network. To each subsystem is associated a load-dependent exponential station in the equivalent network. We define a set of rules in order to partition any general closed network with various features such as general service time distributions, pupulation constraints, finite buffers, state-dependent routing. We then show that the aggregation method and Marie's method are two ways of obtaining the parameters of the equivalent network associated with a given partition. Finally, we provide a discussion pertaining to the comparison of the two methods with respect to their accuracy and computational complexity.     

A multi-class closed queueing maintenance network model with a parts inventory system

The system we address is a maintenance network of repairable items where a set of bases is supported by a centrally located repair depot and a consumable replacement parts inventory system. If an item fails, a replacement part must be obtained at the parts inventory system before the failed item enters the repair depot. The ordering policy for the parts is the (S,Q) inventory policy. An approximation method for this system is developed to obtain performance measures such as steady-state probabilities of the number of items at each site and the expected backorders at the parts inventory system. The proposed system is modelled as a multi-class closed queueing network with a synchronization station and analyzed using a product-form approximation method. Particularly, the product-form approximation method is adapted so that the computational effort on estimating the parameters of the equivalent multi-class network is minimized. In analyzing a sub-network, a recursive method is used to solve balance equations by exploiting the special structure of the Markov chain. Numerical tests show that the approximation method provides fairly good estimation of the performance measures of interests.     

Approximate performance modeling and decision making for manufacturing systems: A queueing network optimization framework

In this paper we discuss queueing network methodology as a framework to address issues that arise in the design and planning of discrete manufacturing systems. Our review focuses on three aspects: modeling of manufacturing facilities, performance evaluation and optimization with queueing networks. We describe both open and closed network models and present several examples from the literature illustrating applications of the methodology. We also provide a brief outline of outstanding research issues. The paper is directed towards the practitioner with operations research background and the operations management researcher with interest in this topic.     

A generalized method of moments for closed queueing networks

We introduce a new solution technique for closed product-form queueing networks that generalizes the Method of Moments (MoM), a recently proposed exact algorithm that is several orders of magnitude faster and memory efficient than the established Mean Value Analysis (MVA) algorithm. Compared to MVA, MoM recursively computes higher-order moments of queue lengths instead of mean values, an approach that remarkably reduces the computational costs of exact solutions, especially on models with large numbers of jobs.In this paper, we show that the MoM recursion can be generalized to include multiple recursive branches that evaluate models with different numbers of queues, a solution approach inspired by the Convolution algorithm. Combining the approaches of MoM and Convolution simplifies the evaluation of normalizing constants and leads to large computational savings with respect to the recursive structure originally proposed for MoM.     

闭环Jackson网络的资源利用率分析方法及应用

排队网络是一种常见的对供应链、生产线以及交通系统等进行建模的工具, 可以被用来分析系统中各资源 的利用率, 并对系统结构的设计提供指导. 相比较于利用仿真进行分析, 排队网络可以更快速地得到系统的资源利 用率. 在实际中, 常用闭环Jackson网络来对顾客总数不变的封闭系统进行建模. 在本文中, 首先利用闭环Jackson网 络归一化参数的母函数, 得到了网络中各节点利用率的解析表达式. 通过对利用率解析表达式的分析, 给出了在顾 客总数趋于无穷时利用率的极限, 并证明了利用率是饱和函数. 在这些结论的基础上, 进一步计算不同服务时间下 达到饱和状态所需的顾客总数. 最后将该方法应用于一个实际的自动化码头例子, 将其建模为闭环Jackson网络, 分 析码头的瓶颈所在, 计算系统饱和点对应的车辆数, 并与仿真实验进行了对比.     

Strong consistency of infinitesimal perturbation analysis for tandem queueing networks

Strong consistency of infinitesimal perturbation analysis for the sojourn times in a class of tandem queueing networks is proved. Service times at the queues are correlated, and they are affine functions of the variable parameters. Differentiability of the average sojourn times is not assumed, but proved. The analysis is not based on assumptions of regenerative cycles of the networks but on stability and ergodicity of the queueing processes involved. The proof of strong consistency is based on a set of abstract conditions, described in terms of properties of the sample performance functions. These conditions are first shown to be sufficient for strong consistency, and then their validity for the networks in question is proved.Research supported in part by the NSF under grants Nos. ECS85-15449 and CDR-8803012, under ONR contract nos. N00014-90-K-1093 and N00014-89-J-1023, and under Army contract no. DAAL-03-83-K-0171. This author is now with the Department of Manufacturing Engineering, Boston University, Boston, MA 02215.