Perturbation analysis and optimization of queueing networks

A new time-domain-based approach is developed in this paper for the perturbation analysis of queueing networks. We show that, by observing a single sample path realization of the network trajectory, we can derive sensitivity information of the throughput of the system with respect to various parameters. This information can then be used for the optimization of queueing networks. Numerous experiments as well as analytical results demonstrating the validity of this new approach are given and discussed.     

Performance optimization of queueing systems with perturbation realization

After the intensive studies of queueing theory in the past decades, many excellent results in performance analysis have been obtained, and successful examples abound. However, exploring special features of queueing systems directly in performance optimization still seems to be a territory not very well cultivated. Recent progresses of perturbation analysis (PA) and sensitivity-based optimization provide a new perspective of performance optimization of queueing systems. PA utilizes the structural information of queueing systems to efficiently extract the performance sensitivity information from a sample path of system. This paper gives a brief review of PA and performance optimization of queueing systems, focusing on a fundamental concept called perturbation realization factors, which captures the special dynamic feature of a queueing system. With the perturbation realization factors as building blocks, the performance derivative formula and performance difference formula can be obtained. With performance derivatives, gradient-based optimization can be derived, while with performance difference, policy iteration and optimality equations can be derived. These two fundamental formulas provide a foundation for performance optimization of queueing systems from a sensitivity-based point of view. We hope this survey may provide some inspirations on this promising research topic.     

具有相型服务分布的排队系统的性能灵敏度分析

具有非线数服务分布的排队网络已被广泛应用于许多领域,如通讯网络和管理系统。本文借助于无穷小说矩阵摄动方法,研究了M/PH/1排队系统的稳态性能灵敏度分析问题,给出了性能灵敏度公式,并表明了稳态性能灵敏度很容易通过系统势能进行计算。同时,给出一种计算势能及性能导数的算法。这个算法可直接用于系统的控制与优化,因为它基于分析系统的一条单一样本轨道。最后提供一个数值例子来表明这个算法的应用。     

M/G/1排队系统的性能灵敏度分析

非Markov型排除系统经常被用来作为某些实际工程问题（如通讯网络）的研究模型,对于一般的M／G／1排队系统,本文通过研究其嵌入Markov链,讨论了系统的稳态性能灵敏度分析问题,并给出用嵌入Markov链的势能表示的稳态性能灵敏度公式,由于嵌入Markov链要比描述其系统状态的半Markov过程简单得多,故本文的结果对M／G／1排队系统的性能灵敏度仿真计算及系统的优化,都将带来极大的方便。     

闭排队网络中性能势与无穷小实现因子之间的关系

In this paper,the concept of the infinitesimal realization factor is extended to the parameter-dependent performance functions in closed queueing networks. Then the concepts of realization matrix (its elements are called realization factors) and performance potential are introduced,and the relations between infinitesimal realization factors and these two quantities are discussed. This provides a united framework for both IPA and non IPA approaches. Finally,another physical meaning of the service rate is given.     

Estimating the sojourn time sensitivity in queueing networks using perturbation analysis

The sample path perturbation analysis technique developed earlier for the analysis of throughput sensitivities (Refs. 1–3) is extended to the performance measures involving mean sojourn times of customers. The major features of the sojourn time sensitivity problem are twofold. Firstly, it is a performance associated with servers, and not with customers. Secondly, the average sojourn time in any finite observation period can be a discontinuous function of mean service times when blocking is involved in a system. This discontinuity causes errors which must be accounted for in the estimation of sensitivities. Numerical experiments and analysis validate this method of computation of the sensitivities.This work was supported by the US Office of Naval Research, Contracts N00014-84-K-0465 and N00014-79-C-0776, and by the National Science Foundation, Grant No. ENG-78-15231.     

Decomposable score function estimators for sensitivity analysis and optimization of queueing networks

This paper surveys some recent results and presents some new results on the so-called decomposable and truncated score functions (DSF and TSF) estimators for performance evaluation, sensitivity analysis and optimization of open non-Markovian (non-product) queueing networks. The idea behind the TSF estimators is based on truncation of the score function process, while the idea behind the DSF estimators is to decompose the queueing network into smaller units, calledmodules, such that each module contains several connected queues, and then approximate the unknown quantities by treating these modules as if they were completely independent. In other words, in the DSF estimators we use frequently occurrentlocal regenerative cycles at eachindividual module instead oftrue but seldom occurrentglobal ones of theentire system. Although the local cycles at each module interact with their neighbors, our numerical studies show that typically the contribution from the neighbors is quite small and thus DSF estimators approximate the unknown quantities rather well, in the sense that their bias is reasonably small and the variance is much smaller than that of the standard score function estimators. Both DSF and TSF estimators were implemented in a simulation package, called thequeueing network stabilizer and optimizer (QNSO). This package is suitable for performance evaluation, sensitivity analysis and optimization of general open non-Markovian queueing networks with respect to the parameter vector of an exponential family of distributions.Research supported by the L. Edelstein Research Fund of the Technion — Israel Institute of Technology and École Polytechnique Fédérale de Lausanne, Switzerland.     

Sensitivity analysis in vector optimization

For a vector optimization problem that depends on a parameter vector, the sensitivity analysis of perturbation, proper perturbation, and weak perturbation maps is dealth with. Each of the perturbation maps is defined as a set-valued map which associates to each parameter value the set of all minimal, properly minimal, and weakly minimal points of the perturbed feasible set in the objective space with respect to a fixed ordering cone. Using contingent cones in a finite-dimensional Euclidean space, we investigate the relationship between the contingent derivatives of the three types of perturbation maps and three types of minimal point sets for the contingent derivative of the feasible-set map in the objective space. These results provide quantitative informations on the behavior of the perturbation maps.The authors would like to thank the referees for their valuable comments and suggestions.     

加权线性支持向量分类机的数据扰动分析

加权线性支持向量分类机是数据挖掘的新方法.它对应于一个优化问题.针对加权线性支持向量分类机优化问题建立了数据扰动分析理论方法.具体地针对加权线性支持向量分类机的原始问题建立了数据扰动分析基本定理,定理可以得到加权线性支持向量分类机问题的解及决策函数对数据参数的偏导数,同时可以定量分析输入数据的误差以及数据各种变化对其解以及决策函数值的定量影响,可以回答加权线性支持向量分类机问题的稳定性问题和灵敏度分析问题.