（基础数学专业论文）带有不耐烦顾客的排队模型.pdf

江苏大学硕士学位论文 摘要 本课题首先研究了具有强占优先权、多个服务台的不耐烦排队模 型。具有多个服务台的不耐烦排队模型已得到很多学者的研究，并已 获得了不少成果。但是将强占优先权与等待空间有限、到达率与服务 率为变量相结合的不耐烦排队系统尚未得到关注。针对以上情况，本 文先研究了有两类顾客、强占优先权、两个有限等待轨道、到达率与 服务率为定值的m m m 2 k m 排队系统。然后，对有两类顾客、强占 优先权、一个等待轨道、到达率与服务率为变量的m i m m k 不耐烦 排队模型进行了分析。上述两个模型，在求解中运用了矩阵分析的方 法。 最后，考虑了一个带有休假、负顾客和正顾客有流失的不耐烦排 队模型。这个模型是以往文献所没有讨论过的。在模型求解中，应用 了矩阵迭代的方法，使得求解过程简单明了。 在以上三个模型中，通过求解给出了平均队长、溢出率、平均等 待顾客数等一些性能指标。 关键词：排队，不耐烦，强占优先权，矩阵分析，q b d 过程，负顾客， 休假 江苏大学硕士学位论文 a b s t r a c t f i r s t ，t h i sp a p e rs t u d i e sm u l t i p l es e r v e r s q u e u e sw i t hi m p a t i e n t c u s t o m e r so fp r e e m p t i v ep r i o r i t y m a n yr e s e a r c h e r sh a v es t u d i e dt h e q u e u es y s t e m sw i t hm u l t i p l es e r v e r sa n di m p a t i e n tc u s t o m e r s t h e yh a v e o b t a i n e dl o t so fr e s u l t s h o w e v e r , t h eq u e u i n gs y s t e mc o m b i n i n gm u l t i p l e s e r v e r s ，p r e e m p t i v ep r i o r i t y , f i n i t ew a i t i n gr o o m ，c h a n g e a b l ea r r i v a lr a t e a n ds e r v i c er a t eh 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 ，t h i sp a p e r s t u d i e st h es y s t e mb a s e do nm m m 2 k 一所q u e u ew i t ht w ok i n d so f c u s t o m e r s ，f i n i t ew a i t i n gr o o m s ，c o n s t a n ta r r i v a la n ds e r v i c er a t e t h e n ，i t s t u d i e st h es y s t e mw i t ht w ok i n d so fc u s t o m e r s ，af i n i t ew a i t i n gr o o m ， c h a n g e a b l ea r r i v a lr a t ea n ds e r v i c er a t e t h et w om o u l d sa b o v em e n t i o n e d a r es t u d i e db ym a t r i xa n a l y s i s a tl a s t ，t h i sp a p e rs t u d i e saq u e u i n gs y s t e mw i t hv a c a t i o n ，n e g a t i v e c u s t o m e r s ，l o s tp o s i t i v ec u s t o m e r sa n di m p a t i e n c e t h i sm o u l d u s e sm a t r i x m e t h o d t h i sm a k e st h ep r o c e s sb es i m p l e i nt h i sp a p e r , w es t u d yt h r e em o u l d sa n dg e tt h em e a nq u e u es e i z e ， l o s e r a t e ，a v e r a g ew a i t i n g c u s t o m e r sa l o n gw i t ho t h e rp 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 ：q u e u e ，i m p a t i e n t ，p r e e m p t i v ep r i o r i t y , m a t r i xa n a l y s i s ， q b dp r o c e s s ，n e g a t i v ec u s t o m e r , v a c m i o n l i 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规 定，同意学校保留并向国家有关部门或机构送交论文的复印件和电 子版，允许论文被查阅和借阅。本人授权江苏大学可以将本学位论 文的全部内容或部分内容编入有关数据库进行检索，可以采用影 印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 保密口，在年解密后适用本授权书。 不保密彤 学位论文作者签名：锹口角指导教师签名： 川薛上月2 岁日 秘年t _ 月媚 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下， 独立进行研究工作所取得的成果。除文中已注明引用的内容以外， 本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式 标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：玎火响 日期：2 口口绰f 2 月工莎日 江苏大学硕士学位论文 第一章绪论 本章对排队论的发展状况及不耐烦顾客排队模型的研究现状，研究背景作一 简单介绍，同时阐明本课题的研究意义以及主要的研究内容。 1 1 排队论简介 1 1 1 排队论的发展 随着科学技术的不断发展，运筹学在现实生活中发挥了重要作用。学的重要 排队论又称随机服务系统理论，它是运筹学的重要组成部分，是专门研究由于随 机因素的影响而产生拥挤现象的科学。它通过研究各种服务系统在排队等待中的 概率特性，来解决系统的最优设计和最优控制。排队论最早可追溯到上个世纪丹 麦数学家、工程师爱尔朗将概率论方法用于电话通话闯题，从而开创了排队论这 门学科的先河，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 世纪以来， 随着计算机通讯网络、柔性制造系统( f m s ) 、异步转换模式( a t m ) 等高新技术的 发展，提出了大量的复杂系统设计和控制问题，经典排队系统处理这类问题时表 现出很大的局限性。7 0 年代以来，n e u t s 等系统地发展了结构矩阵分析方法，使 随机模型分析由以指数分布为核心发展到广泛使用位相型( p h a s et y p e ，简记p h ) 分布的新阶段。经典生灭过程稳态分布的古老方法发展为矩阵几何解方法。这一 变化为复杂随机模型的分析提供了强有力的工具，使得排队论的应用范围更加广 泛。 排队论应用范围很广，主要应用领域有：铁路。公路，航空的运输管理，城 市交通管理及控制，制定生产方案，生产任务的分配，医疗服务，计算机设计、 使用和维修、可靠性等等。 江苏大学硕士学位论文 i i 。2 排队系统的各部分组成 排队在我们的周围到处可见，比如排队买票，排队买饭以及排队上车，这些 都是排队系统的一部分，当然还有其他排队，像计算机数据的处理也是一种排队。 既然如此就要了解排队系统的组成部分。 一般排队系统有输入过程和到达规则、排队规则、服务机构的结构、服务时 间、服务规则和输出过程。 1 输入过程和到达规则。输入过程一殷是用顾客到达间隔来描述的。根据到 达间隔时间所服从的分布，输入过程可分为定长输入、指数输入、几何输入等。 到达规则指到达是单个到达、成批到达等等。本文将研究的是单个到达。 2 排队规则。一般分为等待制、损失制和混合制。等待制指顾客来到系统发 现服务台均被占用，自动排到队尾等待服务。损失制指顾客来到服务台发现服务 台均被占用i 或因为顾客的等待时间有限，达到其等待期限则马上离开系统。等 待制和混合制又分为先来先服务、后来先服务、随机服务等等，此外还有顾客服 务后反馈等。本文研究的是排队规则为损失制，服务规则为先到先服务。 3 服务机构的结构。服务机构的结构可分为单服务台、有限个服务台与无限 个服务台，而在多个服务台中又可分为并联和串联。还有一个服务台连续为顾客 服务多次以及一个顾客连续被服务多次的情形，后者可分为并联和串联结构。 4 服务时间与服务规则。服务时间指服务一个顾客需要的时间，可分为定长 分布、指数分布、与一般分布等。服务时间分为有假时问和无假时间两类。有假 时间的又分为穷尽服务、闸门服务、限量服务、减量服务，在穷尽服务和闸门服 务中又分为单重休假和多重休假。还有单个服务和批量服务。 。5 输出过程指的是顾客的离去过程，可分为离去和反馈两种。 1 i 3 排队系统的表示方法 1 9 5 1 年肯德尔用三个字母组成的符号a b c 来表示排队系统。其中a 表示到 达间隔时间分布，b 表示服务时间分布，c 表示服务机构中服务台的个数。一般用 m 表示指数分布，用g 表示一般分布，后来在前两个字母的右上角加字母以表示 每次到达几个顾客与每次服务几个顾客。一般还假定到达间隔时间序列为独立同 分布的随机变量序列，服务时间序列也为独立同分布的随机变量序列且这两个随 2 江苏大学硕士学位论文 机变量序列也相互独立。 1 1 4 排队系统的主要指标 一个排队系统要从两方面考虑，即服务机构和顾客的利益来考虑，顾客希望 等待的时间越短越好，那就需要服务机构的服务台越多越好，而服务机构要想获 得高的利益就必须限制服务台的个数。综合考虑排队的几个指标：队长、等待时 间、和服务台的忙期，成为排队论的主要研究内容。 队长：指系统中的顾客数。 等待时间；指从顾客到达时起到他接受服务时止这段时间。 忙期：指空闲的服务机构从有顾客到达开始服务时起到系统服务完所有 顾客时止这段时间。 1 2 不耐烦简介 经典排队理论一般均假设顾客的等待时间或系统的容量是无限的。这些指标 有限制的排队模型的相关文献是很有限的。然而，一方面，现实生活中的许多情 况，时间与空间有限的情况是很普遍的。例如，在网络中高速传输的数据包 ( p a c k e t ) ，每个数据包的传输一般都有时间限制，即只有在一定的时间内到达目 的地才能被接收到，如果超过了这个时间限制就被认为作废。数据包也可能会因 为网络中转换接点处容量有限而不能进入转换器，从而丢失。类似的情况在其它 应用方面也是很常见的，例如，实时计算，自动化生产，工业包装流程，易腐食 品储藏等。 在排队理论文献中，通常把具有有限等待时间的顾客称为“不耐烦顾客”。 ； 一旦涉及到不耐烦顾客，有两种不同情况：“有意识”顾客与“无意识”顾客。一， “有意识”顾客指一旦到达系统，该顾客的服务时间就为已知，若系统的工作量 超过的它的等待期限( 或它要接受完服务所需的服务时间与等待时间之和超过了 它的逗留时间期限) 则马上离开系统，不进行排队。二，“无意识”顾客指所有到 达顾客都进行排队等待，如果直到达到顾客的等待时间期限仍未开始接受服务( 或 达到此顾客的逗留时间期限仍未完成服务，即使它这对正在接受服务) 则它要马 上离开系统。不耐烦顾客的排队时间有一个期限，超过这个期限则它必须离开系 江苏大学硕士学位论丈 统，不再接受服务。在研究中把这种情况分为两种模型：期限截止到服务开始时 1 2 3 】 4 与期限截止到服务结束时 5 6 7 8 9 。在第一种模型中，顾客 仅在服务开始前有等待期限，只要顾客在达到期限前开始接受服务贝嗟捱0 接受完 服务才离开系统，不管逗留时间是否超过期限。在第二种模型中，顾客的期限截 止到服务结束时，即无论顾客是否己开始接受服务，只要达到期限则顾客必须马 上离开系统，从而顾客可能会因为达到期限而中断服务离开系统。 1 3 休假排队简介 经典排队系统规定服务台随时等待为顾客服务，但是在某种情况下并不能得 到最优的统筹安排，如果在系统无顾客时让服务台去迸行其他辅助工作，就会得 到很好的利用。休假排队指服务台在某些时候没有顾客时，暂时中断为顾客服务 的排队系统。随着科技的发展，现实生活中已经出现了多种休假排队的例子。 例l ( 保养策略)为了使服务系统长久有效的对顾客服务，当系统空闲时 就对服务设施进行一次例行保养，实施保养的时间可以视为休假，此期间到达的 顾客需等待完成保养以后才依次被接待。 例2 ( 辅助工作) 在负荷较低的排队系统中，为了有效的利用空闲时间， 可设置某种辅助工作。假定辅助工作也需一项接一项的地完成，完成每项辅助工 作的时间是独立同分布的随机变量。一旦系统内无顾客，服务员就立刻开始一项 辘助工作。完成后若系统中仍无顾客，就继续从事另一项辅助工作，直到完成某 项辅助工作时遇到系统中已有顾客等待则立刻恢复对顾客的服务。若顾客在服务 员从事某项辅助工作时到达，即使前面没有顾客等待也不能立刻得到服务，须等 到该项辅助工作完成后才能利用服务台。把辅助工作时间看作服务员休假。 例3 ( 启动时间)为降低服务成本，当系统中无顾客时可以关闭服务设施， 当有顾客到达时通常需要一个启动时间，启动时间也可以是随机变量。该顾客及 启动期内到达的顾客均需等到启动时间完成后才能相继得到服务。启动时间可以 看作由闲期到达的第一个顾客触发的一段休假时间。 例4 ( 优先权)具有不同优先权的多类顾客的排队系统在经典排队论中已 得到深入研究。如果把高优先权顾客造成的低优先权顾客的服务中断( 强占或非 强占) 视为对低优先权顾客的服务员休假，优先权排队也可纳入休假排队的框架 4 江苏大学硕士学位论文 中。 例5 ( 机器故障)服务台在运行过程中可能发生损坏或需要补充能量，而 故障维修或能量补充必需中断正在进行的服务，这些中断时间可视为服务员休假。 1 4 负顾客排队简介 负顾客的排队模型是排队论的一个新兴分支。负顾客或者是一次误操作或者 是外来对服务台实施服务援助或者是系统的灾难，其主要作用是抵消系统中通常 的顾客正顾客。负顾客的抵消作用按抵消时刻、抵消策略的不同对系统产生 不同的影响。抵消时刻可分为两类：一类是负顾客到达后立即抵消系统中现有的 正顾客；另一类是负顾客仅在服务结束时刻抵消现有的正顾客。抵消策略可分为： 抵消队首正在接受服务的顾客( r c h ) ；抵消队尾的顾客( r c e ) ；抵消整个系统的 顾客( d s t ) 以及随机数量的抵消。 g e l e n b e i o 最早将负顾客引入排队模型，开创了负顾客研究的先河。这以 后有许多科研工作者投身到负顾客的这个领域，产生了很多令人鼓舞的科研成果， 例如h a r r i s o n & p i t e l 1 1 z 2 ，a r t a l e j o & c o r r a l 1 3 儿1 4 ，z h uy i j u n 1 5 等 等。 1 5 优先权排队简介 优先权排队是实际排队系统中很常见的现象，有了这种规定，原来的许多在 f c f s 排队规则下的结论都会发生实质性的变化，例如常见的l i t t l e 公式j 已= 丑万在 这里已经失效，本课题所涉及的优先权全是固定的优先权，属于某一类顾客的优先 权的权值均是固定的，不发生变化。 图1 i 优先权排队分类图 5 江苏大学硕士学位论丈 强占优先权：假定系统中有两类顾客，第一类顾客较第二类顾客具有强占优 先权是指，当服务台空出时，排队中的第一类顾客将到达队伍头部率先接受服务， 即使第一类顾客到达时第二类顾客正在接受服务它也必须退出服务台，让排在头 部的第一类顾客强占服务台接受服务，同一类顾客的服务规则遵循f c f s 准则。 强占继续优先权：在强占优先权下，第二类顾客的服务若被第一类顾客打断， 它回到等待队列中，当系统中无第一类顾客时，它又回到服务台，从被打断处继 续原来的服务。 强占重复优先权：在强占优先权下，第二类顾客的服务若被第一类顾客打断， 它回到等待队列中，当系统中无第一类顾客时，它有回到服务台，如同没接受过 服务一样，重新开始被服务。 非强占优先权：假定系统中有两类顾客，第一类顾客较第二类顾客具有非强 占优先权是指，当到达系统的第一类顾客看到第二类顾客正在接受服务，只有等 到该第二类顾客被服务完毕，排在队伍头部的第一类顾客才可以被服务，同一类 顾客的服务规则遵循f c f s 准则。 1 6 不耐烦排队系统的研究背景、内容及现状 在现实生活中的许多排队现象中，有的顾客可能由于这样或那样的原因在未 接受服务前或正在接受服务但未完成时就离开系统：有的顾客虽然到达但由于队 列过长或其他原因未进行排队就离开系统。这些现象在排队论中称为不耐烦。 p a l m i 6 第一个把不耐烦问题引入排队论中进行了研究。b a r r e r 1 7 、 1 分析了m m 1 + d 系统。b r o d i i 8 、 1 9 研究了m m l + d 系统，给出了 微分积分方程，并求解出了结果。较一般的a 饼l + 研系统在 2 0 中给予了分 析。g n e d e n k o 与k o w a l e n k o 2 i 分析了具有多个服务台的m m s + d 系统，通 过求得s 个服务台的工作量的积分微分方程的确切解，给出了相应性能指标的公 式。利用此方法，j u r k e v i c 2 2 成功地研究了当最大等待时间为一个常量和一个 服从指数分布的随机变量最小值时两种情况下的多服务台模型，并进一步在 2 3 中分析了m m s + g i 系统，其中顾客的到达率依赖于忙着的服务台数。之后， h a u g e n 和s k o g a n 2 4 b a c c e l l i 与h e b u t e r n e 5 独立给出了m m s + 饼分 析结果。h a u g e n 和s k o g a n 利用w a l l s t r o m 2 5 的一个结论，研究了有s 个服务台， 6 江苏大学硕士学位论文 多个泊松输入流，其中每类信元具有各自固定的最大等待时间，系统中的信元( 正 在接受服务和正在等待) 的最大等待时间服从指数分布，通过构造恰当的极限形 式，他们得到了m m s + g i 系统等待时间的分布公式，并令信元在系统中的逗 留时间取极限得到了此结论的推广形式。 在 2 3 、 5 的基础上，a n d r e a sb r a n d t ，m a n f r e db r a n d t 2 6 研究了 m ( ”) m ( 一) s + 口系统，通过求解由信元的最大剩余等待时间和初始时的最大 等待时间构成的向量为元素的积分方程，得到了系统的稳态条件、占有率和各种 等待时间分布。同年，他们又研究了 2 7 具有两个队列，不同优先级的 m f n ) m ( n ) s + a 不耐烦排队系统，此模型是含有多个服务台的不耐烦排队模型 的推广。在多服务台排队模型的研究基础上，b o n gd a ec h o i ，b a r ak i m 和j i n m i n c h u n g 研究了 2 8 带有较高优先权的m m 1 系统，其中一类顾客具有强占优先 权。2 0 0 2 年，c o n o l l y ，p a r t h a s a r t h y 与s e l v a r a j u 2 9 研究了带有不耐烦顾客 的双端排队系统，这使得不耐烦性质的应用范围大大增加。2 0 0 4 年，m e h m e t 与 s o n g 3 0 给出了离散时间、优先权排队模型的性能分析，此结论多应用在宽带网 络传输中。同年，m a d h uj a i n ，r a k h e e ，s a n d h y am a h e s l y v a r i 3 1 将不耐烦性质 应用于带有备用服务装置的可修系统中，并对于损坏的服务装置的修理采用一 策略，这样可以降低系统的工作成本，从而提高收益。在上面的文献中，虽然对 多个服务台、两个队列、不同优先级的系统均有研究，但并未同时限制等待空间 有限。而在实际情况中，系统的等待空间绝大多数都是有限的。本文在第三，四 章将对有两类顾客、其中一类具有强占优先权、等待空间有限的不耐烦排队模型 进行讨论。负顾客排队模型是现在排队论研究的热点，而休假以其广泛的实际应 用背景已得到了深入研究，但是把休假、负顾客、不耐烦相结合的排队模型并未 得到研究，本文将在第五章给予讨论。 1 7 本课题研究内容及解决问题的方法 本课题首先研究了带有强占优先权的m m 2 k m 不耐烦排队模型，其中有 两个等待轨道、等待空间有限、到达率与服务率为定值。利用已有结论：只有一 类顾客的模型中所得到的因不耐烦造成的顾客的离去率公式，结合系统中等待空 7 江苏大学硕士学位论文 间有限这一特性画出了系统稳态下的状态转移图，从而得到了系统稳态下的平衡 方程，利用矩阵性质和稳态分布的唯一性，求得了两类顾客的平稳分布、队长分 布和溢出概率等。进一步在此模型的基础上作一些改进：有一个等待轨道、到达 率和服务率为变量，从而得到了带有强占优先权的m m m k 不耐烦排队模型。 利用类似的方法进行了分析，求得了相应的性能指标。最后，采用矩阵迭代的方 法研究了带有休假、负顾客和正顾客有流失的不耐烦排队模型，并给出了系统中 的平均逗留顾客数、顾客因不耐烦而离去的概率等性能指标。 8 江苏大学硕士学位论文 第二章研究排队模型的主要方法 本章将简要介绍一卞排队论的几种主要研究方法，以及各方法在研究排队论 中的特点。 2 1 嵌入马尔可夫链法 定义设随机过程 x 似f t 的状态空间s 为r 中的可列集，如果对t 中任 意n 个 t z 0 ) 由于到达流是p o s s i o n 流，在这些再生时刻，观察系统的状态一顾客数， l o 江苏大学硕士学位论文 它具有马尔可夫性。n 。表示一个顾客服务结束后刚离开系统时留在系统中的顾客 数，则f n 。 就是一个马尔可夫链，这叫嵌入马尔可夫链。由于t ，一t 。对一切r l 都 是同分布的，到达又是以p o s s i o n 流，于是经过+ ；一毛这段时间，系统从状态a 0 到。+ 一1 状态的概率相同，因此是一个齐次马尔可夫链。为求得此马尔可夫链 的平稳分布，首先应求出转移概率。 2 - 2 补充变量法 许多排队系统的队长过程本身并非马氏过程，但为了利用马氏过程知识分析 排队系统，可把这种排队系统的队长过程嵌入在状态空间更复杂的多维过程中， 使新的多维过程具有马氏性。这种方法称为补充变量法，它是研究排队模型的一 种常用方法。e r l a n g 的阶段化思想可以看成是最早引入补充变量的尝试。k o s t e n 和c o x 也曾经使用过补充变量的技巧。 下面我们以m 。g 1 排队模型为例来说明补充变量法的求解思路。 考虑一个经典的m 。g i 排队模型，顾客成批到达，每批到达的顾客数是随 机变量x 个，批到达流是参数为2 的洎松流，服务时间为一般分布 g g o ) = f g o 如= 一e x p ( 一f a g 皿) ，e ( g ) _ 1 “ 系统中只有一个服务台 p ( x = f ) = qc g ) = c , z 设o ) 表示f 时刻系统中的顾客数，显然o ) 不是马尔可夫过程。设z o ) = x 为，时刻正在接受服务的顾客已经用去的服务时间，贝t l g l 入补充变量x t ) 后 z o ) 是一个二维马尔可夫过程。 令 b o ) = p ( o ) = 0 ) 只( f ，x ：b k = p o v ( f ) = 胛，工 0 当极限分布存在时设 江苏大学硕士学位论文 只= 烩最 只( x 陋= l i m e ( t ，z 由 e o ( t + f ) = p ( 在f 时刻，系统中没有顾客且在压0 ，+ 出没有顾客到达系统) + p ( 拄f 时刻系统中有一个顾客且在f 到h 出他的剩余服务时间为o ) 得p o o + a t ) = p o ( t x l 一五出) + f g 皿( f ，x + 。( 出) 两端除以a t 并令血一0 整理可得 ( 五+ 珈( f ) = f g 跳枷 再令t 斗可得 弛= f 。g ) 鼻g ) 出 同理可得( 丢+ 五十g ) 只g ) = 善n 勉。只一，g ) 珂- 这里规定一0 只( o ) = 血。r + r g 圮。g ) 出 只+ 妻f g 这= l 然后可以对方程求解，从而得到一些排队指标。 2 3 拟生灭过程和矩阵分析法 定义考虑一个二维马尔可夫过程 x ，o ) ，状态空间是 q = 骶，以七0 , 1 m k 称( x n j ( f ) 是一个拟生灭过程，如果其生成元可写成 下列分块三对角形式。 1 2 江苏大学项士学位论文 q = a oc o b 4 b 其中所有子块都是聊阶方阵，满足 0 0 + c o ) e = 慨+ 4 + c k = p + 4 + c k = 0 鸽和4 有负的对角线元素和非负的非对角线元素，其余子块均是非负阵，e 是 元素全为l 的列向量。 称状态集( k ，1 ) ，( k ，2 ) ，( k ，m ) 为水平k 。若过程是正常返的，以讧，) 表示过程 x ( f ) ，( r ) 的极限变量，并记 = 受p 讧( f ) = j i ，o ) = _ ， = 尸伍= 七，= 力 其中k 0 , 1 _ ，所。为适应q 的分块形式，将稳态概率按水平写成分段形式 一0 冲以2 ，万h ) 七0 拟生灭过程是经典生灭过程从一维状态空间到多维状态空间的推广，正如生 灭过程的生成元具有三对角形式一样，拟生灭过程的生成元是分块三对角阵。 从2 0 世纪8 0 年代到9 0 年代田乃硕等把n e u t s 首创的矩阵几何解方法引入到 休假排队模型中，促进了多服务台休假排队系统的研究，并且初步建立起多服务 台休假中以条件随机分解为核心的理论框架，为经典排队论的发展和应用开辟了 更为广阔的前景。 2 4 随机分解 假设当系统变为空时，服务员进行一次休假，如果休假结束时系统不空，服 务员立即开始服务，一直到系统中又无顾客为止；如果休假结束时系统仍为空， 服务员立即开始另一次体假，一直到休假结束时系统中至少有一个顾客为止或服 务员休假一次，若无顾客仍不离岗等待，此系统称为空竭服务、多重休假或单重 休假模型。在系统m 。g 1 中引入此休假策略，简记为m 。g ( e ，m v s v ) i 。 1 3 c ； c 4 ； c 4 b ； 江苏大学硕士学位论文 假设每次休假时间 k ，i 1 独立同分布且与到达过程独立。k ( i 1 ) 同v 的分布有 p ( v = ) = v ，j 1 e ( z ”) = 矿( z ) ，e ( 矿) 0b o o 0 ， f 一， l ，= 其中6 = f t d f ( t ) ( 4 2 p 2 9 0 定理8 3 1 ) 证明：因为s ( ” f s ( ，) + 1 ，所以 监 上兰盟。 n ( f )n ( f )n ( f ) 江苏大学硕士学位论文 记n ( o o ) = l i m n ( t ) 又因 t 呻 p ( ) ) = p ( c o ) = 疗) = p 晶 0 。 江苏大学硕士学住论文 第三章具有强占优先权的不耐烦顾客的 m i m l m l 2 k r n 排队模型 3 1模型的应用背景 具有不耐烦顾客的排队模型已得到了广泛的研究与应用，尤其在网络上的应 用尤为突出，例如在个人通讯服务网络 3 2 3 3 和 3 0 宽带网络中有关声音、信 号、图像及数据信号的传输由于在通信系统中，语音信号只有在有限的时间内传 播才是有效的，而数据信号就没有这种要求，所以语音信号的传递相对于数据信号 而言具有高优先权并且具有一定的有效期现在一些文献利用不耐烦顾客的理论 可对一些服务部门的排队情况及报酬问题进行优化 3 4 3 5 但到目前为止对具 有两类顾客、强占型优先权、有限等待空间的多服务台模型未被研究，本文将在第 三部分研究具有多个服务台，有两类顾客其中一类具有不耐烦和强占优先权的排 队模型 3 2 具有一类顾客的排队模型的描述与假设 3 2 1具有一类顾客的排队模型 在此模型中，只有一个等待队列，等待空间可以是无限或有限的，若等待空 间为有限时到达顾客发现队列已满则马上离开系统不再回来，有m 个相同的服务 台顾客的到达相互独立，服从参数为旯的泊松分布，遵循先到先服务的服务规则， 服务时间服从参数为的指数分布，顾客的等待期限服从参数为v 的指数分布一 般等待期限分为两种：一是等待期限截至服务开始时，二是等待期限截至服务结束 4 本文中顾客的等待期限只适用于服务开始前，它是指：若在等待期限内尚未 接受服务则一旦达到等待期限马上离开系统，若在等待期限内接受了服务则接受 完服务再离开系统，不论总时间是否超过等待期限 1 记口为顾客的等待时间期限，其概率分布为易( f ) = l - e 一( f 0 ) 其中 历( 0 ) = 0 顾客的服务时间与等待期限是相互独立的随机变量序列且各自是同分 1 6 江苏大学硕士学位论文 布的 记 为一个有无限等待期限的顾客到达时看到系统中有1 1 个顾客，他接受服 务前所需的等待时间其分布函数为( r ) = 尸( u r ) 系统达到稳态的充要 上 ，+ ， w 条件为p 侈) e - d 善 o o 成立，其中f ( 孝) = s ( 1 一局( r ) p r ( 2 6 定理 j ；uj o0 3 1 ) 令u 为稳态下，具有无限等待期的顾客在接受服务前需等待的时间分布函 数为毛( r ) = 尹( f r ) ，其密度函数为磊( r ) = 竺鍪尘 顾客的等待时间超过等待期限目的概率为p p u o o ) = 仁( r 溉( r ) 0 e 是服从参数为删的n 阶爱尔朗分布的随机变量，设昂= 0 ，则e 的概率分布 为： 础) 叫e ) 斗e ”篓掣 对v f ，f 肜，z n ，令帆( f ，s ) 表示时刻f 系统中有疗个顾客的条件下，在 ，f + 占) 内 头前顽客的等待时间超过占的概率 定义： ( r ) = 姆掣，= 烘( r ) 称为顾客的丢弃率 2 引理1 p ( 口) 2 老 证明：此定理的详细证明见 4 中引理3 1 引理2 ： 1 7 江苏大学硕士学位论文 p ( r ) = p ( “一，+ e i ! ，i 虬一。目) ：i ： 其中气( r ) = p ( 互r ) = 卜e 一”，互与一。相互独立 此定理的详细证明见 4 中引理3 2 栅2 有酬= 1 丽 枷 蘸忡，出r n m - ， m i 特别规定： 兀尸( 巩口) = 1 t 4 ” 嘲巾驴出 ，l ：( 等卜换为 吼。卜0 m 咖1 叼弘志 li i f 上 ，、 所州小 南。一。 o ( 3 2 ) 珂( 州如陛。 ( 3 3 ( 月一历) ! l v 以脚 f l 玎 m 比较( 3 1 ) 和( 3 3 ) 两式有p ( u 0 ) = 肌 中+ ( m , a ) 【肝一m + lo ( 埘) n m f o 咒 m 门，” 当系统的等待空间为有限时，不妨设系统的容量为k 这种情况是上面所讨论 的特殊情况只需限定了n 的取值范围则有 以= 岛熹= l s 胛肼 岛万而而七 1 9 ( 3 6 ) 一州 y l ， 旯一p，l p r 江苏大学硕士学位论文 f 0 疗m = 1 ( 珂一卅) vm r n l ，系统中 有m 个相同的服务台若到达的顾客发现系统已满则马上离开系统，称为溢出任 意时刻f 时系统中第f 类顾客数为m ( f ) ，i = 1 ，2 令( f ) = l ( f ) ，2 ( f ) ，第一类顾 客较第二类顾客有强占优先权，只要系统中有第一类顾客，第二类顾客数必少予k 记系统状态空间为s ，则 s = ( f ，j ) l o f - k ，0 j k 一所 u ( f ，j ) l o i l ，k 一州+ l s ，k - ， ，o ，m 1 ( r ) 过程在很小的时间段上的状态转移只能发生在相邻的四种可能状态，因此为 二维的生灭过程记状态空间有限，稳态分布必存在记 江苏大学硕士学位论文 只，= 鳃p i ( r ) = i ，2 ( f ) = - ，) 系统得稳态条件将在本章第3 5 部分给出 下面我们均假设系统是满足稳态条件的因为第一类顾客对第二类顾客具有 强占优先权，所以第二类顾客对第一类顾客没有影响，则此模型中顾客的丢弃率可 由第二部分中的模型分析得到，仍记为其中，z 表示稳态下系统中第一类顾客的 人数稳态下的状态转移图如下： ，t 州 j = 脚一1 = 2 ，= l ，t0 趣鸬! 霸x , j m - 0 “l o 曲! 翻 t b jt b 竹毒辎i 。乙一 芷奎m i 袋! 醢 卜：以2t 【 j 盐l ：k f 2陋1 ) “# 2 一 f符 2 图3 2 稳态下系统的状态转移图 3 3 1 稳态下的平衡方程 谖p i = l i p iip 2i p k 飞j = o ，1 ，2 k - m 且= ( 岛p lj n 吖j0 o ) 7 其中= 七一m + l ，k 豆，取只的前七一j + l 行构成的七一+ l 阶行向量其中_ ，= k - m + l ，k 且j = ( 胁，见，。0 ) ，= t m + l ，k e i 。= ( 11 1 ) 丫一 ( 1 ) 由系统稳态下的状态转移图可得下列方程： 圈圈 露秘 2 江苏大学硕士学位论文 = 0 时( + 五) 岛。= hp lo + 心肌1 ( + 五+ f h ) 只o = p f lo + ( i 十1 ) 4 p , + lo + 鲍且l i = 1 ，2 m - i ( a + 如+ m 4 + ) 只o = 只一lo + ( ，卵h + + 1 ) p f + lo i = m ，聊+ l | i 一1 ( 屯+ m 4 + 珞) 以o = a p