多类顾客共享排队系统的信息理论

多类顾客的共享排队系统是排队论中一个既重要又困难的研究方向,它在计算机网络、生产制造系统与交通网络等领域中有着许多重要的实际应用.近年来,国外学者对多类顾客的共享排队系统已经开展了一些关键性的研究工作,给出了稳态联合队长的母函数,由此可以得到稳态联合队长的一阶矩和二阶矩.然而,由这个母函数反演来提供多类顾客共享排队系统的稳态联合队长的直接表达式却是一个多年来的困难问题.基于此,本文利用信息论中的最大熵原理,提供了一个高精度的近似表达式,其中这个近似表达式与它的精确表达式能够保证前三阶矩是相同的.另一方面,针对这个近似表达式,本文实现了它的有效数值计算,并通过数值算例分析了这个近似表达式中的重要因子是如何依赖于系统的原始参数.因此这个近似表达式对于推进多类顾客共享排队系统的实际应用具有重要的理论意义,同时本文的方法与结果不仅为研究多类顾客的共享排队系统提供了一条新的重要途径,而且为如何将信息理论应用于排队系统、排队网络以及更一般的随机模型研究提供了理论依据与技术支撑.     

具有优先权的Lu-Kumar排队网络的扩散逼近

对Lu-Kumar排队网络来说,标准的额定负荷条件,即每个工作站的工作强度ρ<1,并不足以保证该排队网络的稳定性,特别是在具有优先权的服务规则下.论文在讨论了Lu-Kumar排队网络稳定性相关结果的基础上,研究了Lu-Kumar排队网络在具有优先权的服务规则下的扩散逼近.证明了当每个工作站的额定负荷ρ→1时,Lu-Kumar排队网络对具有优先权的服务规则的所有优先级别来说,扩散逼近定理均成立.     

延迟Min(N,D)-策略下M/G/1排队系统的离去过程

考虑延迟Min(N, D)-策略下M/G/1排队系统的离去过程.运用全概率分解技术、更新过程理论和Laplace-Stieltjes变换,从任意初始状态出发,讨论在有限区间(0, t]内离去顾客的平均数,给出了离去过程、服务员状态过程和服务员忙期中的服务更新过程之间的关系,该关系揭示了离去过程的随机分解特性,并得到了离去顾客平均数的渐近展开式.在排队网络中,由于一个排队系统的输出即为下游排队系统的输入,希望本文所得结果为排队网络的研究提供有用的信息.     

离散时间Geo~(λ_1,λ_2)/G/1(ES,MV)排队系统离去过程的分解

考虑顾客到达率可变的多重休假Geo/G/1排队系统的离去过程.运用全概率分解,更新过程理论和u-变换,讨论了从任意初始状态出发,在(0⁺,n+,n⁺]中离去顾客的平均数,得到系统在(0+]中离去顾客的平均数,得到系统在(0⁺,n+,n⁺]中离去顾客平均数的瞬态分解表达式,以及其稳态分解结果.揭示了系统离去更新过程的特殊结构:离去更新过程被分解为两部分,一部分是系统服务状态(忙,闲)过程,另一部分是忙期中的服务更新过程,从而简化了对离去过程的研究.在排队网络中,由于一个排队系统的输出即为下游排队系统的输入,因此,本文所得结果对研究排队网络有重要意义.     

复杂网状排队系统的模拟研究

在详细分析网状排队系统特点的基础上,给出了该排队系统的模拟仿真算法,并通过模拟例子,研究了串联、最少人数选择和具有反馈的排队网络等不同情形下网状排队模型的队长、等待时间、停留时间、忙期等各种排队指标的统计特性.所得到的算法设计和统计分析具有灵活性和普遍性,为分析和评价网状排队服务系统提供了一个有力的工具.     

G-极限点集和G-链等价集的研究

根据度量空间中极限点和链等价点的定义,给出度量G-空间中G-极限点和G-链等价点的概念,并在度量G-空间中研究了它们的动力学性质,得到了G-极限点和G-链等价点的一些结果,这些结果丰富了度量G-空间中G-极限点和G-链等价点的理论.     

G-分次环与G-集的冲积(Smash Product)

对任意群G,[1]中研究了G-分次环与可迁有限G-集的冲积.在本文中我们对任意可迁G-集A,讨论了G-分次环R与G-集A的冲积,从而推广了[2][3]中给出的关于G-分次环与群G的冲积的主要结果.     

G-分次环与G-集的冲积(Smash Product)

对任意群G,[1]中研究了G-分次环与可迁有限G-集的冲积.在本文中我们对任意可迁G-集A,讨论了G-分次环R与G-集A的冲积,从而推广了[2][3]中给出的关于G-分次环与群G的冲积的主要结果.     

一个具有随机丢弃分组机制且分组成批到达的GI~X/M/1/N排队系统

