（应用数学专业论文）n级串联休假开排队网络系统分析.pdf

abs i ， ract mu l t i 一 de tan d eln o penq u e u e ing n e 卜 刀 o rk sy st eln 俪th s e r v e rv a c a t i o nis 姗l y z e d i n 而s p a pe lt 五 e m u l ti 币 o detand e mo pen q u e u e in g n e two rksy st em h as 悦e n引 刀 d l ed by many rese 田 rc h ers andalotofresultshav e been o bt ained. ho 、 ， e v er， m u l t l 一 node栩 口 d em 0 p enq ueu e ing n e two rks y st e m俪ths erverv ac ationh asnot be 印 引 刀 d l ed s een ino pen li t c r a 奴 叮 e s. f orthis r easo n ， th e p a pe r c ons i d e r s n-n o d e ta n d e mop en que u e in g n e two r k sy s t e mwith石 n 1 tec ap ac ity an dserv erv ac ati on the ge n er a t o r n 1 a tri xofmai k o v p r o c es s isglv en inrecurrence fo n 力 u l ati on. t b e s t e a d y . 引 泊 t e di strib u t l o n a n d o t h er rela t l v e i n d ex of th esyst 。 叮are obt a in e dby 幻 q 已 越 巧of m at ri xana l y s isthe o ry and p r o b ab il ity theo ry . ai th e sam e ti m e ， c o m p u 扭 t i o 回 al gori t hr nstoo b t 田 的 n ulne rical solutin ns oft h es y s t e mins t e a d ys t a t e are dev el o 侧 记. t 七 e p aperal so anal y ses 面5 mo del b as ed on nuln erical obs e r v ati呱 s in ce the o per at i o nofm a t ri xandr e c u r s i on are e asy top e rfo rm o nc o 住 ip u t er s ， th e c o n c 】 u s i ons o f 血s p al 犯 r c anbe con v e 刃 u e n t l y a p p l i ed. k 卫 ywo r d s:queueing sy st eln， 功 团 的 x 一 g e o m et ri c so l utio 残。 pen n e two r k sy st e 风 呵 而。 几s l e ady 一 引 a t e d i s 苗b u t i o 氏q b dp r o c e s s e s n 声明 本学 位论文是我在导师的指导下取得的 研究成果， 尽我所知， 在本 学位 论文中，除了加以 标注和致谢的部分外，不包含其他人己 经发表或 公布过的研究成果，也不包含我为获得任何教育机构的学位或学历而使 用过的材料。与我一同 工作的同 事对本学位论文做出的贡献均己 在论文 中作了明确的说明。 去， 于 石 研 究 生 签名 : 一茸卫年攀 词年 7 月 了 日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电 子和纸质文档，可以 借阅或 上网公布本学位论文的全部或部分内容， 可以同 有关部门 或机构送交并 授权其保存、 借阅或上网 公布本学位论文的全部或部分内容。 对于保密 论文， 按保密的有关规定和程序处理。 研 究 生 签 名 : - 葺鱼 聋 一 词年 7 ” 日 硕士论文 n级串联休假开排队网络系统分析 第一章 绪论 本章对排队 论的发 展， 串 联排队网 络系统， 休 假排队系统的 研究内容、 背 景 和现状作一些 简单介绍，同 时阐明 本文的 主要研究内 容和本文的结 构。 1 . 1 排队论简介 排队论又称随机服务系统，起源于 20 世纪初关于电话中接线问题的研究。 19 09一1 9 加年丹麦 数学 家、 电气工 程师爱 尔朗( a. k.erlan g ) 用概率论 方法研究 电话通话问题， 从而开创了这门新学科，并建立了 许多基本规则。30年代中期， 当费勒 ( w.f eller)引进了生灭过程时，排队论才被数学界承认为一门重要的学 科。 在二战期间和二战以后， 排队论在运筹学这个新领域中成为一个必不可少的 重要内容。20 世纪50 年代初肯德尔 ( d.gken d a 】 1 )对排队论作了系统的研究， 他用嵌入马尔可夫链 ( amarkov)方法研究了排队问题，使排队论得到的进一 步发展。 从 2 0 世纪60 年代起， 排队论研究的课题日趋复杂， 很多问题不是很难 求的精确 解， 就 是求得的 解非常复杂， 不便于应用， 因而开 始了 近似 方法的 研究。 排队论的产生与发展来自 于现实生活的需要， 实际的需要必将决定它今后的 发展方向， 排队论的 应用范围 很广，它应用于一 切服务系统， 尤其 在通讯 系统、 交通系统、 计算机、 存储系统 、生产管理等方面 应用得最多。 排队 系统尽管千 差万别， 但都可以 抽象为顾客到 达服务台前， 服务台 有空闲 便立刻 服务， 若没 有空 闲， 则需要等待服务台出 现空闲时再 接受服务， 服务完后 离开服务台。下图为排队系统图，虚线筐内为排队系统。 排队模型 图 1 . 1 f i gl . 1 沿 用k e n dall( 1 9 5l ) 采 用 的 表 示 方 法 ， 一 个 排 队 过 程 通 常 采 用 符 号川 b / c 了刀 y 其中a表示顾客到 达间 隔时间 分布的类型， b代表 服务台 服务时 间分布的 类型， c表示服务台的台数，x表示队伍的容量，y表示排队规则。如m/ m / c表示泊 松到达， 服务时间服 从指数分 布、 c 个服务台、 无限 等待空 间的排队 系统。 硕士论文n级申联休假开排队网络系统分析 一 个排队系 统要从 两方面 考虑， 即 服务机构和 顾客的 利益来 考虑， 顾客希 望 的 等 待时 间 越短越 好， 那就需 要服务机构的 服务台 越多 越好， 而服务 机构要想 获 得很高 的利益 就必须限 制服 务台的个数。 综 合考虑 排队 的几 个指标: 队 长、 等 待 时间、和服务台的忙期，成为排队论的主要研究内容。 队长:指系统中的顾客数。 等待时间 :指 从顾客到 达时 起到 他接受服务时 止这段时 间。 忙期: 指空闲 的 服务机构从 有顾客到达开 始服务时 起到 系统服务完 所有 顾客时止的这段时间。 自 排队 论这门 学科 形成以 来， 新的 研究 方向 和 研究方法 层出 不穷。 大量的 科 研工作 者在此领域 取得了 丰硕的成 果。 排队论专 家田 乃硕 等把 矩阵 解析法引 入 gl/ m/l型 休假排队系统， 并研究了 部分服务台同步的 休 假排队 模型， 极大的 丰 富了 排队 模型的 理论; 史定华 将频度转移法 用于可修服 务系统 并且对可 靠性作了 大量 工作; gel e n b e 将负顾客引 入排队 系统。当 前， 排队 论的 研究主要 集中 在排 队网络、矩阵解析法、数值计算、极限定理以及特殊模型等方面。 1 . 2 串连排队网 络系统的内 容、 背景及现状 排队网 络是指由 一些 服务点和联结 它们的 路径 所构成的 总体， 其中 每个服务 点 相当于 一个单台或 多台的 排队系统， 顾客在一 个服务点 接受完 服务后按照一定 的 规律 沿着路径到下 一个 服务点 接受 服务。 最 早考虑的排队网 络 模型是j a c k s o n (1 9 5 7 ) 1 8 提出 的网 络， 后称j a c k s o n 网 络， 或称是 j ack so n 开网 络， 或指数开网 络， 它由 m 个编号 为1 ， 2 ， ， 二 ， m的服务 点 所组 成， 其中 第1 个服 务点包括mi个独立同 分 布的 指数分 布服务时间的 服务 台， 第1 个 服务点的 外部输 入是参数为入的p o i s s on流， 各服务点的 外部输入与各 服 务 时 间 为 相 互 独 立。 在 第 1 个 服 务 点 接 受 服 务 后 的 顾 客 立 即 以 概 率p 。 沿 路 径 转 移 到 第 ， 个 服 务 点 排 队 等 待 服 务 ， 而 以 概 率 q ， = 一 艺 二 lp 。 离 开 系 统 ， 对 于 指 数开网络， 容易证明它具有乘积型解， 也即网络的平稳分布等于各服务点平稳分 布 的 乘 积。 若 在 j ac k s on 网 络 中 令 所 有儿 = 0 ， 即 没 有 外 部 输 入: 令 所 有q 二 0 即 没 有输出; 且假定系 统中 顾 客总数为固 定的 n ， 便得到 指数闭网 络，或 jackson 闭网 络， 或g o r d o n 一e w e l l 网 络( g o r d o 吸 n e ， e l l ( 1 9 6 7 ) 1 4 ) 对于指数闭网 络，平 稳 分布 仍然是乘积型的 ，此时 各乘 积项可以 看成是带 有p oiss on输入的 各服务点单 独存 在时 的平 稳分布， 但并非 是网 络中各服务点的 边缘分 布， 也就 是说， 这些 服 务点中的顾客数相互不独立. 各服务点中顾客数的不独立性是显而易见的， 因为 此网 络中 顾客总 数固 定。 此后， 逐渐开始研究非 指数网络是 否能具 有乘积型 解。 m u n t z ( 1 9 7 2 ) 3 0 研究t p o l s s o n 输入蕴 涵p o i s s o n 输出 这种性 质， 记为 硕士论文n级串 联休假开排队 网络系统分析 m冷m， 证明了 服务点具有m，m性质的网络具有乘积型解，同时该网络也 具有m二万性质。b ask e t t 等( 1 9 75) 4 证明对一般服务分布的多类顾客网络， 只要排队规则为处理机分享( 份ocesso r-sh ari ng) ， 后来先服务的强占 继续型 ( l a s t 一 c ome 一 f i r s t 一 s e r v e d 一 p r e e 帅t i v e ，e s u m e ) 、 或无穷多个服务台， 平稳 分布仍为乘积型的. chand y 等( 1 9 7 7) 6证明了 在非指数服务情形， 具有乘积型解 的网 络的排队规则必须是即 刻服务规则， 也即 顾客在到达时刻必须立即开始接受 服务。因此，像先来先服务、 优先权服务等非即刻服务规则不能产生乘积型解。 n o e t z e t ( 1 9 7 9 ) 3 2 提出t 一种更一般的排队规则l b p s ( 末批分享处理机 l a s t 一 b a t c h 一 p r o c e s s o r 一 s h a r i n g ) ， 它 包括上 述处理 机分享、 后 来 先 服务的 强占 继续型、 和无穷多个服务台为特例， 证明了在一类更广泛的对称排队 规则中， l b ps 类是唯一的对所有服务分布都能产生乘积型解的类。另外， k ell y ( 1 9 76) 【 21 与 b arb o u r ( 1 9 7 6)【 3 则考虑了包括多种路径方式，多种排队规则在内的多 类顾客， 一般服务分布的网络，利用可逆性给出了一种乘积型解。 最近， s erf 。 加( 1 9 89) 【 33 研究了 路 径与服务速度依赖于系统拥挤长度的 m arkov 网络， 它把通常考虑的各服务点的服务相互独立、 各顾客选择路径相互独 立的网络包含在内 作为特例， 而且现在的模型更便于描述并行处理， 由 于容量受 限的转移阻 塞、 避免拥挤而改变路径、 以 及增加或缩减处理速度以 适应后面路径 的拥挤等现象。 他引进了 描写各服务点 顾客数的一般网络过程， 导出了它的 平稳 分布， 此分布具有向量函数的乘积型。 v a n d i j 陇r ajna s e ， i c z ( 1 9 9 1 ) 3 8 考虑t 具有一般服务需求的网络， 其路径依赖于顾客在下一服务点所需的服务时间， 求 得了非标准的乘积型解。 服务点 容量有限的网 络一般没 有乘 积型解，除非 路径可逆( 见k ell y ( 1 9 7 9) 2 幻) ， 或遇到服务点容量饱和时顾客 会越过此服务点， 如同此时的 服务速度等 于。 . 对后面这种情形，以 前文献中的 证明都是直观的，而v an d ij k ( 1 9 8 8) 3 5 则给出了简单、严格的证明. 对有阻塞的非指数网络，v a n dij k ( 1 9 91) 【 3 7研究了顾客遇到阻塞时服务 “ 停止” 或 “ 重复” 两种类型。 在某种条件下，两种类型被证明是等价的，而且 可导出乘积型解。 串联排队网 络系统在港口( 海港， 航空港) 运输、 计算机通讯、 交通控制、 存 储系统、 生产管理、 柔性制造系统、 生产流程等领域中的应用十分广泛， 特别是 有限容量的排队系统网络更是如此. 有限容量的串联排队网络系统， 人们研究得 较多的 是用逼近的 方法， 求系统指标的 近似数值解. 如: a l t iok 【 1 ( 19 8 9)， b r a n 面a l 成j o ， 2 ( 1 9 8 8 ) ， g e r s 加i n 1 3 ( 1 9 8 7 ) ， h i l l i e r 周家良， 贾 波 ( 1 9 9 6) 48 对尸 月型串联反馈开 排队网 络系统进 行了 分析， 得到了 其状态过 程的伞矩阵，给出了 系统的稳态概率解，忙期长度分布. 1 . 3 休假排队系统的内容、背景及现状 休假排队泛指服务台在某些时候不能被顾客利用的排队系统， 导致服务暂时 中断的理由有多种多样的解释，而暂时不能用于接待顾客的那些时间统称为休 假.以下是一些诱发休假排队研究的典型例子。 ( 辅助工作) 在负荷较低的排队系统中， 为了有效的利用空闲时间， 可设置某种辅助工作， 假定辅助工作也需一项一项的实施， 完成每项辅助工作的时间是独立同 分布的随 机变量。 一旦系统内 无顾客， 服务员立刻开始一项辅助工作。 完成后若系统中仍 无顾客， 就继续从事另一项辅助工作， 直到完成某项辅助工作时遇系统中已 有顾 客等待则立刻恢复顾客的服务， 若顾客在服务员从事某辅助工作时到达， 即使前 面没有顾客等待也不能立刻得到服务， 需等到该项辅助工作完成后才能利用服务 台。对顾客而言，从事辅助工作的时间可看成服务员休假。适当设置辅助工作， 即可以 充分利用空闲时间增加系统收益。 这类模型已 在中心处理机运行策略， 柔 性制造系统，通讯网络及生产过程控制中得到重要应用。 ( 保养策略) 为使服务台长期有效运行， 有时需对服务设施进行一些例行保养. 例如， 每 当 服务台 空闲时 就实 施一次 保养程序， 完成保养的 时间 也可以 是随 机变量。 在实 施保养程序的过程中到达的 顾客需等到例行保养完成后才能得到服务。 若保养程 序完成后系统内 仍无顾客， 服务员可进入通常的闲期， 直到有顾客到达时 服务立 刻开始. 我们关心的典型问题是， 例行保养时间对系统指标将发生怎样的影响? 如何制定最优的保养策略。 ( 机器故障) 假定服务台在运行过程中可能发生损坏或需要补充能量， 而故障维修或能量 补充时中断正 在进行的 服务， 这些中断时间 可视为 服务员 休假。 这类模型也称为 4 硕士论文 n级串联休假开排队网络系统分析 服务台 可修的 排队 系统， 它们均可纳入休假排队的 框架来研究。 在这里， 休假可 使正在进行的 服务中断而抢先发生。 ( 启动时间) 为降低服务成本， 当系统中心无顾客时可以 关闭服务设施。 当有顾客到达时 通常需要一个启动 ( 预热) 时间， 启动时间也可以是随机变量. 该顾客及启动时 期内到达的其他顾客均需等到启动时间完成后才能相继得到服务。 启动时间可以 看成由闲期到达的第一个顾客触发的一段休假时间。 ( 轮循服务) 一个服务员依某种规则轮流地为若干队列顾客服务， 这种排队现象发生在计 算机系统、 通讯网 络、 多泊位码头等各种实际问 题中。 在计算机系统， 程序都是 多路复用的。 当 程序用于处理某种特定类型工作时， 其他类型工作 ( 顾客) 就不 能利用， 如果我们把注意力集中于某种特定类型工作， 程序用于处理其他类型工 作的时间对该类顾客可视为休假. 完全类似的， 当标定轮循排队中某特定队列时， 服务员接待其他队列及在诸队列间转移的时间， 对该队 列顾客相当于服务员在休 假。 这时， 每次休假时间的长短，即取决于当前队列的状态， 也取决于服务员到 达各队列的服务规则。 ( 交通堵塞) 在公路交通问 题中， 通常把车辆通过某特定路段看成为顾客服务。 由交通事 故或其他原因造成的交通堵塞可视为服务员休假. 对河道上航行的船只也可作类 似的解释， 在空运中把飞机利用跑道起降的时间看成顾客服务， 因各种理由 造成 的暂时关闭可视为服务员休假。 ( 优先权) 具有不同 优先权的多类顾客的排队系统在经典排队论中已 得到深入的研究。 如果把高优先权顾客造成的低优先权顾客的 服务的中 断( 抢占 或非抢占 的) 视为 对低优先权顾客的服务员休假，优先权排队也可纳入休假排队的框架之中. 大量的实际问题均可通过在经典排队论系统中引 入某种休假策略加以描述 和研究。 20 世纪中期以 来随着计算机通讯网络， 柔性制造系统 ( fms ) ， 异步转 换模式( atm ) 等高新技术领域的发展，提出了大量复杂系统的设计与控制问题， 经典排队模型在处理这类问题时存在着极大的局限性. 休假排队正是在这些实用 背景中 产生的. 休假排队 研究是从2 0 世纪7 0 年代才开始的。 l e v y 与y e c h i a l i ( 1 9 7 5 ) 2 8 从有效利用排队系统闲期的 观点出 发， 首先研究了m/ g 八型休假排队系统，并 引人了“ 休假” 和“ 休假策略” 等术语。 一方面， 休假排队系统反映了 服务过程 可能因某种理由发生中断这一客观事实: 另一方面， 各种休假机制为系统的优化 硕士论文n级串 联休假开排队网 络系统分析 设计和运行控制提供了 极大的灵活性。 因此休假排队立刻受到广泛关注并成为一 个研究热点。 从8 0 年代末到90年代， 田 乃硕等【 5 6首先把矩阵 几何解方法引入休假排队 研究， 推进了gl/ m/l型 休假排队 系统 和多 服务台 休假排队 系统的 研究。 平行于 休假排队理论研究的进展， 取得的结果迅速在众多领域得到了卓而有效的 应用。 例如，中心处理机时间表的设计与控制、 最优保养策略的拟定和实施、 生产过程 的经济效益分析、 行政工作及其他维持性工作对中心处理机运行过程的影响、 数 据通讯网络中定时询查系统分析、 柔性制造系统的生产调度、 atm 中的 拥塞分析 问 题等等。20 对年的发展表明，休假排队 研究不仅为经典随机服务系统理论的 发展注入了新的活力和生机， 也为排队论在各种高 新技术领域的应用开辟了 更广 阔的前景。 1 . 4 本文的主要研究内 容和本文的结构 本文从有效利用系统闲 期的 观点出发，在文献的【 4 7 基础上引入休假策略。 以前的休假排队理论仅针对一级服务台进行了研究， 本论文把休假理论与多级串 联排队网络系统相结合，首先，运用矩阵解析的方法对有限容量的n级串联休 假排队网络系统模型进行分析， 得到了 其状态的q 矩阵; 其次分析了 这个系统的 运行特征: 稳态概率解， 顾客的稳态逗留时间， 忙期， 系统的阻塞率以及顾客因 不能进入系统而消失的 概率; 最后， 借助计算机对系统进行了 仿真， 利用这些特 征对两级串联休假排队网络系统模型进行了分析. 本文把休假理论与串联排队网 络系统结合起来，对多级串联开排队网络系统引入服务台休假机制进行综合排 队分析，这在国内外公开发表的文献中还未成见到. 硕士论文n级串联休假开排队网络系统分析 第二章基本理论和主要方法 本章 将简单 介绍几种常用的 研究排队 模型的 方法， 以 及各方法在研究排队问 题中的特点。 2 . 1生灭过程 以指数分布为基础的经典生灭过程，是分析处理随机现象的基本工具之一， 不仅在排队 伦、 可靠性、 库存论等学 科的 发展中 起 着重 要的 作用， 还广泛应用于 工程技术、 管理科学、 生命科学、生态系统、 人口理论、行为科学及社会科学等 领域。 2. l l 生灭过程的定义 假设有 一系统， 该系统具有 有限 个状 态。 ，1 ， k， 或可数 个状态。 ，1 ， 令n (t)为系统在时刻t 所处的 状态。 在任一时 刻t ，若系统处于状 态1 ， 则在 (t，t + 夕 ) 内 系统由 状态1 转移到1 +1( 有限 状态时。 1 k; 可数 状态时。 1 0 为一 常数; 而由 状 态1 转移到1 一 1 ( 有限 状态时 1 引 k ; 可 数 状 态时 1 1 0 为 一 常 数 ; 并 且 在 (t ， t 十 夕 ) 内 发生两次或两次以 上转 移的 概率为o( 山) .这 样一 个系统状态随时间 变化的 过程n (t)就称为一个生 灭过程。 2. 1 .2.生灭过程的微分方程组 只 (t)为 系统在时刻t 处 于状态1 的 概率，即 只 (t) = p 厦 n ( t)=1 系统在时 刻t 十 山处于1 ( 有限 状 态时0 i k: 可数状态时0 i 。) 这一事 件 可以在下列互斥情形下发生: ( 1) 系统 在时 刻t 处于 状态1 ， 一而在时 刻(t + 0内 没有变化.它的 概率为 只 ( t ) (l 一 凡 夕一 从夕 ) + 0 ( a t ) ; (2) 系统在时刻t 处 于状态1 一 1 ， 而在(t 十 夕) 内由卜 1 转移到1 。 它的 概率 为 硕士论文 n级串联休假开排队网络系统分析 毛 (t ) 凡 _ 1 夕+ 0 ( 夕 ) ; (3) 系统在时 刻t 处于 状态1+1 ， 而在(t + 左 ) 内由1 +1 转 移到1 。 它的概 率 为 月 + ，(t )产 ，+ ;夕 + 0 (夕 ) ; (4) 系 统在(t + 夕 ) 内 发生两次或 两次以 上 转移， 它的概率为o( 0 。 故由全概率定理，在有限状态时， 君 (t + 夕 ) = 君 (t) ( 1 一 凡 夕一 从 at) + 君 _ : ( t ) 凡 _ ; 夕 + 君 + 1 ( t ) 尸 ，+ 1 夕+ 0 ( t ) ，0 1 k， 移项后， 只 ( t 两端都除以夕得 + 夕) 一 只 ( t ) 夕 = 凡 _ ， 凡1 (t ) 一 ( 凡+ ilj) 只 ( t) + p ， + 1 君 ; 1 ( t ) + 0 ( 夕) ， 0 1 k ， 令夕一0 即得 君 = 儿 一 几(t ) 一 ( 儿 + 产 )只 ( t) + 产 ，+l 君 十1 (t ) + 0 (左 ) ，0 0 ( c ai 。 ， 则 存 在 一 个t 。 ， 当 t 之 to 硕士论文 n级串联 休假开排队网络系统分析 浊 “ (t ， = 粤 : (t 。， 十 丈 : (u )du ， : : (t 。) + 聆 a ，du = 只 ( 。 ) + 浊a ， ( 一 。 ) 二 此 与君 (t) 1 矛 盾， 因 而 必 有 (2 .8)式 于是在 ( 2 . 1 ) ，( 2 .2 ) 与 ( 2 3 )中令t 峥二，由 ( 2 .7 ) ，( 2 名 )即得 斗_ : p _ ， 一 八p : 凡 一 ;尸 一 认+ 料 玩+ 从 +l 几 + ， ，0 1 k ， 一 凡 夕 。 + 从 尸 ， 1一 了冈拓厂四 ( 当可数状态时，只需将第一式划去，并将第二式中的k改成co即可) 由此得 寿一 p k _ ， 一 产 k p k = 0， 凡 p ， 一 从 +l pt + ， = 入 一 几 _ 1 一 从 p ， 0 1 k ( 当 可数 状态时 ， 只 需 将 上面 第 一式 之1 j k换 成j 之 1 ， 并 划去 第 二时即 可 . ) 其 中p 。 由 条件 ( 2 . 1 1 ) - p k艺j-0 决定，故得 l po = ， 军 ，k 儿1-1儿卜 2 内 1 十乙 _ ， 一 产 j 尸 j 一 1 ” 肠 ( 2 . 1 2 ) ( 当可数状态时，只需上式中的k改成。即可，由 (2.5 ) ， 此级数是收敛的。 ) 硕士论文n级串联休假开排队网络系统分析 2 . 2 拟生灭过程和矩阵解析法 20 世纪中期以 来，随着计算机通讯网络、柔性制造系统 ( f ms) 异步转换 模式 帆t m) 、电 子商务 ( ec ) 等高 新技术领域的发展， 提出了 大量复杂随 机系 统的设计于控制问 题. 于传统随机模型不同这些系统表现出多层次、 多位相、 变 动参数、 随机环境等复杂特性。 经典生灭过程在处理这些问题时存在着极大的局 限性。 7 0 年代以 来， n e tu s 等系统地发展了结构矩阵分析方法， 使随机模型分析 由 以 指 数 分 布为 核 心 发展 到 广 泛使 用位相型( p h as e type， 简记p h ) 分 布的 新阶 段。 经典生灭过程发展为拟生灭过程， 导致生灭过程稳态分布的古老方法发展为矩阵 几何解方法. 这一变化为复杂随机模型的分析提供了强有力的工具。 在随机模型 的研究和应用中广泛使用这些新思想和新方法，已经成为当代流行的趋势. 2. 2. 1 矩阵解析法 由 于neu ts 发展的矩阵解析法在这十多年来得到空前的发展， 他的两本专著 ( 1 9 81， 1 9 89 ) 2 9 是关于这一方法的 理论 基础和应用领域的 代表作。 他的 两本专著 分别讨论了拟生灭过程于m/ g 八型几 白 r 肋v 过程的基本周期 ( 特别包括忙期在 内) ， 以及它们的矩公式。 以尸 万分布为基础， neu ts引进了gl/ m/l型与m/ g /l 型两类入 白 川 必 v 过程， 使得原来在指数分布假定下才能分析的很多随机模型推广 到尸 万分布的情形。由 于尸 万分布可以 逼近任意非负随机变量的分布， 从而使一 般分布假定下的随机模型能够得到易于计算的逼近。 2. 2. 2 拟生灭过程 拟生 灭 过程 ( q u as i b irth an d d e at h 困ee ss ) 是 经典生 灭过 程的 最 近新发展， 是经典生灭过程 ( 王梓坤，19 801 5 8 ) 从一维状态空间到多维状态空间的推广。 正如生灭过程的生成元具有三对角形式一样， 拟生灭过程的生成元是分块的三对 角矩阵.近二十年已 成为复杂随机模型分析得重要工具 考 虑 一 个 二 维 ma而， 过 程你 (t) ， j (t) ， 状 态 空 间 是 q= ( k ， j ) ， k 之 0 ， 1 j m ， 称扭(t) ， j(t) 是 一 个 拟 生 灭 过 程 ， 如 果 其 生 成 元 可 写 成 下 列 分 块 三 对 角 形 式 硕士论文n级串 联休假开排队网 络系统分析 ( 2 . 1 3 ) 、.月.!十了足 满 c阵 ca方 阶 c0ab 丙bl 2一.、 一一 q 其中所有子块都是m ( ao+ co) e = ( 几+ a + c ) e = ( a + b + oe = 0 鸡和a 有 负 的 对 角 元 素 和 非 负 的 非 对 角 元 素， 其 余 子 块 均 是 非 负 阵 ， 称 状 态 集 ( k ，1) ， ( k 沟， ， ( k ， m) 为 水 平 k 。 若 过 程 是 正 常 返 的 ， 以 ( x ， j)表 示 过 程扭(t) ， j (t) 的 极 限 变 量 ， 并 记 、一 兜 p 扭 ( ;) 二 k ， j( t) = 乃 = p 扭二 k ， j = 乃 ， 其中k 之 0，1 j m . 为 适 应q 的 分 块 形式， 将 稳 态 概率 按 水平写 成分 段 形式 万 * = 伪; ， ， 凡2 ， ， 二 ， ) ， k 之 。 我 们直接引 用下 列结 果， 证明 见文献1 2 9 第三章。 定理2. 2. 1 过程q 正常返，当且仅当矩阵 方 程 r z b+ 无 4 + c=0 的 最小非负 解r 的 谱半 径sp( r) 1 ，并且线 性齐次方程组 二 。 ( ao+ 拙】 ) = 0 有正解。 定理2. 2. 2若矩阵g= a 十 b + c 不可约， 率阵r 满足sp( 刃 万 . ce ， 这里矿是生成元g的平稳概率向量， 满足 万 . g= 0 ， 汀 、= 1 . 定 理2. 2 ，3当 过 程q 正 常 返时， 稳态 概率向 量 可 用 矩阵 几何解表为 凡二 几 r 互 ， k = 0 ，l ， ， 、 硕士论文n级串联休假开排队网 络系统分析 其中汀 。 是 方 程 组汀 。 ( 成十 rbi ) = 0 的 解， 满 足 正 则 化 条 件 才 。 (i一 r ) 一 ， e = 1 。 从2 0 世纪80年代到90年代天田 乃硕等把矩阵 几何解方法引 入到休假排队 模型中， 促进了多服务台休假排队系统的研究， 并且初步建立起多服务台 休假系 统中以条件随机分解为核心的理论框架， 为经典排队轮的发展和应用开辟了更为 广阔的前景。 2 . 3 概率守恒原理 概率 守 恒 原 理设x : = 伏(t ) 才 乃为 具 有 有 限 状 态空间 的 齐 次 马氏 过 程， 状 态 空 间 1 = 0，1 ， k 其 转 移 密 度 矩 阵 为 q = (q ， ) 而 洲而。 若 xt的 所 有 状 态 互 通 ， 则 凡的 平 稳 分 布 乃 ， j o 1 必 存 在 ， 并 满 足 方 程 组 : 艺只 q ， 二 艺 尺 q 。 。 1. j 价 矛k 内 抽1互 目 ( 2 . 1 4 ) 事实上由生灭过程的定理 (2. 1 . 1) 以及题设可知， 乃 一 忽 p(x (t) = j7，菩 该马氏过程必存在平稳分布 凡= 1 且平稳分布应满足 君 。 ， = 艺几 。 。 ， 1 o 1 ( 2 . 1 5 ) 由 于 xt为 有 限 状 态 的 齐 次 马 氏 过 程 ， 故 石满 足 关 系 式 艺 、 ， q ， 一 0 或 ; ， = 艺。 ， ， 。 1 ( 2 . 1 6 ) 落 以 ( 2 . 1 6 )代入 (2. 巧)即 可得 (2. 1 4)。下面说明 (2. 1 4 ) 式的概率含义: 注意 到 (214)左端和式的每一项均可写成 只 叮 ， = 1 油 尸 (x(t ) 二 ) 恕 p ( x ( t + 夕) = j ! x( t ) = 1 ) 夕j) =1 面 l ha 1 份， . 夕弓幻 p (x( t ) = 1 ， x(t + 夕) = j ) 夕 它表示在达到统计平衡状态 (t峥二) 后的任一时刻t ， 系统从状态1 转移到其他 硕 士 论 文 n级串联休假开排队网络系统分析 状 态j 的 转 移 概 率 。 类 似 地(2 .1 4)式 右 端 和 式内 的 每 一 项 几 表 示 在到 达 平 衡 状态后的任 一时 刻t ， 系统 从状态k 转移 到状态1 的 转移 概率。 于是 (2. 1 4) 式表 达了 在系统 进入统计平 衡状 态后的 任一时 刻t ， 对于 系统得 每一状态1 (i 。 1)有等 式: 系统自 状态1 离开的 转移概率 和= 系 统进入状 态1 的 转移概 率和。 上述等式称为概率守恒原理。 一个有限 状态的 马氏 过 程几 = x (t )t。 t经验证得 知能 达到统计 平衡状态 时 ， 则 利 用 上 述 概 率 守 恒 原 理 很易 求 出 其 平 稳 分 布 pj ， j o 1，作 法 如 下: ( 1)求出 价的 转 移 密 度 矩 阵q 二 ( 外 )， 其 中 = 1 而 二 三 竺 上 二 三 里 . 在一般应 用系 统中， 这 往往是很容易 得到的， 然后，画出 其对应的 转移密度图。 (2)在转移密度图中，对于每一个选定的状态1 ，观察其流入1 与流出1 的 密度及 其状态，并根据 概率守 恒原理，写出 该状态应 满足的 稳态方程 艺只 ， ， = 艺 几 。 j 沪 1女 鸽 j j . ik 以 ( 3 ) 一次观察状态空间1 中的每一状态， 满足的稳态方程，从而可得到方程组 (2. 1 4). ( 4 )求解如下方程组，即可得平稳分布 并按照 (2)的方法逐个写出其应 只 ， j 。 月 = 艺几 才 住1 纵个 v自卿川丫川 2 . 4 母函 数方法 定义 设x是取非负 整数值的 离散型随 机变量， 其概 率分布为 几= p 扭= k 孔 k = 0，1 ，2 ， 硕士论文n级串联休假开排队网络系统分析 甲 (2) = 艺 几 zk2 1 称为随即变量x的 概率母函 数， 简 称母函 数。 叭2) 在121 1 上 是 一 致 收 敛 且 绝 对 收 敛， 因 此 ， 母函 数 对 任 何 取 非 负 整 数 值 的随机变量都存在。 母函数的主要性质有: 性质 1 ( 唯一性) 取非 负整数 值的 离散型随即 变量， 其概率分布认 ， k 之 oj与 其母函数是一一对应的。 性质2 若筑x 】 存在，则 e x 卜 备 沙 (2 )z-， 性 质3 设戈， 凡， 二 、 戈均 为 取 非 负 正 整 数 值 离 散 随 机 变 量 ， 若戈， x z ， ， 戈 相 互 独 立， 则x = 戈十 凡 +.二 + 戈的 母 函 数 等 于 各 个 母 函 数 之 积， 即 咒= 气 (z)气 (z) 气 (z) 主要引理 儒 歇定理如 果函 数f(z) 和g(习 在简单闭曲 线l 的内部d 解析， 且在曲 线l 上 有 f (2 ) ， 0 ，f ( 2 ) 卜!9 (2 ) 则 在l 内 部，f ( 习与f ( 2)+g( z)有 相同的 零点 个数。 对于单服务台的排队模型，常采用嵌入马尔可夫链法和补充向量法，如下 2 . 5 嵌入马尔可夫链法 在泊松到达与 服务时间 为负 指数分布的排队 系统中， 在 任何时 刻系统都具有 马 尔可夫性质，因而 可用连续 参数马尔可夫 链的 方法化成可求 解的 平衡方程组， 得到系统的平衡解。对于如m/ g/1或gl / m/l那样的一般服务或一般到达的排 队系 统， 不是在任何时刻系 统都具有马 尔可夫性质， 只是在某 些特殊的随即时刻 系统 才具有这种性 质， 我们称这 种随机时刻点为 再生点， 即从 这个时 刻起， 系统 行为 好像又重新开 始一样。 利 用再生点，前面所述的 如m/ g /l或gl/ m/l那样 的一般服务或一般到达的排队系统的分析， 可用马尔可夫链的方法予以解决， 这 种 方法就叫 做嵌 入马 尔可夫链 法。 徐光辉 6 0 ， 孟玉坷， 唐应辉和唐 小我， 陆传 硕士论文n级串联休假开排队网络系统分析 赛， 华兴， 孙荣恒和李建平， 对此做了详细的论述。以下我们说明马尔可夫链并 以 经典的m/ g 门排队 系统为 例， 说明如 何寻求马 尔可夫嵌入点. 定 义 网设 随 机 过 程 x (t) ，t o t的 状 态 空 间 5 为r 中 的 可 列 集， 如 果 对t 中 任意。 个t ， t z 0)， 由 于 到 达 流 是 尸 。 “ ion流 ， 在 这 些 再 生 时 刻 ， 观 察 系