（概率论与数理统计专业论文）相关到达及负顾客到达的离散时间排队.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 离散时间相关到达排队系统是排队理论的一个重要研究领域在相关到达排 队系统中，顾客的到达不再是相互独立的，而是具有一定的相关性即存在两个参 数口和晟用来刻划到达过程其中o r = p 在一个时隙中有一个顾客到达i 在前一 个时隙有一个顾客到达】，卢= p 在一个时隙中没有顾客到达i 在前一个时隙没有顾 客到达】 离散时间排队在数字通讯、计算机网络以及b i s d n 网络( 宽带综合业务数 字网络) 中有广泛的应用，他们的运作都是以离散时间为基准的，内部的所有行为 都是发生在一些规则的时间点上，从而离散时间排队系统比其对应的连续时间排 队系统更为合适 负顾客是相对于正顾客而出现的，是一种特殊的顾客，作为一种控制机制在 许多电信及计算机网络中有广泛的应用，负顾客的到达会对系统产生负面的影 响，在有等待空间的一般排队系统中，影响主要有：r c h ：负顾客到达移除队首的 顾客；r c e ：负顾客到达移除队尾的顾客；d s t ：负顾客到达移除系统内的所有顾 客 本文的模型主要有两个第一个模型描述的是有相关到达及负顾客到达固定 服务时间的离散时间排队模型，负顾客移除正在接受服务的顾客，顾客到达过程 为马氏调节相关到达，服务时间分布为定长分布，等待空间有限第二个模型描 述的是有相关到达及负顾客到达一般服务时间的离散时间排队模型，负顾客移除 正在接受服务的顾客，顾客到达为相关到达，服务时间分布为一般分布，等待空间 无限本文详细的讨论了系统的状态方程，并给出了系统在稳态条件下的性能参 数以及负顾客对系统的影响最后通过数值算例来分析几个参量对系统的影响 关键词：离散时间排队；负顾客；相关到达；马尔可夫链；概率母函数 分类号：0 2 2 6 些童堕通本塑堂焦迨銮 垒旦墨t r a c t a b s t r a c t d i s c r e t e t i m eq u e u ew i t hc o r r e l a t e da r r i v a l si sa ni m p o r t a n tr e s e a r c ha r e ai nq u e u e i n gt h e o r y i nd i s c r e t e t i m eq u e u e w i t hc o r r e l a t e da r r i v a l s ，a r r i v a l so fc u s t o m e r sa r en o t i n d e p e n d e n t ，b u tc o r r e l a t e d t h e r ea r et w op a r a m e t e r s 口a n d 卢，d e f i n e da sa = p r o b 【 o n ea r r i v a ld u r i n gas l o tio n ea r r i v a ld u r i n gp r e v i o u ss l o t 】，p = p r o b 【1 1 0a r r i v a ld u r i n g as l o tin oa r r i v a ld u r i n gp r e v i o u ss l o t 】 d i s c r e t e t i m eq u e u e i n gm o d e l sa r ew i d e l yu s e di nt h es l o ts y s t e ms u c ha sa l o h a a n da t m ( a s y n c h r o n o u st r a n s f e rm o d e ) i nb i s d n ( b r o a d b a n di n t e g r a t e ds e r v i c e s d i g i t a ln e t w o r k ) ，w h e r ee v e n t sc a no n l yh a p p e na tr e g u l a r l ys p a c e de p o c h s o n e o ft h e m a i nr e a s o n sf o ra n a l y s i n gd i s c r e t e t i m eq u e u e si st h a tt h e s es y s t e m sa r em o r ea p p r o 。 p r i a t et h a nt h e i rc o n t i n u o u s t i m ec o u n t e r p a r t sf o rm o d e l l i n gc o m p u t e r a n dt e l e c o m m u 。 n i c a t i o ns y s t e m s n e g a t i v ea r r i v e sh a v eb e e ni n t e r p r e t e da s i n h i b i t o ra n ds y n c h r o n i z a t i o ns i g n a l s s ot h ee x i s t e n c eo fn e g a t i v ec u s t o m e r sp r o v i d e sam e c h a n i s mt oc o n t r o la ne x c e s s i v e c o n g e s t i o na tt h es y s t e m t y p i c a lk i l l i n gs t r a t e g i e sa r er c h ：r e m o v a lo fc u s t o m e r a t t 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 ee n d ；d s t ：r e m o v a la l lc u s t o m e r si nt h e s y s t e m i nt h i sp a p e rw ec o n s i d e rt w oq u e u e i n gs y s t e m s t h ef i r s ti sd i s c r e t e t i m eq u e u e s w i t hc o r r e l a t e da r r i v a l sa n dn e g a t i v ea r r i v a l sa n dc o n s t a n ts e r v i c et i m e s n e g a t i v ec u s t o m e r sr e m o v eac u s t o m e rw h oi sb e i n gs e r v e d w ef o c u so nad i s c r e t e t i m es i n g l e - s e r v e rq u e u e i n gs y s t e mw i t hc o n s t a n ts e r v i c et i m e so fa r b i t r a r yl e n g t h ，af i n i t es t o r - a g ec a p a c i t ya n das i m p l en o n - i n d e p e n d e n t a r r i v a lm o d e l t h es e c o n di sd i s c r e t e t i m e q u e u e sw i t hc o r r e l a t e da r r i v a l sa n dn e g a t i v ea r r i v a l sa n dg e n e r a l l yd i s t r i b u t e ds e r v i c e t i m e s n e g a t i v ec u s t o m e r sr e m o v eac u s t o m e rw h o i sb e i n gs e r v e d w ef o c u so na d i s c r e t e - t i m es i n g l e s e r v e rq u e u e i n gs y s t e mw i t hg e n e r a l l yd i s t r i b u t e ds e r v i c et i m e so f a r b i t r a r yl e n g t h ，ai n f i n i t es t o r a g ec a p a c i t ya n d as i m p l en o n i n d e p e n d e n ta r r i v a lm o d e l i ne a c hm o d e l ，w ea n a l y s i st h em a r k o vc h a i nu n d e r l i n gt h eq u e u e i n gs y s t e ma n do b t a i n i t se r g o d i c i t y w ep r e s e n ts o m ep e r f o r m a n c em e a s u r e so ft h es y s t e mi ns t e a d y s t e a d y , t h ee f f e c to fn e g a t i v ec u s t o m e r so nt h es y s t e m f i n a l l y , s o m en u m e r i c a le x a m p l e ss h o w t h ei n f l u e n c eo ft h ep a r a m e t e r so ns e v e r a lp e r f o r m a n c ec h a r a c t e r i s t i c s k e y w o r d s ：d i s c r e t e t i m eq u e u e s ；n e g a t i v ec u s t o m e r s ；c o r r e l a t e da r r i v a l s ；m a r k o v c h a i n ；p r o b a b i l i t yg e n e r a t i n gf u n c t i o n ； c l a s s n o ：0 2 2 6 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特别加以标注和致谢之处外，论文中不包含其他人已经发 表或撰写过的研究成果，也不包含为获得北京交通大学或其他教育机构的学位 或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在 论文中作了明确的说明并表示了谢意。 学位论文作者签名：签字e t 期：年月日 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留、使用学位论文的规定。 特授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学 校向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名： 陈闫伍 签字日期：呷年办乃南 导师签名： | 嗡 夕 签字日期1 年石序髫日 | 致谢 本论文的工作是在我的导师王金亭教授的悉心指导下完成的，在论文选题、 研究、定稿的过程中，王老师自始至终给了我大力的支持和无私的关怀感谢我 的导师，他严谨细致、一丝不苟的作风一直是我工作、学习中的榜样，他循循善 诱的教导和不拘一格的思路给予我无尽的启迪无论是在科研上，还是在平时的 生活中，他都给了我无微不至的关怀与鼓励他严谨的治学风格，广博的知识，精 益求精的科研作风，敏锐的学术思想和忘我的工作精神影响并鞭策了我，是我今 后生活与工作中一笔极大的财富，在此谨向王老师表示深深的感谢 感谢我同门的师姐师妹师兄师弟共同的学习生活使我收获多多 我还要感谢同窗两年的各位同学我从他们身上学到了很多有益的知识和学 习的方法两年多的同窗之谊，离别之际，更显珍贵我为自己两年来生活在那种 坦诚相待，互帮互助的氛围中感到莫大的荣幸! 最后，感谢各位专家，学者在百忙中审阅我的论文，并给出批评意见在完成 本论文，即将踏入工作岗位之时，我深深地感到：自己每一步的前进，都离不开老 师，亲朋和同学的支持与教诲，在此表达我对他们最衷心的感谢! 北京交通大学硕士学位论文第1 章绪论 第1 章绪论 1 1 排队论及离散时间相关到达排队理论简介及发展 排队论( 又称随机服务系统) 是研究系统由于随机因素的干扰而出现排队( 或 拥塞) 现象的规律性的一门学科，它通过研究各种服务系统在排队等待中的各种 概率特性，来解决系统的最优设计和最优控制排队是一种普遍的现象，比如到商 场购物，在公共电话亭打电话，到医院看病，去图书馆借阅书刊，高考查询成绩，汽 车到汽油站加油等等，这些问题都可以看作是顾客与服务台之间的一种服务关系 所以，排队论适用于一切服务系统，包括通信系统，交通与运输系统，生产 预算服务系统，存储与装卸系统，管理运筹系统以及计算机网络等 排队论是运筹学的重要组成部分，它起源于电话服务理论的研究2 0 世纪丹 麦数学家、电器学家爱尔朗( a k e r l a n g ) 用概率论方法研究电话通话问题，从而 开创了这门应用数学学科，并建立了许多基本原则3 0 年代中期，费勒( w f e l l e r ) 引进了生灭过程的研究方法，排队论才被数学界承认为一门重要学科第二次世 界大战之前，其研究多侧重于电话和距离通信方面的研究，发展比较的缓慢二 战后，由于排队论渗透到军事、经济、生产与服务的领域，于是迎来了理论与应 用的大发展，使之成为运筹学管理科学的一个热门分支，5 0 年代初，肯德尔( d g k e n d a l l ) 用嵌入马氏链( a m a r k o v ) 方法研究排队论，使排队论得到了进一步的发 展特别是7 0 年代以来，随着计算机的不断发展与更新，通信网的建立与完善，信 息科学与控制理论的蓬勃发展均涉及到最优化设计与最佳服务问题，从而使排队 理论与应用获得了飞速发展 相关到达排队系统是排队理论和通信网络理论的一个重要组成部分，它 在许多实际问题中得到了应用，但至今为止关于其的研究还不是特别多，见文 献【1 3 ，2 1 ，3 1 ，3 2 在z h o ua n dw a n g 【2 9 】中，考虑b e r n o u l l i 相关到达和一般服务 时间单服务台离散时间排队模型，在w i t t e v r o n g e la n db r u n e e l 【2 2 】中，考虑相关 到达和固定服务时间单服务台离散时间排队模型相关到达排队系统的特征就是 顾客到达的过程不再是相互独立的过程，而是具有一定的相关性即将时间轴等 间距分割，每一段称作一个时隙，若有顾客到达，则称为o n 状态，相反若没顾客到 达，则称为o n 状态，它以概率口停留于o n 状态，以概率届停留于o n 状态，而 以概率1 一口( 或概率1 一助从o n 状态( 或o f f 状态) 转移到o f f 状态( 或o n 状 北京交通大学硕士学位论文第1 章绪论 态) 到达过程的相关性对系统性能有很大影响，在文献【2 0 ，2 9 ，3 1 ，3 2 】中讨论了系 统的队长、缓冲器容量等性能指标随相关性增强而增大，有效输出率随相关性 增强而减小，所以顾客到达过程的相关性不能忽视，有必要考虑 过去的十几年，有负顾客到达的排队系统( g 一排队) 成为研究的热点负顾客 与正顾客不同，它可以对系统产生各种影响：删除排队中的顾客、删除正在接受 服务的顾客，或者导致服务器坏等多种影响负顾客作为一种控制机制在通信计 算机网络中有着广泛的应用1 8 9 8 ，g e l e n b e 【8 】在研究神经网络模型时首次引入 了负顾客的概念，用于刻划正负神经元之后他陆续发表了一系列论文，把负顾客 引入到排队理论及排对网络中来，均可见文献 9 ，l o ，l l 】连续时间g 排队已经 得到了很多的研究，均可见文献【3 ，7 ，1 6 】，但离散时间g 一排队系统近期才得到发 展，均可见文献【1 2 ，1 4 ，1 6 ，2 7 ，2 8 本文就是在此基础上研究有相关到达的离散时 间g 排队系统的两个不同的模型 1 2 排队系统的基本概念 1 2 1 排队系统的组成部分 一般排队系统由输入过程与到达规则、排队规则与服务机构的结构、服务 时间与服务规则组成 1 输入过程与到达规则一般情况下，输入过程是用顾客到达间隔时间来 描述的根据到达间隔时间所服从的分布，输入过程可分为定长分布、几何到 达( b e r n o u l l i 到达) 、( 负) 指数分布( p o s s i o n 分布) 、爱尔朗到达，负二项到达与一 般到达到达规则指顾客到达系统的方式，可以是单个到达、成批到达、依时到 达、移态到达等今后若不特别说明，到达均为单个到达 2 排队规则排队规则一般分为等待制、损失制和混合制，在等待制和混合 制中，又可以分为先来先服务( f c f s ) 、后来先服务( l c f s ) 、随机服务( r o s ) 、优先非抢占服务、优先抢占服务等在混合制中又分为队长( 容量) 有限、等 待时间有限此外，还有顾客服务后反馈以及共同占用、占而不用等等今后，若 不特别说明，总认为系统的排队规则为等待制先来先服务 3 服务机构服务机构主要指服务台的数目，有( 有限) 多个服务台时服务的 方式是并联还是串联，服务时间( 服务一个顾客所用的时间) 服从什么分布，服务 时间一般分为定长分布、指数分布、几何分布与一般分布等 2 北京交通大学硕士学位论文第1 章绪论 1 2 2 排队系统的主要指标 对个排队系统的好坏进行评价要从顾客和服务机构两方面的利益来考虑 对顾客而言，总是希望等待时间或者逗留时间越短越好，所以希望服务台个数越 多越好但是，对服务机构而言，增加服务台的个数，就意味着需要加大投资，增加 多了要造成浪费，那么增加多少最为合适呢? 顾客与服务机构考虑到自己的利益， 非常关注排队系统中的几个指标：队长、等待时间、服务台的忙期因此这几个 指标成了排队论的主要研究内容 1 队长队长是指系统中的顾客数也就是正在服务的顾客数与等待服务的 顾客数之和通常要求其分布和前两阶矩 2 等待时间从顾客到达系统时开始算起一直到他被接受服务时为止的这段 时间称为( 该) 顾客的等待时间，而称从顾客到达系统时开始算起一直到他被服务 完成离开系统时为止的这段时间称为( 该) 顾客的逗留时间，即顾客的等待时间与 服务时间之和我们也要求其分布及前两阶矩 3 忙期忙期是指空闲的服务机构从有顾客到达系统时开始算起一直到服务 机构又没有顾客时为止的这段时间与忙期对应的是闲期他指服务机构从开始 没有顾客时算起一直到服务机构又有顾客时为止的这段时间对于有n 个服务台 的系统，通常还要讨论其k 阶繁忙期从系统中开始有k 个顾客在等待服务时起一 直到有一个服务台空闲时止的这段时间称为该系统的k 阶繁忙期零阶繁忙期称 为繁忙期忙期、闲期、k 阶繁忙期也是随机变量一般也要讨论他们的分布与前 两阶矩 1 3 相关到达离散时间g 一排队系统 相关到达排队系统是排队理论和通信网络理论的一个重要组成部分，它 在许多实际问题中得到了应用例如，对计算机网络的性能评价( p e r f o r m a n c e e v a l u a t i o n ) 是计算机网路和计算机系统研究与应用的重要理论基础和支撑技 术，是通信和计算机科学领域的重要研究方向，我们可以利用排队论来做网络 性能评价，相关到达排队系统的研究使建立的数学模型更加符合实际问题例 如，在宽带综合业务数字网络( b i s d n ) 中，异步转移模式( a t m ) 被国际电联 电信标准部确立为未来的通用技术之一，它是线路交换与分组交换相结合的产 物a t m 网络是一种以信元为基础的快速分组交换光纤网络，其特点是采用面 向连接方式，信息被分成4 8 个字节( 外加5 个字节的控制信息) 的固定长度的单 元，称为信元( c e l l ) 当网络终端向网络提出通信要求，网络根据带宽资源利用 3 北京交通大学硕士学位论文第1 章绪论 情况建立通向另一端的固定通道，建立连接后，信元就可以沿着这条通道传送 因而a t m 网络以单一的网络结构和综合的方式处理语音、数据、图形和电视各 种信息传输所有的消息数字化以后都被分割成有固定长度的a t m 信元在这 个系统中，顾客就是随机到达并要求传输的信息，排队指消息在缓冲器中等待 传输，服务台就是计算机通讯系统或传输路线任何消息的服务( 传输) 时间是单 位a t m 信元持续时间的整数倍，因此是正整值随机变量这一系统中最自然和 最基本的时间单位是一个a t m 信元在线路中的传送时间，服务开始和结束都只 能在有确定间隔的分点处发生所以，在b i s d n 中，需求的到达过程表现出明 显的相依性和突发性，传统的更新到达过程已不能描述这些新的特征这些年引 入的m o r k o v 到达过程克服了传统到达模式的局限性，能很好的适用于b i s d n 建模和分析 到达间隔和服务时间是非负连续随机变量的排队系统，称为连续时间排 队在这类模型中，顾客到达或离去这些事件的发生时刻可以取任何正实数 排队论的大量文献和著作，主要集中于连续时间排队系统到达间隔和服务时 间都是正整值随机变量的排队系统，称为离散时间排队所以离散时间排队系 统，将时间轴等间距分割，每一段称作一个时隙( s l o t ) 进一步，在时间轴上标 记o ，l ，l 顾客的到达和离去只能发生在时隙的分点处与连续时间排队 不同的是，在离散时间排队中到达和离开同时发生的概率不再是0 ，也就是说， 对于离散时间模型顾客的到达与离去发生在同一时刻点是正常现象因此我们有 必要设定到达和离开同时发生的先后顺序在以前的文献中，有这样两种规则：( 1 ) 如果到达在离开之前发生，这样的系统称为l a t ea r r i v a ls y s t e m ( l a s ) ；( 2 ) 如果离 开在到达之前发生，则称之为e a r l ya r r i v a ls y s t e m ( e a s ) 在本文中，若无特别说明 我们讨论第二种情形为了能用数学的语言准确的描述这一模型，我们假定顾客 到达发生在( n ，n + ) ，而离开的结束点发生在伽一，万) ；也就是说，达到发生在边界点 之后的瞬间，离开发生在边界点之前的瞬间 e a s 模型：在时间轴上我们将时间点记为o ，1 ，2 ，以考虑任意一个时间点 假设顾客的离开发生在时间段( ，l 一，1 ) ，到达发生在( t l , ，l + ) ，其中n - ( n + ) 表示，l 时刻 的前( 后) 一瞬间此模型可以用图表示： 4 北京交通大学硕士学位论文第l 章绪论 dd 顾客离开0顾客到达 l a s 模型：在时间轴上我们将时间点记为0 ，l ，2 ，1 考虑任意一个时间点 假设顾客的离开发生在时间段( n ，n + ) ，到达发生在一，1 ) ，其中n - + ) 表示n 时刻 的前( 后) 一瞬间此模型可以用图表示： dd 0 顾客到达顾客离开 相关到达排队系统是指外界顾客的到达过程不再是相互独立的，而是具有一 定的相关性，例如，任意一个时隙顾客到达的数量是一个随机变量，它与前一个时 隙到达的顾客数量有关在一个时隙内，可能有一个顾客到达，也可能没有顾客到 达所以到达过程可以用两个独立的参数来刻划其中： 口= p r 【在一个时隙中有一个顾客到达i 在前一个时隙有个顾客到达】， 卢= p r 【在一个时隙中没有顾客到达i 在前个时隙没有顾客到达】 5 北京交通大学硕士学位论文第1 章绪论 也就是说到达过程在o i l 状态和o f f 状态之间转换，其中o i l 状态是指在此时 隙内有顾客到达，o f f 状态是指在此时隙内没有顾客到达所以我们就可以得到系 统以概率1 一0 4 或l 一励从o i l 状态( 或o f f 状态) 转移到o f f 状态( 或o n 状态) 其图形表示如下图1 ： ( 固l 】 为了更好的理解这- - n 达所刻划的到达的相关性，我们引入另外两个重要 的参数因子： y = 揣= 厕1 - 3 ( 1 1 ) y = 一= 一 i 1 - e 【】+ e 【l ，厂】 2 一a 一声 ”一7 b2 南 ( 1 2 ) 其中y 是在稳态下任一个时隙处于o n 状态的稳态概率，或称稳态负荷b 称 为突发性因子，用于描述e 【】，e 【l ，r 】的绝对长度由交替更新过程理论易知 由( 1 1 ) 式给出的稳态负荷y 为一个周期中处于o n 状态的时间所占的比例换句 话说，当研】= 2 0 ，研】= 2 0 时，其稳态负荷与e 【】= 1 0 ，研砌】= 1 0 相同，都是 y = 互丽2 0 石= 熹1 0 1 0 = o 52 0 + 2 0+ 然而，易见这两个到达并不一样，第一个到达过程突发性更强一些因而因 子y 不能反映到达的突发性，它只是稳态下的平均所以有必要引入一个参数来 刻划突发性，突发性因子b 正起着这个作用由( 1 1 ) 、( 1 2 ) 有： 删一半 卢= 1 一二b 则可知当稳态负荷不变的情况下，突发性因子b 越大，口，卢也越大另一方面又 有： e t o n l = 而1 = 菩 6 北京交通大学硕士学位论文第1 章绪论 日哳】= 南= 南 故b 越大，昱 】和e 【l ，厂】越大，从而突发性越强在上面例子中突发性因子 分别为b = 1 0 和b - - 5 当b = 1 时，a = 1 一卢，则在任一时隙处于o n 状态的概 率为口，而与前一时隙无关，此时到达变为不相关 负顾客的到达也有两种方式：可能与正顾客混在一起，以某一个概率出现例 如顾客的到达服从参数为p 的几何过程正顾客以q + 的概率出现，负顾客以q 一 的概率出现负顾客可能与正顾客相互独立出现，即为两个顾客流例如正顾客可 以为几何到达过程或者为相关到达过程，而负顾客可为几何到达过程，两者是相 互独立的 1 4 本课题研究的主要模型及方法 本课题研究的主要是到达过程为相关到达且有负顾客到达的离散时间排队 系统主要通过“嵌入马氏链”的方法得到系统的转移概率，运用“概率母函数 法 得到系统的稳态方程，最终得到我们所考察的排队模型在稳态条件下的各个 性能指标，例如，缓冲器容量，未完成工作，服务延迟等等最后通过具体的数值 算例来分析几个参量对系统的影响 根据实际问题的需要，本课题建立并解决了两个相关到达及负顾客到达的离 散时间排队模型： ( 1 ) 有负顾客到达的m m b p d 1 离散排队模型； ( 2 ) 有负顾客到达的肘m b p g 1 离散排队模型 7 北京交通大学硕士学位论文第2 章有负顾客到达的m m b p d i 离散排队模型 第2 章有负顾客到达的m m b p d 1 离散排队模型 2 1 模型描述 考虑离散时间排队系统，将时间轴等间距分割，每一段称作一个时隙进一 步，在时间轴上标记o ，1 ，n 我们考虑单服务台和有限的等待空间，其大小 为s ( s o ) 所以我们可以知道等待空间内总的顾客数最多为s + 1 在排队系 统中顾客到达是随机的，如果等待空间未满且服务台忙碌，则顾客在等待空间内 等待；反之若等待空间已满，则顾客丢失在等待空间内，顾客等待一段时间，直到 最后他们得到服务假设每位顾客的服务时间是固定服务时间，为肘个时隙，其 中m 1 但是负顾客不需要服务，负顾客到达，若有正在接受服务的正顾客，则 删除正在接受服务的正顾客；若服务器空闲，则负顾客对系统无影响从外界到达 的正顾客为马氏调节b e r n o u l l i 相关达到， ( 固i j 也就是说，存在两个参数口和届，用来刻划到达过程其中 口= p r 【在一个时隙中有一个顾客到达i 在前一个时隙有一个顾客到达】， 卢= p r 【在一个时隙中没有顾客到达i 在前一个时隙没有顾客到达】 为了避免一些平凡的情况，我们假定0 口 1 ，0 0 且攻m 一1 ：若无负顾客到达， 则 若有负顾客到达，则 若政 0 且取= m l ： 若s k = 0 ( 所以心= o ) ： s k + 1 = 础n ( & + a k ，s + 1 ) ， 以+ 12 攻+ 1 s k + 1 = m i n ( s k + a k 一1 ，s + 1 ) ， h + i = o ； s k + 1 2 m i n ( s k + a k ，s + 1 ) 一1 ， h + 1 2 0 ； & + l= a k ， 攻+ 1 = 0 ( 2 1 ) ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) ( 2 6 ) ( 2 7 ) ( 2 8 ) 由上面的系统方程( 2 1 h 2 8 ) ，可以很容易的判断出向量( r 七，站l ，& ) 是 一三维马氏状态，即系统在第k 个时隙开始时一种状态令p ( i ，l ，_ ) 为马氏 链( 心，口扣l ，取) 的稳态概率，即： p ( i ，n ，_ ) = 。l i mp r 【= f ，a k - i = n ，政= 刀 对所有的0 i m 一1 ，n = 0 ，l 和0 j s + 1 为分析以上方程定义部分概率母函数q 抽( z ) ： s + l q i 刃( z ) = p ( i ，l ，j ) z j ，0 f m l ，n = 0 ，1 j - _ _ 一 9 ( 2 9 ) ( 2 1 0 ) 北京交通大学硕士学位论文 和函数r 。( y ，z ) ： 第2 章有负顾客到达的m m b p d 1 离散排队模型 m l 也( y ，z ) = a i 一( z i = o 利用状态方程( 2 1 ) 一( 2 8 ) ，可以得到一步转移概率： ( 1 ) 当f = l ， 当，l = 0 ， p ( 1 ，0 ，力= 元印( o ，0 ，j ) + 于( 1 一e ) p ( o ，1 ，j d ，1 j s + l ， p ( 1 ，0 ，0 ) = 0 ，p ( o ，0 ，0 ) = p o ，p ( o ，1 ，0 ) = 0 ，j = 0 上式等号两边同时乘以后对_ 相加得： j + l工+ lj + i p ( 1 ，0 ，j ) d = p 夕p ( o ，0 ，j ) z j + 亍( 1 一a ) p ( o ，1 ，j ) z i p p o 亍 j = oj = oj = o 由概率母函数的定义可以得到 当n = 1 。 ( 2 1 1 ) 0 1 ，o ( z ) = f l 亏q o ，o ( z ) + ( 1 一a ) 于q o ，1 ( z ) 一卢p o 于( 2 1 2 ) p ( 1 ，1 ，力= 甲( 1 - f 1 ) p ( o ，o ，j 一1 ) + 于c r p ( o ，1 ，j 1 ) ，2sj s ， p ( 1 ，1 ，1 ) = 0 ，j = 1 ， p ( 0 ，0 ，0 ) = p o ，p ( 0 ，1 ，0 ) = 0 ，j = 0 ， p ( 1 ，1 ，s + 1 ) = 亍( 1 一卢) p ( 0 ，0 ，s ) + p o r p ( o ，l ，s ) + 亍o t p ( o ，1 ，s + 1 ) + 认1 - f 1 ) p ( o ，o ，s + 1 ) ，j = s + 1 上式等号两边同时乘以后对歹相加得： p ( 1 ，1 ，j ) z j = 于( 1 - f 1 ) 2 p ( 0 ，0 ，一1 ) z j + 于a 2 p ( 0 ，1 ，j 一1 ) z i j = 2j = 2 j = 2 葺一lj l 弋1x1 = 于( 1 一p ) z p ( o ，o ，j 1 ) + 亍口 p ( o ，l ，_ 一1 ) j - j 二一 再由p ( 1 ，1 ，1 ) = 0 ，p ( 1 ，1 ，s + 1 ) = 亍( 1 - f 1 ) p ( o ，o ，s ) + y a p ( o ，l ，s ) 得 j l = 夕( 1 一卢) z p ( o ，0 ，歹) + 于( 1 一f 1 ) p ( o ，0 ，s ) r + 1 净l 1 0 力p 州芦 北京交通大学硕士学位论文第2 章有负顾客到达的m m b p ! d 1 离散排队模型 十尹( 1 - f 1 ) p ( o ，0 ，s + 1 ) z 什1 + 穸a zz p ( o ，l ，j ) f l + 于, a p ( o ，1 ，s ) r 十l j = l + 亍( 堆7 ( 0 ，1 ，j + 1 1 i z 什1 j + lj + l = 夕( 卜仞z p ( o ，0 ，j ) z j + 纰yp ( o ，l ，j 3 z j -jl-j j = 1j = 1 + ( 1 - f 1 ) 亍y p ( o ，0 ，s + 1 ) + 1 ( 1 一z ) + 昕p ( 0 ，1 ，s + 1 ) z j + 1 ( 1 一z ) s + lj + l，+ l 即p ( 1 ，l ，j ) z j = 亍( 1 - f 1 ) z p ( o ，0 ，j ) + 于毗p ( 0 ，l ，d 一( 1 一f 1 ) z p o j = oj = oj = o 由概率母函数的定义可以得到： q l ，l ( z ) = ( 1 一f 1 ) 让q o ，o ( z ) + 研a o ，l ( z ) 一( 1 一f 1 ) z p o ( 2 1 3 ) ( 2 ) 当2 i m 一1 ， 当n = 0 ， p ( i ，0 ，d = 于, f l p ( i 一1 ，0 ，j ) + 于( 1 一o t ) p ( i 一1 ，1 ，j ) ，1 j s + 1 ， 上式等号两边同时乘以后对j 相加得： 葶十1j + 1j + l p ( f ，0 ，j ) z j = 祁p ( i 一1 ，0 ，j ) d + 于( 1 一口) p ( i 一1 ，1 ，j ) z j j = l= l j = l 由概率母函数的定义可以得到： 当咒= 1 。 q f ，o ( z ) = 所q i l ，o ( z ) + ( 1 一a ) c q i - 1 ，l ( z )( 2 1 4 ) p ( i ，1 ，j ) = 夕( 1 一f 1 ) p ( i 一1 ，0 ，j 一1 ) + 亍, t r p ( i 一1 ，1 ，j 一1 ) ，1 j s ， p ( i ，l ，s + 1 ) = 夕( 1 - f 1 ) p ( i 一1 ，0 ，s ) + 亍, a l p ( i 一1 ，1 ，s ) + 亍( 1 一f 1 ) p ( i 一1 ，0 ，s + 1 ) + 亍口p ( f 一1 ，l ，s + 1 ) ，歹= s + 1 上式等号两边同时乘以后对_ 相加得： = 亍( 1 一f 1 ) z p ( i - l ，0 ，歹一1 ) + 亍( 1 一f 1 ) p ( i 一1 ，0 ，j ) r + l 卢1 d “ 矽 州州 北京交通大学硕士学位论文 第2 章有负顾客到达的m m b p d 1 离散排队模型 + 亍( 1 一f 1 ) p ( i 一1 ，0 ，j + 1 ) r + 1 、 + 甲a ：p ( f 一1 ，1 ，j f 一1 ) + 于, o t p ( i 一1 ，1 ，j ) z 5 + 1 = 1 + 亍口p ( f 一1 ，1 ，j + 1 ) r + 1 = 于( 1 - f 1 ) z p ( i - l ，0 ，j ) z j + ? o r ze p ( i 一1 ，1 ，j ) z j j = oj = o + ( 1 一助于p ( f 一1 ，0 ，s + 1 ) r + 1 ( 1 一z ) + 研p ( f 一1 ，1 ，5 + 1 ) ，1 ( 1 一z ) = 亍( 1 一f 1 ) z p ( f 一1 ，0 ，j ) z j + 亏o t z e p ( i l ，1 ，j 9 = 0j = o + ( 1 - f 1 ) y p ( i 一1 ，0 ，s + 1 ) ? + 1 ( 1 一z ) + o t 7 , p ( i 一1 ，1 ，s + 1 ) + 1 ( 1 一z ) 由概率母函数的定义可以得到： q i ，l ( z ) = ( 1 - f 1 ) 亍 z q f 一1 ，o ( z ) + a 亍, z q f 一1 ，l ( z ) + p i - i z s + 1 ( 1 一z )( 2 1 5 ) ( 3 ) 当i = 0 ， 当n = 0 ， p ( o ，0 ，- ) = p ( o ，0 ，0 ) = p ( o ，0 ，s + 1 ) = 于, f l p ( m 一1 ，0 ，j + 1 ) + 夕( 1 一o o p ( m 一1 ，1 ，j + 1 ) 1 1 + 伊 p ( f ，0 ，j + 1 ) f = l m l + y ( 1 一叻p ( f ，1 ，歹+ 1 ) ，1 j s ， f = l 于, f l p ( m 一1 ，0 ，1 ) + 于( 1 一o o p ( m 一1 ，1 ，1 ) |lflfl + p 护+ 馏 p ( f ，0 ，1 ) + y ( 1 一口) ：p ( 1 ，1 ) ，j = s + 1 ， i1 l = l j = l 0 ，f = 0 上式等号两边同时乘以后对_ 相加得： 亍, , 8 ep ( m - 1 ，0 ，j + 1 ) + 夕( 1 一口) p ( 肘一l ，1 ，_ + 1 ) z j j = 1j = 1 j + 1m - l s + 1 f 一1 + y f l ep ( i ，0 ，j + 1 ) z j + t ( 1 一p ( 扎1 歹+ 1 ) z y j = 1i = 1 j = lf - 1 + 谚印( 肘一1 ，0 ，1 ) + 亍( 1 一o o p ( m 一1 ，l ，1 ) + p 护 1 2 = ， 00 p 州间 北京交通大学硕士学位论文第2 章有负顾客到达的m m b p d i 离散排队模型 由概率母函数的定义可以得到： z q o o ( z ) = p 夕q m 一1 ，o ( z ) + ( 1 一o t ) 于 q m 一1 ，k z ) + p o b z 当，l = 1 。 p ( o ，1 ，d = 于( 1 一f 1 ) p ( m 一1 ，0 ，) + 夕口p ( m 一1 ，1 ，j ) p ( o ，1 ，1 ) = 亍( 1 - f 1 ) p ( m 一1 ，0 ，1 ) + 甲o t p ( m 一1 ，1 ，1 ) p ( o ，1 ，0 ) = 0 ，j = 0 ， ( 2 1 6 ) 2 _ s 一1 ， p ( o ，1 ，s + 1 ) = 0 ， 歹= s + 1 ， p ( o ，l ，s ) = 亍( 1 一f 1 ) p ( m 一1 ，o ，s ) + 讯r p ( m 一1 ，1 ，s ) + p 叩( m 一1 ，1 ，s + 1 ) + 于( 1 一f 1 ) p ( m 一1 ，0 ，s + 1 ) m l 肘一l 岬( 1 一励p ( i ，0 ，s ) + y a z p ( i ，l ，j ) ，j = s 式等号两边同时乘以后对，相加得： s + ls + l j + l p ( o ，1 ，：3 z j = 亍( 1 一) p ( 肘一1 ，0 ，彬+ 于az p ( m 一1 ，1 ，歹) j = oj = 2y - - 2 j = 1 ， + 巧( 1 一卢) p ( m 一1 ，0 ，1 ) + z 弘p ( m 一1 ，1 ，1 ) + p o ( 1 一国z m 一1 + y ( 1 一励z p ( i ，0 ，o z i 可 s + 1 j + l f l = 亍( 1 一) p ( m 一1 ，0 ，j ) z j + y ( 1 一卢) p ( f ，0 ，歹) j = 1，= l f - l 1 3 u p 斟 口一 y +0 “ p 汐 + 力 “ p 岸 口 一 y + 力“q 斟 泸 + p， 0 “p 叫 励 一 y + b lp 训 口 m + 、乃up 斟 口 y +0 ap 斟 一 y + 励 一 op + 力 o up 川甜 州胆 黟 一 y + 力up 斟 州芦 口 y + 北京交通大学硕士学位论文 第2 章有负顾