利用排队论中输入流稀疏化的方法,在标准的GIX/M/1/N排队系统中嵌入网络交换设备随机丢弃分组的机制,建立了一个具有随机丢弃分组机制的扩充的GIX/M/1/N排队系统,并讨论了该排队系统的分组丢失率、系统利用率、队列长度的均值/方差、平均等待时间等性能评价指标.     

一类Fork-Join排队网络的强逼近

本文借助于强逼近理论,对一类Fork-Join排队网络进行了较为细致的研究,得到了在各种负荷条件下响应时间的强逼近定理.     

Bibliography on G-networks,negative customers and applications

The idea of G-networks with negative arrivals, as well as of the relevant product form solution including non-linear traffic equations, was first published by Erol Gelenbe in 1989. In contrast to classical queues and queueing networks, the arrivals of negative customers which remove customers from a non-empty queue upon their arrival are possible in G-networks. Negative customers with appropriate killing discipline can be used to model breakdowns and to model packet losses, etc., while triggered customer movement can represent control processes in networks. This work presents a bibliography¹ on G-networks, negative customers and the use of G-networks, negative customers and triggers to various performance analysis problems. We hope that we can include a majority of publications on G-networks. This bibliography in the BibTex format and a grouping by various themes is available online from http://www.hit.bme.hu/~do/G-networks/. We would encourage readers and researchers to send information to the author in order to make this bibliography as complete as possible.     

G-networks with multiple classes of signals and positive customers

G-networks are queueing models in which the types of customers one usually deals with in queues are enriched in several ways. In Gnetworks, positive customers are those that are ordinarily found in queueing systems; they queue up and wait for service, obtain service and then leave or go to some other queue. Negative customers have the specific function of destroying ordinary or positive customers. Finally triggers simply move an ordinary customer from one queue to the other. The term “signal” is used to cover negative customers and triggers. G-networks contain these three type of entities with certain restrictions; positive customers can move from one queue to another, and they can change into negative customers or into triggers when they leave a queue. On the other hand, signals (i.e. negative customers and triggers) do not queue up for service and simply disappear after having joined a queue and having destroyed or moved a negative customer. This paper considers this class of networks with multiple classes of positive customers and of signals. We show that with appropriate assumptions on service times, service disciplines, and triggering or destruction rules on the part of signals, these networks have a product form solution, extending earlier results.     

排队系统中的泰勒展开方法

综述了排队系统中的泰勒展开方法。它由Gong和Hu在1990s首次提出,并在最近几年里有了一些新的发展。首先,通过GI/GI/1队列的简单例子介绍其基本原理;其次,展示如何应用该方法分析相关性队列和离去过程;然后,阐述如何基于该方法发展排队网络近似的高阶矩方法;最后,讨论未来的几个可能研究方向。     

Optimal Server Acquisition in Open Queueing Networks

Several production and flexible manufacturing systems can naturally be modelled using queueing networks. In this paper, we consider the problem of acquiring servers for the nodes of an open queueing network, so as to optimize the steady-state mean virtual system parameters subject to a budget constraint. A partial enumeration scheme and a heuristic method have been proposed to solve this problem. Empirical results based on randomly generated test problems are used to identify a class of problems for which the heuristic performs well.     

Local balance in queueing networks with positive and negative customers

This paper investigates to what extent a recently developed new product form result for queueing networks with positive and negative customers fits into the class of product form queueing networks that satisfy a notion of partial or local balance. As such, this paper investigates whether this new product form is still a consequence of an appropriate notion of local balance. To this end, a new and non-standard type of local balance is introduced as an extension of standard local balance. This new type of local balance appears more restrictive and is no longer directly sufficient for global balance. Nevertheless, based on this new type of local balance, some extensions such as blocking phenomena for queueing networks with positive and negative customers can be concluded.     

Interconnected networks of queues with randomized arrival and departure blocking

In this paper, we study two interconnected multiclass non-exponential queueing networks. Jobs can jump from one cluster to another, but subject to randomized blocking depending on the class occupancies. Such systems naturally arise in communication networks, like Metropolitan Area Networks. We present sufficient conditions for the existence of a product form equilibrium distribution under both the recirculate and the stop blocking protocol. A number of examples are given.     

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.     

A new method of performance sensitivity analysis for non-Markovian queueing networks

The paper develops a new method of calculating and estimating the sensitivities of a class of performance measures with respect to a parameter of the service or interarrival time distributions in queueing networks. The distribution functions may be of a general form. The study is based on perturbation analysis of queueing networks. A new concept, the realization factor of a perturbation, is introduced for the network studied. The properties of realization factors are discussed, and a set of linear differential equations specifying the realization factors are derived. The sensitivity of the steady-state performance with respect to a parameter can be expressed in a simple form using realization factors. Based on this, the sensitivity can be estimated by applying a perturbation analysis algorithm to a sample path of the system. We show that the derivative of the performance measure with respect to a parameter based on a single sample path converges with probability one to the derivative of the steady-state performance as the length of the sample path goes to infinity. The results provide a new analytical method of calculating performance sensitivities and justifies the application of perturbation analysis algorithms to non-Markovian queueing networks.     

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

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