（概率论与数理统计专业论文）一类具有随机限制条件的排队模型.pdf

摘要 摘要 本文主要考虑了一类具有随机限制条件的排队模型在引言中给出了本文论 题的历史概述以及论文的内容提要，然后开始论述主要部分 论文的第一部分，主要研究了具有有限容量的点斯z 帆9 ( n ) g l 排队模型与具 有可利用的服务员的州g i 模型在第二章中，应用无穷小方法和定义了两个辅 助停时，获得了两个积分微分方程，计算出忙期的拉普拉斯变换在第三章中，当 工作量超过时，外来的服务员加入系统工作，一直到工作量小于等于七应用 l e v e l c r o s s i n g 方法，计算了工作量的平稳分布以及应用k o l m o g o r 叫向后微分 方程方法，获得了忙期的拉普拉斯变换 论文的第二部分，考虑了两个二阶的流体排队模型，意味着流量不仅由输入和 输出表示，而且还受到一个波动因子和布朗运动的影响第一个模型分析了流量 过程的暂态性质以及首中时第二个模型的输入是一个从属过程，而输出是线性 的且速率受一个具有有限状态的马氏链控制，主要应用无穷小算子和鞅方法，研 究了其平稳分布及暂态性质 论文的第三部分，研究了具有定时装置与随机时间闸门装置的轮循模型假定 p o i s s o n 到达，具有一般的服务时间分布和转移时间分布获得了在到达时刻队长 的概率母函数，平均循环长度及工作量的拉普拉斯变换 关键词：忙期；首中时；马氏调节的流体模型；轮循模型 学科分类号：0 2 1 2 i i i a b s t r a c t a b s t r a c t i nt h i sd i 8 r t a t i o n ，w es 七u d yq u e u e i n gm o d e l sw i t hr 甜l d o m l yr e s t r i c t e d r e 酉i n e t h eb r i e fr e v i e w 昌o ft h eh i s t o r yo nt h ec o n c e m e dt o p i c s 硝w e ua st h e o u t l i n eo ft h e 出s s e r t a t i o na r e 西v e ni nt h ei n l ；r o d u c t i o n a 此e rt h a tt h em a i nb o d y o ft h ed i s s e r t a t i o ns t 锄吒s i nt h e 丘飙p 吼，w ef o c l l so n8 t u 蛳n ge r f o 聊( n ) g 1q u e u ew i t h 丘n j t e c o n t e n ta n d 圳g lq u e u e 谢t ha 1 1a m 缸l a b l e8 e r v e r i nc h 印t e rt w qa p p l y i n gt h e i n f l n i t e s i m a lm e t h o d ，w ed e r i v et w oi n t e f o - d i 髓r e n t me q u a t i o 璐，a n db yw h i c h t h el 印l a c i a nf u l l c t i o n a lo ft h eb u s yp e r i o di si d e n t i f i e d i 出a p t e rt h r e e ，w h e n t h ew o r o a de x c e e d s 七a na 张i l a b l es e r v e ra t t e n d sa n dw o r k sw i t hi n i t i a ls 帆r l i n t n t h ew o r 埘o a d i s l e s s t h a no re q u a l t o 忌，i h ea 俐l 可b l e 鲥唧sr a t ed e p e n d s o nt h ew o r k l o a dp r 髑e n t a p p l y i n gt h el e v 4 c r o s s i n g 盯g 啪e n t ，w es h o wt h e s 七e a d y - 8 t a t ed i s t r i b u t i o no ft h ew o r l 【1 0 a d a 1 s o 璐i n g 七h ek o l m o g o r o v sb a c k w a r d d i 脑e n t i a le q u a t i o n ，w eo o n s t r u c tr e n e w a le q u a t i o 璐t og e tt h el a p l a c et r a n s f o r m o ft h eb l l s yp e r i o d i nt h es e c o n dp a r t ，w ec o n s i d e r 却os e c o n d 一0 r d e r 丑1 l i dq u e u 船w h i c hm e a n t h a tt h e 丑i l i d1 e v e li sn o to l yr e p r e s e n t e db yt h ei n c o m i n g 丑1 l i da n d8 e 】n ，i c er a t e ， b u ta l s ob ya 、，a r i a b m t yf a c t o ra n dab r o w n i a nm o t i o n f b rt h e 丘r s tm o d e l ，w e d i s c l l 8 st r a n s i e n te x p e c t a t i o no fl e v e lp r o c e 鹋a n ds t u d yt h el 印1 a c et r a n s f o 衄 a n dt h em e a no ft h eh i t t i n gt i m eo fs o m ep o s i t i v el e v e l 百v e nt h a tt h ep r o c e 韶 s t a r t s 靠o ms o m e 西v e np 0 8 i t i v el e v e lt h es e c o n dm o d e lh a ss u b o r d i n a t o ri n p u t a n dm 缸k o v m o d l l l a t e dh n e a rr e l e a s er a t e - a p p l y i n gi 埘嘶t e s i m a lg e n e r a t o r ，w e o b t 斫nt h es t a t i o n a r yd i s t r i b u t i o nt h a ts a t i s f i e 8a ni n t e g r o - d i 髓r e n t i a le q u a t i o n a n dw es t u d yt h et r a n s i e n tl e v e l sc o n v e r g e n c ei nd i s t r i b u t i o n i n t h e t h i r d p 疵，w ec o n s i d e ra 钿o q u e u e p o m n gm 1 ) d e l 祈t ha t i m e ra n da r a n d o m l v - t i m e dg a t e dm e c h 8 n i s m a s s m et h a tp o i s s o n 盯r i v a l s ，g e n e r a ls e r - v i c ea 丑ds w i tc ：h o v e rt i i l l ed i s t r i b u t i o n 8 ，eo b t 咖p r o b a b i h t yg e n e r a t i n gf i l n c t i o n 0 ft h eq u e u el e n 戥h sa tp o l l i n gi n s 七a n t ，t h em e a nc y c l el e n 酗ha n dt h el a p l a c e t r a 血s f b r mo ft h ew o r k 【o a d i a b 8 t r a c t k e yw b r d s 锄dp l l r a s e s ：b 1 1 s yp e r i o d ；丑r s t1 l i t t i n gt i m e ；m a r k a v - m o d u l a t e d f l u i dq u e u e ；p o m n gm o d e l a m s2 0 0 0s u b j e c tc l a s s i f i c a t i o n s ：6 0 k 2 5 i i 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：夕簪譬税 忉扫6 年j 月订日 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解，密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：带犯 矿6 年r 月订日 引言 引言 经典的随机服务系统理论( 也称排队论) 源于e r l 眦g 关于电话服务的研究 在第二次世界大战中为了对飞机场跑道的容量进行估算，它得到了进一步的发展， 成为随机运筹学与应用概率论中最有活力的研究课题，其相应的学科更新论、可 靠性理论等也都发展起来 排队现象是一个随机现象，因此在研究排队现象的时候，主要采用的是研究 随机现象的概率论作为主要工具此外，还有微分和微分方程排队论把它所要研 究的对象形象的描述为顾客来到服务台前要求接待如果服务台已被其它顾客占 用，那么就要排队另一方面，服务台也时而空闲时而忙碌这就需要通过数学方 法求得顾客的等待时间、排队长度等的概率分布排队论在日常生活中的应用是 相当广泛的，比如水库水量的调节、生产流水线的安排、铁路分成场的调度，电网 的设计等等 在传统的排队论中，基本的模型假设为州b 叫m s ，这里a 与b 分别表 示到达时间间隔分布与服务时间分布，n 表示服务员的个数，m 表示系统最多能 容纳的顾客数，s 则表示系统的服务原理在实际的应用中，研究者已经扩充了基 本模型，比如各种类型的反馈模型，多种类型的顾客模型，有优先权模型，服务员 休假模型，循环服务的模型，与状态有关的到达速率的模型，具有不耐烦顾客的模 型，成批到达，成批服务模型等等在所有的这些模型当中，顾客进入系统接受某 种类型的服务，反映出模拟现象的离散特征近二十年以来，研究者也考虑了连续 的模型，通常指流体排队下面分别从三个方面来介绍我们的工作 m g 1 排队模型 。 在标准的m g 1 排队模型中，假定有一个服务员，具有无限的容量顾客到 达是参数为a 的p 0 8 8 i o n 过程，即到达时间间隔服从均值为l 似的相互独立的指 数分布服务时间是服从一般分布的的独立同分布的随机变量这个模型也可以 被当作连续时间存储模型，最初是由m o r 蛆，g a n i 以及其他学者介绍的他们所 考虑的模型，输入是个“、r y 过程，当系统不空时，以单位速率连续输出虽然这 个模型比较简单，但是基于他的概念和方法适用于多种应用，比如风险理论，先来 先服务的排队模型，以及具有优先权的排队模型等下面我们介绍关于驯g 1 的 一些扩展模型 引言 对于典型的m g l 排队模型的两个重要的推广是多重休假模型和单重休假 模型，在文献中已经被广泛研究( 见m v y 和i 幽f 1 0 6 】，t a b 萄f 1 4 1 】) 多重 休假协议是当服务员从一次休假返回系统时，发现系统空，他立即离开，开始一次 新的休假；而单重休假模型，如果服务员一次休假后发现系统为空，他开始等待直 到有顾客到达，开始个新的忙期这两个协议表示了两种极端的情形：多重休假 模型中，系统空时服务员不会等待，在单重休假模型中服务员一次休假后发现系 统为空，一直等到有顾客到达然而在各种实际情形当中，服务员一次休假后发 现系统空时，可能会等待一段时间，希望在这段时间内有顾客到达，这段时间称 作t i m e r 如果在t i i n e r 期满时还没有顾客到达，服务员立刻开始一次新的休假 b 彻a ，s c h i e g d 和砌a hf 2 4 】分析了这类服务员休假的驯g l 排队模型，服 务员休假回来后发现系统为空，立即启动一个t i m e r 他们取得了一些基本变量 的分布性质，以及表明这是一个一般化的模型 清除模型主要是用来研究累积存货系统的容量，见【8 l 】，【1 3 6 】与【1 3 7 】；对于 j a c k s o n 网络的清除模型，见【1 3 3 】在排队模型的研究中，近来有工作转移的系统 受到广泛的关注，见1 2 7 】， 6 3 】，f 6 9 】及f 7 6 】这些论文主要考虑的是部分清除引起 ，全部清除的原因可能为：在剩余工作损失或者由另一系统接管时的定期关闭，不 e 依赖于系统发展的灾难事件的发生，达到某一水平时的系统检查，或者是由这些 因素的各种组合在【2 3 j 中，b o 蛐a a ，p e r 叮和s 乇a d j e 系统地介绍了以上几种的情 形他们考虑的清除模型是随机时间发生的，引起系统剩余工作量的瞬时全部清 除这种清除后，假定系统可以立即恢复工作他们考虑了固定时间的清除，随机 时间的清除，以及工作量达到某一水平时的清除取得了对于这些清除时间工作 量过程的平稳分布 有限的大坝模型也称作具有一致有界的实际等待时间的驯6 r l 排队模型， 见【4 】与f 1 2 3 】水的输入根据p o i s s o n 过程，输入量为独立同分布的随机变量，服 从一般的分布然而，在每次输入时，大坝中水的容量都要受到限制只要容量超 过一定范围k ，大坝就会发生溢出，水量会立即变为k 在排队系统中，也可以解 释为具有不耐烦的顾客，他们的等待时间一旦超过k ，就会离开系统 至于各种排队模型的忙期已经得到广泛的研究，一些研究工作见a 锄u s 8 e n 4 】然而，大多数应用的是复分析的方法h e y m a n 【7 3 】给出了 g 1 排队模型 的忙期的近似值后来r d s e d 盯锄t z 【1 3 0 】应用鞅方法，获得了驯g 1 排队忙期 的拉普拉斯变换同时，k o r 0 1 y 1 1 1 【g 嘲应用位势方法研究了首中时以及 g 1 排队的实际等待时间的极大值p h a t a f o d 【1 2 0 】应用w 瑚等式，得出有限容量的 v 引言 大坝模型忙期拉普拉斯变换的近似解d ek 0 k 和t i j m 8 【4 5 】研究了具有不耐烦 顾客的圳g 1 模型忙期的期望近来，k i n a t e d e r 和l e e 【9 4 】考虑了具有指数 输入的有限容量的忙期，获得了关于忙期的期望值，以及利用鞅的可选停时定理 和k o l m 塘0 r 吖向后微分方程，得出忙期的拉普拉斯变换的精确解后来，在【9 2 1 中k i m 研究了类似的问题，计算了有损失的州( v 1 模型的忙期的拉普拉斯变换 d u b ef 5 0 】则应用l 6 v y 过程的首中时理论，取得了有限容量的叫g l 排队的忙 期的分布 在第二章中，我们在这些工作的基础上，把p o i 8 s o n 到达推广到e r l a n g ( n ) 到 达到达时间间隔为均值为n n 的e r l a n g 分布，服务时间服从一般分布这里到 达装置可以看作是由n 个相互独立的指数阶段构成的一个到达的顾客必须通过 ，1 个相继独立的阶段，只有当他全部通过时，才会被系统接收；当他处于某一阶段 时，后面的顾客不会被系统接收，必须排队等待直到前面的顾客完成所有的步骤 进入系统我们应用g e r b e r 和s h i u 【6 4 】中的无穷小方法，通过定义两个辅助停 时，取得了两个积分微分方程，从而获得了忙期的拉普拉斯变换特别地，当n = 2 时，我们建立一个更新方程，给出这个模型的忙期的拉普拉斯变换的明确表达式 上面我们介绍的清除模型和有限容量的 g 1 排队模型都是损失模型但 是在现实中，当工作量超过七时，我们并不希望系统有损失，而是可以通过增加 服务员的方法提高服务的速率这种情形尤其出现在以人为服务员的系统中我 们可以使用外来可利用的资源来增强服务的性能这使得我们考虑了具有可利用 服务员的州g l 排队模型，外来的服务员的服务速率可以依赖于系统的工作量 我们可以通过控制服务的速率来优化系统的性能事实上，这种服务速率依赖于 工作量的模型已经有所研究，见灿耻跚n 【4 】，c o h e n 【4 2 】，g a v e r 和m i u e r 【6 1 1 ， h 盯r i s o n 和舭s n i c k 【7 q 等 在第三章中，我们考虑具有可利用的服务员的 g 1 排队模型最初的服务 员以单位速率服务当工作量超过后时，可利用的服务员开始提供服务直到工作 量小于等于七为止他的服务速率依赖于当前的工作量我们分析了工作量过程 以及系统的忙期，最后获得了工作量过程的平稳分布及忙期的拉普拉斯变换 流体排队模型 流体排队模型近来由于它在通信网络方面的应用而倍受欢迎网络传输的数 据是以很多小的信息包的形式打包的，所以很自然的模拟成流体模型然而这种模 型已经有相当长的历史在早期的文献中，常常称为大坝模型或者随机存储模型， 引言 见m 0 r a n ( 1 9 5 9 ) 和p r a b h u ( 1 9 9 8 ) 除了排队论外，还有存货与风险模型 在一个流体排队模型中，一个可分得商品( 流体) 到达一个缓冲器被储存，然 后逐渐释放我们考虑一个开放模型，即流体从外部到达，描述缓冲器任意时刻的 的容量相比较而言，顾客到达服务台，可能需要等待，接受服务然后离开这种模 型需要计算系统的顾客数与顾客的等待时间流体排队模型可以甩来表示一般排 队模型中的未完成工作量在顾客到达时，输入是由顾客的服务需求构成的当提 供服务时未完成的工作量以单位速率递减 有关首中时的问题在风险理论及排队论中是非常重要的，所有跳为正的l 6 v y 过程的首中时已有很好的结论，见d ev y l d e r 和g o o v r t 8 【4 6 】，m i y a 啪，【1 l o 】， p i c a r d 和l e v e v r e 【1 2 1 】等此外，在文献【7 0 】中，h a ”i s o n 和 t e s n i c k 计算了具有 指数跳的大坝模型的首中时k e u a 和s t a d j e 【8 4 】也考虑了具有线性输出及带指 数跳的复合p 0 i s s o n 模型的首中时 关于扩散模型，见【1 1 8 】与【1 2 7 】特别地，在【1 1 8 1 中，p e r r y 和s t a d j e 考虑了 一个带正负跳的复合p o i s s o n 过程与一个布朗运动叠加的反射模型这个模型可 以解释为有不同顾客流的存储模型的容量过程即频繁存取的小的顾客流被模拟 成布朗运动；大的交易出现在大公司，进出的资金较多，可以被复合p o i 8 s o n 过程 模拟他们计算了忙循环的分布以及在一个循环中最大容量的分布 i在第四章中，我们研究了有无限容量的流体排队模型，带扰动且线性服务率 这种扰动由布朗运动和一个方差函数模拟这种流体排队模型的状态可以描述为 个随机微分方程扩散项可以表示输入的不确定性，当然也可以理解为输出的不 确定性我们应用鞅方法研究了过程的暂态期望通过建立一个二阶微分方程，获 得了容量过程首中时的拉普拉斯变换通过变换，我们得到一个合流超几何函数 以及它的两个积分型解经分析我们可以选择适当的函数来获得给定初始位置z 时，首中口时的拉普拉斯变换 另一类感兴趣的流体排队模型是马氏调节的流体模型，一个二维马氏过程 五，五 ，这里五表示容量过程，背景过程五是一个马尔科夫过程，它甩来控 制容量的递增或者递减，见文献【3 】近来一个重要的推广是反馈流体排队【1 】，不 仅容量过程受到背景过程的限制，而且背景过程也会受容量过程的影响反馈流 体模型的分析见f l o l l 与f 1 0 8 】 k e a 和s t 锄e 【8 7 】考虑了由有限状态马氏链五调节的，且输入过程与状态 有关的流体模型他们取得了 五，肼的平稳分布及拉普拉斯变换，研究了五的 首中时流体模型的文献主要关注于平稳状态，比如在马氏链调节的线性递增或递 i 引言 减的例子中b o m a 和p e r r y 也给出了这个问题的历史背景的详细论述e 1 w a l i d 和m i t r a 【5 6 】考虑了个逐段为常数的系统，刻画了这个过程的平稳分布对于相 应的带纯跳的输入以及一般释放率的非调节的存储过程见h a r r i o n 和r 舶n i c k 【7 0 】，b r o d 【w e l l ，r e 缸山血和t w e e d i e 【3 0 】 b 锄a ，k e u a 和p e r r y 【1 9 】考虑了一个有中断的流体系统，在关期容量逐段 线性递增，在开期以一个与状态有关的速率减少关期的长度服从指数分布说明 了这个系统平稳分布满足分解性质，可以分解为大坝过程和清除过程对于常数 和线性输出的的例子，容量平稳状态的拉普拉斯变换和矩可以被计算在【1 8 】中， b 蚴a 考虑了一个开关的存储模型当处于开期时，容量以一个与状态有关的 速率增加，且系统以一个与状态有关的速率转移到关期当处于关期时容量以一 个与状态有关的速率减少，且系统也可以以个与状态有关的速率转移到开期这 个过程是逐段决定的马尔科夫过程的特例他们确定了平稳分布以及存在唯一的 条件 在【1 0 3 】中，k u i k 吲血介绍了一个二阶流体排队模型 五，五 ，它的输入和输 出的速率不仅依赖于流量，而且依赖于一个环境过程厶，一个具有有限状态的连 续时间马氏链 五 满足 d 咒= a ( 五，五) d t r ( 五，五) 巩+ 盯( 五，五) d b t + 扎t 这里厶是个非减过程。阻止咒为负对这类模型的输入和输出速率的假设 已经有广泛的研究，主要集中于线性模型，即t 时刻的服务速率是r 伍) 五，见 a 8 n m s s e n 和k e n a 【5 】，k e u a 和w k t t 【9 0 】，k e u a 和s t a d j e 【8 5 】等在【8 5 】中，作 者确定了一个平稳状态的拉普拉斯变换所满足的函数方程这类方程虽然不易解 出。但可以计算出它的一二阶矩a 锄u 8 s e n 【5 】考虑了从属过程输入以及马氏调 节的线性输出率，且盯= 0 ， m 山e h 够a i n a 和s e r i c o l a 【1 2 5 】考虑了一个受连续时间马氏链控制以及线性 服务速率的流体排队模型这种流体排队模型的状态由一个线性微分方程描述 他们研究了流体排队模型的暂态分布，获得了一个流量分布所满足的偏微分方 程应用这个偏微分方程，获得了一个暂态分布的矩以及拉普拉斯变换在【1 2 6 】 中，r a b e h 觞a i n a 和s e r i c o l a 考虑了一个无限容量的受马氏链控制的二阶流体排 队模型流量的波动性由一个布朗运动和一个方差函数模拟这个流体模型的状 态可以描述为一个线性的随机微分方程在这个模型中他们给出了容量依分布收 敛，获得了流量的平稳分布对一阶模型。给出了各阶矩的表达式以及拉普拉斯 i i 引言 变换对于二阶模型，计算了一，二阶矩 在第五章中，我们进一步考虑了一个马氏调节的二阶模型t 时刻的流量由 咒表示流体到达是根据不带飘移的从属过程五，输出的速率是r ( 厶) 咒，则五 满足下面的随机微分方程 d 五= d 以一r ( 五) 五d t + 仃m ) 五d b 这里d 厶消失，因为五不可能为负应用无穷小算子，我们获得它的平稳分布满 足一个积分微分方程通过求解随机微分方程研究了状态依分布的收敛性当随机 微分方程的系数为常数时，取得了系统的暂态性质 轮循模型 循环服务系统是有多列排队的系统，一个服务员根据某种顺序为等待的顾客 提供服务，从个队列转移到另一个循环模型广泛的应用于计算机通信，生产制 造，机器人技术以及维修系统中由于应用广泛，循环模型早在十九世纪六十年代 就受到广泛注意( 见【1 4 3 】) 我们考虑典型的循环服务模型t 它的每个队列都有不同的p o i s s o n 到达流， 服务时间分布及转移时间分布传统的零转移时间和非零转移时间的模型已经分 别被研究零转移时间的模型是一个基本的模型非零转移时间模型的等待时间 可以分解为两项，一项是转移时间，另一项是相应于零转移时间模型的等待时间 这推广了近来的常数转移时间模型的结果这些研究减少了计算，提高了循环服 务模型在理论方面的应用 在许多应用中，在每次服务员服务期间，对服务时间有许多种限制一般的服 务原理有空竭服务，闸门服务，全局闸门服务以及1 l i m i t e d 服务在空竭服务装 置下，服务员每次加入到一队列服务直到该队为空，才允许离开到另一个排队闸 门装置要求在服务员为一个队列服务时，只服务他到达时已存在的顾客，而在他 服务时所到达的顾客下一次再服务1 一l i m i t e d 服务装置，则是服务员每次至多服 务一个顾客对于这些模型的理论和应用见，i 址a 百【1 4 0 】与础a l i 【1 4 5 】至于全 局闸门装置被b o 咖嗯，l 6 、，y 和y e d 虹a l i 【2 2 】介绍。b 咄a ，w j s t s t r a t e 和y e ! c h i a l i 【2 6 】进一步推广在这种全局闸门服务装置下，选取一个时刻作为一次循环的开 始，在每个循环中，服务员访问每个队列时只服务在一次循环开始时已经存在的 顾客 我们简要的概述一下相关的文献对循环服务模型广泛的调查可以查看7 r 址 引言 a g i 【1 4 0 ，1 4 3 】与y e c h j a l i 【1 4 5 】在各种假设装置下，两个排队的轮流服务系统被许 多学者研究a 订i t z h a k ，m a x w e u 和m m e r 【8 】首先研究了零转移时间，每个队列 都是空竭服务的模型取得了平均对长和期望等待时间，还计算了忙期的一、二阶 矩t a b c s 【1 3 8 】研究了相同的模型，获得了一些基本指标的拉普拉斯变换和概率 母函数n e u t 8 和y 砒i n 【1 1 5 】进一步分析了系统的暂态性质e i 8 e n b e r g 【5 1 】研究 了服务原理是1 l i m i t e d 的循环服务系统这个模型也被b o 妯a 和g r o e n e n d i j k 【1 7 1 所研究，获得了在服务员到达时刻队长的平稳分布，等待时间分布以及服务 员的循环服务时间分布 g r o e n e n d i j l 【6 5 1 和i b e 【7 5 】详细论述了一列排队是空竭服务，另一列是1 一 l i i n i t e d 服务的循环服务模型两队列都是1 一l i m i t e d 循环服务模型要比两队列 都是空竭服务的模型或者一列是空竭服务一列是l l i m i t e d 的模型难度要大些 b o x m a 和g r o e n e n d i j k 【1 7 】就这个模型经一个变换考察了一个边界值问题，这个 模型也可以推广为多列排队的模型k a t a r 鲫嗡和撇嬲l l i 【7 9 】分析了个两 队列模型。一队列遵循1 l i m i t e a 服务原理，另一列服从b e m o m 服务原理，即 服务员继续服务下一个顾客的的概率是p 而转移到另一列排队的概率是l p 获得了队长的概率母函数以及等待时间分布的拉普拉变换f e n g 5 8 】研究了两队 都是b e m o u l l i 服务原理的模型在这个模型中，获得了平稳队长的联合概率母函 数，以及等待时间的拉普拉斯变换和期望值 某些优先权也可以通过使用端口来执行端口服务原理，口1 被空竭服务，而 q 2 被服务直到工作全部完成，或者直到主队队长达到某一给定的长度，见l 【1 0 4 】，b o m a ，k 0 0 l e 和m i t r a n i 【2 0 】，b 咖和d o w n 【1 6 】在【2 0 】中，服务时间 服从指数分布，当q 1 的队长达到一定长度时，q 2 的服务被有优先权顾客中断 而在【2 l 】中，当q l 的队长达到一定长度时，q 2 的服务被有非优先权顾客中断 f 1 6 】把【2 1 】中的分析推广到服务时间为般分布的情形，而且分别考虑了零转移 时间与非零转移时间的情况，取得了顾客离开时对长的联合分布队长的平稳状 态以及逗留时间分布的表达式l e ei l o 卅处理了一个类似的模型，给出重交通的 分析 关于( 2 ) 个排队的循环服务模型，t a k a 舀得到了进一步的发展，在【1 4 0 】 论述了这类模型y e d 缸a d j 【1 4 5 】讨论了【1 4 羽中的模型，循环服务的最优控制是一 个只有部分解的问题两队列的循环服务模型被h o 缸和i k 螨 7 4 】研究b r a w n e 和y j d l i a l i 【3 1 1 研究了( 2 ) 条队列，具有一般的服务时间和转移时间的模型 对于闸门装置和空竭服务装置，他们系统的阐述动力控制问题作为一个半马尔科 x 引言 夫决定过程，取得了n 维系统的b e u m a n 优化方程然而，方程组的解似乎是不 可行的不过一种新的方法可以得到易于求解的一个半动力优化控制程序各种 循环服务系统的优化控制和静态控制策略见文献【1 4 5 】 在 2 4 1 ，b o x m a 分析了服务员休假的m g 1 排队模型在这个模型中，一 次休假后发现系统为空，服务员启动一个t i m e r 如果在t i m e r 期满前有一个到 达，则忙期立刻开始如果t i m e r 比到达时间间隔短，服务员不再等待，开始一次 新的休假这种等和看的策略对于人的行为是常见的，适用于许多情形( 如公路交 通的十字路口，能够处理几种工作的机器等) 这种等和看的策略见p e k i j z 【1 1 7 】， 这里服务员为一个排队提供服务，在这条对列变空后，服务员要在这里等待一个 固定的时问后来，b a ，s c l l l e g e l 和y 础a l i 【2 5 】把【2 4 】中的分析推广到两队 列的循环服务模型中在这个模型中，服务员在q l 执行这种策略考虑了三种构 造：( i ) q l 实行1 一l i m i t e d 协议，q 2 是空竭服务的；( i i ) q 1 是空竭服务的，q 2 服从 l l i m i t e d 服务原理；( i i i ) 这两个排队都是空竭服务的他们分别考虑了零和非零 转移时间，非零转移时间服从一般分布，获得了在服务员到达时刻队长分布，等待 时间分布以及系统中总的工作量的分布 近来e h a z a r 和y e d l i a d i 【5 4 】介绍了一种随机时间闸门装置，它设置在单信道 的肘g l 排队的间断区间( 间断区间是个随机时间，通常与系统有关，服务员 不工作的时间) 把这种随机时间闸门装置应用到循环服务模型，可以产生如下的 程序：当服务员进入一个站点时，启动一个指数时间的t i m 盯如果在t i 嗍期 满前，服务员清空了这个站点，他则转移到下一个站点；否则，服务员遵循下面的 规则之一，每条规则会导致一个不同的模型： ( 1 ) 服务员完成t i i n e r 内所有的工作，然后离开到下一个站点 ( 2 ) 服务员只完成当前工作，然后离开 ( 3 ) 服务员立即停止工作，然后离开 随机时间闸门装置定义了一类型的时间控制装置，对于典型的闸门装置，空竭 服务装置，还有1 一l i m i t e d 装置都是其特殊的类型 在【5 3 】中，e n 船盯和砌a h 进一步研究了多服务器问题，把该问题分析为 具有随机时间闸门装置的循环服务模型主队是空竭服务的，而服务员在次队服务 的时间要由q 1 的发展情况决定他们获得了许多性能指标，可以由在到达q 2 时 刻信息数的概率母函数表示，获得了这些指标的近似值 在论文的第六章中，我们把【5 4 】的分析推广到具有耐心的服务员的循环服务 模型中，这将丰富了两队列的循环服务模型我们考虑一个服务员参加两个排队， f l 言 记作q l 和q 2 ，在它们之间轮流进行服务，而且还装备了定时与随机时间闸门机 制通过这两个装置q 1 享有某种优先权，具体操作如下在q l ，设置一个定时机 制t ( 1 ) ：当服务员到达q 1 时，发现为空时 启动个定时机制定时机制期满时， 如果有顾客到达，忙期开始且按照q l 空竭服务原理服务；然而如果无顾客到达， 服务员不再等待，转移到q 2 在q 2 ，设置一个随机时间机制：无论服务员何时到 达q 2 ，指数时间t ( 2 ) 启动t ( 2 ) 期满时，如果服务完所有顾客，服务员立即离开； 否则服务员只完成t ( 2 ) 内到达的工作然后离开假定p o i 8 8 0 n 到达，一般的服务 时间和转移时间分布获得了在到达时刻队长的概率母函数，平均循环长度及工 作量的拉普拉斯变换 。 c l l a p t 凹1 h t o d u 吲帅 c h a p t e r1 i n t o d u c t i o n t h ed a 鸽i c a lr a n d o m 鼬r 、，i c es y 贰锄t h 踟r y ( a l s oc a l l e dq u e u e i n gt h e a r y ) d 西v e d 矗0 me i 1 扯培8r e 醴咀r c h n c e 如血曙t e l e p h o n e8 e r 、，i c e s j n c e 也e & 船) n d w b r l dw 打，i tg o taf 1 1 r t h e rd e v e l o p m e n t ，b 唧血n go n eo ft h em 0 8 t 啊9 0 r o u s t o p i c 8i nr a n d o mo p e r a t i o n a lr e 砌a n d 叩l p h e dp r o b a b i u t y b e c 8 i l s eq i l e u e i n g p h e n o m e n o ni 8ar a n d o mo n e ，w em 越n i ya p p l yp r o b a b i l i t yt o8 t u d yq u e u e i n g t h e o r yk e n d b uw 嬲t h ep i o n e 叮w h ov i e w e da 丑dd e v e l o p e dq u e u e i n gt h 唧丘o m t h ep e r s p e c 七i v eo fs t o c h 铺t i cp r o c e 翳铭 q u e u e i n gt h e o r yi 8t h em a t h e m a t i c a ls t u d yo f ”( 1 u e 啷”o r ”w 越t i n gu n e ”a q u e u ei 8f o 】皿e d 订h e n e v e rt h ed e m a n df o r 刚c ee x c e e d st h ec a p a c i 锣t op r o 、，i d e r v i o ea t 也8 tp o i n tj nt i m e a q t 地u e i n gs y 8 t e mj s m p r i s e do fc u s t o m e 瑁o r 1 1 n i t 8n e e d i n g m ek 砌o f n ，i c ew h oa r r i 、，ea _ 七a8 邮d c ef a c m t yw h e r es l l c h s e r v i o ei 6p r o 、，i d e d am e ( 血a n i s mt h a tp e r f o r 嵋t h el d l l do fs e r 、r i c eo nc u s t o m e r s o rl l n i t 8f b di n l di ti sc 止1 e dds e r v e ro ra n 哇c ec h 踟m e l ，f b ra 【a 皿【p l e ，c u s t o m e r 6 a tab 龇1 ko rr e s e r v a t i o nc o u m e r c a 卫aa r r i v i n g8 tat e l e p h o n e 王。可b o 越 d ，m 8 c h i n 郫 丽t har 印a j r m 蛆n e e d i n gr e p 出，m e r c h a n d i 8 e f o rs h i p i n ta ta ) 砌，8 n d o n j o b 8a r r i 、，i n ga tac o m p o n e n ti na c o m p u t e ro e n t e ra r ea l r e g 鲫d e d 够c u s t o m e r s 柚dt h ec o m p o n 髓t t h ec o m p u t i n g 科s t e mw h e r es t l c hf a c i h t yi sp r 0 、，i d e di s c o n s j d e r e dt h e8 e r v 盱ac 毛l s 锄e rr e o e i 诎唱删c ej ss a i dt ob ej ns e r 、，i c e i u p o na r r i 、，8 l ，a ”c u s t o m e ，丘n d bt h e 眙r v e rb l l s y i tf o r m 8o rj o i n saq u e u e t h e r e a l s o 缸i c a s 够w h e r ec u s t o m e r 8l e a 靶t h es y s t e mw i t h o u tj 砌n gt h eq u e l l eo r l e a v e 丽t h o u tr e c e i 、，i n g8 e n 哇c ee v e na f c e rw 耐t i n gf o r m et i m e 1 1 1t r a d i t i o n a 王q u e u e i n gt h e o r y 虹屺b 蠲i ca 船啦p t i o nc a nb e 吼i m m 吡e di n t h en o t 8 t i o na b n m s ，w h i c hi s 啦e x t 咖i o n0 fk e n d a l l 8 出神a c t 曲a t i o n o faq u e u e i n g 盯s 乞e m h e r e ，aa n d 曰i n d 渤托t h ed i s t r i b u t i o n so fi n t e r a r r i v a l t i 珈嗍a n d 船r 、r i c et i i n 鹊( t h a tm a yo rn o tb ei n d 印e n d e n t ) ，ni 8t h e 肌皿【b e r 8 e r v e r s mi 8t h e 岫洳咖n u m b e ro fc u s t d m e r st h a tc a nb ea o 。o 毗1 0 d a t e d i nt h e 毋僦锄，a n ds 印e c m 铭t h e 鼬r 、，i c ed i s c i p l i l l e i nt h e 缸s e 眦hf o rm o r e a d v a n o e dw a y 8t om o d e lp r a c t i c a lq l l e u e i n gs i t l 埔此i o 璐，r e 眦h e r sh a v e “i d e da 1 c h a p t 盯1 i n t o d u c t i o n 帆d ev 枷e 锣o ff e a t l l r 鲳t o 也i sb a s i cm o d e l ，8 u