（运筹学与控制论专业论文）服务速率可变的排队模型分析.pdf

摘要 服务速率可变的排队模型研究是排队论的一个重要研究领域，之所以有如此多 的学者热衷于此，是因为服务速率的变化带来了排队系统的最优化和智能化，又因 为排队现象在日常生产生活中的普遍性，从而，对其进行深入的研究，如果能获得 较好的结果并将其应用开来，必将在很大程度上优化社会资源，节约大量的时间、 空间、人力和物力，从而有助于推动整个社会生产生活有序顺畅地进行。因此，近 几十年来国内外学者对服务速率可变的排队模型进行了大量的研究，并得到了一些 显著的成果，包括一些有效的排队论研究方法的提出。本文在前人的基础上利用密 度演化方法首先对两个排队模型服务速率不变的情况进行了一点研究，然后，在此 基础上对服务速率变化的m i g i i 和m m 1 1 排队做了一点创新性的研究，具体工作 如下： ( 1 ) 利用密度演化方法重新对m i g 1 排队进行了一些研究，证明了m i g l l 排 队的稳定性，得到了m g 1 1 排队的等待时间、队长、忙期的稳态分布。由于我们 考虑忙闲过程，只有两个状态，所以从推导过程可以看出，密度演化方法比其他考 虑队长过程的方法显得简洁； ( 2 ) 利用密度演化方法研究了p h g 1 1 排队，得到了等待时间的稳态分布； ( 3 ) 利用密度演化方法研究了服务速率可变的m g i i 排队，导出了它的密度演 化方程：在此基础上对m m 1 排队得到了等待时间的稳态分布； ( 4 ) 通过数值仿真对不变速率和可变速率的m m 1 排队进行了比较，得到的结 论说明我们的研究方法比较合理，通过改变服务速率的变化系数可有效地控制排队 系统。 关键词：未完成工作量向量马氏过程( v m p ) 密度演化方程等待时间可变速率 a b s t r a c t t h er e s e a r c ho f q u e u es y s t e mo fv a r y i n gs e r v i c er a t ei s a ni m p o r t a n tf i e l do f q u e u e s y s t e m ，a n dt h er e a s o nt h a ts om a n yr e s e a r c h e r sh a da p p l i e dt h e m s e l v e st ot h i sf i e l di s t h a tt h ec o n t r o lo fs e r v i c er a t ea r i s e so p t i m i z a t i o na n di n t e l | i g e n t i z a t i o no f q u e u es y s t e m ， a n dq u e u e si s u b i q u i t o u si no u rl i f e t h e r e b y , i fp l e n t yo fr e s e a r c ha b o u tt h e mi sd o n e ， a n ds o m eg o o dc o n c l u s i o n sw o u l db eo b m i n e da n da p p l i e d ，w h i c hw i l lo p t i m i z es o c i e t y r e s o u r c e st o g r e a te x t e n t ，e c o n o m i z e l o t so ft i m e ，s p a c e ，l a b o rf o r c ea n dm a t e r i a l r e s o u r c e s t h e r e f o r e ，r e c e n ts e v e r a ld e c a d e s l o t so f r e s e a r c h e r sg a v eag r e a td e a lo ft h e i r a t t e n t i o nt ot h i sf i e l da n dm a d e p l e n t yo f e x c e l l e n tf r u i ti n c l u d i n gs o m ee f f e c t i v em e t h o d s i nt h eb a s eo ff o r m e rw o r k ，al i t t l er e s e a r c ha b o u tv a r y i n gs e r v i c er a t ei sd o n ei nt h i s t h e s i s ，a n ds o m ew o r ki sf o l l o w e d ( 1 ) m i g l lq u e u ei ss t u d i e da g a i nb yd e n s i t ye v o l u t i o nm e t h o d ，a n dw ep r o v et h e s t a b i l i t yo f t h i sq u e u es y s t e m m e a n w h i l ew eo b t a i nt h es t a t i o n a r yd i s t r i b u t i o no f w a i t i n g t i m ea n dq u e u el e n g t ha n dt h eb u s y p e r i o dd i s t r i b u t i o na g a i n s i n c eo u rp r o c e s so fb u s y a n di d l eo n l yh a st w os t a t e s ，i ti s s i m p l e ra n dm o r ec o n v e n i e n tt od e r i v es o m ev a r i a n t s t h a nq u e u el e n g t hp r o c e s s ，a n do u rm e t h o dm e n d s t a k a c s w a y s t 2 、p h | g i1 q u e u e i ss t u d i e d a g a i nb yd e n s i t y e v o l u t i o n m e t h o d ，a n dt h e s t a t i o n a r yd i s t r i b u t i o no f w a i t i n gt i m ei so b t a i n e d ( 3 ) m g 1q u e u eo fv a r y i n gs e r v i c er a t ei ss t u d i e db y d e n s i t ye v o l u t i o nm e t h o d w ec o n s i d e rs o m eu n f i n i s h e dw o r k l o a dma sat h r e s h o l d w h e nu n f i n i s h e dw o r k l o a d o f q u e u es y s t e mi sm o r e t h a nm q u e u es y s t e me n t e r si n t ot h ep e r i o do fh i g hs e r v i c er a t e ， a n dw h e ni ti sl e s st h a nm q u e u es y s t e me n t e r si n t ot h ep e r i o do f l o ws e r v i c er a t e w e o b t a i nt h ed e n s i t ye v o l u t i o ne q u a t i o n so fm g 1 q u e u e i nt h eb a s eo f t h i sw ed e r i v e t h es t a t i o n a r yd i s t r i b u t i o no f w a i t i n g t i m eo fm m 1 q u e u e ( 4 ) w ec o m p a r et h ec a s eo fu n v a r y i n gs e r v i c er a t ew i t ht h ec a s eo fv a r y i n gs e r v i c e r a t eo fm m 1 q u e u eb ye m l u a t o r c o n c l u s i o n so b t a i n e d s h o wt h a to u rm e t h o di s r e a s o n a b l e ，a n dw ec a nc o n t r o lq u e u es y s t e me f f e c t i v e l yb ya l t e r i n gt h ec o e f f i c i e n to f s e r v i c er a t e k e y w o r d s ：u n f i n i s h e d w o r k ，v e c t o r m a r k o vp r o c e s s ( v m p ) ，d e n s i t y e v o l u t i o n e q u a t i o n s ，w a i t i n gt i m e ，v a r y i n gs e r v i c e r a t e 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作。除 了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰 写过的研究成果。参与同一工作的其他同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：日期印甲j 。f 丢 本论文使用授权说明 本人完全了解上海大学有关保留、使用学位论文的规定，即：学校 有权保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公 布论文的全部或部分内容。 ( 保密的论文在解密后应遵守此规定) 签名：善i 鎏导师签名：三警皇三墨 _ 日期：幺趔 2 0 0 4 年上海大学硕士学位论文 服务速率可变的排队模型分折 第一章引言 1 1 排队论概述 1 1 1 排队系统的基本概念 排队现象在我们的生活中几乎无处不在，例如，等公共汽车排队，医院看病排 队，电话忙线时排队，网上下载资料时数据的传输也要排队等等。但排队现象的存 在，也给人们的工作和生活带来了一定程度上的不便，如等待时间的无谓花费，空 间场所的长时间占用等。于是，对它们进行研究找出其中的规律，使社会生活生产 顺畅而有效率地进行就变得非常有意义。其实，早在二十世纪初人们就已经开始关 注排队现象，并对它们进行了初步的研究。1 9 0 9 年，丹麦工程师a k e r l a n g 第一 次用严格的数学理论研究了电话排队问题。随着研究的深入，关于排队系统的知识 不断丰富，以致最终形成了一门专门研究排队系统的数学理论排队论，它的目 标是研究排队系统运行的效率，通过确定系统参数的最优值，以决定系统结构是否 合理，并研究设计改进措旄提高服务质量。 以系统的观点来看，尽管排队现象千差万别，但它们却有一个共性：即一方有 需求，要求得到服务，我们不妨将需求方统称为顾客；而另一方要设法满足对方的 需求，给予服务，不妨将之统称为服务台：另外，还有排队规则和服务规则。具有 以上三点特征的系统就可称之为排队系统，由于顾客到达和服务的随机性，故又称 之为随机服务系统，如图1 1 。 | 一型| 翌些婴坐堑型型一 图1 1 排队系统 2 0 0 4 年上海人掌硕士学位论文 服务速率可变的排队模型分析 相应地，排队系统由三个部分组成： 1 输入过程 即顾客按怎样的规律到达。通常顾客的到达间隔时间会近似地 服从某种分布，例如，指数分布、定长分布、负二项分布、e r l a n g 分布， 几何分布以及一般独立分布等； 2 排队规则与服务规则排队规则有损失制、等待制和混合制等；服务规则 有先到先服务、后到先服务、随机服务以及有优先权的服务等； 3 服务机构包括服务台数目、服务时间等，服务台对顾客进行服务的间隔 时间通常会近似地服从某些概率分布，例如，定长分布、指数分布以及一 般分布等。 1 1 2 排队系统的几个重要指标 1 队长与等待队长 1 ) 队长是指系统中顾客的数目，包括正在接受服务的和等待服务的顾客。按 不同情况，队长有三种：到达队长、任意队长和离去队长： 2 ) 等待队长是指正在排队等待的顾客数。 2 等待时间与逗留时间 1 ) 实等待时间是指从顾客到达排队系统直到接受服务的这段时间； 2 ) 虚等待时间是指在先到先服务的规则下，t 时刻到达的某个假想的顾客的等 待时间： 3 ) 顾客在系统中的等待时间与接受服务的时间之和称为顾客的逗留时间。 3 忙期与闲期 1 ) 忙期是指服务系统中所有服务台连续繁忙的时期； 2 ) 对应的，所有服务台保持空闲的时间长度称为闲期。 1 1 3 排队系统的描述 dgk e n d a l l 在1 9 5 3 年引进了排队模型的符号，把排队模型记为 a | b c m 奠：由 2 0 0 4 年上海大学硕士学位论文 服务速率可变的排队摸型分析 爿表示输入分布类型，即相继到达的顾客的间隔时间分布； 口表示服务时间分布类型： c 表示服务台数目： m 表示系统内最大排队容量，当= o o 时，一般可省略。 表示相继到达间隔时间和服务时间的各种分布的符号有： m 表示负指数分布； d 表示定长分布； 丘表示尼阶e r l a n g 分布； g 表示一般( g e n e r a l ) 服务时间分布： g e o m 表示几何( g e o m e t r y ) 分布： g ，表示一般相互独立f p ，甜i n d e p e n d e n t ) 间隔时间分布； m 表示每批到达或服务r 个顾客的批到达或服务负指数分布； p 片表示位相型( p h a s et y p e ) 分布： 于是，m g i 表示到达时间间隔是负指数分布，即泊松到达，服务时间服从 一般分布的单服务台系统，系统排队容量为无限，故省略未写。 1 2 排队论的主要研究方法 经过一代代科学工作者近一个世纪的发展和完善，排队论已经形成了一门体系 完整逻辑严谨的学科。在这个过程中，各种研究方法不断涌现，到目前为止，常用 的方法有以下几种： ( 1 ) 解析方法包括积分方程方法、马氏更新过程方法和向量马氏过程( v m p ) 方法等； 排队论最早的研究方法是p o l l a c z e k 的积分方程方法，他主要研究了g i g l 排 队，得到了p o l l a c z e k 型积分方程、闲期、忙期、忙循环、等待时间、队长等排队指 标及其它们之间的关系，这些结果为以后排队模型的研究奠定了良好的基础。马氏 2 0 0 4 年上海大学硕士学位论文服务速率可变的排队模型分析 更新过程方法是由嵌入马氏链方法发展而来的。d ，g k e n d a l l 于1 9 4 8 年提出嵌入马 氏链的概念，它是指可以通过观察离去时刻的系统状态( 系统中顾客数) 来研究 m g l 模型。后来，n e u t s 把嵌入马氏链发展为嵌入更新过程，形成了马氏更新过 程方法，它通过研究队长过程，找到更新点，然后构造马氏链来研究排队模型。此 类方法以概率方法为主。向量马氏过程( v m p ) 方法是由补充变量方法发展而来的。 c o x 【1 4 引入了补充变量来使非马氏过程马氏化，再求解状态概率密度函数的偏微分 方程组。后来，史定华 1 引入向量马氏过程和状态转移计数过程，把k o l m o g o r o v 6 开创的解析方法和补充变量技巧程式化，通过构造向量马氏过程，然后求解状态概 率( 偏) 微分方程组来研究排队模型，从而形成了向量马氏过程( v m p ) 方法。它以分析 方法为主，技巧性较高，关键在于构造合适的v m p 。v m p 方法考虑忙闲过程，只 有忙和闲两个状态，比马氏更新过程中考虑的队长过程的状态数少得多，因此，排 队模型的处理也变得较简单。 ( 2 ) 数值方法包括矩阵解析方法、矩形迭代方法和寻根方法等； 尽管研究排队论的方法多种多样，得到的各种排队指标的结果也非常漂亮，但 这些结果大都是理论上的推导结果，要想把这些理论结果应用到实际问题中，还要 经过数值计算这一步。于是，到2 0 世纪7 0 年代，排队论发展到了算法阶段，其中占 主导地位的方法是n e u t s 提出的矩阵解析方法。n e u t s 2 9 首先用它来研究了g i m l 型排队，后来又研究了m i g t l 型排队r 见 3 0 】) 。在矩阵解析方法中通过位相型近似 可以把一个非马氏系统建模成一个连续时间马氏链，这个连续时间马氏链有特殊的 结构，由它得到的稳态分布具有矩阵几何形式( 几何分布的矩阵推广) ，于是稳态分 布的计算就成了一个线性代数的数值计算问题，借助线性代数和计算数学的成熟结 果便可得到比较满意的排队模型的解。矩阵解析方法以简洁的形式统一和推广了大 量复杂排队系统的分柝结果，摆脱了复分析和超越方程求根的困扰。尽管如此，由 于排队现象的繁纷复杂，仍然有很多排队模型无法用此法来研究解决，例如，当位 相是无限时，矩阵解析方法便无能为力了，为此史定华 1 】给出了无限位相分布( 伊h 分布和即日分布) 的概念，并对相应的无限位相的模型给出了比较满意的处理。作 为另一种有效的数值方法，应用概率大师a s m u s s e n 7 提出的矩形迭代算法可谓是独 树一帜，虽然比起矩阵解析方法，它的梯点、梯步、梯高等概念和思想稍显复杂难 2 0 0 4 年上海丈学硕士学位论文服务速率可变的排队模型分析 懂，但它可以解决矩阵解析方法不能处理的排队模型，而且，它扩展了n e u t s 的矩 阵指数分布。另外，c h a u d h r y 1 2 等人2 0 世纪9 0 年代提出的基于谱分解技巧的寻 根方法也是一种有效的数值方法。 f 3 ) 模拟方法包括模拟软件和离散事件动态系统方法等： f 4 1 逼近方法包括流体模型和高维反射布朗运动方法等。 排队论的其他研究方法，像模拟方法、逼近方法等，也是一些有效的但研究角 度不同的方法，在此不再一一叙述。 1 3 可变速率排队研究现状 我们知道，排队是目常生活中比较常见的一种随机现象，小到买票的排队大到 轮船停靠码头的排队，以及因特网中数据包的传输也要排队，这其中的每一个系统 的运行效率是我们最关心的问题，而这种排队系统中决定运行效率的关键之一便是 服务台的服务速率，对服务速率进行适当的控制，可以使整个排队系统的达到一定 条件下的最优化，所以研究服务速率可变的排队模型就变得非常有意义。例如，在 排队系统应用最广泛的通讯领域，通讯网络中处理器就可以看成一个服务台，如今， 像彩信、语音等各种各样的数据包的大量传输对服务台的服务速率要求越来越高， 即要使服务台在业务量高峰时保持网络畅通，又要使它在业务量低谷时，在保证正 常服务的前提下，尽量减少参与运行的处理单元，从而降低系统的运行成本。像这 一类业务量存在大幅度变化的排队系统，对其中的服务速率进行优化调整来降低运 行成本，就显得至关重要了。鉴于它的重要性，国内外的学者已经对它进行了一些 研究，主要研究状况概述如下。 排队系统服务速率的变化按照人们的能动性大致可以划分为两种： 一、服务速率在随机环境中随机地变化 较早的研究是p u r d u c p 3 5 对随机环境下m i m i i 排队的研究。n e u t s 2 9 研究了 随机环境下的m m s 排队，得到了稳态占用率分布具有矩阵几何形式的结论。 0 c i n n e i d ec ae ta l 3 3 】研究了到达率和服务率都是随机过程的m m m 排队。 f a l i ng i 1 9 】研究了服务速率按照生灭过程变化的m g 1 o 。排队的负载过程的稳 2 0 0 4 年卜海大学硕士学位论文 服务速率可变的排队模型分析 态分布。s e n g n p t ab 3 8 研究了随机环境是一个两状态的交替更新过程的单服务台排 队。b h a tv n i s 对具有交替变化的p o i s s o n 到达率的单服务台排队进行了研究，并给 出了g ，g 门排队期望等待时间的一个表示。k l u t k eg a 和w o r t m a nm a 2 5 研究了 随机环境下单服务台排队的负载过程，得到了p o l l a c z e k k h i n t c h i n e 方程的一般形 式，证明了随机的服务速率会比恒定速率产生更严重的拥塞现象。s h a r m ay 3 9 研 究了到达过程、服务时间过程和服务速率过程都是更新过程的排队，给出了稳定性 条件和收敛速度等结果。 二、服务速率在人为控制的范围内变化 近二十多年来，国内外学者在这方面做了很多重要的工作，我们大致把它们分 为三类： 1 一个优化的服务速率模式，是指在某种优化准则的前提下，找到一个最优化 的服务速率，然后服务台以这个速率进行服务。 上面已经提到过，这种服务模式相对随机变化的服务速率而言，可以减少拥塞 现象。这方面的主要研究见s c h a s s b e r g e r r 3 6 、l i p p m a n s a 2 7 、s c o t t c h e t a l 3 7 、 j o k y e t a l 【2 3 、t e g h e m 4 1 * 1 3g r a s s m a n nw k e t a l 【2 2 等。 2 可数个优化的服务速率模式，即动态地优化服务速率。设时刻n 的服务速率 是。，它随着m 的不同而随机地变化，在每一个时刻h 都选取最优化的服务速率 0 。 对于这类动态控制最优化问题，很多学者都把它看作马尔可夫决策过程来研究。 例如，d o s h i 丑玎1 5 n 连续马尔可夫决策过程( c m d p ) f l 究了m g 1 排队，得到了 一个充分性的最优化条件，并在对成本结构和需求分布做了一些限制的前提下，证 明了单调最优策略的存在性。近年来，又有一些学者对此类服务速率的最优化问题 做了进一步的研究，如g e o r g e 。删和h a r r i s o n j m 2 1 讨论t n 务速率可变的排队系 统的动态控制问题，给出了最优化方程( h a m i h o n - d a c o b i b e l l m a n 方程) 的简约形式， 并证明了它的充分性：同时，他们还给出了在持有成本( h o l d i n g c o s t o r c o n g e s t i o nc o s t ) 截尾的情况下解最优化方程的方法。出于同样的目的，但p h i l l i s 拗和z h a n gr 3 4 1 用了一个新奇的方法一模糊控制法来解决排队系统中服务速率控制的各种问题，并 2 0 0 4 年t 海大学硕士学位论文服务速率可变的排队摸型分析 就六类排队模型给出了具体的控制方法，这六类模型是：休假的m 1 排队，休 假的m m m 排队，没有转换成本( s w i t c h i n gc o s 坫) 的吖m l 排队，有转换成本的 m m 1 排队，没有服务成本( s e r v i c ec o s 打) 的串连排队，有服务成本的串连排队。 这种方法尽管是有效的，特别是在解析解不存在的情况下，但是它不能给出关于最 优化的严格证明。 这种服务模式的优点是从理论上和服务速率的角度来看是最优化的：缺点是从 实际行为和整个系统的角度来看一般不是最优化的。因为，第一，计算量很大，对 实际中服务台的性能要求很高；第二，一般服务台都存在速率转换时间和转换成本， 这种随着时间动态地优化需要较长的转换时间和较高的转换成本。对于大多数实时 业务而言，这种服务模式意义不大。 3 有限个优化的服务速率模式，即综合上面两种服务模式，选取合适的优化服 务速率的个数，兼顾两者之长处。 近年来，国内外的学者已经对这一模型做了很多研究，并取得了一些很好的结 果。例如，f e d e r g r u e nae la l 2 0 讨论了服务速率依赖于队长在两个服务模式下转 换的m g 1 排队，给出了一种简单易行的递归计算队长稳态概率的方法。 c h a k r a v a r t h y s 1 1 1 研究了有两个阈值m 和的m a p 尸日，l k 排队，给出了稳态分 析和计算系统性能评估0 p 咖r m a n c em e a s u r e s ) 的有效算法，以及达到最优解的算法。 d u d i n a 1 6 对两种运行模式的m ( x ) g i 排队作了研究，提出了模型中的转换时间， 得到了嵌入的稳态队长分布和关于转换水平的运算准则的相依性。接下来，d u d i n a 和n i s h i m u r a s 1 8 又研究了两个服务模式的b m a p g 门排队，也得到了类似的结果。 d u d i na 【1 7 中对于个服务模式的b m a p g l 排队的最优化控制问题给出了一个 计算嵌入的稳态队长分布的算法。同一时期，n o b e lr d 和巧m sh c 3 1 研究了两个 服务模式( 高速服务和常速服务) 的m g 1 排队，用马尔可大决策理论得到了一个 特定的算法来最小化系统长期的顾客平均数，从而最小化系统长期地平均成本。但 该文没有证明这个算法是否收敛到全局最优解。最近的研究是b o x m ao j 和k u r k o v a 别的两篇文章 9 和 1 0 】，在前一篇文章中他们研究了服务速率在s 。，s 。0 。 s 。) 之 间变化的m m i 排队，得到了负载分布尾部的渐进性；在后一篇中他们又研究了 2 0 0 4 年i 海大学硕士学位论文服务速率可变的排队模型分析 相同情况下的时g l 排队，在低速时的分布有有理的l s t 的情况下，分别求得了 两种运行速度下的负载和服务速度状态的联合分布，并在低速时的分布或服务时间 分布无限规则变化的情况下也得到了负载分布尾部的渐进性。 1 4 本文工作与论文安排 本文的主要工作是： 第一，利用密度演化方法重新对m g i 排队和p h i g i 排队进行了一些研究， 证明了m i g l l 排队的稳定性，得到了m i g i 排队的等待时间、队长、忙期的稳态 分布以及p h g 1 排队等待时间的稳态分布。由于我们考虑忙闲过程，只有两个状 态，所以从推导过程可以看出，密度演化方法比其他考虑队长过程的方法显得简洁。 第二，在前面工作的基础上，利用密度演化方法研究了服务速率可变的m g 1 排队，导出了它的密度演化方程，对m 1 排队得到了等待时间的稳态分布，并 通过数值仿真对不变速率和可变速率的m i m l l 排队进行了比较。 本文的以下章节安排如下； 第二章对本文要用到的一些相关知识进行了概括性的介绍，包括马氏链、更新 过程和p h 分布。 第三章利用密度演化方法研究了m g 1 排队。首先我们考虑忙闲过程，通过 补充变量构造向量马氏过程( v m p ) ，然后建立密度演化方程并求解，得到了等待时 间、队长的稳态分布和忙期的分布；在证明系统稳定性时，我们构造了嵌入忙循环 更新过程，通过转移频度公式确定了更新函数，从而成功地由更新函数来确定了更 新分布，进而证得了系统的稳定性。 第四章利用密度演化方法研究了p h g l 排队，得到了等待时间的稳态分布。 第五章利用密度演化方法研究了服务速率可变的m g 1 排队。在前面研究的 基础上，我们考虑当未完成工作量超过一定界限时，采用高速服务，低于这个界限 时回到常速服务( 低速服务) ，对于这个模型我们导出了它的密度演化方程。并对 m m 】排队得到了等待时间的稳态分布。通过数值仿真我们对不变速率和可变速 率的m m 1 排队进行了比较。 2 0 0 4 年h 海大学硕士学位论文 服务速率可变的排队模型分析 第二章预备知识 在这章中，我们将简要介绍一下本文所涉及到的一些预备知识，包括马氏链、 更新过程、p h 分布和密度演化方程等，这部分知识的介绍主要参考 2 】【3 】 4 5 等文献，在此对这些文献的作者所做的工作表示感谢，下文中引用的部分不再一一 注明。 2 1 马氏链与更新过程 2 1 1 离散马氏链 马氏链是一类重要的随机过程，由于它的马氏性或无后效性，使得这类随机 过程变得易于处理，从而关于马氏链的理论也得到了极大的丰富和完善。于是， 人们在处理随机过程问题时，通常先考察它是否具有马氏性，若具有马氏性，则 利用马氏链的相关理论来处理，若不具有马氏性，则通过寻找它的马氏点，构造 马氏链来处理这类问题。当然，还有一些其他方法来处理非马氏性问题，在此不 再赘述。下面我们先来介绍离散马氏链，然后再介绍连续马氏链。 定义1 设 z 。，”j v 为一取值于状态空间e = n 的随机过程， v = 0 , 1 ， ， 若对任意的，i o ，i 。e ，”n ，其条件概率满足： e x = j | x o = i o ，x 。= i n - i , x 。= i = p x 。= j i x 。= i ( 2 1 1 ) 则称此随机过程为状态空间e 上的离散时间马氏链，如果( 2 1 1 ) 式的右边 p x 。= jj 以= i ) 与无关，则称之为齐次离散马氏链，简称离散马氏链。 上述定义中( 2 1 1 ) 式满足的性质称为马氏性或无后效性，它的直观解释是：如 果把时刻i 看作现在，那么j 是将来的时刻，而乇，i 。是过去的时刻，马氏性表 示在确切知道系统现在的状态的条件下，系统将来的状况与过去的状况无关。注 意，不能把马氏性简单地解释为将来决定于现在，而与过去无关，因为( 2 1 i ) 式的 两边都是条件概率。 2 0 0 4 年上海大学硕士学位论文 服务速率可变的排队模型分析 1 齐次马氏链的转移概率及其性质 定义2 称条件概率为 力= p 瓦= j i x o = f ) 为离散马氏链的玎步转移概率，它表示从f 出发经胛步转移到，的概率。 定义3 称矩阵 p “= 【爿” 为离散马氏链的n 步转移概率矩阵。当 = 1 时，记巧1 = 弓为一步转移概率， 转移概率矩阵的性质： ( 1 ) 非负矩阵，即b 0 ； ( 2 ) 行和为l ，即弓= l ； ) e e ( 3 ) 满足c 一世方程 巧) _ 秽， i e 即p ( ) = pc ”尸( ，从而p “= p “。 2 绝对概率与初始概率 定义4 记 p ，( ) = p x 。= ，) ，j e p ，= p ，( 0 ) = p x o = f ) f e 称p ，( n ) 为离散马氏链 x 。，” 在时刻”处于状态，的绝对概率。若 1 i r r 2 ，( ”) 存在，称为极限状态概率。 一p 称系统在初始时刻0 处于状态i 的概率p ，为初始概率，我们有 0 p ，s 1 ，p ，= 1 称 n ，i 毋为离散马氏链的初始分布。 定理l 离散马氏链的绝对概率由初始分布和转移概率矩阵唯一确定，即 n ( ”) = 以 k p ) = 】 ( ，e ， ) 。 2 0 0 4 年上海大学硕士学位论文服务速率可变的排队模型分析 3 齐次马氏链的状态分类 互通如果存在1 ，使巧” 0 ，则称从状态i 可到达状态_ ，记作i 斗，。 如果，寸，且，_ ，则称状态，与状态相通，记作f h 。 吸收若p 。= l ，则状态f 称为吸收状态。 遍历若状态f 正常返、非周期，则称f 为遍历状态。若马氏链的所有状态都 是遍历的，则称此马氏链为遍历马氏链，简称遍历链。 周期如果 ”1 ：p p 0 的最大公约数为d ，称状态i 有周期d ，若矿 1 ， 状态i 称为周期的；著z = 1 ，状态i 称为非周期的。 闭集离散马氏链的一个状态的集合a 称为闭集，如果对每个f 爿，有 p ，= 1 。闭集爿称为极小的，若a 的任何一个真子集不是闭集。显然，整个状 态空间e 是闭集。 不可约若e 是极小闭集，则离散马氏链称为不可约马氏链。 常返性邴= p ( x 。= ，以，k = 1 ， 一1 i x o = i 称为从状态i 第 步首 达状态j 的概率，兀= 刀”称为首达概率；而，称为返回状态f 的概率， h 。1 i 1 = 蜕称为平均返回步数。 ”= 1 平稳分布如果方程组舻= 万，腮= l ，f 0 存在唯一解，其中e 是元素全为 l 的列向量，则称万为离散马氏链的平稳分布。 定理2 对离散马氏链o 川p 扩s 兀1 ，p 护= ”p 孑_ 成立。 ，：) 定理3 相通的状态类型相同，即若i hj ，则状态i 与状态，同常返或非常 返，同零常返或正常返，同周期或非周期。 定理4 不可约马氏链的所有状态都是相通的，因此具有相同的类型。 定理5 不可约正常返非周期的离散马氏链称为遍历链，遍历链平稳分布存 在且等于极限分布。 型里! _ 坠塑丕兰堡主堂堡堕奎 墅墨垄童旦壅竺壁坠堡型坌堑 状态分类 2 1 。2 连续时间马氏链 定义1 设x ( f ) 是一个随机过程，参数空间为t = 【o ，o o ) ，状态空间为 e = o ，1 ，2 - ) 。若对r 中的f l 匕 - 0 。 定义4 记瓦= 0 ，令五= i n f l t ( r ) 彳( o ) ) ，假定i n f a ) = m ，则 ， ) 为 连续马氏链依次发生跳跃的时刻序列。 4 连续马氏链分类 a 。连续性假设：! i m p ，( r ) 2 毛； a ：保守性假设：v i e e ，吼= ； a ，稳定性假设：v f e ，0 q ， 。； a 。规则性假设：_ 。以概率1 成立( w p 1 ) ； a 5 有界性假设：c = s u p q , 0 唯一确定。 2 0 0 4 年上海大学硕士学位论文服务速率可变的排队模型分析 2 1 3 更新过程 定义1 设 以) 是独立同分布的随机变量序列，其分布函数f ( t ) 满足f ( o ) 0 3 。，( ，) 的k 阶原点矩为 ；= x 盯( x ) = ( _ 1 r k ! a t 。p - g 0 ，v i ，j e 和月“中的任意子集a 有 j p f s ( f ) = y ，x ( f ) als ( “) ，工( z ) ，0 t , r = e s ( o = j ，x ( t ) a i s 0 ) ，x 0 ) ) 。 定义3 混合型向量马氏过程拶( f ) ，x ( f ) ) 称为时齐的，如果对任意的f f 0 ， v f ，e 和中的任意子集“有 p s ( t + f ) = x ( t + r ) a i s ( r ) = f ，x ( r ) = j ) = p s ( t ) = j ，x ( t ) a l s ( 0 ) = f ，x ( o ) = 定义4 混合型向量马氏过程 s ( ，) ，x ( f ) ) 的转移概率函数定义为： p , j ( t ，x ，一) = p s ( t ) = j ，x ( t ) a | s ( o ) = f ，x ( o ) = x ) 。 定义5 设掌的密度函数，分布函数和补分布函数分别为，( f ) ，( f ) 和f ( f ) ，则 川l i 邮m1 ，_ 彤 t + a t 炒弘鬻 称为毒的风险率函数。 假定随机过程s ( f ) 只依赖有限个相互独立的寿命，其中非指数寿命都是连续型 的。过程在某一状态的逗留时间将由其最小( 剩余) 寿命决定，且终止的寿命按某 种规则再次出现时仍服从同一分布。令t 时刻这些非指数随机变量的年龄分别为 j 。( r ) ，。( ，) ，则f ( f ) x ( f ) ，以( f ) 形成一个混合型向量随机过程，状态空间为 e 魁。 定理1 对离散状态随机过程s ( t ) ，若都按年龄引进补充变量，则所得混合型 向量随机过程佟( f ) ，x i ( f ) ，以( 啦是齐次稳定的混合型向量马氏过程。 2 0 0 4 年卜海大学硕士学位论文服务速率可变的排队模型分析 第三章利用密度演化方法来研究m g 1 排队 众所周知，m g l 排队的队长过程是非马氏性的。鉴于这种情况，人们找到 了许多方法来处理非马氏性。一个经典的方法是k e n d a l l 2 4 提出的嵌入马氏链方法， 后来n e u t s 发展了这种方法，提出了马氏更新过程方法。另一种方法是补充变量法， 它是由c o x 1 4 等人提出来的。后来，史定华 1 】在这种方法的基础上提出了向量马 氏过程( z m p ) 方法。此外，还有许多其他方法，也都是致力于处理问题的非马氏性。 然而，t a k a c s 却找到了一个连续时间马氏过程( c t m p ) ，即f 时刻系统未完成工作量 v ( t ) ，并且由此得到了著名的t a k a c s 方程和等待时间分布。遗憾的是，由于未完成 工作量中所包含的信息不够充分，不能求出所有的排队指标。作为m g l 排队的 一个完整的解决方案，在中作者用v m p 方法求出了所有的排队指标，即通过引 入了f 时刻系统中的顾客数s ( f ) 和f 时刻系统中正在服务的顾客已花去的时间x ( t ) 来构造了一个v m p s ( f ) ，工( ，) ) 。由于s ( f ) 的状态数是可数的，所以问题的求解过 程稍显复杂。本文综合了上面两种方法，构造了个新的v m p r ( f ) ，矿( f ) ) 来研究 m g 1 排队，即引入了忙闲过程r ( t ) 和引入r 时刻系统未完成工作量v ( t ) 作为补充 变量。这样，r ( t ) 的状态数变成两个，使得问题的处理变得简单方便，同时也完善 了t a k a c s 的方法，这一点在本章里得到很好的体现。本章只研究了稳