（概率论与数理统计专业论文）带负顾客等呼叫中心特性的离散时间休假排队模型.pdf

江苏大学硕士学位论文 摘要 离散时间排队的研究越来越受到重视，本课题主要研究了带负顾 客等呼叫中心特性的离散时间休假排队系统，主要包含三个部分的内 容： 首先研究了n 策略、负顾客、反馈g e o g e o l 多重休假排队模型。 利用拟生灭过程和矩阵几何解的方法得到了队长稳态分布的存在条 件和表达式，系统处于假期和忙期的概率以及稳态下系统队长的条件 随机分解和由休假引起的附加队长的分布表达式。 其次考虑了带负顾客和( p ，n ) 策略启动期g e o g e o l 多重休假排 队。利用拟生灭过程和矩阵几何解的方法，我们得到了队长稳态分布 的存在条件、表达式，稳态下系统队长的条件随机分解及由休假引起 的附加队长的分布表达式。 最后研究了带r c h 抵消策略的负顾客g e o g e o l 单重休假排队。 利用拟生灭过程和矩阵几何解的方法，我们得到了队长稳态分布的存 在条件、表达式，稳态下系统队长的条件随机分解及由休假引起的附 加队长的分布表达式。 关键词：离散时间排队；负顾客；n 策略；反馈；启动期；矩阵几何 解；条件随机分解。 江苏大学硕士学位论文 一_一 a b s t r a c t d i s c r e t e t i m eq u e u em o d e li sb e i n gp a i dt om o r ea n dm o r ea t t e n t i o n t h i sp a p e rm a i n l yr e s e a r c hd i s c r e t e t i m eq u e u e sw i t hv a c a t i o ns c h e d u l e a n dc a l l c e n t e rf e a t u r e ss u c ha sn e g a t i v ec u s t o m e r ，w h i c hm a i n l yi n c l u d e s t h r e ec o n t e n t s ： f i r s t l y , aq u e u eo fg e o g e o 1t y p ew i t hn p o l i c y , n e g a t i v ec u s t o m e r , f e e d b a c ka n dm u l t i p l ev a c a t i o n si sd i s c u s s e d t h ee q u i l i b r i u mc o n d i t i o n a n dc o n c i s ee x p r e s s i o no ft h es t e a d y s t a t ed i s t r i b u t i o nf o rt h eq u e u e l e n g t ha r eo b t a i n e db yu s i n gq b dp r o c e s sa n dm a t r i x g e o m e t r i cs o l u t i o n m e t h o da sw e l la st h ep r o b a b i l i t yw h e nt h es y s t e mi so nv a c a t i o na n d b u s y m e a n w h i l e ，t h ec o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o ns t r u c t u r eo f t h eq u e u el e n g t hi ns t e a d ys t a t ea n dt h ed i s t r i b u t i o no fa d d i t i o n a lq u e u e l e n g t hc a u s e db yv a c a t i o n sa r ea l s oa c q u i r e d s e c o n d l gaq u e u eo fg e o g e o 1t y p ew i t hn e g a t i v ec u s t o m e r , ( p ，n ) p o l i c ys e t - u pt i m ea n dm u l t i p l ev a c a t i o n s i ss t u d i e d t h ee q u i l i b r i u m c o n d i t i o na n dc o n c i s ee x p r e s s i o no ft h es t e a d y - s t a t ed i s t r i b u t i o nf o rt h e q u e u el e n g t ha r eo b t a i n e db yu s i n gq b dp r o c e s sa n dm a t r i x 。g e o m e t r i c s o l u t i o nm e t h o da sw e l la st h ep r o b a b i l i t yw h e nt h es y s t e mi so nv a c a t i o n a n db u s y m e a n w h i l e ，t h ec o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o ns t r u c t u r e o ft h eq u e u el e n g t hi ns t e a d ys t a t ea n dt h ed i s t r i b u t i o no fa d d i t i o n a lq u e u e l e n g t h c a u s e db yv a c a t i o n sa r ea l s oa c q u i r e d l a s t l y , ag e o g e o 1q u e u i n gs y s t e mw i t hr c hs t r a t e g yo fn e g a t i v e c u s t o m e r sa n ds i n g l ev a c a t i o n si ss t u d i e d t h ee q u i l i b r i u mc o n d i t i o na n d c o n c i s ee x p r e s s i o no ft h es t e a d y s t a t ed i s t r i b u t i o nf o rt h eq u e u el e n g t ha r e o b t a i n e db yu s i n gq b d p r o c e s sa n dm a t r i x g e o m e t r i cs o l u t i o nm e t h o d a s w e l la st h ep r o b a b i l i t yw h e nt h es y s t e mi s o nv a c a t i o na n db u s y m e a n w h i l e ，t h ec o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o ns t r u c t u r eo ft h e 江苏大学硕士学位论文 q u e u el e n g t hi ns t e a d ys t a t ea n dt h e d i s t r i b u t i o no fa d d i t i o n a lq u e u e l e n g t hc a u s e db yv a c a t i o n sa r ea l s oa c q u i r e d k e yw o r d s ：d i s c r e t e - t i m eq u e u e ；n e g a t i v ec u s t o m e r ；n - - p o l i c y ；f e e d - b a c k ；s e t - u pp e r i o d ；m a t r i x - g e o m e t r i cs o l u t i o n ； c o n d i t i o n a ls t o c h a s t i cd e c o m p o s i t i o n 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和 电子版，允许论文被查阅和借阅。本人授权江苏大学可以将本学 位论文的全部内容或部分内容编入有关数据库进行检索，可以采 用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口 本学位论文属于，在年我解密后适用本授权书 不保密口 学位论文作者签名：扪一莹豸 2 0 0 9 年1 2 月2 0 日 指导教师签名： 2 0 0 9 年1 2 月 独创性申明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名幽，萎易 日期：2 0 0 9 年1 2 月2 0 日 江苏大学硕士学位论文 第一章本论文相关的排队论研究简介 1 1 关于离散时间排队模型的论述 1 1 1 离散时间排队的发展过程 排队论经历了百年历程，己发展成为运筹学和应用概率中的重要分支学 科经典排队论主要研究和处理各种连续时间系统，已经确立了成熟的理论体系， 并在生产、交通、服务、通信、管理和军事领域得到了广泛的应用 2 1 世纪是信息化时代，计算机和计算机网络的应用已经遍布社会活动和生 产活动的各个领域，信息革命正在改变着传统科学技术领域的思想观念，理论基 础和研究方法在当代计算机产业和宽带综合业务数字网络( b i s d n ) 中，语音、 数据、图像等各种业务都将通过数字化分割成固定长度信元或包，进行统一的处 理和传输一个业务量的大小，用它所包含信元的个数来度量；一个需求占用的 服务时间，是单位信元处理时间的整倍计算机系统和b i s d n 中大量操作环节和 运行过程，更自然地表现出离散时间现象的本质特征计算机科学和信息技术的 发展，激发了人们对离散时间系统的关注和探索，离散时间排队正是在这种背景 下产生和发展起来的 离散时间排队有着广泛的应用背景，特别是计算机通信技术的发展，极大的 推动了离散时间排队的眼睛和应用例如，在宽带综合业务数字网络( b - i s d n ) 中，异步转移模式( a t m ) 被国际电联电信标准部确立为未来的通用技术之一 在交通领域，火车、飞机在确定时刻到达，这些系统均可用离散时间排队模型来 刻画 离散时间排队的研究是较晚才开始的1 9 5 8 年，m e i s l i n g 的论文研究了 g e o m g 1 离散时间排队模型，是离散时间排队分析的起点由于离散时间排队 更适合于计算机系统建模和性能分析，引起了大批排队论和通信工程专家的关 注，并迅速产生了大量理论分析及实际应用成果h u n t e r 对离散时间排队的早 期成果给出了一个系统的处理k o b a y a s h ie ta l ( 1 9 7 7 ) 在计算机通信领域应用 中运用了离散时间排队的相关理论t a k a g i 从为计算机系统性能分析提供数学 工具的角度出发，对各种g e m o g 1 系统给出了完整的分析b r u n n e l 、k i m 及 w o o d w a r d 也使用离散时间排队进行计算机系统和通信网络分析和设计g r a v e y 与h e b u t e r n e ( 1 9 9 2 ) 引入并研究了各种各样的入口行为及其相互关系在国内， 江苏大学硕士学位论文 孙荣恒等亦对离散时间排队进行了系统的分析 1 1 2 离散时间排队系统的主要组成部分 同连续时间排队一样，一个离散时间排队系统主要由下列三部分组成： ( 1 ) 到达模式顾客到达只能发生在时间轴上的整点处若在每个时隙分 点上最多到达一个顾客，称为单个到达如果允许一个整点处有许多顾客同时到 达，称为成批到达这时除了到达问隔分布以外，还需给出批量分布 ( 2 ) 服务机制首先应规定服务场所中服务员的个数，只有一个服务员称为 单服务台系统；多个服务员并列地接待顾客称为多服务台系统 如果在任何时刻，服务台最多只能接待一个顾客，称为单个服务的，服务台可同 时接待多个顾客称为成批服务的对后一种情况，服务员可同时接待的顾客数称 为批量服务，它可以是定数，也可以是个随机变量 ( 3 ) 排队规则当系统中有多个顾客排队等待时，一旦服务台空出，如何 安排队列中顾客进入服务台的方式称为排队规则在大多情况下，按到达顺序安 排顾客服务，称为先到先服务( f i f o ) 依据不同的应用背景，也需要引入其他 排队规则如后到先服务( l i l o ) 、随机顺序服务( s i r o ) 按照顾客的优先权分： 抢占型优先权和非抢占型优先权 在离散时间排队系统中，亦使用k e n d e l l 引入的记法来表示按这种记法， 写成a b c 的形式，符号a 和b 分别用于描述到达间隔和服务时间的分布类型， c 是数字，用于表示系统中服务台的个数a 和b 将用一些特定的符号取代，通 用记号是： d ：表示定长分布：g e o m ：表示集合分布：g ：表示一般分布 对连续实际排队模型，主要关心的仍然是系统中顾客数、等待时间和忙期等 性能指标区别在于，不仅系统中顾客数，现在，等待时间和忙期也是整值随机 变量 1 1 3 离散时间排队系统的入口协议 在连续时间排队中，顾客到达和离去等事件发生于同一时刻的概率为零，因 此，总可以区别这些事件发生的先后顺序在离散时间排队中，所有事件发生在 时间轴上的整点处，在同一个时间轴的整点处，既可以发生顾客的到达，也可以 发生顾客的离去关于在整点时刻到达和离去、服务开始或结束规则的更细致的 2 江苏大学硕士学位论文 约定，统称为入口协议一般分为两种不同的情况： ( 1 ) 早到系统( e a r l ya r r i v a ls y s t e m ) ：到达发生在时隙首端( 刀，n + ) 处， 服务完成只能发生于时隙末端q 一，n ) 处 ( 2 ) 晚到系统( 1 a t ea r r i v a ls y s t e m ) ：到达发生在时隙末端( n - 9 n ) 处，服 务完成只能发生于时隙首端( 以，n + ) 处 在晚到系统中有分为：有直接入口的晚到系统( i m m e d i a t ea c c e s s ) ：到达 的顾客遇到空闲服务台可立即开始服务，并且服务可能在( 以，n + ) 处结束有延 迟入口的晚到系统( d e l a y e da c c e s s ) ：到达的顾客遇到空闲服务台，其服务不能 在( ，z ，n 十) 处结束 在分析一个离散时间排队模型时，必须明确规定入口协议及考察时刻，才能 确保系统状态有明确的意义 1 2 带有n 策略和( p ，n ) 策略的排队系统的研究现状 在排队系统的研究过程中，为了节约系统运作成本或节省运作时间，有学者 提出了n 策略的概念y a d i n 和n a o r n3 首次引入了n 策略的概念，利用n 策略来 限制服务台的开始时刻，当系统中的顾客数大于或等于n 时服务台开始服务最 近，m o r e n o 瞳1 则研究了批量服务先到达的n 个顾客，其余的顾客单个服务，并对 g e o g 1 离散时间排队系统的各项性能指标给出了一个更为详细的推导最近， 许多学者把n 策略引入到休假排队系统中，大大丰富排队论的理论体系 1 9 9 6 年，f e i n b e r g 和k i m 1 首次提出了随机n 策略的概念即( p ，) 策略，在 忙期结束后，当系统中的顾客达到事先设定的数量时服务台以一定的概率随机启 动但在一些带有随机n 策略的离散时间排队中，部分稳态解的求解过程和结果 还不完善，还有待于我们继续去研究 1 3 带有负顾客的排队系统的研究现状 负顾客排队模型时排队论的一个新兴的研究方向自从上世纪九十年代 g e l e n b e 提出这一课题的研究后，该领域一直受到学者的关注 g e l e n b e 是将负顾客引入排队模型h 1 和排队网络畴3 的第一人在近来的研究 3 江苏大学硕士学位论文 中，负顾客可视为一次误操作或是系统的灾难或可看成是某些工作的外来援助， 一般作为系统的制约因素而存在，能抵消队伍中的正顾客，而通常的顾客被视为 正顾客 大多数学者都是让负顾客只起抵消作用，负顾客的抵消原则有两种： c h ( r e m o v a lo fc u s t o m e ra tt h eh e a d ) 和r c e ( r e m o v a lo fc u s t o m e ra tt h e e n d ) r c h 指到达的负顾客抵消正在被服务的正顾客( 若有) ，r c e 指到达的负顾 客抵消队尾的j 下顾客( 若有，不管该顾客是在等待还是在被服务) h a r r i s o n 和p i t e l 阳，刀考虑具有负顾客的m g 1 排队模型b a y e r 和b o x m a 陋3 运用w i e n e rh o p f 分析，证明了一类新的更具一般性的随机徘徊理论 负顾客还可以解释为灾难13 i ，灾难发生时抵消系统中所有的顾客，也可以 解释为集体退出或队伍溃散韩国学者c h a e n 4 1 分析了m g 1 清空系统考虑一 次灾难发生后，系统中的顾客全部消失，服务台失效 a r t a l e j o 和c o r r a l n 印研究了一个既有清理又有竞争再入的排队，即新到达 的顾客发现系统忙时会进入轨道等待，且轨道中的顾客与j 下在服务的顾客以一定 的比例竞争接受服务，灾难发生时系统彻底清理并立即更新 最近，朱翼隽n 6 1 提出负顾客可以接受服务的思想，讨论了一类负顾客m g 1 排队模型，得到队长分布的概率母函数、虚等待时间及等待时间的l s t 表达式文 献n 7 1 通过补充变量法，对具有负顾客的m g 1 模型在不同服务规则的抵消策略下 的对长进行了研究，也得到了各自对长分布的广义概率母函数还首次把负顾客 引入到可修服务中 后来，有学者把负顾客引入休假排队系统，也有学者把负顾客引入可修排队 系统，得到一系列排队指标和可靠性指标的形式解，大大丰富了负顾客排队模型 的理论体系 对负顾客排队的研究是不同领域中发生的许多时间问题的必然目前，负顾 客排队主要的讨论工具有：标值点过程法、补充变量法、w i e n e rh o p f 分析法和 矩阵分析法，尤其以补充变量法建立向量马氏过程最为普遍主要的研究对象是 对长、等待时间和忙期分布 负顾客排队已取得了一定进展，但也有问题尚待解决此外，现有的结果中， 有些因式过于复杂而难以付诸于应用，发展有效的算法或给出简单适用的逼近也 是很有意义的 4 江苏大学硕士学位论文 i 4 休假排队的研究现状 休假排队泛指服务台在某些时候不能被顾客利用的排队系统导致服务暂时 中断的理由可以有各种各样的解释，而而暂时不能用于接待顾客的那些时间统称 为休假 休假排队的研究是从2 0 世纪7 0 年代才开始的l e v y 与y e c h i a li ( 1 9 7 5 ) 从有效 利用排队系统闲期的观点出发，首先研究了m g 1 型休假排队系统，并引入了“休 假”和“休假策略”等术语一方面，休假排队反映了服务过程可能因某种理由 发生中断这一客观事实；另一方面，各种休假机制为系统的优化设计和运行控制 提供了极大的灵活性在8 0 年代，研究的重点是修建m g i 型排队c o o p e r ( 1 9 7 0 ) ， c o u r t o i s ( 1 9 8 0 ) ，f u h r m a n n ( 1 9 8 4 ) ，f u h r m a n n c o u r t o i s ( 1 9 8 5 ) ，h a r r i s 与m a r c h a l ( 1 9 8 8 ) ，k e i i s o n 与r a m a s w a n y ( 1 9 8 8 ) ，l e v y 与k l e i n r o c k ( 1 9 8 6 ) 等众多工作相继讨 论了各种休假策略及服务规则的m g 1 型排队系统，初步形成了以随机分解为核 心的修建排队理论框架1 9 8 6 年，几何同时在美国和欧洲发表了d o s h i ( 1 9 8 6 ) 和 t e g h e m ( 1 9 8 6 ) 两篇论文，总结了已有的研究成果和方法，标志着休假排队已发展 成为一个有独立特色的研究方向从8 0 年代末到9 0 年代，田乃硕等( 1 9 8 9 ) n 8 1 首先把矩阵几何解方法引入休假排队研究，推进了g i m 1 型休假排队系统和多服 务台休假排队系统的研究 2 0 多年的发展表明，休假排队研究不仅为经典随机服务系统理论的发展注入 了新的活力和生机，也为排队论在各种高新技术领域的应用开辟了更广阔的前 景 1 5 本课题研究的内容及解决问题的方法 前面介绍了离散时间排队论的发展及其相关知识，并分析了带n 策略或 ( 阢) 策略、负顾客以及带有休假的排队系统的研究现状然而将上述所提及的 排队系统的特点结合起来考虑的排队系统却很少讨论本文立足于此，首次探讨 了带有n 策略或( p ，) 策略、负顾客、反馈和启动期的离散时间休假排队系统， 通过拟生灭过程和矩阵几何解方法，求得了系统队长的稳态分布，证明了队长的 随机分解等 本文分五章，第一章为本论文相关的离散时间排队论的研究简介，包括离 散时间排队模型的论述，带有n 策略或( p ，n ) 策略、负顾客和休假排队模型的研 5 江苏大学硕士学位论文 究现状第二章为研究排队模型的主要方法，列出了几种常见的求解排队模型的 方法第三章为n 策略、负顾客、反馈g e o g e o 1 多重休假排队模型第 四章为负顾客和( p ，) 策略启动期g e o g e o l 多重休假排队第五章 带r c h 抵消策略的负顾客g e o g e o 1 单重休假排队 江苏大学硕士学位论文 第二章研究排队论模型的主要方法 研究排队论的主要方法有：拟，上灭过程和矩阵分析法、嵌入马尔可夫链法 和补充变量法其中，最近比较流行的方法是拟生火过程和矩阵分析法 。2 1 拟生灭过程和矩阵分析法 w a l l a c e ( 1 9 9 6 ) 首次提出了“拟生灭过程( q b d ) 这一术语2 0 世纪7 0 年 代以来，n e u t s ( 1 9 8 1 ) n 叫等系统地发展了处理q b d 的矩阵分析方法，有力地推动 了q b d 过程在随机模型分析中的广泛应用 定义 考虑一个二维m a r k o v 过程仁 ，j ) ，状态空间是 q = ，办k o ，1 j m ) ，状态集 1 ) ，( k ，i 岍称为水平七，k o 如果将状态 按字典顺序排列后，其生成元可写成下列分块三对角形式： q = 厶c o ea g 垦如q b 。a 。c 。 ( 1 ) 则称弘 ，( f ) ) 是一个拟生灭过程( q b d ) 其中所有字块是m 阶方阵，a ，k 0 ， 有负的对角线元素和非负的非对角线元素，并且行和非正b k ，q 都是非负阵， 满足 ( a + g ) p = ( 4 + 嘎+ g ) p = o ， k 1 迄今广泛使用的只是一类特殊的q b d ，即生成元蚕中的子块从某个水开始不再发 发生变化的情形，这时，过程生成元形如： q = 7 ( 2 ) c c a a 口 一 ；缸口 0 o 1 c a 知历 江苏大学硕士学位论文 若过程是正常返的，以伍，j ) 表示过程弘 ，厂 】的极限变量，并记 2 。l 。i r a 。尸 x ( f ) = 后，( f ) = = p x = k ，= ) ，其中七o ，1 j 朋为适应q 的分块形式，将稳态概率按水平写成分段形式以= ( 气，巩：，l k m ) 对于连续时间排队，常用的定理有： 定理1 啪1 形如( 2 ) 式的复杂边界q b d 过程正常返当且仅当矩阵方程 曰2 b + r 4 + c = 0 的最小非负解r 的谱半径s p ( r ) 1 ，并且以随机阵 b r 】= 厶c 0 眉4q e qa c dc 。 曰r b + a 为系数的齐次线性方程组有正解当过程正常返时，稳态分布可表为 并且，万l 由方程组 吒= 刀c 科1 ， k c c - 1 ( ，t 垆【刚= on k e + t t c ( i r ) 一1 寥= 1 k 如 唯一决定 上述定理表明，对于复杂边界的0 8 0 ，当k c 时，稳态概率向量显示出矩阵 几何分布的特征，称这类分布是具有修正边界的矩阵几何解 定理2 啪1若h = 4 + 曰+ c 是有限的不可约生成元，万是日的平稳概率 向量，即 槲= 0 ，册= l ，贝, u s p ( r ) 砌 相对应的离散时间排队，常用的定理有： 定理3 汹3对于转移概率矩阵形如下式的拟生灭链 p = 氐。 且aa 如aa 8 江苏大学硕士学位论文 其中是m 。阶方阵，a o 。是m 。x m 阶矩阵，置是历胁，阶矩阵，a ( 七= 0 ，1 2 ) 是 m 阶方阵，其正常返的充要条件是：矩阵二次方程 r 2 如+ 她+ a = r 的最小非负解r 的谱半径s p 俾) 1 并n m 。+ m 阶随机阵 即，= ( 翟a 乞： 存在正左不变向量当m c 缸。，。) ，厅o ) 正常返时，其平稳分布满足 吒= 万1 科1 k 1 ( ，玛) = ( ，雹) b 【r 】 n o e + 万1 ( j 一足) e = 1 拟生灭过程是经典生灭过程从一维状态空间到多维状态空间的推广，正如生灭 过程的生成元具有三对角形式一样，拟生灭过程的生成元是分块三对角阵 从2 0 世纪8 0 年代到9 0 年代田乃硕等把n e u t s 的矩阵几何解方法引入到多服务台休 假排队模型中，促进了多服务台休假排队系统的研究，并且初步建立起多服务台休假 中以条件随机分解为核心的理论框架，为经典排队论的发展和应用开辟了更为广阔的 前景 拟生灭过程是当今比较流行的一种方法，它解决了一些传统方法不能解决的模 型，如p h 分布模型，它也是本课题所用的主要方法，其具体的使用方法相见后面的 三篇论文 2 2 嵌入马尔可夫链法 2 2 1 基本概念 定义1 设随机过程讧( f ) ，t z ) 的状态空间s 为r 中的可列集，如果对r 中 任意，z 个 f 2 o ) 由于到达流是 p o i s s o n 流，在这些再生时刻，观察系统的顾客数，它具有马尔可夫性n 。表 示一个顾客服务结束后刚离开系统时留在系统中的顾客数，则 。) 就是一个马 尔可夫链，这叫嵌入马尔可夫链由于t 。 一t 。对一切玎都是同分布的，到达流又 是p o i s s o n 流，于是经过f 。丑一t 。这段时间，系统从状态。到。+ l - 1 状态的概 率相同，因此是一个齐次马尔可夫链为求得此马尔可夫链的平稳分布，首先应 求出转移概率 2 2 3 状态转移分析 以某一顾客服务结束后离开系统时的队长作为系统的状态，因此系统的一步 转移就是一个顾客离开系统到下一个顾客离开系统这段时间系统状态的变化 设服务时间曰的密度函数为6 0 ) ，平均服务时间为 e 阶f 烈f ) 拈1 b ( t ) 的l 变换记为b + ( s ) ，即 曰( s ) = j c o e - t b ( t ) d t 其中要求g ( s ) 0 ，即s 的实数部分大于零再设 p = 九| l l 。 c 。：表示进入系统的第胛个顾客；t 。：表示第行个顾客服务完离开系统时刻： 乙：表示c 。服务完离开系统的时刻， n 。：表示第疗个顾客离开系统后的队长；b 。：表示第，z 个顾客的服务时间； 江苏大学硕士学位论文 k ：表示c 。的服务时间， a n ：表示第珂个顾客的服务时间内到达系统的顾客数 由定义知 y 。 是独立同分布的随机变量序列，分布密度为酞f ) ，似 是独立 同分布的随机变量序列，概率分布记为p 。) ，贝1 ja 。三尸( a = 七) 由于服务时间是随机的，事件似。= 七) 表示在第咒个顾客的服务时间曰。内到 达七个顾客，而0 曰。 0 时，服务台立刻接受第，l + 1 个顾客进行服务服务时间为玩 这段时间达到的顾客数为a h 第万+ 1 个顾客服务结束离丌系统时，系统内有顾 江苏大学硕士学位论丈 客数n 。+ 1 = n 。+ a 。+ l 一1 ( 2 ) 当n 。= 0 ，则第，z 个顾客离开系统后，系统内无顾客，服务台处于空闲 状态，这时第咒+ 1 个顾客还未到达第n + 1 个顾客到达后立刻接受服务在其 接受服务时间内到达a 州个顾客因此第疗+ 1 个顾客服务完，离开系统时留下的 队长。+ 1 = a 。+ 1 因此由时刻f 。到时刻f 州的顾客转移为 = 艮a + l 麓蛩 设p 玎= 尸( 州= _ ln 。= f ) ， 当f = 0 时，p o ，= p ( 。+ 1 = in 。= o ) = p 似。+ l = j ) = 口， ( 2 1 ) 当z 1 时，p 玎= j p ( 。+ l = | l 。= f ) = p ( 。+ a 。+ l 一1 = j ln 。= d = p ( a 。+ l = ，一f + 1 ) = 口卜。+ 1 ，( j f 一1 ) ( 2 2 ) 由此得一步转移概率矩阵p = ( 既) = 口o口1口2 口o口l口2 0 口。口1 0 0 a o 由上面可知， 虬) 是一个齐次马尔可夫链，且非周期不可约，当p = 昙 o 不是马氏过程，但是可以通过引入补充变量使得这个非马氏过程马 江苏大学硕士学位论文 氏化e r l a n g 的阶段化思想可以看成是补充变量法产生的初始背景c o x 完整地 提出了补充变量的技巧下面我们以经典的m g 1 排队模型为例来说明用补充变 量法解决排队问题的主要思路 考虑一个经典的m g 1 排队模型，顾客按到达率为五的p o i s s o n 过程到达， 服务时间为一般分布： g g ( 归胁渺- l - e x p ( 一j c o 雕陟) ，e ) = 石1 其中( 力为服务时间的风险率函数系统中只有一个服务台，顾客按先到 先服务( f c f s ) 的规则接受服务如果到达的顾客发现服务员正在为别的顾客服 务，他就依次排队等待假定等待空间无限，开始时系统中无顾客 设( f ) 表示f 时刻系统中的顾客数，显然o ) 不是状态空间e = o ，1 ，2 ，) 上 的马尔可夫过程通过引进补充变量x ( t 1 ) = x 表示正在服务的顾客在时刻f 已接 受过的服务时间， 则向量过程 ( f ) ，x ( o ) 是状态空间 韪= ( ，z ，砷h = o ，l 2 , ；o x 两端除以& 并令出一0 整理可得 ( 五+ 丢p mf g 玳帆 江苏大学硕士学位论文 令，j0 0 可得 弛= r m g 她g ) 妣 同理可得( 丢+ 兄+ g 归协饵劓， 纠 边界条件 毋( 0 ) = 弛+ j ：e e ( x ) ( x ) a x ， 只( 0 ) 2 上只+ - ( x ) ( x ) 妣 ，l = 2 ，3 ， 最后通过对上面方程的求解，得到一些我们感兴趣的排队指标 1 6 江苏大学硕士学位论文 第三章n 策略、负顾客、反馈g e o g e o 1 3 1 引言 多重休假排队模型 由于离散时间排队系统研究的相对复杂性，现在离散时间排队的研究成果较 连续时间是少之又少，本文首次将n 策略、负顾客、反馈和休假机制同时引入到 离散时间排队系统中运用拟生灭过程和矩阵几何解法，得到了相关的排队指标 3 2 模型的描述 正、负顾客的到达问隔丁+ 、z 一，休假时间y ，正顾客的服务时间s 分别服 从参数为p + 、p 一、乡、的几何分布系统中只有一个服务台，当系统中的正 顾客数为零时，系统进入休假状态，在休假期间，服务台不参与服务 其中 0 p + ，p 一，0 ， l j = o 册， 将m c 的状态按字典顺序排列，其状态转移矩阵可写成如下分块的形式： 0 1 2 p = 一2 一1 n p + a 。 a 。a氐 如aa 如aa 如a 民 如e ( 1 ) 具甲 a 12 ( p ( o ，o x l ，o ) ，p ( o ，o x l 1 ) ) 2 印u ) 舻l p 蜥( i o x o 聊 o ) - ( 而；前 a = ( 7 0p p 而p 彬p 而p , 0 - 易l+ 一+ p + 一+ p + 一f + p + 一手) j a = ( ：p 葡0 而，如= 口矾劢 日= r 0p 讥p 万p 万+ p 毫p 孝+ 而pp i+ 一+ p + 一+ + 一孝+ + 一( 1 一易j 战2 1 0p + _ p 五+ 磊p l+ 一+ p + 一( 1 0 j 引理1 2 0 对于转移概率矩阵形如下式的拟生灭链缸。，j 。) ，万o ) p = a ， 局4a 如aa 其中b o o 是，1 阶方阵，a o 。是珊。xm 阶矩阵，墨是聊m ，阶矩阵，a ( 尼= 0 ，1 2 ) 是 m 阶方阵，其j 下常返的充要条件是：矩阵二次方程 r 2 如+ 魈+ a = r 的最小非负解r 的谱半径s p ( r ) 1 并且m 。+ m 阶随机阵 江苏大学硕士学位论丈 b ：，1 lb 1 a o l、 a l + r a ：j 存在正左不变向量当m c 犯。，j 。) ，l 0 正常返时，其平稳分布满足 巩= 码尺 k 1 ( ，珥) = ( 万o ，玛) 曰【r 】 e + 玛( j - r ) 一e = 1 对于( 1 ) 式 企 吖 日5 钆a ， a 。aa 如aa 如a 氐 如a 0 1 2 一3 一2 则转移概率阵( 1 ) 可转化为形如( 2 ) 式的转移阵，从而得到如下的推论： 推论1 对于转移概率阵形如( 1 ) 式的拟生灭链 。，j 。) ，厅o ) ，其正常返的 充要条件是矩阵二次方程 r 2 如+ r b l + 既= r 的最小非负解足的谱半径s p ( r ) 1 且随机阵 b r 】- a 0 0a 0 1 a 1 0a l a o a ：a 1a - a ：a 1a a 2r a 2 + a l 存在正左不变向量当m c 。，。) ，刀o ) 正常返时， 吒= 一1 r 一+ 1 ( ，刀1 ，刀- q 归【刚= ( ，巩，万q ) r 一2 巩p + 1 ( i - r ) 。1 口= 1 k = 0 0 1 2 一2 一1 其平稳分布满足 k n 定理1 若口 1 ，则矩阵方程：r = r 2 如+ r b l + b o 有最小非负解 r = ( 矧 1 9 江苏大学硕士学位论文 其中口：翌：矍兰2