（概率论与数理统计专业论文）两种类型取号排队系统的性能分析及改进.pdf

摘要 取号排队系统的应用由来已久，由于其特殊的优点，在现代的服务行业和政府 机构中应用更加普遍一般的取号排队为：一个顾客到达后，将得到一个号码；正 在被服务的顾客的号码在显示屏上显示，顾客以自己的号码和显示屏上的号码的差 值来判断自己的位置，并决定是进入排队系统还是离开本文主要讨论两种类型的 取号排队模型：一为带止步和中途退出的取号排队模型，当号差超过顾客的忍耐水 平时，他选择离开( 止步) ，否则，顾客就进入系统排队；对进入系统的顾客，当等 待时间超过他的忍耐限度时，他也离开( 中途退出) 由此，我们建立了一个马尔科 夫链模型，用一种有效的方法给出了他的平稳状态分布，并得到了我们所期望得到 的系统的一些性能指标；同时，我们给出了一种近似的模型以减少计算量二为带 止步的两个服务台的取号排队模型，本文巧妙的给出了系统的状态及平稳概率，为 多服务台的研究提供了一种研究方法 关键词：取号排队，止步，中途退出，超状态，矩阵几何解 i i 摘要 a b s t r a c t t i c k e tq u e u et e c h n o l o g yh a sb e e nu s e df o rm a n yy e a r s i ti sw i d e l yu s e di n s e r v i c ei n d u s t r i e sa n dg o v e r n m e n to f f i c e s a ss o o na sac u s t o m e ra r r i v e ，h ew i l lg e t at i c k e tn u m b e r ，a n dt h en u m b e rc u r r e n t l yb e i n gs e r v e di sb r o a d c a s to nad i s p l a y p a n e l w ew i l ld i s c u s st w om o d e l s ，o n ei st h et i c k e tq u e u ew i t hb a l k i n ga n dr e n e g i n g c u s t o m e r s ，a c c o r d i n gt h ed i f f e r e n tb e t w e e nh i st i c k e tn u m b e ra n dt h eb r o a d c a s t n u m b e r ，h em a k ead e c i s i o nw h e t h e rh ej o i n st h eq u e u eo rl e a v et h es y s t e m w e p r o p o s et h a ti ft h ed i f f e r e n c eb e t w e e nh i st i c k e tn u m b e ra n dt h ed i s p l a y e dn u m b e r e x c e e d sh i sp a t i e n c el e v e l ，h ew i l ll e a v e ( b a l k ) w h e nt h ew a i t i n gt i m ee x c e e d sh i s p a t i e n c el e v e l ，h ea l s ol e a v e ( r e n e g e ) w ep r o p o s eam a r k o vc h a i nm o d e la n dg e ti t s s t a t i o n a r yd i s t r i b u t i o n ；a n dw ea l s og e ts o m ek e yp e r f o r m a n c em e a s u r e so ft h et i c k e t q u e u e a n o t h e ri st h et h et i c k e tq u e u ew i t hb a l k i n gc u s t o m e r sa n dt w os e r v e r s ，w e o f f e rag o o dw a yt os t u d yt h i sm o d e l k e yw o r d s ：t i c k e tq u e u e ；b a l k ；r e n e g e ；s u p e rs t a t e ；m a t r i x - g e o m e t r i cs o l u t i o n s 首都师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工 作所取得的成果除文中已经注明引用的内容外，本论文不含任何其他个人或集体 已经发表或撰写过的作品成果对本文的研究做出重要贡献的个人和集体，均已在 文中以明确方式标明本人完全意识到本声明的法律结果由本人承担 学位论文作者签名：椎城。莎 日期湃钿日 首都师范大学学位论文授权使用声明 本人完全了解首都师范大学有关保留、使用学位论文的规定，学校有权保留学 位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版有权将学位论 文用于非赢利目的的少量复制并允许论文进入学校图书馆被查阅有权将学位论文 的内容编入有关数据库进行检索有权将学位论文的标题和摘要汇编出版保密的 学位论文在解密后适用本规定 学位论文作者签名：胍j 携、，k 6厂。 日期口辉6 月j 日 引言 在我们的日常生活中，有时我们会碰到类似于这样的问题：当我们进入一个服 务系统( 例如一些大的银行) 时，由于等待服务的顾客太多，太拥挤，要维持排队的 秩序就显得特别的困难针对这样的情况，人们想出了一种好的方法来解决它那 就是抛弃原来的物理意义上的排队，而采用了一种新的排队方法一取号排队 所谓取号排队就是说当一个顾客到达一个服务系统时，他立刻得到一个号码 ( 号码是按照顾客来到的先后顺序排列的，并且是递增的；每一单位时间最多只来一 个顾客，每一个顾客都会得到一个号码) ，进入排队系统的顾客按照号码由小到大 的顺序进行服务( 即先到先服务) ，而正在被服务的顾客的号码在显示屏上显示( 若 系统中没有顾客，则显示屏上将显示下一个潜在顾客的号码，以便顾客一到达系统 就可以进行服务) 一 取号排队是用来解决4 不可视。排队的一种非常好的方法；所谓“不可视。，就 是说我们不知道在我们之前，到底有多少顾客在等待服务；不知道有多少顾客在等 待服务，那么我们就不能通过数排在我们之前的顾客到底有多少这种方法，来快速 估计我们所期望的等待时间了，因此，我们就想用取号排队来解决由于在取号排 队中，顾客只知道自己的号码和显示屏上显示的号码，所以，一个自然的也是可行 的想法就是：用顾客的号码和正在被服务的顾客的号码的差值来快速的估计顾客自 己的可能的等待时间，号码的差值越大，就暗示了自己的等待时间可能会越长在 许多情况下，当顾客看到号差过大时，他们可能会选择止步( 不进入排队) ；还有可 能是顾客选择进入了排队系统。但他在排队的过程中，也可能在被服务之前选择离 开( 中途退出) 在这篇文章中，我们首先所要研究的就是这种取号排队的性能及改 进；再者，对一些大的服务系统，由于顾客比较多，这就需要多个服务台同时工作， 以提高效率，只是我们所要研究的第二个问题 随着近几年商业化的发展，先进的取号排队技术，使得我们可以利用计算机来 处理顾客在整个服务系统中的到达流和相关的信息取号排队技术已经被广泛的应 2 引言 用于金融机构、政府机构、医疗组织和零售店许多的经济服务组织也展开了取号 排队技术来维持他们的顾客的服务流取号排队在现实中的原型，如在面包店、肉 店、配药师那里，我们为了维持服务的秩序，就采用了取号技术几乎所有的取号 排队，都有一个有趣的特征，那就是所取号码在被取出之前是隐藏的，只有当一个 顾客到达并把号取出后才能看到号码到底是多少对于这种设计，起初我们感觉 很迷惑，后来我们才明白这样做的好处，那就是这样做我们就可以得到顾客到达的 完整信息 l a r s o n ( 1 9 8 7 ) 和k a t ze ta 1 ( 1 9 9 1 ) 讨论了顾客的看法对排队的影响要大于等待 时间对排队的影响，如等待的环境，社会的公平等k a t ze ta 1 ( 1 9 9 1 ) 经由对一些 案例的研究得出论证：排队环境的改变，如在等候处安装一个新的显示板或一台电 视机，使得等待是积极的，增加顾客的满意度他们还提出如果顾客经历了社会的 不公平，尤其是先到先服务( f i f o ) 的排队系统被侵犯时，他们可能会变得很愤怒 在上述的两种看法中，取号排队为顾客提供了一个好的等待经历想比较于传统的 物理意义上的排队，取号排队把顾客从正是排队的不便和站在拥挤的队列中精神的 厌倦中解放了出来，给他们自由的空间来支配他们的等待时间，这样可以使得环境 比较整洁、宽松、舒适，特别是对那些在同一个场所有不同的排队的情况取号排 队还可以保护顾客的隐私以及减轻她们的不安全感，而这在一些系统如银行和医院 中是比较尖锐的问题最后，由于在取号排队中顾客所取的号码即代表他在队列中 的位置，这就避免了有顾客插队的情况。从而有利于提高顾客的平等性 尽管取号排队比起传统的物理意义上的排队来有许多的先进性，但是他也有缺 点，即它可能会降低服务性能在取票排队系统中，物理意义上的排队信息丢失， 具体来说就是，在取号排队中，我们仅仅能够知道顾客号码的差和正在服务的顾客 的号码，而不知道在他之前的顾客的具体的号码我们把这种号码的差成为号的位 置。以便和以前的排队位置相区分在一些取号排队的例子中，顾客是天真的，不 耐烦的( 象我们大多数人一样) ，认为号的位置就是自己的真实的排队位置，忽视了 也许有一些排在他们之前的顾客由于种种原因已经放弃了他们的排队这就可能使 引言 3 得他们依据号的位置多估计了他们的等待时间，若这个错误的估计超出它们的等待 忍耐极限的时候，他们就会选择放弃即使有一些比较聪明的顾客意识到了用号的 位置来估计排队是多估计的，但是要想获得快速的排队估计，对他们来说也是很困 难的事情这样所导致的结果就是取号排队比传统的物理意义上的排队有更高的止 步率，致使服务难以达到顾客的期望；还导致的一个结果就是不能充分的利用服务 空间，而这是服务系统所期望的 早在二十世纪六十年代，数学家们( c o x 和s m i t h ( 1 9 6 1 ) ，a n e k e r 和g a f a r - i a n ( 1 9 6 2 a b ) ，c o x 和m i l l e r ( 1 9 6 5 ) 以及r e y n o l d s ( 1 9 6 8 ) ) 就已经对带有止步和中途 退出的排队系统进行了很好的研究，特别是对止步和队长独立的情况做了大量的研 究；此后，一些数学家还对止步与等待时间独立的一系列排队模型做了研究，最早 是由b a r t e r ( 1 9 5 7 ) 研究的；七十年代，止步独立于等待和服务时间的情况也得到 l o r i 8 - t e g h e m ( 1 9 7 2 ) ，h o k s t a d ( 1 9 7 9 ) 等数学家的研究这些是对排队模型的研究，我 们所做的取号排队模型是建立在他们的基础之上的，但是我们的研究不同于他们， 我们的止步是基于号码的位置的，并且系统只提供给顾客有关真实排队的部分信息， 主要的分析模型的思想与w h i t t ( 1 9 9 9 ) 是一致的这方面的工作刚刚起步，主要的 结果和研究方法是由s u s a nh x u ，l o n gg a o 和j i h o n go u ( 2 0 0 7 ) 给出的，他们研究 的是带止步的取号排队，通过一个最简单的模型，给出了解决排队模型相关问题的 一种巧妙的方法，为以后研究排队系统提供了一种方法依据本文就是在他们的思 想指导下，进一步的研究了两类取号排队系统，带止步和中途退出的单服务台取号 排队系统和只带止步的两服务台取号排队系统；这两类排队系统都是有很好的实际 意义的，实际应用十分广泛，例如，一些以服务用户为主的营业厅，通常都采用取 号排队的办法，按照规模的不同设置服务台的个数通过对他们的研究，我们就可 以依次为基础，去研究更复杂的取号排队系统了。 本文，我们所讨论的取号排队系统中，顾客的物理意义上的排队是不可视的， 并且顾客的排队位置只能通过他所取号的位置来推测。在本文中我们对以下两类问 题进行了初步的讨论： ( 1 ) 对带有止步和中途退出的取号排队系统建立数学模型。讨论在只有部分信息 的基础上如何准确的预测取号排队的性能；并给出一个逼近性很好的近似模型( 一 个服务台的情况) ( 2 ) 对带有止步顾客的取号排队，在一个服务台的基础上，用一种比较好的方 法讨论两个服务台的情况 第一章带有止步和中途退出顾客的取号排队系统 第一章带有止步和中途退出顾客的取号排队系统 5 顾客到达服务系统时，得到一个号码，顾客将凭号码等待服务，号码按照递增的 顺序依次给出，先到的顾客得到的号码小于后到的顾客的号码，例如；若一个到达的 顾客的号码为n ，则下个到达的顾客的号码即为n + l ，以此类推；正在被服务的顾 客的号码显示在显示板上，当此顾客被服务完，并且系统中还有顾客在等待服务时， 系统将叫下个号( 下个也即排在等待队列第一个位置上的顾客开始被服务) ；当 此顾客被服务完，并且系统中没有顾客在等待服务时，显示屏将显示下个号这样 新的顾客到达后立即就可以进行服务这里，我们假设服务者知道到目前为止取到 的最后一个号码，并且我们还假设无论是在排队的顾客还是服务者，在一个顾客的 号被叫到之前，都不知道这个顾客是在排队还是已经拿着号离开了( 即不知道系统 中某一时刻的真实队长) 1 1几个名词的解释 i 取号排队：取号排队与以往我们学习的物理意义上的排队系统是有区别的， 当一个顾客到达排队系统时，他将得到一个表明他的到达顺序的号码( 一般为一个 自然数字) ，号码是按照递增的顺序排列的；例如，若个到达的顾客的号码为n ， 则下一个到达的顾客的号码即为n + l ，以此类推；正在被服务的顾客的号码显示在 显示板上；顾客只能看到显示板上显示的号码和自己的号码 2 传统的物理意义上的排队：一个顾客到达一个服务系统后，以一定的概率选 择进入排队系统，等待服务台的服务；他与取号排队的一个重要的区别是新到达的 顾客可以知道在他前面排队的准确数( 队长) 3 顾客的忍耐水平：顾客能够坚持的最大值 4 系统中真实的顾客数：除去止步的和中途退出的顾客以外的顾客数，即真正 在排队系统中等待服务的顾客数 6 第一章带有止步和中途退出顾客的取号排队系统 5 超状态：若一个新到达的顾客进入一个状态时，他一定止步，则称此状态为 超状态 6 号码的位置。顾客到达系统后，以自己的号码来判断自己在队列中的位置， 区别于传统的队长 1 2带有止步和中途退出的取号排队的模型 需要注明几个符号的意义 ( 1 ) d ：刚到达的顾客的号码和正在被服务的顾客的号码的差值( 号码位置) ； ( 2 ) k ：顾客的忍耐极限z 即当一个顾客到达排队系统时，如果他发现她所取 得的号码与显示屏上显示的号码的差值超过k 时，那么他就选择不进入排队系统 ( 即止步) ( 3 ) ：系统中真实的顾客数 当d k 时，顾客将一定选择不进入排队系统，即止步 取号排队不同于传统物理意义上的排队的重要一点就是顾客不知道他前面的队 长到底是多长，同样，服务者也不知道某一时刻的具体队长因为顾客只能知道他 的号码和正在被服务的顾客的号码( 显示板上显示的号码) 差值，而由于顾客可能 止步或中途退出，所以顾客知道的这个号差并不一定是系统中真实的顾客数为了 对类似于这种取号排队系统进行深入的了解，我们做了一些简单的工作由于取号 排队系统比传统的物理意义上的排队系统更繁杂，我们先从比较简单的情况入手， 讨论单服务台，带有止步和中途退出，服务空间有限的情况，具体假设如下： ( 1 ) 顾客以参数为a 的普阿松过程到达； ( 2 ) 服务者的叫号时间忽略不计； 1 ( 3 ) 对没有止步，也没有中途退出的顾客，他们的服务时间服从均值为二的指 p 数分布；对止步和中途退出的顾客的服务时间为0 ； ( 4 ) 每一个加入排队系统的顾客在被服务之前，都有一定长度的等待时间，若 第一章带有止步和中途退出顾客的取号排队系统 7 超过这个时间，顾客将离开，不再进行服务，我们设这个时间为一个随机变量，其密 度函数为： d ( t ) = 7 e 一哪，t 0 由于单单由系统中真实的顾客数n 和号码的位置d 或两者结合都包含不了取 号排队的所有信息所以，我们需要将状态空间细分，具体状态定义如下： 。 ( 1 ) 状态0 表示系统为空； ( 2 ) 向量z = ( n l ，扎2 ，n 工) 表示一个状态，其中m 表示从第1 个加入排 队系统的顾客开始算起，到第f + 1 个加入排队系统的顾客之前为止，这之间所取 的号码差值在这里，显然有m l ，z = 1 ，2 ，l ，因为啦中至少包括第z 个顾 客此外，向量z 的维数为l ，i l k ；l 表示此状态下，系统中真实的顾客 数，冬l 铆k 表示此状态下号的差值 需要注意的两点： ( 1 ) n l 中的第个顾客肯定正在被服务；一个新的顾客到达状态z 时，他的号 的位置要么是0 ( 系统中没有顾客在服务，系统为空) 。要么是丝。铆( 系统非空， 有顾客正在服务) ；并且当b l1 砌k 时，顾客止步( 因为顾客只看得到他的号码 和显示板上的号码，即这之间的号差，当号差大于系统空间的最大值时，顾客就认 为系统空间已满，所以顾客此时就选择离开，即止步) ( 2 ) 对状态z = ( n l ，n 2 ，n l ) ，我们有必要做进一步的理解：如果我们把一 个顾客加入排队系统记为1 ，止步记为0 ，若顾客中途退出，我们记为由1 变为0 的 话，那么系统的一个状态( 1 ，1 ，0 ，1 ，0 ，0 ，0 ，1 ，o ) 表示的意思即为第一，二，四，八位 顾客进入了排队系统，而第三，五，六，七，九位顾客止步或中途退出；此状态下， 系统中的此状态下中的真实顾客数为l = 4 ，号的差值d = 9 ；而用我们给出的状 态的表示法表示，此状态可记为( 1 ，2 ，4 ，2 ) 通过上面的分析，我们给出系统的状态空间： 妒= z = o ；z = ( n l ，n l ) ：乏奠：n l k ，n l 1 ，f = 1 ，l ，l = 1 ，k ) 8 第一章带有止步和中途退出顾客的取号排队系统 其中，e 等m k 是为了确保加入排队系统的顾客的号的差值小于排队空间 的最大值，也即在顾客的忍耐水平之内 记h = l 是向量z 的维数 i = 丝，m 给出状态空间以后，我们下面给出各状态之间的转移情况： ( 1 ) 0 _ 1 ，即由状态0 转移到状态1 ；表示系统由空到有一个顾客到达，转移 率为入； ( 2 ) z = ( n ) 一o 。即由状态( n ) 转移到状态0 ；表示有一个顾客被服务完，转 移率为p ； ( 3 ) z = ( n l ，他，n l ) 一，= ( n l ，n 2 ，n l ，1 ) ，即由状态z 转移到，；表示 冬1 埘k ，即真实进入系统一个顾客； ( 4 ) z = ( n l ，n 2 ，n l ) _ 一= ( n l ，耽，n l + 1 ) ，即由状态z 转移到一；表 示丝lm k ，即真实进入系统一个顾客； ( 5 ) z = ( n l ，n 2 ，n l ) _ ，= ( n 2 ，n 3 ，n 工) ，即由状态z 转移到一；表示 服务完一个顾客； ( 6 ) z = ( n l ，n i i ，n i ，n i + l ，礼l ) 一= ( n 1 ，n 一1 - - i - n i ，n + l ，n l ) ， 1 i l ，即由状态z 转移到一；表示真实进入排队系统的第i 个顾客以率，y 中途 退出， 下面以k = 4 为例，从图( 一) 和图( 二) 上直观的具体说明各状态之间的转 移情况；其中图( 一) 反映的是各个状态之间由于顾客到达或被服务完而发生的转 移，图( 二) 反映的是各个状态之间由于顾客中途退出而发生的转移 ( 1 ) 每一行按照真实排队队长逐渐递增的顺序排列；当队长相等时，按照字典 顺序排列即对任意两个状态z = ( n l ，他，n l ) 和状态一= ( 礼i ，礼：，n 2 ) ，若 n l = 吒，笛1 眦笛1 ，对任意的1 i l 1 成立时，有z 排在一之前； 当n l 4 这时， 状态由( 1 ，4 ) 转移到( 1 ，5 ) ； ( 5 ) 其他转移情况举例( 服务完和中途退出) 以状态( 2 ，3 ) 为例说明服务完的情况：当一个顾客服务完后，即状态( 2 ，3 ) 中 排在队首的顾客服务完，那么它后面的，下一个进入排队系统顾客之前的那些止步 的顾客的号随即消失，状态就转移到了状态( 3 ) ； 以状态( 1 ，1 ，3 ) 为例说明中途退出的情况：当第二个进入排队系统的顾客以概 第一章带有止步和中途退出顾客的取号排队系统 1 1 率咆= ，y 中途退出时，状态转移到( 2 ，3 ) ；当第三个进入排队系统的顾客以概率 r 3 = 2 ，y 中途退出时，状态转移到( 1 ，4 ) 1 3有关取号排队的马尔科夫链模型及其平稳状态分布 从我们学过的知识，我们知道，马尔科夫链要求所得到的关于平稳状态分布的 解是精确的，显式解用 p c x ) ，z 妒】来表示而对于我们现在所讨论的情况来看， 当系统空间比较小时，我们可以得到平稳状态分布的精确解；当系统空间比较大时， 则不容易下面举个简单的例子来说明当系统空间比较小时，我们可以得到平稳 状态分布的精确解： 令k = 2 ，此时，状态空间妒中的各个状态及其转移用图( 三) 表示如下t 图( 三) 1 2第一章 带有止步和中途退出顾客的取号排队至统 我们将状态空间砂进行重新划分，分成如下几块； t o = ( o ) ) 死= ( n ) ，( 1 ，n ) ) 其中n = 1 ，2 ，3 ， 那么转移率矩阵为 q = - aa o l a风 a0 a o 00 a 1 20 b c 0b a 。= c 入，。，a = ( ：) ，玩= ( 一i ：卜柚一阻：y + 刈 a - ：= ( _ ：) c = a n ，n + - = ( ：) 玩= ( 一i ：卜入) 一阻j j + 刈 第一章带有止步和中途退出顾客的取号排队系统 1 3 由上边的转移率矩阵，我们看出，对一个分块矩阵已，其中的状态只可能转移 到，r 或者死+ l 。并且可以看出关于死的马尔科夫链是一个g i m 1 1 型的 设关于瓦的平稳状态概率为r ，由于已是2 2 维的矩阵，所以r 也是 2 2 维的矩阵；故由平稳状态方程，我们得到平稳概率的表达式为。 p o a o l + p 1 b o = 0 p 1 a 1 24 - p 2 b = 0 r i c + r b = 0 ，仃3 将具体的数值代入上面的递推式，就可以得到想要的平稳状态概率了 。 对于一般的k ，我们做如下的讨论 按照礼l 的取值的不同，对状态空间矽进行组合，分成不相交的子集 咒) ，n o ， 瓦) 包含所有使得n l = n 的状态z ，其中n = 1 ，2 ，具体为t t o = k o = ( o ) ) 冗= z 1 多：礼工= 扎，l = 1 ，2 ，k ) ，佗= 1 ，2 ， 图中每一行仍按照真实排队队长逐渐递增的顺序排列；当队长相等时，按照字 典顺序排列即对任意两个状态z = ( n 1 ，砌，n l ) 和状态z ，= ( 硝，鸸，吒) ， 若亿工= n 2 ，笛1 啦三1 ，对任意的1 i l 一1 成立时，有z 排在一之 前；当r s l 几2 时，z 排在一之前；每一列按照号数量的增加排列 性质1 ：瓦的维数为 i 死i = 是l 硼l ：nm = 2 k - l , 扎1 证明；冗包含所有使得d , l = n 的状态z ；m 1 ，他，n l ) ，l = 1 ，2 ，k 即露= z 砂：r , l = n ，l = 1 ，2 ，k = z 妒：7 1 1 = n 或n 2 = n 或 、 n l 。n ， 当n l = n 时： 只有状态z = ( n ) 已，即在此情况下，只有1 个状态符合条件 当他= 礼时： 状态( 1 ，n ) ，( 2 ，n ) ，( 一1 ，n ) 符合条件，故共有一1 个 1 4 第一章带有止步和中途退出顾客的取号排队系统 如此进行下去 当n l = 霸时： 系统中共有l 个真实的顾客，其中l = 1 ，2 ， 此时，由于n l = n 为确定的值，而l - l - 1 1 砌 k 所以当礼工= n 时，状态z 中除排在队尾的顾客外，一共有l 一1 个顾客真实 进入了排队系统，而除了排在队尾的顾客外，前面最多有k 一1 个真实进入排队系 统的顾客，故此时有噤j 个状态符合条件，即属于霸 最后 当7 1 k = 几时： 由于笛1m 一1 ，由各个单个的状态的转移我们容易得出已，n k - 1 这个状态集的转移情况为足可转移到，或者转移到死+ 1 ，瓦+ 2 ，死+ x 一2 ， 或者在瓦中的各个状态之间转移 这时，相关部分的转移率矩阵q 2 为 o l 2 a 如 ； 矗 a a ； q 2 = a k 一2 a 一3a k 一4 a k 一1 ka k 一2a k 一3 a l a ka k 一1a k 一2 a 2 其中a 是一个下三角矩阵 a ka k 一1 a 3 a ka 4 a k 下面只考虑n k 时状态集露的矩阵形式的平稳概率的情况； n = k 时矩阵形势的平稳方程为 p l a l + 岛a 2 + + r i a k 一1 ，k p r a k = 0 此时有 既= 一( 尸l a l + p 2 a 2 + + 段一l a r l ，k ) a p 其中，r ，岛，p k 一1 已经由第一步得到了 当n k + 1 时，类似的，可以得到 r k + 1 a 1 + r r + 2 a 2 + + r a k = 0 此时有 r = 一( r 一+ 1 a l + r 一+ 2 a 2 + + r 一1 a t 1 ) a 下面以k = 4 为例详细的说明，此时，相关部分的q 为 l 2 a a ； 1 2 3 a a a ； 箍_ 章带有止步和中途退出顾客的取号排队系统 q = 此时，即由k = 4 得 一a 山l ga na 1 2cd ga 2 1a a 2 3c d ga 3 10 aa 3 cd g g abc ab a 瓦= ( n ) ，( 1 ，n ) ，( 2 ，n ) ，( 3 ，n ) ，( 1 ，1 ，n ) ，( 2 ，1 ，n ) ，( 1 ，2 ，扎) ，( 1 ，1 ，1 ，仃) ) a m = ( a ，0 ，0 ) 是8 维的行向量，a = ( p ，o ，o ) t 是8 维的列向量 a 1 22 00 00000 0 70 0 00 00 0 00 00000 0 00 0a0 0 0 0 0 ，y00 0 000 00 ，y0 0a00 0000 00 入0 0000 70 0a 1 7 第一章带有止步和中途退出顾客的取号排丛垂! 统 矩阵 c = 000 000 0 0 00 00 o0 0 0 10 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 000 00 00 0 0 000 0 0 ，y 00 0 0 0 0 00 0 0 o 0 0 0 d 是一个只有第四行第一列的元素为7 ，其余都是0 元素的矩阵 a n = go入0 00000 pg 10 0入000 p 0g 10o久00 p 00 g 10 00 0 0 p，y 0 g 20 0 a 0 p 0 2 7 0g 200 00 p，y 00g 20 0000 p，y2 7g 3 其中g t = 一( a + p + i 7 ) ，i = 0 ，1 ，2 ，3 如。是一个只有第一行第三列和第二行第七列的元素为a ，其余都是0 元素的 第一章带有止步和中途退出顾客的取号排队系统 以2 3 = 0 0 0 0000 0 7 0 0 00000 0 oaooo o 0 0 0 0入0 o 00 070 0 a 0 0 0 0010 0a0 0 0 0 000 0 a 0 000 0 ，y00 a a 3 z 是一个只有第一行第四列的元素为a ，其余都是0 元素的矩阵 a 3 4 = o o0 o o0o 0 7 a 000000 o0a0 0 0 0 0 0 0 0 a 0000 0 ，y0 0a0 00 0 0 7 00 入00 0 0o0 00ao 0 0 0 0 700 a 由矩阵我们看到，a 2 3 和a 3 4 只有对角线上一个元素不同，这由状态的转移可 以得到 第一章带有止步和中途退出顾客的取号雉丛墨统 a = g o pg l p 0 g l p 00g 1 0 p7 0g 2 0 p 0 2 7 0g 2 00 肛，y 00g 2 0000 p，y2 ，y g s b ：= ao 00o00 o 1a 0 0 0 0 0 0 0 0 a 0 0 0 0 0 0 0 o入0 0 o 0 0 1 0 0a0 0 0 0 010 0a0 0 00 o0 o0入0 000 0 7 0 0a 给出各个具体的矩阵之后，代入递推方程，就可以得出各个状态的平稳概率了 1 4系统的一些性能指标 给出平稳分布 p ( z ) ：z 诃以后，我们就可以得到我们所期望得到的系统的 一些性能指标，如 ( 1 ) 系统中真实的顾客数，即确切队长的分布 p ( = 0 ) = p ( o ) p ( n = l ) = 。k l 尸( z ) ，l = 1 ，2 ，k ( 2 ) 新到达的顾客拿到的号码与显示屏上显示的号码的差值d p ( d = 0 ) = p ( 0 ) p ( d = d ) = 啡惭p ( z ) ，d = 1 ，2 ， ( 3 ) 顾客的止步概率 p b = 1 一e 。：z u k p ( x ) ( 4 ) 在已知新到达的顾客拿到的号码与显示屏上显示的号码的差值d 时，可以估计 系统中真实顾客数的概率和均值 p ( n = l i d = d ) = 掣 p(xx：xekli l x l l = a )厶， e 。：i k i i ；a lp ( x ) 其中d = l ，l + 1 ， e n i d = 6 日= d l a ：k ol p ( n = l i d = 田 篙。耽删i ：al p ( x ) 2 磊万r ( 5 ) 在已知新到达的顾客拿到的号码与显示屏上显示的号码的差值d 后，顾客的平 均等待时间w 为 e w i d = d 】= 1 e n i 。= 司 2 2 第二章带有止步和中途退出顾客的取号排队模型的一种近似 第二章带有止步和中途退出顾客的取号排队模型的一种近似 从前面的性质1 ，我们知道了 i 死i = e l k ；1 e 蝴l ：n m = 2 k - i , 礼1 由于瓦的维数是指数增长的，所以当k 增大时，r 增长很快，并且我们得到 的形势比较繁，这样就给我们的计算带来很大的困难，所以我们试图找一种近似， 这种近似不但可以大大减少我们的计算量，而且还能很好的逼近真实的情况 我们的想法是 如果我们把真实进入排队系统的顾客和止步的顾客分开，分成独立的两组，排 成两队我们只要知道这两组中顾客的个数即可这样，状态的个数将大大减少，从 而我们实际计算时就会相对的容易一些下面我们就来考虑这种调整了的取号排队 调整了的取号排队包含两个相互独立的队列，一对为由真实进入排队系统的顾 客排成的队，一列为止步顾客排成的队；对于真实进入排队系统的顾客来说，他和 传统的物理意义上的排队没什么区别；我们仍然假设我们只知道新到达的顾客与显 示屏上显示的号码的差值，而不知道实际的队长，这样对止步顾客的讨论和前面系 统一致一个顾客到达后，他要么排在真实进入排队系统的顾客这一队的队尾，要 么就排在止步顾客的队尾；由于真实进入排队系统的顾客有很高的服务优先权，所 以我们可以认为真实进入排队系统的顾客一服务完，止步顾客的队列马上就变空 类似于真实的系统，我们可以对调整了的取号排队建立个马尔科夫链模型，并给 出平稳状态概率，具体讨论如下 对调整了的取号排队，他的状态我们可以由一个有序数对来表示，即用数对 ( l ，7 , ) 来表示一个状态，其中l 表示在此状态下，系统中真实的顾客数，n 表示此 时止步顾客的队长；故状态空间我们可以表示为 妒= ( ，n ) ：0 lsk ；几= 0 ，1 ，2 ，) 求平稳状态概率的步骤和前面类似，基本思想一样，所以我们在这里只做粗略的讨 第二章 带有止步和中途退出顾客的取号排队模型的一种近似 2 3 论 以k = 4 为例，图( 四) 给出了各个状态之间的转移情况 图( 四) 按照n 值的不同进行分块，用死表示有n 个止步顾客的集合，即有 t o = ( o ，0 ) u ( l ，0 ) ：l = 1 ，2 ，耳) ， 死= ( l ，佗) ：l = 1 ，2 ，k ) ，n = 1 ，2 ， 此时，i 死l = k 对中途退出的顾客，状态转移情况为z = ( l ，n ) _ = ( l 一1 ，n + 1 ) ，即对于 中途退出的顾客，我们的处理方法与在真实系统中的处理方法一样 结合图和状态之间的转移，我们容易得到，r 只可能转移到而，已+ 1 或者它本 身乃，所以转移率矩阵q 为 第二章带有止步和中途退出顾客盟墼号竖丛熊型笪二登i 呈型 q = a o oa o l aa 1 1a 1 2 a a z 2 a 2 3 a a a a a k 一2 ，k 一2 a k 一2 ，k 一1 b ab ab 其中a 是第一个元素为p ，其他权威0 的1 7 1 i l t o i 维的列矩阵；a 和b 都是 下三角距阵，具体为 b = a = 入 ，y a ya 一y a 一( a + 弘) p一( a + ，+ ，y ) p一( a + p + ，r ) p一( a + p + ，y ) 令只是瓦的概率向量，故可得 ( 1 ) 当1 礼k 一2 时，有 p o 1 + p l a l l = 0 p 1 a 1 2 + p 2 a 2 2 = 0 p k 一3 a k 一3 ，k 一2 + p k 一2 a k 一2 k 一2 = 0 整理得 瓦= _ on 留忍 l + l ，1 n k 一2 其中扁，l + 1 = - a z ，l + l ( a t + 1 ，l + 1 ) ( 2 ) 当礼k 一1 时，有 p k 一2 a k 一2 k 一1 + p k aa = 0 p 。一1 b + p m a = 0 ，m k 整理得 瓦= _ o 兀邕3 r ，l + 。卯凡 其中，尹= - a k 一2 耳一1 a 一1 凡= 一b a 一1 2 6 第三章带有止步顾客和两个服务台的取号排队模型 第三章带有止步顾客和两个服务台的取号排队模型 对于有两个服务台，并带有止步顾客的取号排队系统，我们做如下的讨论，在 这里，我们还是假设顾客是以参数为a 的泊松过程到达，进入排队系统的顾客的服 务时间是服从参数为p 的指数分布的，两个服务台的服务率是一样的，我们在这里 规定当系统为空时，下一个到来的顾客将到1 号服务台进行服务顾客到达时，如 果他发现他的号码和正在被服务的两个顾客中较大的号码的差值超过x 时，顾客 就止步 我们定义状态如下； ( 1 ) ( 0 ) 表示系统中没有顾客； 2 ) ( p ，0 ) 和( 0 ，9 ) 表示系统中有一个真实的顾客，其中( p ，0 ) 表示这个顾客在 1 号服务台服务，( 0 ，p ) 表示这个顾客在2 号服务台服务； ( 3 ) 向量z = ( s ，死l ，n 2 ，n 二) 表示系统中有l + 1 个真实的顾客( 包括正在 被服务的顾客) ；其中，s 表示在1 号服务台服务的顾客的号码小于在2 号服务台的 顾客的号码；l 仍然表示从第z 个真实进入排队系统的顾客算起，到第z + 1 个真 实进入排队系统的顾客之前的号码的差值； ( 4 ) 向量z = ( n l ，8 ，n 2 ，n l ) 表示系统中有l + 1 个真实的顾客( 包括正在 被服务的顾客) ；其中，8 表示在2 号服务台服务的顾客的号码小于在1 号服务台的 顾客的号码；f 仍然表示从第：个真实进入排队系统的顾客算起，到第z + 1 个真 实进入排队系统的顾客之前的号码的差值。 由此，我们就可以给出系统的状态空间 历= z = ( o ) ，( 口，o ) ，( 0 ，口) ，z = ( s ，1 1 , 1 ，t t 2 ，n l ) ，z = ( n l ，s ，n 2 ，n 工) 其中旨硼 k 一1 的那些状态( 如当k = 2 时，图( 五) 中阴影部分的状 态) 按照系统真实队长的不同进行组合，当系统中真实的顾客数为l ( 包括正在被 服务的顾客) 时，我们记此时的组合为既，即有 & = ( 口，o ) ，( 0 ，曰) 鼠= 【z 妒：l z l = 上，n l 一1 k ) ，l = 2 ，k s k + 1 = ( s ，e k 一1 ，n k ) ，( 1 ，s ，e k 一2 ，几k ) ：7 1 k k 其中e 工= ( 1 ，1 ，1 ) 是l 维的单位向量，h 表示向量z 的维数 ( e j f 一1 ，b k ) = ( 1 ，1 ，n k ) 第三章带有止步顾客和两个服务台的取号排队模型 2 9 此时，状态空间击就变成了一个有限的状态空间，我们用u 来表示，则有 u = z = ( o ) ，z = ( 8 ，n l ，礼2 ，n l ) ，z = ( n 1 ，s ，n 2 ，n l ) ： m k ；n l k l ；n f l ；f = 1 ，2 ，l ；l = 1 ，2 ，k ) u 岛， 下面我们在此基础上再把状态分块。方法为把系统中真实顾客数相等的放到一 组，即把u 分成有限的不相交的子集k l ，l = 0 ，1 ，k + l ，具体为 g o = ( 0 ) k 1 = 研= ( 0 ，0 ) ，( 0 ，日) n l = h = l ，n l l u ，l = 2 ，3 ，k + 1 以k = 4 为例来具体的说明，其中状态的排列顺序类同于带止步和中途退出顾 客的排列顺序( 即类同于图( 五) ) 那么