（运筹学与控制论专业论文）带启动期的n策略——单重休假mg1排队系统.pdf

中山九学颂 ：论义带启动j 1 目的n 镱略一单重体戗m g 1 持队系统 带扁动期的n 策略单重休假m g 1 排队系统 运筹学与授制论 硕士生：陈蹙彬 指导教师：尹小玲副教授 摘要 本文主要研究排队论中的一类带启动期、服务器有n 策略一单重休假的 m g 1 排队系统。与前人的研究相比，本文将启动期、n 策略和单重休假三个休 假策略结合在一起。系统有一个服务员，他交替的处于工作、休假( 或空闲) 和 启动状态。当系统为空时，服务员开始一次随机长度的休假。若休假结束时系统 中的人数大于或等于n 个，则开始一个随机长度的启动期，然后进入忙期；若休 假结束时系统中的人数不足n 个，则系统进入空闲期，直至累计发生n 次到达时 开始一个随机长度的启动期，然后进入忙期。系统服务为空竭服务。 本文给出了系统稳态存在的充分必要条件；利用嵌入m a r k o v 链法，借助概 率母函数求得系统在稳态下队长的随机分解性质、稳态下的平均队长、系统处于 各个状态的概率等重要性能指标；求出了忙期内到达顾客的条件等待时间的随机 分解性质和稳态下顾客等待时间的l s t 。最后给出系统在一些特殊情形下的系统 指标值，与前人所得的结果一致。 关键词：启动期、n 策略、单重休假、嵌入m a r k o v 法、随机分解 中山大学颂。i ：论文带启动期的n 策略一单毋休假m g 1 捧队系统 a nm g 1q u e u es y s t e mw i t hs e t u pt i m e ，n - p o l i c ya n ds i n g l ev a c a t i o n s t o c h a s t i co p e r a t i o nr e s e a r c h n a m e ：c h e nb i b i n s u p e r v i s o r ：p r o f y i nx i a o l i n g a b s t r a c t t h em g iq u e u es y s t e mw i t hs e t u pt i m e ，n - p o l i c ya n ds i n g l ev a c a t i o n i sd i s c u s s e di nt h i sp a p e r t h es y s t e mh a sas i n g l es e r v e rw h oi sa tt h e s t a t eo fb u s y ，v a c a t i o n ( o ri d l e ) o rs e t u pt i m ea l t e r n a t e l y w h e nt h e s y s t e mi se m p t y ，t h es e r v e rs t a r t sav a c a t i o n w i t hs t o c h a s t i cl e n g t h w h e n t h ev a c a t i o ni so v e r ，i ft h e r ea r em o r et h a nnc u s t o m e r si nt h es y s t e m ， t h es y s t e ms t a r t sas e t u pt i m ew i t hs t o c h a s t i cl e n g t ha n dt h e nb e g i nt o s e r v e rt h ec u s t o m e r s o t h e r w i s e ，t h es y s t e md o e s n ts t a r t sas e t u pt i m e w i t hs t o c h a s t i cl e n g t hu n t i lt h en t hc u s t o m e ra r r i v e s t h e nt h es e r v e r b e g i nt os e r v et h ec u s t o m e r s t h es e r v i c eo ft h i ss y s t e mi se x h a u s t i v e s e r v i c e t h en e c e s s a r ya n ds u f f i c i e n tc o n d i t i o nf o rt h es y s t e mi ns t a b l ei s o b t a i n e di nt h i sp a p e r b yu s i n gt h ee m b e d d e dm a r k o vc h a i nm e t h o da n d g e n e r a t i n gf u n c t i o na p p r o a c h ，w eo b t a i nt h es t o c h a s t i cd e c o m p o s i t i o n p r o p e r t i e so ft h eq u e u el e n g t hi ns t a b i l i t y ，t h ea v e r a g eq u e u el e n g t hi n s t a b i l i t y 。t h ep r o b a b i l i t yo fb u s ys t a t e 、v a c a t i o ns t a t e 、i d l es t a t ea n d s e t u pt i m es t a t e w ea l s od e r i v et h es t o c h a s t i cd e c o m p o s i t i o np r o p e r t i e s o ft h ec u s t o m e r sw h oa r r i v ea tt h eb u s yt i m ea n dt h el a p l a c e s t i e l t j e s t r a n s f o r m a t i o no fq u e u ew a i t i n gt i m e k e yw o r d s ：s e t u pt i m e ，n - p o l i c y ，s i n g l ev a c a t i o n ，e m b e d d e dm a r k o vc h a i n ， s t o c h a s t i cd e c o m p o s i t i o n i i 中山犬学颂：b 论文 带启动期的n 簧略一单重休似摊队系统 第1 章引言一模型研究的应用背景和发展历史概述 经典的排队论，源于丹麦工程师e r l a n g 关于电话服务的研究，第二次世界 大战以后得到迅猛发展，成为随机运筹学与应用概率论中最有活力的研究课题。 它不仅建立了较完备的理论体系，而且在军事、生产、经济、管理、交通等领域 得到广泛的应用。 2 0 世纪中期以来，随着计算机通讯网络、柔性制造系统( f m s ) 、异步转换模 式( a t m ) 等高新技术领域的发展，提出了大量的复杂系统设计和控制问题。这 些系统的行为通常依赖于随着状态而变化的参数，经典排队模型在处理这类问题 时表现出极大的局限性。休假( v a c a t i o n ) 排队研究正是在这种背景下始于2 0 世纪7 0 年代。作为经典排队系统的推广，休假排队中允许服务台采取各种在某 些时候不接待顾客的策略，这些暂时中断服务的时间( 通常是随机变量) 统称为 休假。导致系统暂时中断服务的理由可以有多种解释： 辅助工作：在负荷较低的排队系统中，为了有效利用空闲时间，可以设置某 些辅助工作。对顾客而言，从事辅助工作的时间可以看成服务员休假，适当 设置辅助工作，既可较好的满足相继到达的顾客需求，又可充分利用空闲时 间增加系统收益。 保养策略：为使服务台长期而有效的运行，有时需对服务设施进行一些例行 保养。 机器故障：假定服务台在运行过程中可能发生损坏或需要补充能量，而故障 维修或能量补充时必须中断正在进行的服务，这些中断时间可视为服务员休 假。 启动时间：为降低成本，当系统中没有顾客时可以关闭服务设施，当有顾客 到达时通常需要一个启动( 预热) 时间，启动时间通常是一个随机变量。则 启动时间可以看成由闲期到达的第一个顾客触发的一段休假时间。 轮循服务：个服务员依某种规则轮流为若干队列顾客服务，这种排队现象 发生在计算机系统、通讯网络、多泊位码头等各种实际问题中。当标定了轮 中山人举硕1 ：论义带廊动期的n 镱略一单藏休假排队系统 锸撵酞审某特定酞弼时，稚务员接待其他酞列及在诸酞翔闽转移的时间，对 该队列顾客相当子服务员体假。 交通堵塞：在公路交通随题中，通常把车辆通过特定路段看成为顾客服务。 妇交通攀敞或其匏原因造成的交通堵塞可视为服务员休假。对澎道上航行鲍 船只也可做类似解释。 捷先彀；磐采恕嶷霞走投颞客造戏戆鬣撬先投鬏客熬s 爱务孛薮( 笼占戆竣棼 抢占的) 视为对低优先投顾客的服务员休假，则优先权排队也可纳入休假排 驮豹挺絮中。 大量实际问题可以通过在经典排队系统中引入某种休假策略加以描述和研究。 方面，休假排队反映了服务可能发生中断这一客观事实：另一方面，各种休假策 略为系统的优化设计和过程控制提供了极大的灵活性。因此，休假排队研究受到 广泛的关注，并迅速成为随机运筹学的一个研究热点。 经典排队系统由到达过程、服务机制、排队规则三部分组成，休假排队系统 只是在此基础上增加一个休假策略。一个完整的休假策略，包括休假开始和结束 的规则以及休假时间的分布。按休假开始的规则可将休假策略分成两类：空竭服 务( e x h a u s t i v es e r v i c e ) 和非空竭服务( n o n e x h a u s t i v es e r v i c e ) 。 空竭服务指服务员一旦接待顾客，就一直持续工作到系统变成空的，休假只 能在系统中没有顾客时开始。典型的空竭服务策略主要有： ( 1 ) 多重休假( m u l t i p l ev a c a t i o n ) ：一旦系统内无顾客，服务员立即开始一 次随机长度的休假，结束一次休假时系统中若仍无顾客，就继续一个独立 同分布的休假，直到某次休假结束时系统中已有顾客等待，服务员终止休 假并开始接待顾客，直到服务台再次变成空闲的。 ( 2 ) 单重休假( s i n g l ev a c a t i o n ) ：一旦系统内无顾客，服务员恰好休假一次。 休假结束时若系统中已有顾客等待，立即开始为顾客服务并一直持续到系 统再次空出；若休假结束时系统中没有顾客等待，服务员就进入通常的闲 期，直到发生顾客到达时再开始一个新的忙期。 ( 3 ) 多级适应性体假：由田乃硕提出的一种休假策略，是多重休假和单重休假 的推广。一旦系统内无顾客，根据当前需要完成的辅助工作量，服务员要 求连续进行h 次独立同分布的休假，h 是正值随机变量。若在这h 次休假 2 中由大学坝 论定俯启动期的h 策略一单最休假排1 执系统 肉锯笼颟客鲻这，结寐第 次体程嚣黻务员进入通鬻静空闲潮，直戮有颓 客到达再转入忙期。若在第k ( 1 墨七蠛h ) 次休假内已发生顾客到达休 假期将在该次休假结束时提前终止，并立刻转入忙期。显然，当h ；1 时， 对应单重休假策略；当h 一* 时，对应多重休假策略。 ( 4 ) 带启动时间( s e t u pt i m e ) ：忙期第一个顾客开始服务前要经历一个随机 长度的启动时间( 也叫启动期) ，当系统中没有顾客时关闭服务设施，再 有新顾客到达时重新启动。 ( 5 ) n 一策略：每当系统变成空时，服务员开始休假，直到累积到达顾客数为 n 个时开始一个新的忙期。 非空竭服务泛指在系统中有顾客也可以进入休假状态的策略。典型的非空竭 服务策略主要有： ( 1 ) 闸门服务( g a t e ds e r v i c e ) ：当服务员终止休假而开始一个忙期时，他只 陆续完成那些当时已经在场的顾客的服务。然后就开始另一次休假，而在 这些顾客的服务期间内到达的顾客，要等到休假结束后的另一个忙期才受 到接待。 ( 2 ) 限量服务( 1 i m i t e ds e r v i c e ) ：对服务台每次连续工作的总量加以限制， 一旦服务台完成某顾客服务，并且连续工作的总量已达到或超过了规定的 上限，无论系统中还有无顾客，系统都进入休假状态。 ( 3 ) 减量服务( d e c r e m e n t i n gs e r v i c e ) ：当服务员结束休假进入忙期时，连 续工作到比该服务期开始时在场的工作量有所减少或减少到一个规定的 数量时，不管系统中有无顾客都进入下一次休假。 ( 4 ) b e r n o u l l i 进程：每当完成一个顾客服务，以概率口进入长为v 的休假， 以概率1 一p 继续为下一个顾客服务( 如果系统中还有顾客等待) ，其中 0 p 1 。 迄今，已经研究了几十种不同休假策略的模型。针对不同的应用背景，可以引入 各种相应的休假策略。 早在1 9 7 5 年，l e v y 和y e c h i a l i 1 从有效利用排队系统闲期的观点出发， 首先研究了m g 1 型休假排队系统，并引入了“休假”和“休假策略”等术语， 中山火学硕一l 论立 带启动期的n 策略一单赣休假排队系统 在休假时间服从指数分布的条件下，给出了稳态队长分布和l a p l a c e 变换。8 0 年代以来，体假排队系统得到广泛的关注并迅速成为运筹学豹一个研究热点。 c o o p e r ，r 2 ，c o u r t o i s 3 ，k e i l s o n 和r a m a s w a m y 4 ，l e v y 和k l e i n r o c k 5 等做了众多工作相继讨论了各种休假策略及服务规则的m g i 型排队系统。1 9 8 5 年，d o s h i b t 6 研究了g i g 1 模型的系统特征( 如队长、平均等待时间) 的 随机分解性。同年，f u h r m a n m ，s w 和c o o p e r ，r b 7 研究了有一般分布休假的 m g 1 排队系统的随机分解问题。初步形成了以随机分解为核心的休假排队理论 框架。从8 0 年代末到9 0 年代，田乃硕等( 1 9 8 9 ) 首先把矩阵几何解方法引入休 假排队的研究，推进了g i m 1 型休假排队系统和多服务器休假排队系统的研究， 并对各种策略下的休假排队系统( 特别是这些系统性能指标的随机分解问题及 p h 封闭性) 做了大量和系统的工作，取得的结果迅速在众多领域得到卓有成效 的应用( 参看 8 、 9 、 1 0 、 1 1 、 1 2 ) 。1 9 9 6 年，史定华和刘斌 1 3 3 利用 向量m a r k o v 过程方法，研究了具有n 一策略休假且休假时间为一般分布的m g 1 排队，得到了稳态下的队长分布、证明它的稳态队长存在随机分解并讨论了当休 假时间服从指数分布时的最优策略问题。1 9 9 2 年，l e u n ge 1 4 分析了一些复杂休 假策略的m g 1 模型，这类模型在数字通讯、计算机网络和生产库存系统中有 广泛的应用。随着计算机和通讯网络的发展，与优先权相关的排队模型得到了高 度的重视。但由于问题求解的困难性，通常限于研究泊松到达和指数服务时间的 情况( 参看 1 5 3 、 1 6 3 、h 7 、 1 8 ) 。t 9 9 9 年后，y o n g l ud e n g 等( 1 9 3 、 2 0 3 ) ， 和邓永录、宋世斌、谭纪青 2 1 先后分别研究了带有阀值转换和启动时间的优先 权排队系统。d o s h i ( 1 9 8 6 ) 2 2 在其综述中就指出：无论在理论上还是实际应 用中，多服务台休假排队系统的研究都更为重要。但是由于问题本身的复杂性且 只有零星的工作涉及到多服务台休假排队，休假排队发展的前2 0 年，多服务台 休假系统的分析几乎未取得任何实质性进展。最近几年，这个方向上的研究才取 得一些较重要的成果，对m m e 休假排队系统以及其他各种策略的m m c ，g i m c 系统，均得到稳态指标的详尽刻画。( 参看 2 3 、 2 4 ) n 一策略是诸多统称为“控制排队”策略中的一种( 如t 一策略 2 5 、d 一策 略 2 6 等) ，曾由b a l a c h a n d r a n ( 1 9 7 3 ) 2 7 3 ，h e y m a n 与s o b e l ( 1 9 8 2 ) 2 8 等使 用不同的方法研究。一个既有多重休假策略又有n 一策略的系统首先由h o f r i 4 中山人学坝一l ：论义带启动期的n 策略一单藁休假排队系统 ( 1 9 8 6 ) 2 9 1 弓i 入，他称谓多重休假和阀值的排队。k e l l a ( 1 9 8 9 ) 3 0 使用不 同的方法也讨论了这一排队系统。1 9 9 4 年，s o o ns e o kl e e 簿 3 1 用於充变量法 研究t n - - 策略单重休假的m 1 g i 排队系统，求出了队长和平均等待时间分布和 其他一些指标，找出在稳态下，使得费用最小的最优控制策略。g v k r i s h n a r e d d y ，r n a d a r a j a n 和r a r u m u g a n a t h a n 3 2 研究了n 一策略下成批到达的多重 休假和启动时间的m 。g ，1 排队模型，求出了稳态下的队长分布。1 9 9 8 年，h ow o o l e e ，w o nj o os e o 和s e u n gh y u ny o o n 3 3 研究带有多种不同类型的顾客且对不同 类型的顾客带有多个阀值的休假m g 1 模型，得到了顾客平均等待时间分布的l s t 及每一类顾客的平均等待时间。a k r i s h n a m o o r t h y 和t g d e e p a k 3 4 于1 9 9 9 年用 补充变量法研究了一种改进的n 一策略m g l 休假排队系统，为避免顾客的不耐烦 情绪，忙期开始时的n 个顾客采用整批进行服务。2 0 0 2 年，z h eg e o r g ez h a n g 并d n a i s h u ot i a n 3 5 用嵌入马氏链法得到了n 一策略g i m 1 排队的队长和等待时间 的稳态分布，并证明了其的随机分解性质。2 0 0 3 年，朱翼隽 3 6 等在一般批量到 达排队模型的基础上，通过运用补充变量法构造向量马氏过程，研究了到达率依 服务员状态( 空闲、忙期) 而不同的n 一策略批量到达排队系统。给出了系统队 长分布、顾客在离去时刻点系统队长分布、忙期内到达顾客的条件等待时间、闲 期分布及其均值等排队指标。 启动时间的m g i 排队模型曾先后由d o s h i 2 2 ，k l e i n r o c k 与s c h o l l 3 7 ， l e v y 与k l e i n r o c k 5 等使用多种方法研究。最近，田乃硕等( 3 8 、 4 9 ) 研究 了带启动期的多重休假、多级适应性休假的m g 1 排队，利用嵌入马氏链方法， 给出了稳态队长分布和母函数、等待时间分布的l s t 及其随机分解性质等结果。 在休假排队系统方面，特别是随机分解问题上，田乃硕做了大量工作，总结在 4 0 。 在休假m g 1 排队系统中，将启动时间、n 一策略和单重休假三个休假策略结 合在一起的文章还没有出现，本文在文献 3 8 、 3 9 、 4 0 的基础上，采用嵌入 m a r k o v 链法，借助概率母函数，求出系统存在稳态的充要条件、稳态下的队长的 随机分解、平均队长和顾客等待时间的l s t 、忙期到达顾客的平均等待时间等系 统指标。较之文献 3 2 采用补充变量法计算出稳态下系统指标更为简便，避开了 复杂的微分方程组的计算。 中山人举颂士论_ 史=带启动媚的n 懿略一单象休假排队系统 第2 章模型分析与结果 2 1 模型描述和定义 本文研究的排队系统可以用以下的数学模型简单描述： 1 系统有一个队列，一个服务器。新顾客到达遵循参数为a 的p o i s s o n 过程； 服务时问有一般分布函数b ( t ) ，其一阶矩和l s t 记为：三一c “t d b ( t ) ， “ ” 口+ ( s ) 一j ：* e - s t d b ( t ) ；记6 2 = r f 2 d b ( f ) 。到达间隔记为t ，服务时间记为s 。 2 排队规则为先到先服务( f c f s ) 。 3 休假策略：当系统为空时，服务员开始一次休假。若休假结束时系统中的顾 客数大于或等于n 个，则开始一个随机长度的启动期，然后进入忙期；若休 假结束时系统中的顾客数不足n 个，则系统进入空闲期，直至累计发生n 次 到达时开始一个随机长度的启动期，然后进入忙期。服务为空竭服务，即服 务员一旦开始接待顾客，就一直持续工作到系统变成空，休假只能在系统中 没有顾客的时候才开始。( 如下图所示：) l竺竺塑望塑旦翌竺i竺塑翌竺竺塑 l竺堡翌皇苎塑i竺竺! 竺竺竺 图2 1 4 休假时间v 有一般分布函数y b ) 和l s t ：v + ( 5 ) 6 中山人学坝 j 论文带扁动抛的n 螭略一单菔休似排队系统 5 启动时间u 有一般分布函数u ( f ) 和l s t ：u 0 ) 6 约定t ，s ，￥，百疆互独立； 7 设q 表示忙期开始时系统内的顾客数，记也- e ( e 。一j ) ，苫； 墨e ( g ) + 有母函数；蜴( z ) 。荟6 ，z 。善q z 。 2 。2 模型的嵌入m a r k o v 链 以( f ) 表示时刻t 系统中的顾客数，又设k 是第n 个顾客完成服务离去时 刻看到系统内的顾客数。则 ，以z 1 ) 是队长过程l ( r ) 的嵌入m a r k o v 链。 在相继离去时刻系统中顾客数之间存在着关系式： l r 嗡l - 一1 1 + + a 4 , ，l 厶。1 。 ( 2 2 1 ) 其中，a 是一个服务时间内到达的顾客数，有概率分布及母函数如下： ”等e d b ( t ) _ 蝴， 4 ( z ) = 嘉叩7 。嘉z _ ”警e “拈一* 。e - x o _ = y 扭一丑+ ( a ( t z ) ) ，+ 1 记 j 。p ( q 一1 + 一i ，) 。磊6 j n m ，一1 ；8 i h j 是忙期开始后第一个顾客 离去时刻系统中恰有j 个顾客的概率。 显然有：h ，= o ，萄- o ，1 ，n - 2 则由公式( 2 2 1 ) 得到 厶，n 1 ) 的转移概率矩阵是 尸i 口0 0 o 啊 n 1 口o 0 h 2 口2 4 1 口0 7 蚝 n 3 痒2 口1 i ( 2 2 2 ) 中山人学确l ：论文 站麝动期的n 懿昭一睁燕侏镁排队系统 若记一= l i m p 。l - j ) ，一o ，1 j ；p ，= l i m p ( l ( t ) = j ) ，。0 , 1 ，一。娜在 系统存在稳态懿渣凝下，囟p a s t a 穗质氧：嘞= p ，j = 0 , i ，。 4 0 1 由【4 0 】中翁迩理2 。3 i 褥裂：上述漱r k 。v 键( 2 。2 。2 ) 歪零遨当显投警p 。查。1 。 敲系统存在稳态豹究瑟条辞楚：p 。查。1 “ 2 3 稳态下队长的随机分解 2 3 i 先求q ( z ) 的表达式： 设q 。表示启动期开始时刻系统内的顾客数( 乌苫) ，先求g ( z ) 的表达式 记4 = 启动期开始时刻为空闲期结束时刻 ； 4 = 启动期开始时刻为休假期结束时刻j ，则： 尸( 4 ) - p ( 墨+ t + 小咖椎等岛一墓u 泣s ， p ( 引小p ( 4 ) 。1 。荟u ( 2 3 2 ) 其中，u ；f ”垡 d y o ) ，表示一个休假期内到达k 个顾客的概率； 故得到： p ( g = ，) = o ，t 1 ，2 ，一1 p ( 岛- ) ，p ( 4 ) + h p ( g - j ) zv j ，；n + i ，n + 2 ， 中山 学硕：i ：论嶷 带启动期的n 策略一啦煎休似排队系统 q ，( z ) 。薹z ? ( q 。；j ) 一薹z ，尸( q ，；，) 町“【乏”卟，p ”， 。z ”磊唯+ 蔷z 7 v ， 纠荟n - 1 h ( a ( ，训一n 磊- 1 甲 ( a ( 1 一z ) ) + 善v 小”- z j ) 故得到 g ( z ) ( a ( 1 圳+ n 蔷- 1 v ，z n _ z j ) 由( 2 3 3 ) 得到 ( 2 3 3 ) e ( g ) = 纠( ，) 。( 。) + 薹v ，( 肫“1 一豇) i 。；a e ( 矿) + 蓑v ，( 一n = 1 2 ， 设k 表示一个启动期内到达的顾客数，则q = g + k ( 2 3 4 ) 设“，= f 。垡号d u o ) ，：。，表示一个启动期到达j 个顾客的概率：则 足( z ) 。磊2 ，。u + ( a ( 1 训 e ( k ) 一k 7 ( z ) l ；。一t e ( u ) ( 2 3 5 ) ( 2 3 6 ) 由于g 与k 相互独立，所以么( z ) - 或( z ) k ( z ) ，由( 2 3 3 ) 和( 2 3 5 ) 得到 啡) iv 俳叫) + 釉扎z 州m 圳 又由( 2 3 4 ) 和( 2 3 6 ) ( 2 3 7 ) e ( 姥) = e ( g ) + 占( 足) a a 忙( y ) + 占( 们) + n 篆- 1 v ，( 一n 一1 ，2 ， ( 2 3 8 ) 由( 2 3 7 ) 得到： 9 中山人举坝l 论义带启动期的n 策略一单敷休假排队羝统 e ( 饼) = 彰( 1 ) + 剑( 1 ) 一j 2 眇2 ) + 露磁( 嘲f f ) 】+ 凇 秽) ( 叫 n l n l + v ， nc n 1 ) 一s ( s l 驴磊咖e + l 妒砖一珐1 , 2 ， 2 3 2 稳态下队长的随机分解定理 ( 2 3 。g ) 利崩l 4 0j 甲的定理2 3 2 得到该模型队长的随机分解定理： 引理：当pt 1 时，由( 2 2 2 ) 所确定的mi o 变体中的稳态队长可分解成两 个独立随机变1 1 2 , t - o ：l ，- l + l ，其中l 是经典无休假m i g i i 中的稳态队长， 有母函数： l ( z ) l 叫紫牡阻； 附加队长乙有母函数： 岛( z ) 兰揣。 将上面求得的公式( 2 3 7 ) 和公式( 2 3 8 ) 代入乙( z ) 的表达式，可以得到如 下队长随机分解定理： 定理l ：当pt1 时，带启动期的n 策略一单重休假m l o l l 排队系统的稳态队长可 分解成两个独立随机变量之和：l ；工+ 厶，其中l 是经典无休侣i m i g i i 中的稳 态队长，有母函数：工( z ) 。g 二宅等磊掣，i z l ：附加队长乙有母函 数： 州小揣= 业竺：鲨麴! 坐竺兰 ( e ( y ) + e ( u ) ) + 篆v ，( 一，) ( ，一z ) 由上述定理可以求出系统平均队长 1 0 中山火学钡j ：论文带启动期的n 镱略一单重休假排队系统 地m 叫讣卅钟h + 篙+ 器 将公式( 2 。3 8 ) 和公式( 2 3 9 ) 代入上式，得猁系统平均队长： 毗h + 篙寺 型竺型：竺型：竺堕塾。 - 1 型j 璺竺：兰! 型1 2 4 忙期分析 兢( y m f ) + 2 薹。陋， 设见表示模型中的忙期，d 表示经典m i g l l 模型中的忙期( 于是有 e ( o ) 一_ 与) ，它们对应的l s t 分别为：珥( j ) 和d ( s ) 。由于到达间隔的无后 “一l 效性，由第j 个顾客开始的忙期长度是经典m g 1 中忙期d 的j 重独立和 d “( j 1 ) 。现在忙期开始时刻系统中有g 个顾客，于是有： 珥( s ) 5 荟q d ( s ) 。荟6 j ( s ) 】。q 【d ( 5 ) 。 y ( a ( ，一。+ ( s ) ) ) + 薹v ，( 。( s ) 一。+ ( s ) 。) ) u ( a ( - 一。( s ) ) ) 平均忙期是： 卜警l 卟印川+ 萋州谭( 卟旭( 中( d ) ；e ( 。) z e ( y ) + a e ( u ) + 薹v ，( 一，) 钉( d iy ) “e ( u ) + 乏”，( 卅i 。击 z e ( 咖旭c 卟融， ，i 驼。击ly ) m ( u ) + 驴肛叫加伢 ( 2 4 1 ) 中出_ 人学颤- ：论文 锩癌动嘏的辩繁略一簪藤体戡捧跌系统 从一个忙期结束时算超到下一个相邻的忙期结束时止的时间区段称为一个 忙循环，记为口c 。易见i 若秫假期间捌达顾客不足n 个，刚b o = v + ，+ u + 职( 一 个体假絮、一令耀联、一令定动攒髑一个虻凝懿秘) ；若傣缓翅霹到达颞嚣数大 于等于n 个，则乓一v + u + q ( 个休假期、一个启动期和一个忙期的和) 。由 茈，忙循环的平均长度是： ) 。副印) + 竿m 薹k ) 印m ( u ) + ) 2 者 e ( y ) + e ( u ) + 与n 磊- i v 一一，) 2 桶眇m 印，+ 釉州) ( 2 4 2 ) 现在，以p n , p v ，p l ，p 。分别表示稳态下任何时刻系统处在工作、休假、空闲、启 动状态的概率，由( 2 4 1 ) 和( 2 4 2 ) 我们有： p 日 p v e ( 或) 2 可可。 。里堕。 e ( b ) 壶匮竺兰堕竺 尚眇m 科融叫 p y ) 【 ，( n 一 胪骡。一,v-,zn_k、驴器丽韵 ，l 。一= o “ 可阻看出，系统处于忙期和非忙期的概率分别为：口和1 一p 。 中山大学硕i ：论文带船动髑的n 策略一荦歪林梭排献系统 2 5 等待时闷分析 由于顾客的等待时间与该顾客到达时刻以后的输入间隔不是相互独立的，故 将顾客分成“在忙期内到达”和“在非忙期内到达”两类进行分析。 设4 表示事件：“顾客在忙期内到达”；以。表示事件：“顾客在非忙期内到达”。 则由忙期分析结果，稳态下的等待时间彬的l s t 可表示为： 吖( s ) 一p 。w ( s h ) + ( 1 一p 。) w ( s i 如) ；p 孵( s h ) + ( 1 一p ) 町( s i 如) ( 2 5 1 ) 2 5 1 求彬( s i ) ： 置条件，令q ：j ，则任一顾客恰为第k 个到达的概率都是三，k ；l 2 ，。 j 由2 3 1 和2 3 2 有：p ( 4 ) 2 荟咋，尸( 4 ) = 1 一荟v t 。 在“启动期开始时刻为空闲期结束时刻”条件下。 第k 个到达者的排队等待时间哌表示为： 肌i a ，一 “一t 个到达间隔”+ “一个启动期”+ “k - 1 个服务时间” 若k = 1 ，n “一个启动期”一“k - n 个到达间隔”+ “k 一1 个服务时间” 若k = n + l ，j 所以，若s a ，有： 中山人学坝 论义 带启动期的n 策i 咯一单熙体假拇队系统 町( sn a 。，骁= j , a ，) 2 悄封饥俨小玎+ 。抑s ) ( 封“p r 1 。堡盟 j n ( s ) = 则有： 型险! 堕l 止型：鲤( 型妇 a 一( a + s ) 口+ ( s ) 。 ( a s ) 一a b ( s ) 一 型畦血型： a 一( a + s ) 曰+ ( j ) ：! 丛兰) ( a s ) 一a b ( s ) + 勰 ( 撕 叭川一半+ 半( 掣) 所以： 彰( s i ，4 ) 2 蚤町( s i ，q 2j ，4 ) p ( 玩2j ) 刮惜州薹掣 型 叫s ) 嚣1 啪) 出+ ( s ) 彳如) 出 在“启动期开始时刻为休假期结束时刻”条件下。 第k 个到达者的排队等待时间表示为 ( 2 5 3 ) ( 2 5 4 ) 哌1 4 - “一个休假期”+ “一个启动期”一“k 个到达间隔”+ “k - 1 个服务时间” 1 4 s 已 1 荆 可 是 0 于 m 中山大学颁一i ：论嶷带启动期的n 策略一单蘑休假摊队系统 。匕：! 坐2 ， e 掣黼m 掣y 封 则有： 孵( s i ，4 ) 磊嘭( s 1 4 瑚，q ；，4 ) 。p ( q o 2j ) 2 薹等端掣卅， 一( s ) u + ( s ) _ - - - - - - - - - - - - - - - - - - - - - - - - - 一 a s - a b ( 5 ) 由( 2 3 1 ) 、( 2 3 2 ) 、( 2 5 4 ) 和( 2 5 5 ) 得到： w ( s i ) w ( s i ，4 ) p ( 4 ) + 町( s l ，4 ) p ( 4 ) 一) 堡她 坤) 嚣1 啪) 出+ ( s ) ：如) 出 _ 瑚 2 5 2 求彰( s h ) ： + ( 2 5 5 ) ( 2 5 6 ) 置条件，令q 一，。以x 。表示忙期前j 个顾客的服务时间之和，称为该忙 期的初始延迟，按f c f s 顺序，x 。内到达的所有顾客的服务时间之和记为墨， 称为忙期的第一阶段。一般地，忙期第m 一1 个阶段内到达的所有顾客的服务时 f， p o、j 击 扩 扩 塞l一。j 青 每 a 茹 鼢 露 若 黜嘴 出 “：，q 1 一r 掣善 一毽 “：一 q lf l rj0 “：一 蜴 1 一t 掣，。 一珈 g l f 1rj0 中山火学碘：论h 盘= 带胺动期的n 策略一单鹏休倒排队系统 间之和称为忙期的第m 阶段，m z l ，并记为以。珑扛) 和d 二( s ) 袭示z ，的分 布遗数和l s t 。忙麓w 以表示为：域5 薹一m 口毛蹙j 个独立同分布服务时间 之和，故：跣( s ) - b + ( s ) 。 若_ 。内到达k 个顾客，则j ，卅是k 个服务时间之和。于是： 珑( s ) t 蠢fp 。( s ) 笔e 一“d 巩一，( r ) - f e ( 1 _ 矿h 1 ( t ) - 峨一，( a ( 1 一b ( s ) ) ) ，柳皂1 设一个顾客在长为j ，卅的第m 阶段结束前的y 个时间单位到达，其等待时间 是y 加上j 一y 内到达的全部顾客的服务时间之和。于是，其条件等待时间h 么的 l s t 是： ees w x 乩以结束前y 删达嵫e 一，瞰) ”掣叫” 一， 一p + a ( r y ) ( t “( s i ) i ) 由p o s s i o n 到达的性质，已知顾客在 o ，f 内到达，则其到达时刻在 o ，f 上 均匀分布，有密度函数r a y ，以y 为条件，我们有 e e “吒l 以一r 一上e x p 一s y + a ( r y ) ( t 一口( s ) ) 】) 方 = e 。1 ( 1 。r “j ：e x p 一 s a1 - b ( s ) ) y 方 e 一。1 - s l j ) p _ e - s t r 卜a ( 一b + ( s ) ) 】 另一方砸，容易证明已知x 。内有一个顾客到达的条件下，到达发生在 ( u + 出) 的概率是i 壶：丁蛾( f ) 。于是，我们有 中山大学碗：i ：论嶷带启动期的n 雉略一单震休假翎队系统 ( s ) = e ( e “k ) = f e p x m = t 】南蛾( o 盟= 兰竺塑 露( 以) 卜 ( 1 珂( s ) ) 】 巩f a l b + ( s 瑚一峨 尽( 以) 卜a ( 1 “( s ) ) 1 因为己知顾客在忙期q 内到达，则到达发生于第m 町段的概率是专黯。 另外，当p c 1 时，忙期以概率1 在有限长时间内结束，即：l i m x m - o , a j ； l i m 磷( s ) 一1 。 综上所述，条件等待时间( 耽1 4 ，见= ，) 有l s t ： 毗加小蠢矧僻端 ：! 二堡蛐 e ( d v ) 卜a ( 1 - 丑( 堋 将成( s ) 。 曰小) 】。和e ( d v ) 2 瓦1 了 a e ( 矿) + a e ( 【，) + 薹咋( 一尼) 代入，得到 彬( s 协，q j ) 一 故有： ，一 曰+ ( s ) 件一a ) e ( 矿) + x e ( u ) + 篡唯( 一七) 】 s a ( 一b + ( s ) ) 1 7 中山人举顾1 二论文带船动j i i 】的n 懿略一单嫩休假排从系统 孵( 5 h ) 。善蟛( s h ，q = j ) b ， 2 磊 出坐业坐二! ! r n 一1 1 旧矿) m ( u ) + 乏删卅卜a ( 1 坷( 叫 ：! 竺二剑! 二鱼盟必 一卟吲卟飘) 卜a ( 坷) 丝! 二鱼堕必 s a ( y ) + a e ( u ) + 薹咋( 一七) ( 2 5 7 ) 易见，揣是经典m ，g ，排队中的稳态等待时间的。s t 。于是有 定理2 ：当pc 1 时，对上述模型，忙期到达顾客的条件等待时间( 睨l 心) 可分解 成两个独立随机变量之和( k i 。) = + ，其中，是经典m g 1 排队中的稳 态等待时间，l s t i s 1 b 。条件附加延迟的l s t 是 一川一is “ ! 二鱼堕翊 s 加( y ) + 加( u ) + 薹u ( 一七) 由定理2 可e , z 1 4 稳态下忙期到达顾客的平均条件等待时间为 e ( 联h ) 一e ( 彤) + 昱( 比) 硒( 2 ) 2 2 ( 1 - p ) + l 一 艚( y ) + 旭( u ) + 荟u ( 一七) 肪( 2 ) 肛 2 ( 1 - 一p ) 【面而葡 由( 2 3 9 ) 知，上式中： 硝( b ( s ) ) ( b ( s ) ) 2 + 碰( 曰( s ) ) 曰”( s ) 2 型：型竺 1 8 2 s = 0 描 中山人学坝士论文 带启动期的n 策略一单躯休假排队系统 创( 1 ) 卅p ( y 2 ) + 层( u 2 ) + 2 e ( v ) e ( u ) 】 + 2 a 嚣( u1 ”搿- 1 v ，( 一，) ) + 篙v ，【( 一，) ，( ，一，) 、 越 酬；a ( e ( 矿) + e ( u ) ) + 蒜”一一j 将( 2 5 6 ) 和( 2 5 7 ) 代入( 2 5 1 ) 即得到稳态下等待时间的l s t 。 定理3 ：当pt 1 时，带启动期的n 策略一单重休假m g 1 排队系统的稳态等待时 间形的l s t 是 啡) 。) 竺m 坤) # 嘶) 出+ ( s ) ：如) 出 兰! ! 二! ! ! 二生堕必 一啪州卟n 荟- 1 唯( 吲卜a ( ，( s ) ) 其中： m ( s ) - u + ( s ) ( s ) = 型畦坐型：】 a 一( a + s ) b + ( s ) ：型! ( 兰1 ： ( a s ) 一a b + ( s ) 1 9 ( 1 一p ) + ( 1 - p ) + + 蕊 ( 2 5 8 ) 出 “：一 g 1 一f 警，。 一出 “：， 幺 1 一f r州l 葺掣 o 哺 中山人学硕j ：论文 带扁动期的n 策略一孵取休假排队系统 第3 章特殊情形下的性能指标 3 1 没有启动时间、n 策略和单重休假的情形 若不考虑启动时间、n 策略和单重休假，则系统退化为一个m g 1 排队系统。 此时，由定理1 可以明显看出队长的概率母函数和平均队长与经典m g 1 排队的 结果相一致。而对于等待时间，由于系统已经没有休假了，故由定理2 知等待时 间的l s t 是 ，也与经典的m f g t l 排队的结果相一致。 3 2 u = o 且n = 1 的情形 若不考虑启动时间且n 取1 ，则系统等价于一个单重休假的m g 1 休假排队 系统。 此时，由定理1 得到附加队长乙的母函数和平均附加队长e ( 厶) 为： 岛( z ) 一业竺：尘麴! 坐竺兰 a ( e ( y ) + e ( u ) ) + 薹v ，( 一，) ( ，一z ) 耶小器 与前人的研究结果一致。 2 0 1 一v ( a ( 1 一z ) ) + v o ( z 一1 ) 啊万而丽刁一 一讲 j m 中山火学硕j ：论文 带启动期的n 镱略一单蓐休假排队系统 3 3v = o 且n = 1 的情形 若不考虑单重休假且n 取1 ，则系统等价于一个启动时间