（应用数学专业论文）mg1型非空竭服务休假排队系统的随机分解.pdf

江苏大学硕士学位论文 摘要 本文讨论一般非空竭服务w g i 型休假排队系统及其变体的稳态队长随机分解。 运用广义分支链，在独立休假策略下得到稳态队长随机分解的一般结构，而且各部 分随机分解结构的概率含义明确。利用随机分解一般结构式从独立休假策略与经典 m g i 变体两方面来推广f u h r m a n n 与c o o p e r ( 1 9 8 5 ) 的随机分解的结论，得到一系 列非空竭服务m c i 型休假排队系统变体稳态队长的随机分解。实现了一般非空竭 服务m g i 型休假排队系统稳态队长的随机分解的统一处理。简化了再生循环方法 的繁琐运算。 并讨论了一般非空竭服务m g i 型休假排队系统的嵌入更新过程常返的条件， 为稳态队长与等待时间的随机分解奠定理论基础。并且在独立休假策略下进一步简 化f u h r m a n n 与c o o p e r ( 1 9 8 5 ) 休假排队系统的随机分解的条件，得到完整的随机分解 结构。 在独立休假策略下，根据m c i 型非空竭服务休假排队系统稳态队长随机分解的 结构特征提出一种新型算法：结构分析法。该方法简洁高效，避免了再生循环方法 繁杂的运算。运用该方法得出的结果与已知的用再生循环方法得出的结论一致，并且 修正了l e u n g ( 1 9 8 9 ) 关于b e r n o u lli 闸门服务休假排队系统随机分解的一个错误。进 一步讨论了m g i 型一般限量、减量服务单重休假排队模型，运用结构分析法得到 稳态队长和服务时间的随机分解的母函数和拉氏变换，并给出稳态分布成立的条件。 对于非独立休假策略排队系统，运用再生循环法，讨论了非零服务期m g i 闸门 服务排队系统的随机分解，得到稳态队长和等待时间母函数( p g f ) 及拉氏变换 ( l s t ) 。可根据其随机分解的结构特征，为非空竭服务休假排队系统的排队指标 的控制提供直接依据。 关键词：休假排队，随机分解，广义分支链，稳态队长，再生过程，平衡条件，结 构分析法 江苏火学硕，i ：学位论文 a b s t r a c t i n t h i sp a p e rap r o p e r t yo fs t o c h a s t i cd e c o m p o s i t i o nw i t hi t sc e r t a i ns t r u c t u r ei s d i s c u s s e do nt h em g 1v o c a t i o nq u e u eo ri t sv a r i a n t sw i t hn o n e x h a u s t i v es e r v i c e w i t h i n d e p e n d e n tv o c a t i o np o l i c yac e r t a i ns t r u c t u r eo fs t o c h a s t i cd e c o m p o s i t i o no fs t e a d y q u e u el e n g t hi sa c q u i r e d b a s e do nt h eg e n e r a ls t r u c t u r e ，t h es t o c h a s t i cd e c o m p o s i t i o ni s e a s i l yo b t a i n e do fs e v e r a lc l a s so fq u e u e so fm g 1t y p ev a r i a n t sw i t hc e r t a i nv o c a t i o n p o l i c y t h er e c c u r e n tc o n d i t i o ni sd i s c u s s e do ft h er e g e n e r a t i v ep r o c e s se m b e d d e di nam g 1 t y p ev o c m i o nq u e u e 州t hn o n e x h a u s t i v e ，w h i c hi sas u f f i c i e n tc o n d i t i o no ft h eq u e u e s s t e a d ys t a t e b a s e do nt h i sr e s u l ta n di n d e p e n d e n tv o c a t i o np o l i c yw eg e taw e a k e rs t e a d y c o n d i t i o no fq u e u es y s t e mw i t hi t sd e c o m p o s i t i o no f f e r e d b yf u h r m a na n dc o o p e r ( 19 8 5 ) m o r e o v e r , as i m p l i f i e dm e t h o dc a l l e ds t r u c t u r e a n a l y s i sm e t h o di so f f e r e da c c o r d i n gt o p r o p e r t yo fs t o c h a s t i cd e c o m p o s i t i o no fm g 1t y p ev o c a t i o nq u e u ew i t hn o n e x h a u s t i v e s e r v i c e w i t ht h i sm e t h o do p e r a t e do ns o m et y p i c a lm g 1n o n e x h a u s t i v ev o c m i o nq u e u e ， t h es a m er e s u l tw a so b t a i n e da st ot h ek n o w no n e sa c q u i r e db yt h er e g e n e r a t i v e c y c l e m e t h o d a ne r r o ri sa l s oc o r r e c t e do nt h es t o c h a s t i cd e c o m p o s i t i o no fm g 1t y p ev o c a t i o n q u e u ew i t hb e r n o u l l i - g a t e ds e r v i c e w i t hs t r u c t u r e a n a l y s i sm e t h o dam g 1t y p es i n g l e v o c a t i o nq u e u ew i t hg e n e r a ld e c r e a s e ds e r v i c eo rg e n e r a l - l i m i t e ds e r v i c ei sd i s c u s s e d ，t h e s t o c h a g i cd e c o m p o s i t i o no fq u e u e l e n g t ha n dw a i t i n gt i m ew i t hg e pa n dl s to nt h e s t e a d ys t a t ei sa l s oo b t a i n e d i nt h ee n d ，am g 1t y p ev o c a t i o nq u e u e 谢t 1 1n o n z e r os e r v i c e p e r i o di sd i s c u s s e d w i t h t h e r e g e n e r a t i v e - c y c l e m e t h o dt h es t o c h a s t i c d e c o m p o s i t i o n o fq u e u e - l e n g t ha n d w a i t i n g - t i m ew i t hg e pa n dl s to nt h es t e a d ys t a t ei st o oa c q u i r e d t h es t o c h a s t i c d e c o m p o s i t i o ni sq u i t ed i f f e r e n tf r o mt h eu p p e ro n e s ，w i t c hc a l lb eab a s i so fq u e u e c o n t r 0 1 k e y w o r d s ：v o c m i o nq u e u e ，s t o c h a s t i cd e c o m p o s i t i o n ，g e n e r a la n c e s t o rl i n e ，s t e a d yq u e u e l e n g t h ，r e g e n e r a t i v ep r o c e s s ，s t e a d y s t a t ec o n d i t i o n ，s t r u c t u r e a n a l y s i s m e t h o d s 江苏大学硕十学位论文 常用符号说明 s 。 第n 个服务期结束( n 个假期开始) 时刻 t 。 第n 个服务期开始( n 1 个假期结束) 时刻 b 。= s 。一t 。 第n 个服务期的长度 v 。= t 槲一s 。第n 个假期长度 y 。= l ：一l ：( 假定非负) 第n 个服务期间到达并留在系统中的顾客数 l ：第n 个假期开始( n - 1 个服务期结束时) 系统中的顾客数 l ： 第n 个假期结束( n + 1 个服务期开始) 系统中的顾客数 q ：第n 个服务期开始系统中的顾客数，母函数为q ：( z ) q 。稳态下服务期开始系统中的顾客数，q 。= p ( q 。= k ) ，母函数q 。( z ) l ：第n 个假期开始系统中的顾客数，母函数为l ：( z ) l 5 稳态下假期开始系统中的顾客数，母函数为l5 ( z ) a 。第n 个假期内到达的顾客数，母函数为a 。( z ) a稳态下一个假期内到达的顾客数，母函数为a ( z ) s 印第n 个服务期的长度，l s t 为s ( s ) s p稳态下一个服务期的长度，l s t 为s ：，( s ) o 。第n 个服务期内接待的顾客数，母函数为。( z ) 稳态下- - n 务期内接待的顾客数，母函数为( z ) v 。第r 1 个服务循环中假期的长度，l s t 为v ：( s ) v 独立同分布假期长度，l s t 为v ( s ) b _ 个顾客服务时间，l s t 为b ( s ) d ，m g 1 ( e s ) 忙期的长度，l s t 为d ：( s ) d 经典m g 1 忙期的长度，l s t 为d ( s ) 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 保密团，在多年解密后适用本授权书。 本学位论文属于 不保密口。 学位论文作者签名： 私力杠 导师签名： 签字日期：口。铎多月，二日签字日期：砷乡月么日 学位论文作者毕业后去向： 工作单位：、南守欠彳瑾大孚盘闭参文字存电话：，罗彦矽 ，7 7 ，印 通讯地址：南京财勿大魏 习苏善岔 邮编：2 力护乡 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容以外，本论文 不包含任何其他个人或集体己经发表或撰写过的作品成果。对本文的 研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人 完全意识到本声明的法律结果由本人承担。 学位论文作者签名： 日期：年月日 江苏大学硕士学位论文 第一章绪论 1 1m g 1 型休假排队系统的研究历史与现状 休假排队系统的研究开始于二十世纪六十年代，从目前的研究文献来看，g a v e r 与k e i l s o n ( 1 9 6 2 ) 的工作似乎是最早的一篇，七十年代至八十年代中期，m g 1 型空 竭服务( e x h a u s t i v es e r v i c e ) 模型的研究较为成熟。八十年代后期至九十年代初， g g 1 、g m 1 模型均得到充分研究。而且对m g 1 型非空竭服务( n o n e x h a u s t i v e s e r v i c e ) 休假排队模型展开了研究。九十年代后，随着矩阵几何解与p h 分布理论 的发展，休假排队系统发展到非更新到达( 如马尔可夫到达模型m a p g 1 ，b 姒p g 1 ) ， 并且由单服务台模型发展到m m k 型多服务台休假排队模型。 休假排队系统的研究核心是建立队长、等待时间等排队指标的随机分解 ( s t o c h a s t i cd e c o m p o s i t i o n ) 。根据其随机分解的结构特点为网络、通讯、柔性制 造技术等实际排队模型的优化、控制提供理论依据。 休假排队系统主要分为空竭服务与非空竭服务两大类。从目前的研究成果来看， 主要集中在空竭服务情形，具体表现在以下方面： 其一，研究面广、研究成果丰富。与各种单服务台经典排队模型( m m 1 ，d g 1 ， m g 1 ，g i m 1 ，g g 1 ) 相对应的休假排队系统都进行了深入的研究，得到漂亮的 随机分解结果( 文献 1 - 1 4 、专著 1 9 ) 。尤其是经典m g 1 型及其变体( 批量 到达、批量服务，反馈情形等) ，附加相应的休假策略均得到了概率含义十分明确的 随机分解结构。自上世纪九十年代后，随着矩阵几何解与p h 分布理论的发展，经典 排队系统发展到非更新到达( 如马尔可夫到达模型m a p g l ，b m a p g 1 ) ，与之相应 的休假排队系统也得到深入研究。 其二，理论成熟，方法多样化。具体有：直接概率法( f u h r m a n1 9 8 4 ，s h a n t h i k u m a r 1 9 8 8 ) ( 文献 2 3 ) ；水平交叉分析法( d o s h i1 9 9 0 ，1 9 8 6h a r r i s 与m a r c h e l1 9 8 8 ) ( 文献 4 5 ) ；样本轨道比较法( d o s h i1 9 8 5 ，l e v y 与k l e i n r o c k1 9 8 6 ) ( 文献 6 7 ) ； ? 补充变量法( t a k a g i1 9 9 1 ，l e e1 9 9 4 ) ( 文献 8 、专著 9 ) ；样本轨道偏差法( l e e l 9 8 4 ) ( 文献 9 ) ；分支链法( f u h r m a n n 与c o o p e r1 9 8 5 ) ( 文献 i o ) ；修正的l i n d l e y 方 程法( g e l e n b e 与i a s n o n g o r o d s k i1 9 8 0 ) ；随机步行法( k e i l s o n 与s e r v i1 9 8 6 ) ( 文 江苏大学硕士学位论文 献 11 ) ；矩阵几何解法( n e u t s1 9 9 0 等，田乃硕1 9 8 9 ，1 9 9 8 ，2 0 0 1 ) ( 文献 1 2 、专 著 1 ) ：鞅方法( j o s e p 与f e r r a n d i z1 9 9 3 ) ( 文献 1 3 ) 。值得一提的是，田乃硕 ( 1 9 9 2 ) 运用嵌入马氏链方法，将m g 1 休假排队模型归结为经典m g 1 边界状态 变体，用嵌入马氏链得到随机分解结果。该方法理论基础稳固，主要是利用( 嵌入) 马氏链和半马尔可夫过程理论，实现理论与方法的高度统一( 专著 1 ) 。 其三，多服务台m m k 型同步或异步休假排队系统已建立条件随机分解理论并 得到相应随机分解结果( 田乃硕等1 9 9 7 ，1 9 9 8 ，2 0 0 0 ) ( 专著 1 ) 。 其四，近年来经典闭排队网络已发展到休假排队网络新阶段( 朱翼隽 2 0 0 2 ，2 0 0 3 ) ( 文献 3 0 儿3 2 ) 非空竭服务休假排队系统的研究起始于二十世纪八十年代初，从目前的研究成 果来看，主要是在八十至九十年代之间形成的。文献 1 7 - 2 8 较有代表性，专著 1 9 做了系统总结。非空竭服务休假排队系统的研究还不成熟，尚有很大发展空 间。具体而言： 一，研究对象单一，主要是针对m g 1 型排队系统。对于g m 1 、g g 1 、d g 1 等模型几乎未曾涉及。 二，研究方法单一，主要是再生循环法，该方法并不能从理论上揭示m g 1 非 空竭服务休假排队系统的随机分解规律与结构，而且运算过程繁杂，随机分解的结 构与概率含义不很明确。 三，由于非空竭服务规则的多样化，尚未形成有效的统一处理方法，以及一般 意义上的系统的平衡条件。 1 2 m g 1 型非空竭服务休假排队系统的研究难点剖析 m g t 型非空竭服务休假排队系统 以下简记：m g 1 ( n e ) 与m g 1 型空竭服 务休假排队系统 以下简记：m g t ( e s ) 既有联系又有区别。首先，我们来分析两 类排队过程的特点，从中归纳出m g l 型非空竭服务休假排队系统的研究难点。 1 2 1m g 1 ( e s ) 排队过程的特点。 一，该排队过程的再生点可取服务空竭时刻，整个过程可视为忙期与假期( 这 里假期可能包含部分闲期，如单重休假策略情形) 交替更新过程。若考察系统的平 衡条件、队长与等待时间等排队指标，均可利用更新过程的极限定理、年龄与剩余 2 江苏大学硕士学位论文 寿命的分布得到确定的答案。 二，若选取服务完成时刻作为队长过程的嵌入点，则该嵌入过程为一时间与状 态均离散的马氏链。这样便可以借助稳固的马氏链的分析性质和一般理论，得到稳 态解与系统的平衡条件。 三，若考虑一服务期开始时刻系统中的顾客数 q ：，n 1 ) ，则可构造一离散鞅 l 。，n 1 ) 如下： l 。= l o + r h ，l o = q ： j = l 其中，l 。为服务期中第n 个顾客离去时刻系统中的顾客数；仇= 缶一1 ，缶为一 个顾客服务期间到达的顾客数。则服务期结束时刻为鞅的停时，这样便可借助鞅的极 限定理与停时定理来分析系统的平衡条件。 1 2 2m g i ( n e ) 排队过程的特征与研究困难。 一，若选取服务期结束时刻且系统中的顾客数为零的时点为队长过程的嵌入点， 则该时刻以后的过程如同重新开始。这样得到一系列再生点s 。，s 。，其中s 。= 0 ， 任意两个再生点之间的时段( 独立同分布) t 称为再生周期。一个再生周期由若干服 务期与假期( 亦可能含有闲期) 组成。而且一个再生周期的各个服务期分布_ 二般不 同，而且不独立。再生过程可视为更新过程的推广，更新过程的理论基础是更新过 程的常返性( 一般由更新间隔分布决定) ：再生过程的常返性( 由再生周期决定) 是 再生过程极限理论的基础。由于非空竭服务规则的多样性引起的再生周期分布的复 杂性，欲从一般意义上寻求再生过程的常返性条件( 即系统的平衡条件) 非常困难。 目前的研究结论或者只是为了解决实际问题需要忽略平衡条件，或者只是给出直观 解释( 专著 1 3 9 3 ) 。 二，若选取服务完成时刻作为队长过程的嵌入点，则嵌入过程为一类特殊的非 齐次马氏链。因为每一服务期内的最后一个嵌入点的转移概率矩阵与该服务期内其 它嵌入点的转移概率矩阵不同。如果想借助嵌入马氏链方法进行分析处理，则可构 造二维向量马氏过程 l 。，l ：) ，其中l ：为第n 个服务期结束时刻队长，l 。为服务 期中其它时刻系统中的队长( 第n 个顾客离去时刻系统中的顾客数) 。由于高维向量 马氏过程的遍历论尚不完善，这无疑给分析系统的平衡条件带来困难。 3 江苏大学硕士学位论文 三，若考虑借助分支过程理论，m g 1 经典排队模型与m g 1 ( e s ) 模型都可视 为一类特殊的粒子系统，即由一个或q 。个粒子开始分裂而产生的粒子系统，可由分 支过程理论或粒子系统的灭绝条件来获得相应的排队过程的平衡条件。若考察m g 1 ( n e ) 排队过程，则可视为按一定规则( 各种非空竭服务规则) 有迁入的粒子系统。 而该类粒子系统的平衡( 或灭绝) 条件，笔者还没有查阅到研究结论。 四，m g 1 ( n e ) 排队系统的休假策略远比m g 1 ( e s ) 排队系统的休假策略丰 富。一般m g 1 ( e s ) 排队系统的休假策略与到达、服务过程独立，具体可分为多重、 单重、多级适应性休假( 专著 1 ) 以及l e u n g ( 1 9 9 2 ) ( 文献 1 6 ) 提出的八种。m g 1 ( n e ) 排队系统的休假策略的丰富性主要体现在以下两方面：1 抬占体筱缴嗒与菲搿 占鲈筱策谬。抢占休假策略指休假对服务抢占，如t 限量服务，正在服务的顾客被 休假抢占中断而后续。非抢占休假策略指休假对服务非抢占，即休假开始时刻只能 在服务完成时刻。显然m g i ( e s ) 排队系统的休假策略均属非抢占休假策略。2 猫 立钟缓蔚璐与嚣独立鲈缆策璐。独立休假策略指休假的长度和级数与休假前系统中 的顾客数独立。而非独立休假策略指休假的长度和级数与休假前系统中的顾客数相 关。从目前的研究文献来看，几乎是针对独立休假策略。 综上所述，m g 1 ( n e ) 排队系统的研究难点是：对于各种不同的非空竭服务规 则与休假策略的排队系统，如何寻求一般意义上的随机分解结构以及系统平衡的条 件。 1 3 本文研究思想、方法、进展概况和结构安排 首先，本文试图从理论上寻求m g 1 ( n e ) 随机分解的规律和结构，从而提供简 洁高效的统一处理方法。由于m g 1 ( n e ) 的随机分解理论一般不独立给出，而是蕴含 于m g 1 型一般休假排队系统( 空竭或非空竭) 的随机分解的理论中。所以本文尝试 从一般休假排队系统的随机分解理论中寻找突破口。 一般休假排队的随机分解理论首先由f u r m a n n 与c o o p e r ( 1 9 8 5 ) ( 文献 1 0 ) 提出，并且用直观形象的乡坡( a n c e s t o rl i n e ) 方法给出证明，而且随机分解各部 分的概率含义非常明确。s h a n t h i k u m a r ( 1 9 8 8 ) ( 文献 3 ) 推广了f u h r m a n n 与 c o o p e r 的结论，给出了一般休假排队系统的随机分解成立的较为宽泛的条件。 b o x i m a 与g r o e n e n d i j k ( 1 9 8 7 ) ( 文献 1 7 ) 在研究休假对服务抢占m g 1 型一般 4 工苏人学硕士学位论文 休假排队系统时提出并证明了未完成工作量( u n f i n i s h e dw o r k ) 的随机分解。d o s h i ( 1 9 9 0 ) ( 文献 4 ) 在相当一般的条件下，推广了未完成工作量的随机分解。九十 年代以后，一般休假排队的随机分解发展到非更新到达的情形。本文主要是受到 f u h r m a n n 与c o o p e r 以及s h a n t h i k u m a r 的工作的启发，将一般休假排队的随机分解 结论推广到非空竭服务情形。讨论一般非空竭服务m g 1 型休假排队系统及其变体 的稳态队长与等待时间的随机分解，运用广义分支链，在独立休假策略下得到稳态 队长随机分解的一般结构，而且各部分随机分解结构的概率含义很明确，从中发现 了m g 1 ( e s ) 与m g 1 ( n e ) 之间的随机分解的密切联系，从而使问题大大简化。 利用随机分解一般结构式，从独立休假策略与经典m g 1 变体两方面来推广 f u h r m a n n 与c o o p e r ( 文献 1 0 ) 的随机分解的结论，得到一系列非空竭服务m g 1 型休假排队系统变体的稳态队长的随机分解。实现了一般非空竭服务m g 1 型休假 排队系统稳态队长的随机分解的统一处理，简化了再生循环方法的繁琐运算，为进 一步研究m g 1 ( n e ) 排队模型提供理论指导与简洁的方法。 其次，在独立休假策略下，利用m g 1 ( n e ) 与m g 1 ( e s ) 的随机分解的密切联系， 进一步探索出一种简洁算法：结构分析法。该方法从m g 1 ( n e ) 稳态队长随机分解的 结构特征出发，简洁高效，并做如下推广和应用：1 运用该算法对几类典型m g 1 ( n e ) 模型进行检验，得到的结果与已知结论一致；2 运用该方法发现并修正m g 1 型 b e r n o u l l i 闸门服务休假排队的随机分解的一个错误( 文献 2 4 、专著 9 ) ；3 运用 该方法我们非常简便地获得单重休假策略下m g 1 ( n e ) 随机分解结构。 其三，对于m g 1 ( n e ) 排队系统，目前的研究结论或者只是为了解决实际问题 需要忽略系统平衡条件，或者只是给出系统平衡条件直观解释。本文尝试系统地讨 论m g 1 ( n e ) 的平衡条件，并且在独立休假策略下进一步简化f u h r m a n n 与c o o p e r ( 文 献 1 0 ) 休假排队系统的随机分解的条件，并得到完整的随机分解结构。 最后，目前有关m g 1 ( n e ) 排队系统的研究结论基本上是针对独立休假策略模型， 而对于非独立休假模型几乎未曾涉及。对于非独立休假模型，虽然上述随机分解与系 统平衡条件等理论基础仍然成立，然而，稳态队长的随机分解已不能运用结构分析 法求解，只能用传统的再生循环法。本文以闸门服务，多重休假策略模型为例，其 他非空竭服务模型可类似讨论。发现其稳态队长过程呈现出一种有趣特征：m g 1 ( n e ) 排队系统以确定的概率口“空竭化”，以概率( 卜口) “非空竭化 ，这为非空竭服务 休假排队系统的控制提供直接依据。 江苏大学硕士学位论文 第二章理论基础 2 1 m ，g ，1 非空竭服务休假排队系统随机分解的结构分析 2 1 1m g 1 ( n e ) 休假排队系统的一般定义 ( 1 ) 到达过程是参数为允的泊松过程，可为批量到达，每批数目专( i = 1 ，2 ，3 ，) 独立同分布且与到达过程独立。缶的一般分布为孝，并假定e 孝= r ， d 孝- - o r 2 ，善的母函数为r ( z ) ，且允许休假期间到达率五与服务期间到达率兄：不同； ( 2 ) 服务台每次接待一个顾客，每个顾客服务时间刁；( i = 1 ，2 ，3 ，) 独立同分布， 其一般分布函数b ( t ) ，一二阶矩和l s t 分别记为：i 1 = r t d b ( t ) ，b2 = f ，2 d b ( t ) ， b 。( 允一允) 。服务时间与到达过程独立，也独立于该次服务前的休假。所有顾客终 将得到服务，而且服务顺序不影响服务时间； ( 3 ) 休假对服务非抢占，休假长度与到达、服务过程独立，假期长度不为零常量； ( 4 ) 服务期内到达的顾客可在接受服务之前以某一规则退出系统，但应与服务 期开始系统中的顾客数独立，允许假期内到达的顾客以某一规则退出系统； ( 5 ) 完成服务的顾客可依某规则，例如以概率1 - a ( o 口1 ) 返回系统； ( 6 ) 非空竭服务规则( n e ) ：( 1 ) 闸门服务( g a t e ds e r v i c e ) ( 文献 2 1 2 4 ) ； ( 2 ) 限量服务( l i m i t e ds e r v i c e ) ( 文献 2 2 2 5 ) ；( 3 ) 减量服务( d e c r e a s i n gs e r v i c e ) ( 专著 9 ) ；( 4 ) 贝努里进程( b e r n o u l l is c h e d u l i n g ) ( 专著 9 ) ；( 5 ) 搜寻服务 ( s e a r c h i n gp h a s es e r v i c e ) ( 文献 1 8 ) ( 6 ) 轮循服务( c i r c l es e r v i c e ) ( 文献 1 9 2 1 ) 等，本文主要讨论( 1 ) 一4 ) ； ( 7 ) 休假策略：定义l 猫立钟穰第够仃眇；休假长度和级数与休假前系统中顾 客数独立的休假策略，具体休假方式可为m g 1 ( e s ) 中的任一种，关于m g 1 ( e s ) 各种休假方式可参见文献 1 6 ；定义2 ：嚣缎玄钟绞壤璐仞”：休假长度和级数与 休假开始系统中的顾客数相关，具体休假方式同上。依此定义，m g 1 ( e s ) 的各种 休假策略均可视为独立休假策略。 6 江苏火学硕士学位论文 注：若删去( 5 ) 上述模型只是对文献 3 中一般休假排队系统的非空竭化。 显然，文献 3 中一般休假排队系统的队长随机分解结论对上述模型m g 1 ( n e ) 成 立，但文献 1 0 中一般休假排队系统的结论对上述m g 1 ( n e ) 模型不一定成立。不 过本文将证明 1 0 中一般休假排队系统的随机分解结论及其所用的分支链 ( a n c e s t o r1 i n e ) 方法均可以推广到更为一般情形，从而得到m g 1 ( n e ) 变体的随机 分解。 2 1 2m g 1 ( n e ) 稳态队长随机分解的结构分析 首先，我们直接引用一般休假排队系统( 含零假期) 随机分解的结论( 文献 3 ) ， 并推广到2 1 1 中m g 1 ( n e ) 非空竭服务情形。 引理1 假设： ( 1 ) ( y 。，l ：，) 生专( y ，l ) ，l ：与l 5 ，b 。鸟b 这里，d 表示依分布收敛 ( 2 ) y 为非负随机变量，并且y 与l 相互独立 ( 3 ) l5 l 即稳态下服务期开始系统中的顾客数几乎必然大于服务期结束 时系统中的顾客数，则： l 5g ) = x ( z ) 石( z ) ( 2 1 1 ) 式中万g ) = ( 1 - p 坟) ( 万1 - _ z ) r ( z ) ，y ( z ) = b q 一厄) x ( z ) = 嬲， p = e 陟】即一个服务期内到达的顾客平均数 这里，l 、l 、y 的母函数分别为l5 ( z ) 、l ( z ) 、y ( z ) 。 引理1 虽然证明了m g 1 ( n e ) 稳态队长的随机分解在相当一般的条件下成立， 但( 2 1 1 ) 式并没有给出m g 1 ( n e ) 稳态队长的随机分解的明确结构。主要原因 m g 1 ( n e ) 的服务期受非空竭服务规则和休假策略的影响，使得式中b 与y 的分布 难以求出，从而y ( z ) 与万的概率含义不明确。其次l 5 与l 的求解无定式可循，因 此从一般条件下出发去寻求m g 1 ( n e ) 的随机分解的确定结构非常困难。下面我们 沿用并推广( 文献 1 0 ) 分支链方法，并且在独立休假策略下得到确定的随机分解结 7 江苏大学硕士学位论文 构。 首先引入广义分支链的定义，把文献 3 中一般休假排队系统的稳态队长的随机 分解结构推广到2 1 1 中描述的m g 1 ( n e ) 休假排队模型，即经典m g 1 排队模型 及其变体情形。 定义3 广义分支链：独立休假策略下，i 。表示某一休假期间到达( 可以某规 则退出) 并留在系统中的顾客总体，i 。表示i 。的服务期内到达( 可以批量到达，或 以某规则退出或反馈) 并留在系统中的顾客总体( i 形象地称为i 。的第一代) ，一 般地i 。表示i 川的服务期内到达的顾客总体( i 。的第k 代) 。定义i 。的广义分支链 为u ，k ，记为i ；。显然，这里定义的分支链与2 1 1 中m g 1 ( n e ) 休假排队模型 k = o 相对应，是对文献 1 0 中分支链( a n c e s t o rl i n e ) 的推广。并作如下假设： ( 1 ) ( a 。，l ：) n = l ，2 ，3 ，是遍历链，且a ，l5 分别为a 。，l ：的极限分布， 其母函数分别为a ( z ) ，l 。( z ) ； ( 2 ) 独立休假策略，假期不为零常量，且视具体休假策略可能含有部分闲期， 如单重休假策略。 下面，在假设( 1 ) ( 2 ) 成立条件下，用广义分支链来推导m g 1 ( n e ) 的随机分解 构，得到定理1 与定理2 。 定理l 独立休假策略下的m g 1 ( n e ) 中，稳态下当系统中某顾客c 服务完毕 时，c 。所在的分支链i 中尚留在系统中的顾客数与服务规则( e s ，n e ) 无关，且与 相应休假策略的m g 1 ( e s ) 的稳态队长同分布。用公式表示为 l e = l + l d 或 l e ( z ) = l d ( z ) 万 ( 2 1 2 ) 式中l 为m g 1 经典乒休假排队系统的稳态队长，母函数为刀( z ) ； l d 为相应休假策略下m g 1 ( e s ) 稳态队长的附加延迟，母函数为l d ( z ) ； l e 为c 所在的分支链i 中尚留在系统中的顾客数，母函数为l 厅( z ) 。 江苏大学硕士学位论文 证明 设：t 表示i 中第j 个顾客开始接受服务的时刻；f ，表示i 中第j 个 顾客服务完成的时刻；i 。表示某休假期间到达的顾客总体；x ，表示f ；时 刻留在系统中的分支链i 中的顾客数。 由于独立休假策略，对于空竭或某非空竭服务规则( 1 ) 一( 4 ) ，每次休假中到达的 顾客总体i 。同分布。某时刻t 系统中的顾客总体可能由多条分支链组成，当系统为空 竭服务规则时，系统中只有一条分支链。若t 有限，且系统在( 0 ，t ) 期间已经休 假k 次，则t 时刻系统中某顾客c 。必位于这k 条分支链中的某一支i + 。假设t 专0 0 时系统的队长的极限分布存在，则稳态下系统中的分支链的条数以概率1 有限，而且 各分支链的极限队长同分布。因为( t ，f ，) 时段分支链i + 中增加的顾客数的母 函数为b ( 入一入z ) 同时减少1 ，其余分支链中的顾客数并不改变，而且服务规n ( f s ， n s ) 不影响x ，的极限分布( 当然，会影响系统中的总体顾客数的分布) 。当服务规则 为空竭服务( e s ) 时，时刻f ；系统中的分支链只有一条，x ，的极限分布为m g 1 ( e s ) 稳态队长分布。所以稳态下x ，的分布完全由休假策略决定，与服务规则( e s ，n e ) 无关，由此得( 2 1 2 ) 式。 定理2 独立休假策略下m g 1 ( n s ) 中，若假设l ，2 成立，服务期内任一时刻 的稳态队长l ”可分解为两部分独立和，其中一部分为休假开始系统中的顾客数l5 ， 另一部分为相应的m g 1 ( e s ) 的稳态队长l e 。用公式表示为： l9 = l + l 日= l + l d + l 或 l ”( z ) = l 。( z ) l d ( z ) 7 7 ( z ) ( 2 1 3 ) 式中l5 为m g 1 ( n e ) 休假开始系统中的顾客数，母函数为l ( z ) ； l d 为相应休假策略下m g 1 ( e s ) 稳态队长的附加延迟，母函数为l d ( z ) ； ? l 为经典无休假排队系统i g 1 ( 或其变体) 的稳态队长，母函数为l ： l 为m g 1 ( n e ) 服务期内任一时刻系统中的顾客数，母函数为l9 ( z ) 。 证明 由于队长过程不受服务顺序的影响，不妨选取后到先服务的顺序( l i f o ) ， 9 江苏大学硕士学位论文 考虑稳态下系统中某一顾客c + ，则c 必属于某一假期v + 到达的顾客总体i 。产生的 分支链i 。p 。表示假期v 开始前瞬时系统中的顾客总体，n 。表示p 。中的顾客数， 则n 。的母函数为l 。( z ) 。p ：表示c 离开系统瞬时留在系统中的分支链i + 中的顾客总 体，n ：表示p ：中的顾客数，由定理1 ，n2 有母函数l 占( z ) 。p 表示当c 服务完成离 开系统时系统中的顾客总体，n 表示p 中的顾客数。 首先，由于( l i f o ) ，p lc p ，由p2 的定义p 2c - - p ，所以p iup 2cp 。其次，假设 v 之后且c 接受服务之前有假顾客c 到达( 有休假发生) ，由于( l i f o ) ，只有当假 顾客c 产生的分支链i 。中的所有顾客服务空竭时，才开始接待c 。当c 服务完成 时p 中的顾客或属于e 。或属于p ：，而且c 服务期间到达的顾客皆属于p ：，所以 p c p lu p 2 。且由上述分析可知p 。np 2 = ，由独立休假策略和( l i f o ) 服务顺序可 得n = n l + n2 ，再由p a s t a 性质得( 2 1 3 ) 式。 2 1 3 几类m g 1 ( n e ) 稳态队长的随机分解结构 下面利用( 2 1 3 ) 式从独立休假策略与经典m g 1 变体两方面来推广( 文献 1 0 ) 的随机分解的结构式：l 0 ) = l5 ( z ) l dz ) x ( z ) 这里主要讨论l d ( z ) ，万( z ) ，我们将在3 1 提供求解l5 ( z ) 的一种简洁方法。 1 到达、服务过程同经典m g i ，独立休假策略分别为多重、单重、多级适应性休假 的m g i ( n e ) 的稳态队长的随机分解结构。 ( 1 ) 当系统为多重休假m g 1 ( n e ，蝌) 时： l d ( z ) ：i - = v ： ( _ ；t - 2 _ z ) ( 2 1 4 ) 一 e ( y ) ( 1 一z ) 万( z ) - - 号黯等笋， 亿， 即经典无休假m g 1 稳态队长，这是( 文献 ：- 二亨托三二采。 ( 2 ) 当系统为独立单重休假m g i ( n e ，s i v ) 时 1 0 江苏人学硕士学位论文 叭矿蒙帮 ( 2 1 6 ) 万g ) 同式( 2 1 5 ) ( 3 ) 当系统为独立多级适应性休假m g 1 ( n e ) ( 专著 1 叭垆卜c m 卜错警叭m 名，栌( 1 - z ) z c - ( 2 1 7 ) 。州v 一) ) + 半磐a e ( v ) m ) 恻2 1 5 ) 2 批量到达，每批到达数目孝的母函数为r ( z ) ，其他同经典m g i ( 见模型描述) ( 专 著 5 ) ，独立休假策略分别为多重、单重休假的m 毒g 1 ( n e ) 的稳态队长的随机分 解结构。 ( 1 ) 当系统为多重休假m 善g 1 ( n e ，m y ) 时： l d ( z 1 ：i - v ( a - a r ( z ) ) 、7 e ( 矿) ( 1 一r ( z ) ) 荆2 罢裂篙铲，夕= 鲁 1 ( 2 ) 当系统为独立单重休假m 5 c ：( n e ，s i v ) 时： ( 2 1 8 ) ( 2 1 9 ) 以垆篙署( 2 1 1 0 ， 万( z ) 同式( 2 1 5 ) 3 服务期内每当一个顾客服务完毕时以概率l 一口返回系统，而以概率口( 0 口1 ) 离开系统，其他同经典m 4 g 1 ( 专著 5 ) 。独立休假策略为多重或单重休假m g 1 ( n e ) 的稳态队长的随机分解结构。注：这里与其他情形不同，由于m g 1 经典排 队系统输出流非p o i s s o n 流，若视反馈为到达，则到达过程非p o i s s o n 过程，p a s t a 性质不成立。故稳态队长为服务完成时刻的队长，不是服务期内任一时刻的队长。 ( 1 ) 当系统为多重休假m 口g 1 ( n e ，i ) 时： 江苏大学硕士学位论文 心z ) 2 帮( 2 1 1 1 ) 乃g ) 。丙a ( 1 正- p 面) o - 瓯z ) b 而 6 无- 厄) ，p 2 亳 l ( 2 1 1 2 ) 即稳态下，服务期内某顾客服务结束( 离开系统) 时，系统中的顾客数的母函 数。 柞) = 坐篇饕巍磐( 2 1 1 3 ， 即