（应用数学专业论文）具有工作休假的单服务台排队模型.pdf

江苏大学硕士学位论文 摘要 本文研究了具有工作休假的单服务台排队模型，在具有反馈或 非反馈的前提条件下，讨论了几种不同情况的排队模型。具有工作 休假的单服务台排队模型已经得到了许多学者的研究，获得了不少 成果。然而有关将负顾客、重试、反馈与n 一策略相结合的单服务台 工作休假排队系统尚未得到充分研究。 针对上述情况本文首先研究了一个具有n 二策略及b e r n o u l l i 反馈的单服务台工作休假排队模型；其次，研究了一个带重试的单 服务台工作休假排队系统；最后，考虑了一个具有n 一策略及r c e 抵消 策略的负顾客工作休假排队系统。在模型求解过程中，本文采用拟 生灭过程和矩阵几何解方法得到了各模型的稳态队长分布以及其相 关指标。 关键词：工作休假，b e r n o u l l i 反馈，n 一策略，重试，负顾客，矩 阵几何解，稳态分布，条件随机分解 江苏大学硕士学位论文 a bs t r a c t i nt h i sp a p e r ，w er e s e a r c ht h es i n g l e - s e r v e rq u e u i n gs y s t e mw i t h f e e d b a c k ，a n dn o n f e e d b a c k ，w es t u d ys e v e r a lm o d e l s t h es i n g l e - s e r v e r q u e u i n gs y s t e mw i t hw o r k i n gv a c a t i o n sh a sb e e ns t u d i e db ym a n y r e s e a r c h e r sa n dm a n yr e s u l t sh a v eb e e no b t a i n e d h o w e v e r ，t h ew o r k i n g v a c a t i o n q u e u i n gs y s t e mc o m b i n i n gr e t r i a l 、n e g a t i v ec u s t o m e r s 、 f e e d b a c k ，n p o l i c yh a sn o tb e e ns t u d i e d u n d e rt h i sc i r c u m s t a n c e ，w es t u d ys e v e r a lm o d e l sa sf o l l o w s ：f i r s t l y ， w e s t u d yas i n g l e - s e r v e rw o r k i n g v a c a t i o n sq u e u i n gs y s t e mw i t hn - - p o l i c y a n db e r n o u l l if e e d b a c k ；s e c o n d l y ，w er e s e a r c has i n g l e - s e r v e rw o r k i n g v a c a t i o n s q u e u i n gs y s t e m w i t hr e t r i a l ； a t l a s t ，w e c o n s i d e ra s i n g l e - s e r v e rw o r k i n gv a c a t i o n sq u e u i n gs y s t e mw i t hn e g a t i v ec u s t o m e r s a n dn p o l i c y i nt h ep r o c e s so fr e s o l u t i o n ，w eu s em a t r i x - g e o m e t r i c s o l u t i o n ，a n dd e r i v et h eq u e u el e n g t hd i s t r i b u t i o na n ds o m ep e r f o r m a n c e m e a s u r e s k e y w o r d s ：w o r k i n gv a c a t i o n s ，b e r n o u l l if e e d b a c k ，n p o l i c y ， r e t r i a l ，n e g a t i v ec u s t o m e r s ，m a t r i x g e o m e t r i cs o l u t i o n ， s t e a d y s t a t ed i s t r i b u t i o n s ，c o n d i t i o n a ls t o c h a s t i c d e c o m p o s i t i o n 江苏大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子版， 允许论文被查阅和借阅。本人授权江苏大学可以将本学位论文的全部 内容或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密团。 学位论文作者签名：炎辛亚7 2 0 0 8 年1 2 月 学 嫒 以形1 名 月 签 2 “卜 1 教 手 黝 阵 匕日 0 制丁 o 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已注明引用的内容以外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：炎、辛翌l 日期：2 0 0 8 年1 2 月 江苏大学硕士学位论文 第一章绪论 本章对排队论的发展及具有工作休假的单服务台排队模型的研究内容、背景 和现状作一简单介绍，同时阐明本课题的研究内容及解决问题的方法。 1 1 排队论简介 1 1 1 排队论的发展 排队论又称随机服务系统，起源于2 0 世纪初关于电话中继线问题的研究。 1 9 0 9 1 9 2 0 年丹麦数学家、电气工程师爱尔朗( a k e r l a n g ) 用概率论方法研究电 话通话问题，从而开创了这门新学科，并建立了许多基本规则。3 0 年代中期，当 费勒( w f e l l e r ) 引进了生灭过程时，排队论才被数学界承认为一门重要的学科。 在二战期间和二战以后，排队论在运筹学这个新领域中成为了一个必不可少的重 要内容。2 0 世纪5 0 年代初肯德尔( d g k e n d a l l ) 对排队论作了系统的研究，他用嵌 入马尔可夫链( a m a r k o v ) 方法研究了排队问题，使排队论得到了进一步的发展， 从2 0 世纪6 0 年代起，排队论研究的课题日趋复杂，很多问题不是很难求得其精确 解，就是求得的解非常复杂，不便于应用因而开始了近似方法的研究。 排队论的产生与发展来自于现实生产生活的需要，实际的需要必将决定它今 后的发展方向，排队论的应用范围很广，它应用于一切服务系统，尤其在通讯系 统、交通系统、计算机、存储系统、生产管理等方面应用得最多。 排队系统尽管千差万别，但都可以抽象为顾客达到服务台前，服务台有空闲 便立刻服务，若没有空闲，则需等待服务台出现空闲时再接受服务，服务完后离 开服务台。下图为排队系统图，线框内为排队系统。 4 3 顾客到达 顾客离去 排队 服务机构 排队系统图1 1 f i g u r e l 1 1 江苏大学硕士学位论文 1 1 2 排队系统的各部分组成 排队在我们的周围到处可见，比如排队买票，排队买饭以及排队上车，这些 都是排队系统的一部分，当然还有其他排队，像计算机数据的处理也是一种排队。 既然如此就要了解排队系统的组成部分。一般排队系统有输入过程和到达规则、 排队规则、服务机构的结构、服务时问、服务规则和输出过程。 1 输入过程和到达规则。输入过程一般是用顾客到达间隔来描述的。根据 到达间隔时问所服从的分布，输入过程可分为定长输入、指数输入、几何输入等。 到达规则指到达是单个到达、成批到达等等。本文将研究的是单个到达。 2 排队规则。一般分为等待制、损失制和混合制。等待制指顾客来到系统 发现服务台均被占用，自动排到队尾等待服务。损失制指顾客来到服务台发现服 务台均被占用，或因为顾客的等待时间有限，达到其等待期限则马上离开系统。 等待制和混合制又分为先来先服务、后来先服务、随机服务等等，此外还有顾客 服务后反馈等。 3 服务机构的结构。服务机构的结构可分为单服务台、有限个服务台与无 限个服务台，而在多个服务台中又可分为并联和串联。还有一个服务台连续为顾 客服务多次以及一个顾客连续被服务多次的情形，后者可分为并联和串联结构。 4 服务时间与服务规则。服务时间指服务一个顾客需要的时间，可分为定 长分布、指数分布、与一般分布等。服务时间分为有假时间和无假时间两类。有 假时间的又分为穷尽服务、闸门服务、限量服务、减量服务，在穷尽服务和闸门 服务中又分为单重休假和多重休假。还有单个服务和批量服务。 5 输出过程指的是顾客的离去过程，可分为离去和反馈两种。 1 1 3 排队系统的表示方法 1 9 5 1 年肯德尔用三个字母组成的符号a b c 来表示排队系统。其中a 表示 到达间隔时间分布，b 表示服务时间分布，c 表示服务机构中服务台的个数。一 般用m 表示指数分布，用g 表示一般分布，后来在前两个字母的右上角加字母以 表示每次到达几个顾客与每次服务几个顾客。一般还假定到达间隔时间序列为独 立同分布的随机变量序列，服务时间序列也为独立同分布的随机变量序列且这两 个随机变量序列也相互独立。 2 江苏大学硕士学位论文 1 1 4 排队系统的主要指标 一个排队系统要从两方面考虑，即服务机构和顾客的利益来考虑，顾客希 望等待的时间越短越好，那就需要服务机构的服务台越多越好，而服务机构要想 获得高的利益就必须限制服务台的个数。综合考虑排队的几个指标：队长、等待 时间、服务台的忙期，成为排队论的主要研究内容。 队 长：指系统中的顾客数。 等待时间：指从顾客到达时起到他接受服务时止这段时间。 忙期：指空闲的服务机构从有顾客到达开始服务时起到系统服务完所有 顾客时止这段时问。 1 2 重试排队系统研究现状 重试排队系统的特征就是当顾客到达系统时如果发现服务台空闲，则立即接 受服务；如果发现服务台忙，就必须离开服务区域，进入重试区域( o r b i t ) ， 经过一段时间后再次要求服务，不断进行重试，直到重试成功。 重试排队系统已经在许多实际模型中获得了广泛的应用，如电话交换系统， 通信网络，以及计算机系统和遵循c s m a c d 协议的局域网中。 对于连续时间的重试排队系统，已经有不少作者进行研究，但是大多数关于 重试排队系统研究的文献，它们的重试时间分布是服从指数分布 3 5 ，3 6 ，3 7 c h o i bd 在文献 3 8 3 9 中分别讨论了其在通信系统a l c h a 和 c s m a c d 协议的局域网中应用。 在最近几年又有不少作者对具有一般重试时间的m g 1 排队模型进行了研 究，在1 9 9 4 年ty a n g 3 4 采用一种近似的方法对具有一般重试时问的m g 1 排 队模型进行了研究。在1 9 9 9 年a g o m e z - c o r r a l 1 2 对有一般重试时间的单服务 台重试排队系统给出了精确解。b k r i s h n ak u m a r 1 1 于2 0 0 2 年考虑了具有 b e r n o u l l i 休假的m g 1 重试排队模型，2 0 0 5 年，周文慧 1 5 在此基础上考虑了 具有启动时间和b e r n o u l l i 休假的m g 1 重试排队模型。同年，朱翼隽 1 7 研究 了具有两个服务阶段、反馈的m g 1 重试排队系统。 对于离散的重试排队系统，m e i s l i n g 2 3 早在1 9 5 8 年就开始对此进行了研 究。之后此类排队系统的研究工作成果很少。但离散的排队系统在最近十年由于 3 江苏大学硕士学位论文 计算机和通讯系统的迅速发展又引起重视。这是因为在计算机和通讯系统及其相 关领域中，最基本的时间单元是二进制码，所以离散的排队模型比连续的排队模 型更适合模拟计算机和通讯系统而且在理论上，h t a k a g i 2 2 于1 9 9 3 年证明了 离散的排队系统可以用来逼近连续排队系统：反之，一般来说是不成立的1 9 9 5 年，t y a n g 和h 1 i 2 7 研究了重试时间服从几何分布的g e o g 1 重试排队系统 在2 0 0 4 年，i v a na t e n c i a 3 1 研究了有一般重试时间的g e o g l 重试排队系统。 1 3 休假排队简介 经典排队系统规定服务台随时等待为顾客服务，但是在某种情况下并不能得 到最优的统筹安排，如果在系统无顾客时让服务台去进行其他辅助工作，就会得 到很好的利用。休假排队指服务台在某些时候没有顾客时，暂时中断为顾客服务 的排队系统。随着科技的发展，现实生活中已经出现了多种休假排队的例子。 例l ( 保养策略) 为了使服务系统长久有效的对顾客服务，当系统空闲时就 对服务设施进行一次例行保养，实施保养的时间可以视为休假，此期间到达的顾 客需等待完成保养以后才依次被接待。 例2 ( 辅助工作) 在负荷较低的排队系统中，为了有效的利用空闲时间，可 设置某种辅助工作。假定辅助工作也需一项接一项的地完成，完成每项辅助工作 的时间是独立同分布的随机变量。一旦系统内无顾客，服务员就立刻开始一项辅 助工作。完成后若系统中仍无顾客，就继续从事另一项辅助工作，直到完成某项 辅助工作时遇到系统中已有顾客等待则立刻恢复对顾客的服务。若顾客在服务员 从事某项辅助工作时到达，即使i j f 面没有顾客等待也不能立刻得到服务，须等到 该项辅助工作完成后才能利用服务台。把辅助工作时间看作服务员休假。 例3 ( 启动时间) 为降低服务成本，当系统中无顾客时可以关闭服务设施， 当有顾客到达时通常需要一个启动时间，启动时间也可以是随机变量。该顾客及 启动期内到达的顾客均需等到启动时间完成后才能相继得到服务。启动时间可以 看作由闲期到达的第一个顾客触发的一段休假时间。 例4 ( 优先权) 具有不同优先权的多类顾客的排队系统在经典排队论中已得 到深入研究。如果把高优先权顾客造成的低优先权顾客的服务中断( 强占或非强 占) 视为对低优先权顾客的服务员休假，优先权排队也可纳入休假排队的框架中。 4 江苏大学硕士学位论文 例5 ( 机器故障) 服务台在运行过程中可能发生损坏或需要补充能量，而故 障维修或能量补充必需中断正在进行的服务，这些中断时间可视为服务员休假。 1 4 负顾客排队模型的发展及研究现状 负顾客的排队模型是排队论的一个新兴分支。负顾客可视为一次误操作或者 是外来对服务台实施服务援助或者是系统的灾难，其主要作用是抵消系统中通常 的顾客正顾客。负顾客的抵消作用按抵消时刻、抵消策略的不同对系统产生 不同的影响。抵消时刻可分为两类：一类是负顾客到达后立即抵消系统中现有的 正顾客；另一类是负顾客仅在服务结束时刻抵消现有的正顾客。抵消策略可分为： 抵消队首正在接受服务的顾客( r c h ) ；抵消队尾的顾客( r c e ) ；抵消整个系统 的顾客( d s t ) 以及随机数量的抵消。 g e l e n b e 是将负顾客引入排队模型 1 4 和排队网络 1 6 的第一人。在文 1 4 中作者采用标值点过程来研究问题，得到了不同抵消策略下的马氏链 ( r ) 为正 常返的再生过程的充要条件，并且说明了新模型的稳态条件与负到达有关。文献 1 6 作者将负顾客引进排队网络后，证明了能描述网络性质与顾客流方程解存在 唯一性的关系的几个定理。 h a r r i s o n 和p i t e l 在文 1 8 中获得了不同服务规则和抵消原则下的系统稳 态队长分布的概率母函数及平均队长。首先，对策略为先到先服务、抵消队尾顾 客的系统，得到了稳态队长母函数的表达式，并引出了第一类f r e d h o l m 积分方 程，其次，对策略为先到先服务、抵消被服务顾客的系统，通过讨论对系统的服 务时间进行修正，获得队长分布的概率母函数，接着，对策略为后到先服务、抵 消被服务顾客的系统，作者运用补充变量法，对稳态条件下的系统状态转移概率 进行分析，获得结论，此外，对其余具有不同的服务规则和抵消规则的系统，作 者也作了讨论。j a i n 和s i g m a n 在文 1 9 中分析了负到达抵消目前系统中的所有顾 客的情形，根据比率守恒律，得到该系统的载荷量分布类似的p o l l a c z e r k h i n t c h i n ( p - k ) 公式。b o u c h e r i e 和b o x m a 在文 2 0 中研究了负顾客抵消随机数 量的正顾客的m g 1 排队模型，作者利用两种不同的方法来研究稳态系统的载荷 量。b a y e r 和b o x m a 在文 21 中讨论了负顾客的m g 1 排队模型的w ie n e r h o p f 分析和随机徘徊问题，得到了嵌入点时刻和任意时刻的队长分布的概率母函数。 5 江苏大学硕士学位论文 在求嵌入点时刻的队长时，文章考虑两种情形：一类是系统空时，负到达自动消 失；一类是系统空时，负到达停留在系统中，直到下一次服务结束时才去抵消正 顾客，分别得到了各自队长分布的概率母函数。 最近，朱翼隽在文 2 4 ，2 5 中创造性地提出了负顾客可以接受服务的思想， 研究了一类服务规则为f c f s ，抵消规则为r c e 的负顾客的m a 1 排队模型，得到 了队长分布的概率母函数、虚等待时间及等待时f 、日j 的l 变换表达式。文 4 1 的作 者运用补充变量法，对具有负顾客的m g 1 可修排队模型进行了研究，得到了各 自队长分布的广义概率母函数。文 4 2 的作者还将负顾客引入休假排队系统，研 究了具有负顾客的m g 1 和g i m 1 休假排队模型，分别得到了系统队长的概率 母函数，大大丰富了负顾客排队模型的理论体系 4 3 。 1 5 工作休假排队系统研究的内容、背景及现状 近2 0 年，休假排队模型得到了广泛深入的研究，d o s h i 在其综述 1 ，2 中对 此进行了详细阐述。在各种各样的休假排队模型中，服务员在假期中完全停止服 务，但是他可以从事辅助工作。休假排队反映了服务过程可能因某种原因发生中 断这一客观事实；此外，各种休假机制为系统的优化设计和运行控制提供了极大 的灵活性，因此休假排队受到广泛的关注并成为一个研究热点。近来，s e r v i 和 f i n n 3 引入了一种半休假策略，服务员在假期中并未完全停止工作而是以较低 的速率为顾客服务，这种休假策略称为工作休假( w o r k i n gv a c a t io nw v ) 。他们 研究了工作休假m m 1 排队，得出了稳态下系统中顾客数的p g f 和稳态逗留时间 的l s t ，并且将研究结果应用到了光纤通信网络的网关路由器的性能分析。随后， k i m ，c h o i 和c h a e 4 ，w u 和t a k a g i 5 研究了工作休假m g 1 排队，b a b a 6 用矩阵几何解方法分析了工作休假g i m 1 排队。从在休假期部分地利用系统 资源的角度来看，单服务台排队的工作休假策略类似于多服务台排队的部分服务 台休假策略。t i a n 和z h a n g 7 ，z h a n g 和t i a n 8 分析了后者。 1 6 本课题研究的内容及解决问题的方法 本文研究了一类具有工作休假的单服务台排队模型，在工作休假的单服务台 排队模型的基础上，考虑赋予反馈顾客及n 一策略的情况，利用拟生灭过程及矩阵 6 江苏大学硕士学位论文 几何解的方法得到了系统的稳态队长分布，条件随机分解；其次研究了具有重试 的单服务台工作休假排队模型，顾客的到达虽遵循泊松过程，利用拟生灭过程及 矩阵几何解的方法得到了顾客的队长分布及条件随机分解；最后研究了在具有工 作休假的情况下，考虑带有n 一策略及负顾客的单服务台工作休假排队模型，利用 拟生灭过程及矩阵几何解方法得到了队长的稳态分布及条件随机分解。 7 江苏大学硕士学位论文 第二章研究排队模型的主要方法 本章将简单介绍几种常用的研究排队模型的方法，以及各方法在研究排队问 题中的特点。 2 1 拟生灭过程和矩阵分析法 矩阵解析方法是由美国随机模型( s t o c h a s t i cm o d e l ) 杂志主编m n e u t s 首 次提出，并且在他1 9 8 1 年和1 9 8 9 年出版的两本专著中作了详细阐述。该方法主 要从计算概率的角度解决随机模型研究中的数值计算问题，其突出特点在于用该 方法得出的结果均以矩阵形式给出，便于在计算机上进行计算。而传统的嵌入马 尔可夫链方法所得结果均以l a p l a c e 变换或母函数的形式给出。因此矩阵解析方 法是研究随机模型的一种有效的和重要的方法。 2 1 1q b d 过程的定义 定义 考虑一个连续时间的二维马尔可夫过程 ，( f ) ，j ( f ) ) ，状态空间是 q = ( i | ，) ，后o ，1 歹m ) 称 ，( f ) ，( f ) ) 是一个拟生灭过程，如果其生成元可写成下列分块三对角形式 q = ( 2 1 1 ) 满足 ( 彳。+ c 。) p = ( b 。+ 么。+ c 。) p = ( b + 么+ c ) e = 0 么。和a 有负的对角线元素和非负的非对角线元素，其余子块均是非负阵，e 是元素全为1 的列向量。 称状态集( 后，1 ) ，( 七，2 ) ，( 尼，聊) 为水平尼，( f ) ( o , i , l ，聊) 称作位相。当m 1 时，该q b d 过程称作具 有复杂边界。 对于离散的马氏链所对应的q b d 过程( j 。，j 。) ，其转移率矩阵p 也具有与转 移率阵q 相同的形式，只是其所有的元素均为小于1 的非负数，且p e = e 。 若过程 ，( ，) ，( r ) ) 是正常返的，以 ，) 表示过程 ，( f ) ，j ( f ) ) 的极限变量， 并记万甜= l i m e i ( o = 七，( f ) = _ ，) = p i = 七，j = ) ， 其中k 0 ，1 j m 为适应q 的分块形式，将稳态概率按水平写成分段形式 万t = ( 万印万腰人万砌) ，k o 2 1 2q b d 过程的稳态条件 对于有限位相的0 b d 过程，n e u t s 已经给出了完整的系统稳态条件。 定理2 1 形如( 2 1 - 1 ) 的复杂边界q b d 过程正常返当且仅当矩阵方程 r 2 b + r4 + c = o( 2 1 2 ) 最小非负解r 的谱半径印( r ) 0 ) 的q b d 过程是稳态的当且仅当上述特征值问题恰 有聊对( 力，缈) ，其中若某兄有七重根，则恰有后个相应的互相独立的特征向量缈。 这里0 r e ( a ) 1 ，缈的各分量的实部均为正数。此时q b d 过程是稳态分布为： 7 1 。= 以，力_ 缈， 七c ( 2 1 8 ) j = - 其中( 口。，口：，三，口。) 与( 万。，万。，l ，万。一，万。) 可由下面的方程组得到 1 0 江苏大学硕士学位论文 万国o + 万。c 1 = o 万t 一4 + 万b + 万m c m = o 2 l g ( z ) l 则在l 内部，s ( z ) 与厂( z ) + g ( z ) 有相同的零点个数。 对于单服务台的排队模型，常采用嵌入马尔可夫链法和补充变量法，如下： 2 3 嵌入马尔可夫链法 在泊松到达与服务时间为负指数分布的排队系统中，在任何时刻系统都具有 马尔可夫性质，因而可用连续参数马尔可夫链的方法化成可求解的平衡方程组， 得到系统的平稳解。对于如1 m g 1 或g i m l 那样的一般服务或一般到达的排队系 统，不是在任何时刻系统都具有马尔可夫性质，只是在某些特殊的随机时刻系统 才具有这种性质，我们称这种随机时刻点为再生点，即从这个时刻起，系统行为 好像又重新开始一样。利用再生点，前面所述的女n m g 1 或g i m 1 那样的一般 服务或一般到达的排队系统的分析，可用马尔可夫链的方法予以解决，这种方法 就叫做嵌入马尔可夫链法。徐光辉 2 6 ，孟玉珂 2 8 ，唐应辉和唐小娥 2 9 ， 陆传赉 3 0 ，华兴 3 2 孙荣恒和李建平 3 3 对此做了详细的论述。以下我们先说 明马尔可夫链并以经典的m g 1 排队系统为例，说明用嵌入马尔可夫链的方法来 解决排队问题的主要思路。 定义设随机过程 x ( r ) ，f t 的状态空间s 为r 中的可列集，如果对r 中 任意刀个f ， f ： o ) 由于到达流是p o s s i o n 流，在这些再生时刻，观察系统的状 态顾客数，它具有马尔可夫性。表示一个顾客服务结束后刚离开系统时留 在系统中的顾客数，则 。 就是一个马尔可夫链，这啡嵌入马尔可夫链。由于 t n + l - - t 。对一切刀都是同分布的，到达又是p o s s i o n 流，于是经过t + i - t 。这段时 间，系统从状态。到。+ 三一1 状态的概率相同，因此是一个齐次马尔可 夫链。 4 3 江苏大学硕士学位论文 第三章具有n 一策略及b e r n o u l l i 反馈的 m m 1 工作休假 休假排队在近2 0 年中得到了广泛深入的研究。在各种各样的休假排队模型中， 服务员在假期中完全停止服务，但是他可以从事辅助工作，这样服务台就会得到 很好的利用。休假排队的诸多结论，在实际生产生活中有广泛的应用，比如，电 话交换系统，通信网路，计算机系统，各种休假机制为系统的优化设计和运行控 制提供了极大的灵活性，因此休假排队受到广泛的关注并成为一个研究热点。 近来，s e r v i 和f i n n 3 引入了一种半休假策略，服务员在假期中并未完全停 止工作而是以较低的速率为顾客服务，这种休假策略称为工作休假( w o r k i n g v a c a t i o n1 】i r v ) 。他们研究了工作休假m m i 排队，得出了稳态下系统中顾客数的 p g f 和稳态逗留时间的l s t ，并且将研究结果应用到了光纤通信网络的网关路由 器的性能分析。随后，k i m ，c h o i 和c h a e 4 ，w u 和t a k a g i 5 研究了工作休 假m g 1 排队，b a b a 6 用矩阵几何解方法分析了工作休假g i m 1 排队。 从在休假期部分地利用系统资源的角度来看，单服务台排队的工作休假策略 类似于多服务台排队的部分服务台休假策略。带反馈的排队系统是经典排队系统 的服务机制有所变化，顾客到达系统后并不一定经过依次服务就离开系统，可能 经过多次，这个服务次数是由反馈机制所决定的。考虑到工作状态与休假状态的 转换通常需要一定的费用，积累一定数量的顾客再实施转换可能产生更好的经济 效益。因此本文将n 一策略及b e r n o u l l i 反馈结合起来进行研究，而这种排队模型 在以前的研究中尚未出现，但是在实际生产中却有重要的意义。比如对于生产流 水线上某种产品的包装过程，若某一件产品包装不合格，则需要重新包装( 反馈) ， 流水线上需要包装的产品大于等于n 时，流水线开始以正常速率包装产品；否则 开始另一次独立同分布工作休假，即以较低的速率工作，此模型在实际生产中可 以大大降低企业成本。 1 4 江苏大学硕士学位论文 3 1 模型描述 考虑一个经典m m i 排队系统，顾客以参数为a 的p o s s i o n 过程到达系统，在 忙期中，服务员的服务率为z 。相继两次假期之间的时间称为服务期或正规忙期。 现加入下列n 一策略及反馈的工作休假规则：一旦系统变为空的，即正规忙期结束， 服务员立即进入随机长度为v 的工作休假，p 矿f ) = 1 一e ，t o 。与通常 的休假策略不同，服务员在休假期并未完全停止工作，而是以较低的速率 万( 万 ) 为顾客服务，服务规则为f c f s 。当此次工作休假结束时，如果系统中的 顾客数j ( n 事先给定) ，服务员立即停止工作休假，服务率由艿提高至， 一个正规忙期开始，正在接受服务的顾客重新开始接受服务；否则服务员进行另 一次独立同分布的工作休假。顾客在服务完一次后以概率p ( o l ，j = o ，1 ) ，其状态转移图( 3 1 ) 如下： 江苏大学硕士学位论文 允, t + o - p ) 6五+ ( 1 一功万z + ( 1 一功万z + ( 1 一p ) aa i l 劫万 矽o ，0 ) ，r 1p j 1 p j 1 p j 1 p 艿 口 占 ( 1 - p ) 1五+ 0 - p ) u 旯+ ( 1 一p ) a + ( i - l 1l rl ，( n ，1 ) 7 状态转移图3 1 f i g u r e 3 i 将状态按字典序排列，生成元q 可以写成下列分块三对角形式： 其中 q = a 。 b l o c a 。 b 。 c 。 a 。c 。 b 。a 。c 。 bac p ) u 0 1 2 一1 n = 一彳c o o = ( 名，o ) b l o = ( p 8p ) t f ，p 60 、 b 。2 l 1 0p j小一引一。0 ) c 。= ( 肌譬力万五+ 0 p ，曰= ( 苫二) = r 苫柏一。纠 1 6 c = r 艿圳0 刊 江苏大学硕士学位论文 在拟生灭过程中，矩阵方程尺2 b + 剐+ c = o 的最小非负解称为率阵，用 尺表示，率阵尺在矩阵几何解方法中起着关键的作用。 定理3 1 若p ：互掣 l ，矩阵方程r 2 b + 剧+ c ：0 最小非负解 p 躲r 可o r 0 为r ：而) l( 3 1 ) p l 其中，是方程 p s x 2 一( a + 万+ 臼) x + 五+ ( 1 一p ) j = o在( o ，1 ) 中的根。 证明：a ，b ，c 都是上三角阵，可设r 由( 3 2 ) 得 r l l 2 ( 力+ 艿+ 秒) = ( 3 1 r i 2l 代入矩阵方程，得到方程组 r2 21 ( 3 2 ) ( 3 3 ) ( 3 4 ) 2 p 6 经验证，取负号时厂。 1 为使r 为最小非负解，取负号，另 厂。，= 尸 1 ，又( 3 3 ) 得，：= 兰二! ! 掣当兄+ ( 1 - 2 p ) 。时， ，取厂2 2 = p l( r 2 2 另一根为1 ) ，将厂l l ，厂2 2 代入( 3 4 ) ，定理1 得证。容易验证，满足下列关系式 名+ 秒+ 万0 一伊) = p 秒+ 五0 = 元+ ( 1 一p ) 万 r 1 7 = 0 扣 卸 啼叫咖仲 m 1 h 叫 彳 + 2 “ 屹 1 + 一j 矿“ 厂2、j ) z ，- 巩勉 勉 + ，：= 、 r 万 一 十 坍训岬 私 m 七0 2 2 - 1 ，“ z ：n 砣 屹 哆即 即 ，旧 伸 旧、 江苏大学硕士学位论文 3 2 1 队长的稳态分布 p “ 拟生灭过程 ( q ，( f ) ，j ( f ) ) ，f o ) 是正常返的。由 ( 3 1 ) 可知妒( r ) 1 当且仅当p l ，由文献 9 定理2 4 可以证明过程正常返当 且仅当p o 万够= 尸 q ，= 后，= j = l 。i + m 。p q ，( ，) = 后，( r ) = ，) ，( 七，歹) q 定理3 2当p ：兰丛l ! 塑 1 时， p p 合概率分布为 ( q ，( ，) ，j ( ，) ) ) 的稳态极限( q ，j ) 的联 z r ，。= j 【篇 t j i 南c 一，p 6 ；j i 万) 一7 o _ j _ n - 1 万，。= k j 而o r 刁百1 - p 万。= k r 1 矶：k 焘阿尸m + 鲁n - 1 p m + 1 1 n 一1 七= n ，n + 1 后= n ，n + 1 证明：下面先求曰【尺】及正左不变向量( 万。 0 ，万l o ，万l ，l ，1 州，o ，万，。) ， 1 8 ( 3 5 ) 用矩阵几何解方法( 见n e u t s 的专著 1 0 ) ， 万。= y k - n + i = ( 万_ 1 oy 州 1 ) r 扣+ 1 一1 七 ( 3 6 ) 由于 b r 】_ a 。 b l o c 。 a 。 b 。 c 。 a 。 b 。a 。 b c 。 r b + a 舯：p 引p 即i 0 + ) 由( 万。，万。，万l l ，万圳，万- ) 研尺】_ o 可以得到方程组 一a t o o + p 万万l o + p p r l l 。0 一( 旯+ ) 万1 l + p 万2 l 2 0 【五+ ( 1 一p ) 万】万j - l , 0 一( 五+ j ) 万，o + p 万万+ l ，0 2 0 【旯+ ( 1 一p ) 】万j - u 一( 兄+ ) 万，l + p 万+ l ，12 0 【旯+ ( 1 一p ) s l z _ 2 。+ 伊万一( 旯+ 万+ 秒) 刀n - i , o = 0 ”( 1 一p ) 】万删+ 鲁n - i , o + p # p 一( 兄+ ) 万删2 0 令万 ，- 1 。为常数，由( 3 9 ) ( 3 1 1 ) 得 zr一，。zr一，+，。：c一，(：；i：；：i南)。1zf。，。，t，l， 从而 1 9 ( 3 7 ) ( 3 8 ) 1 _ ，n - 2 ( 3 9 ) 1 n - 2 ( 3 1 0 ) ( 3 1 1 ) ( 3 1 2 ) 江苏大学硕士学位论文 绯加= 老瓣卜志卜十( 鼎册州，。 =一a+(1-p)万-p8l【i靠p)万l(1-rc一r，(了fj：南l万一加， i 【五+ ( 1 一) r i 允+ 仃一p 、i 万ji 以- 1 0 。一 由( 3 8 ) ( 3 1 0 ) ( 3 1 2 ) 可得万j + l , l 万，l = t 0 7 万1 1 j n - 2 和 p 万- - 2 而万岬 矾确。静= 等矶= 而& 而百1 - 0 砜。例一1 注意到 r 扣肌1 = 羔r 一p * p b ( 1 - r ) 向 p 将( 万_ 1 ，o ，万川，。) 和尺扣+ 1 代入( 3 6 ) 就得到( 3 5 ) 。由正规化条件可求得 常数万_ 1 o 。 3 2 2 队长的条件随机分解结果 对于到达率为兄服务率为的经典m m i 排队系统，稳态队长为q 。引入条件 随机变量：q o = q 一1 i q 1 ) ，q 。表示已知服务台忙的条件下，系统中的排 队等待顾客数，服从参数为p 的几何分布。 为了与经典m m i 排队系统的稳态指标进行比较，也为了给出n 一策略及反馈 的m m 1 - e 作休假排队的条件随机分解结构，现引入下面条件随机变量： q v = q ，一n iq ，= 1 ) ， q v 表示系统处于正规忙期，且顾客数不少于n 时的条件随机变量，成立下 列简明而直观的随机分解结果。 2 0 江苏大学硕士学位论文 定理3 3 当p ：互丛生里丝 1 时条件随机变量q ，可分解成两个独立的随 plu一7 机变量之和q v m = q 。+ q d 其中q 。是经典无休假m m 1 排队的条件队长，工作 休假引起的附加队长q d 服从修正的几何分布，有分布函数 其中 p o d = 后) = 证明：由( 3 p q ，j = = k 而o 两r p ( j 一，j 詈b i - p 一 ( 1 - p 三上， 1 七 孑再厂 k 庀 k = 0 ( 3 1 3 ) 5 ) 式知，系统处于正规忙期，且顾客数不少于n 的概率为 ) _ 言矶2k 万而o r n 。 i = 、1 7 ， i - p 一 ( 1 - p卜南 尸 q y ( ) = 后) = p q ，一= 七i q ，= ) = 詈 嘉厂7 尸一 q v n ) 的母函数 ) ( z ) = 砉z k p q f , ) = k ) = 附加队长的母函数 i n 1 1 _ p ( 1 - p 2 1 1 p i - p 肛1 沙+ 1 - a 。( z ) q d ( z ) 1 p k - n + 1i p j i ，k = o ，1 ， j p r n，一) 、l-、一2 o 一、- 、 一) p 一一 一一卜 1 上 一， 、料 上却 上h 。 一 一 卫叩 卜1 + dr m 脚 。 l p r nj一) + 上唧 土h 咝 + + 七 d厂 。舢 ，。一 七 z 。脚1一声j、 p 弘一广 高 上却 上h等 江苏大学硕士学位论文 将其展成z 的幂级数就可以得到附加队长q d 的分布，i e 是( 3 1 3 ) 。 3 3 结论 本文给出了具有n 一策略及反馈的m m 1 i