（应用数学专业论文）mmln→mmck排队系统及其应用研究.pdf

独创性声明 本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其 他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 贡献均已在论文中作了明确的说明并表示了谢意。 签名：丝墨墨日期：丝尘：! ! ：三：、 关于论文使用授权的说明 本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保 留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或 部分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：盼导师签名：兰垒三曜日期：2 必矿 摘要 在社会文明高度发展的今天，人们经常遇到一些排队现象，例如，在十字路 口车辆排队等待通行；地铁站，火车站和汽车站乘客排队等待上车等等。随着 人口的不断增加和经济的不断发展，各种排队系统也变得越来越复杂，怎样合 理经济的配置设施才能使人们对所接受的服务满意昵? 这就是排队论要解决的 主要问题。 排队论最早起源于对电话通话问题的研究，当生灭过程被引进后，排队论 被越来越广泛的应用。由于排队网络模型和现实很接近，所以排队论广泛的应 用到各种实际问题的研究之中。许多学者导出了各种排队网络模型的乘积型解， 而对于有限容量的串联排队网络系统，一般是没有乘积型解的，所以人们较多 的是用逼近的方法进行研究，进而求出系统指标的近似数值解。 由于目前许多学者只考虑了i i 级服务台容量有限的两级串联排队模型，而 对两级容量均有限的排队模型还没有提出并研究，本文主要就是在已有模型研 究的基础上，提出了两级容量均有限的串联排队系统一 肘m i n _ m m c k 。本文总共包含五章：第一章为绪论，主要介绍排队 问题研究的一些背景和意义、国内外研究现状、本文的主要研究思路及内容； 第二章为理论知识，是为第三章的内容做铺垫，介绍了排队系统的相关知识、 矩阵解析法和拟生灭过程的知识，然后讨论了在等待空间均无限和等待空间均 为零的情形下的两级串联排队系统模型的各项排队指标；第三章为本文的主要 理论创新部分，提出了m m ，_ m m c k 串联排队系统模型，并用随机过 程、概率论及矩阵分析理论等知识给出它的i 级服务系统的排队指标、i 级服 务系统的受阻时间及其分布、系统平稳队长分布及其算法。第四章是实证分析， 主要是将理论与实际结合，把m m ， ，- m m c k 排队系统模型的知识应 用到烟台港西港区锚地规划中去，首先将港口系统理想化，并把该港口看作一 个单排队系统一m m n 排队模型进行研究，并做仿真计算，然后运用本文提出 的模型研究，也进行了仿真计算，发现结果更精确，得出此模型具有一定的合 理性。 关键词：串联排队系统；矩阵几何解：拟生灭过程；m m ，_ m m c k 排队系统 a b s t r a c t i n t h es o c i a lc i v i l i z a t i o nh i g h l yd e v e l o p e dt o d a y ，p e o p l eo f t e ne n c o u n t e rs o m eq u e u i n g p h e n o m e n o n ，f o re x a m p l e ，i nt h ec r o s s r o a d sv e h i c l e sw a i tf o rp a s s i n g ；i ns u b w a ys t a t i o n ，r a i l w a y s t a t i o n ，b u ss t a t i o n ，p a s s e n g e r sw a i t i n gf o ro n ，e t c w i t ht h ei n c r e a s eo fp o p u l a t i o na n d e c o n o m i c d e v e l o p m e n t ，v a r i o u sq u e u i n gs y s t e mi sa l s ob e c o m i n gm o r ea n dm o l tc o m p l e x ，h o wt om a k e p e o p l ef a c i l i t i e st oa c c e p tt h es e r v i c es a t i s f a c t i o n ? t h i si st h eq u e u i n gt h e o r y t os o l v e q u e u i n gt h e o r yw a so r i g i n a t e df r o mt h ep r o b l e mo ft e l e p h o n ec a l l s ，w h e nt h eb i r t ha n dd e a t h p r o c e s sw e r ei n t r o d u c e d ，q u e u i n gt h e o r yi sa p p l i e dm o r ea n dm o r ew i d e l y b e x 2 a u s eo fq u e u i n g n e t w o r km o d e li sv e r yc l o s et ot h er e a l i t y , i tb e c o m e st h ek e yo fq u e u i n gt h e o r yr e s e a r c hi nt h e p r e s e n t t h ep r o d u c tt y p es o l u t i o no fa l lk i n d so fq u e u i n gn e t w o r km o d e la l ed e d v e db ym a n y s c h o l a r s ，b u tf o rt h el i m i t e dc a p a c i t yo ft a n d e mn e t w o r ks y s t e m ，p e o p l em o r eu s ea p p r o x i m a t i o n m e t h o dt og e tt h ea p p r o x i m a t i o nn u m e r i c a ls o l u t i o no ft h ei n d e xf o rt h es y s t e m a tp r e s e n t , s i n c em a n ys c h o l a r so n l yt a k e t h ec a p a c i t yi sl i m i t e da tt h es e c o n ds t a g eo f s e r v i c e - c e n t e rf o rt w o - s t a g et a n d e mq u e u i n gs y s t e mi n t oc o n s i d e r a t i o n ，b u tt h e yh a v e n tp r o p o s e d t h a tb o t ho ft h ec a p a c i t yi sl i m i t e df o rt h et w os t a g es e r v i c e - c e n t e r b a s e do nt h er e s e a r c ho f p i o n e e r s ，t h e m a i np u r p o s eo ft h i sp a p e ri sa b o u tt w o - s t a g et a n d e mq u e u i n gs y s t e i i 卜。 m m 1 n - m m i c l k ，w h i c hc a p a c i t yi sb o t hl i m i t e df o rt h et w os t a g es e r v i c e - c e n t e r t h e r ea l ef i v ec h a p t e r si nt h i sp a p e r t h ef i r s tc h a p t e rw a sm a i n l yi n t r o d u c e ds o m eb a c k g r o u n d s a n ds i g n i f i c a n c eo ft h ep r o b l e m , t h er e s e a r c hf o rp r e s e n ts i t u a t i o no fd o m e s t i ca n df o r e i g nc o u n t r y a n dt h em a i nr e s e a r c hm e n t a l i t ya n dc o n t e n to ft h i sp a p e r t h es e c o n dc h a p t e ri st h et h e o r e t i c a l k n o w l e d g e ，w h i c hi sp r e p a r e df o rt h er e s e a r c ho ft h et h i r dc h a p t e r t h ek n o w l e d g eo fq u e u i n g s y s t e mw a si n t r o d u c e d ，p u to u tt h ek n o w l e d g eo fm a t r i xa n a l y s i sm e t h o da n dq u a s ib i r t ha n d d e a t hp r o c e s s ，t h e nd i s c u s s e dt w oc i r c u m s t a n c e so ft w o - s t a g et a n d e mq u e u i n gs y s t e m ，w h i c ha l l t h ew a i ts p a c eb o t l lu n l i m i t e da n db o t hz e r o s t h et h i r dc h a p t e ri st h ei n n o v a t i o no ft h i sp a p e r i t h a sm a k e i m p r o v e m e n t o ft h e m m i n _ mim c kq u e u i n gs y s t e mm o d e l ，a n du s e ds t o c h a s t i cp r o c e s s ，p r o b a b i l i t y t h e o r y , m a t r i xa n a l y s i st h e o r yt og e ti ts o m eo fq u e u i n gi n d e x s u c ha s ，t h eq u e u i n gi n d e x ，t h e h i n d e rt i m ea n di t sd i s t r i b u t i o no ft h ef i r s ts t a g eo fs e r v i c e - c e n t e r , t h es m o o t ha n ds t e a d y d i s t r i b u t i o na n di t sa l g o r i t h mo ft h es y s t e m t h ef o u r t hc h a p t e ri se m p i r i c a la n a l y s i s ，w h i c hi s m a i n l ya b o u tl i n k e dt h e o r yw i t hp r a c t i c e ，a p p l i e dt h ek n o w l e d g eo fq u e u i n gs y s t e mm o d e lo f n m m i i l n - m m c kt ot h ep l a n n i n go fa n c h o r a g ef o ry a nt a ip o r ti nw e s tc o a s t a l f i r s t ，g e tt h ep o r ts y s t e mi d e a l i s t ，a n dc o n s i d e ri t i n t oas i n g l es t a g eq u e u i n gs y s t e m - m i m i n ， t h e ns i m u l a t et h i sm o d e la n dc o u n tt h er e s u l t s e c o n d ，u s et h em o d e lo ft h i sp a p e rt os t u d yt h i s p r o b l e m ，s i m u l a t ei ta l s o ，c o m p a r et h er e s u l t s ，w ec a nd i s c o v e rt h el a t t e ri s m o r er e a s o n a b l e ，s o t h em o d e lf o rt h i sp a p e rh a si t sv a l u e k e yw o r d s ：t a n d e mq u e u i n gs y s t e m ；m a t r i xg e o m e t r i cs o l u t i o n ；q u a s ib i r t ha n d d e a t hp r o c e s s ；m m 1 n - m m c kq u e u i n gs y s t e m i l l 目录 摘要i a b s t r a c t i i 第一章绪论。1 1 1 研究背景及意义。1 1 2 国内外研究现状2 1 2 1 排队论的研究进展2 1 2 2 串联排队系统的研究进展。3 1 3 主要研究思路及内容5 1 4 本章小结。5 第二章排队论的基础理论6 2 1 排队系统的概述。6 2 1 1 排队系统的概念及基本的排队系统6 2 1 2 排队系统的基本组成部分7 2 1 3 经典排队系统的符号表示9 2 1 4 排队系统主要研究指标1 0 2 2 矩阵解析法和拟生灭过程1 2 2 2 1 矩阵解析法1 2 2 2 2 拟生灭过程( o b d ) 1 2 2 3 串联排队系统的讨论1 5 2 3 1 两个等待空间均无限的串联排队系统。1 5 2 3 2 两个等待空间均为零的串联排队系统1 6 2 4 本章小结。1 8 第三章m i m i i i n 一m m c k 排队系统 1 9 3 1 模型描述1 9 3 2m m i n m m c k 排队系统指标2 2 3 2 1i 级服务系统的排队指标2 2 3 2 2i 级服务系统的受阻时间及分布。2 5 3 2 3 系统平稳队长分布及其算法2 6 3 3 本章小结2 7 i v 第四章m m i l i n _ m m k 系统在锚地规划中的应用2 8 4 1 烟台港西港区的基本情况及模型建立2 9 4 1 1 烟台港西港区的基本情况2 9 4 1 2 烟台港西港区港口系统的模型建立3 1 4 2 烟台港西港区系统服务能力仿真及结果分析3 3 4 2 1 烟台港西港区港口系统模型算法描述。3 4 4 2 2 烟台港西港区港口系统结果分析。3 5 4 3 本章小结3 8 第5 章总结与展望3 9 5 1 总结3 9 5 2 展望。4 0 j 致谢：4 1 参考文献4 2 攻读硕士学位期间发表的论文4 5 攻读硕士学位期间参加的课题。4 5 v 武汉理工大学硕士学位论文 1 1 研究背景及意义 第一章绪论 日常生活中存在大量有形和无形的排队现象，如旅客在车站排队购票，电 话呼叫占线等现象。由于接受服务的顾客数和服务时间是随机的，排队现象不 可避免，如何使这些排队问题达到最优，排队论的理论就应运而生了。排队论 是运筹学的一个分支，被广泛的应用。例如，顾客去售票厅买票，希望可以少 排队或排短队，而售票厅则希望充分发挥售票员的工作效率。但是，顾客到达 售票厅是随机的，售票员对顾客的服务时间也是随机的，所以，顾客有时要排 长队，或售票员有时闲着无事，这样两者出现了矛盾。排队论则可以通过研究 顾客到达和服务员的服务效率的概率规律，制定既能满足顾客需求又能最大限 度地发挥服务机构经济效益的策略。 面对拥挤现象，人们通常想到的做法是增加服务设施，但是增加的数量越 多，人力，物力，财力的支出就越大，甚至出现空闲浪费；如果服务设施太少， 顾客排队等待的时间相应增长，这样顾客就会受到影响。那么，我们该如何做 到既保证一定的服务质量指标，又使服务设施费用经济合理呢? 对于这类矛盾， 就是排队论所要解决的问题。 对于现代文明社会而言，许多有形的排队现象还可以反映一个国家的文明程 度。例如，排队上车，排队买票等等。目前，排队论已发展成- - i - j 成熟的理论。 特别是计算机技术的迅猛发展，排队论的科学研究更是日新月异，其应用领域 也不断扩大。现阶段，排队论的研究成果已广泛应用到通信工程、交通运输、 生产与库存管理、计算机系统设计、军事作战、港口和铁路运输、柔性制造系 统和系统可靠性等众多领域，并取得了一系列成果。因此，排队论在科学技术 及国民经济发展中起着直接的重要作用，而且是从事通信、计算机等领域研究 的专家、工程技术人员和管理人员现阶段必不可少的重要数学工具之一。 串联排队系统作为排队论研究的一类，目前也得到广泛的应用，比如，病人 去医院看病，需要先到服务台填写个人信息，再排队挂号、到诊室候诊、检查、 划价、交费、取结果、取药等一系列窗口。它是模拟交通运输、计算机网络的 一种重要的数字化模型。而有限容量的串联排队系统经常应用在数据传输、生 产线等模型中，这些都是与现实生活息息相关的，因此，对有限容量的串联排 队系统的研究很有意义。 武汉理工大学硕士学位论文 1 2 国内外研究现状 1 2 1 排队论的研究进展 排队论又名随机服务系统理论，是运筹学的一个分支。它是二十世纪初丹 麦数学家兼电气工程师a k e r l a n g 把概率论应用于电话通话问题而开创的学科； 2 0 世纪3 0 年代中期，w f e l l e r 引进生灭过程，使得排队论被数学界承认为- f - j 重要的学科：2 0 世纪4 0 年代排队论成为运筹学这个领域中一个重要的组成部分； 2 0 世纪5 0 年代d g k e n d a l l 用嵌入m a r k o v 链方法系统的研究排队论，使排队论 得到进一步的发展：2 0 世纪6 0 年代起排队论研究的课题逐渐复杂，排队网络的 研究被提出。 所谓排队网络，顾名思义是指由一些服务点和联结它们的路径所构成的一 个网状模型，其中每个服务点是一个有单个或多个服务台的排队系统，顾客只 有在一个服务点接受完服务后才能按照一定的规律沿着路径到下一个服务点接 受服务。 1 9 5 7 年，j a c k s o nu 。最早提出排队网络模型，后称j a c k s o n 网络，或j a c k s o n 开网络，或指数开网络，它由m 个服务点所组成，将其分别编号为1 ，2 ，m ， 其中第f 个服务点包括m ，个服务台，它们相互独立同分布且服务时间均服从指数 分布，第f 个服务点以参数为入，的p o i s s o n 流输入顾客，各服务点的外部输入与 其对应的服务台服务时间相互独立。在第f 个服务点接受服务后的顾客以概率 p 。按一定的规律沿路径转移到第j 个服务点排队等待服务，离开服务系统的概 率为q ，1 一了j | ：，p 。对于j a c k s o n 网络，可以证明它具有乘积型解，亦即它的平 - j 稳分布与各服务点平稳分布的乘积相等。若在j a c k s o n 网络中假设没有外部输 入，即所有入，o ，又如果没有外部输出，即所有吼一o ，且假定系统中顾客总数 是固定的，不妨设为，得到的即为指数闭网络，或j a c k s o n 闭网络，或 g o r d e n n e w e l l 网络。( g o r d e n & n e w e l l ( 1 9 6 7 ) ) 。对于j a c k s o n 闭网络，其平稳 分布同样具有乘积型解，带有p o i s s o n 输入的各服务点单独存在时的平稳分布可 以看成它的各乘积项，而不是网络中各服务点的边际分布，即这些服务点中的 顾客数是相互不独立的。明显的，各服务点中顾客数是有关联的，因为此网络 中顾客总数是固定的。此后，一些学者逐渐开始研究非指数网络是否也有乘积 型解。 在1 9 7 2 年，服务点符合p o i s s o n 输入蕴涵p o i s s o n 输出这种性质的网络被 2 武汉理工大学硕士学位论文 m u n t z 等。提出并研究，记这种性质为m 净m ，他证明了服务点具有m 号m 性质的网络也有乘积型解，同时该网络也有m 辛m 性质。b a s k e t t 。等( 1 9 7 5 ) 证明了对服务点服务服从一般分布的多类顾客网络，若其排队规则为处理机分 享( p r o c e s s o r s h a r i n g ) 的排队网络、后来先服务的强占继续型排队网络 ( l a s t c o m e f i r s t s e r v e d p r e e m p t i v e r e s u m e ) 、或有无穷多个服务台的排队网 络，其平稳分布仍有乘积型解。c h a n d y 旧。等( 1 9 7 7 ) 证明了在非指数服务的情形 下，排队规则必须是即刻服务规则的网络才具有乘积型解，这种情形要求顾客 在到达后必须立即接受服务。故像服从有优先权的服务、先来先服务等非即刻 服务规则的排队网络不能产生乘积型解。另外，k e l l y 旧。( 1 9 7 6 ) 与b a r b o u r ( 1 9 7 6 ) 考虑了多类顾客包括多种路径方式，多种排队规则在内的服从一般服务分布的 网络，利用可逆性得到了一种乘积型解。一种更一般的排队规则一u ；p s ( 末批 分享处理机，l a s t b a t h e p r o c e e s o r s h a d n g ) 被n o e t z e t ( 1 9 7 9 ) 提出了，它包括 上述处理机分享、后来先服务的强占继续型、有无穷多个服务台的特例，证明 了在一类更广泛的对称排队网络中，l b p s 是唯一的一类对所有服务分布都能产 生乘积型解。 1 9 8 9 年，路径与服务速度依赖于系统拥挤长度的m a r k o v 网络被s e r f o z o 归1 提出，他将通常考虑的各服务点的服务相互独立、各顾客选择的路径相互独立 的网络作为特例包含在内，这种模型对解释并行处理更方便。比如，由于网络 系统容量受限的转移阻塞、改变路径以避免拥挤、以及为适应后面路径的拥挤， 加快或减少处理速度等现象。他引进了一般网络过程来描写各服务点顾客数， 导出了它的平稳分布是具有向量函数的乘积型。v a n d i j k & r a m a s e w i c z ( 1 9 9 1 ) 则考虑了路径依赖于顾客在下一服务点所需的服务时间的一般服务需求的网 络，得出了其非标准的乘积型解。 除非路径可逆( 见k e l l y ( 1 9 7 9 ) ) ，或遇到服务点容量饱和时顾客会越过此服 务点，如同此时的服务速度等于的情况，服务点容量有限的网络一般是没有 乘积型解的。对有阻塞的非指数网络，顾客遇到阻塞时服务“停止 或“重复 两种类型的网络被v a n d i j k ( 1 9 9 1 ) 研究。两种类型在某种条件下被证明是等价 的，而且可导出其乘积型解。 1 2 2 串联排队系统的研究进展 串联排队系统在铁路和港口运输、道路交通控制、计算机通讯、存储系统、 3 武汉理工大学硕士学位论文 生产管理系统、生产流程、柔性制造系统等领域中的应用十分广泛。许多学者 对于容量无限的串联排队系统给出其精确解，而对于有限容量的串联排队系统， 人们较多的是用逼近的方法进行研究，求出该系统的各项排队指标的近似数值 解。如：a l t i o kw 。( 1 9 8 9 ) ，g e r s h w i nu ( 1 9 8 7 ) ，b r a n d w a l n & j o w “( 1 9 8 8 ) ， h i i l i e r & b o l i n g 副( 1 9 6 7 ) 等，这些方法在不同程度反映了计算的精确性和复杂 性。关于有限容量的串联排队系统各项排队指标的精确求解，目前这方面的工 作还不多，而且大多学者考虑的是比较简单的排队系统， 如：k o n h e i n & r e i s e ru 训( 1 9 6 7 ) 用复分析的方法给出了两级串联排队系统 m 肘1 - m 1 k 平稳的充要条件及平稳概率分布； l a t o n c h e & n e u t su 钏( 1 9 8 0 ) 考虑了系统m m r _ m c k ，用矩阵分析理论 给出了其平稳队长分布；在2 0 0 2 年，g o m e z c o r r a lu 训对i 级服务系统排队等待 空间无限，i i 级服务系统排队等待空间为零的串联排队模型一 m a p p h 1 _ g 1 进行了研究。这个模型要求只有当在i i 级服务系统的顾客 被服务完后，被i 级服务系统服务完的顾客才可以进入i i 级服务系统要求服务， 顾客以p o s s i o n 分布到达串联排队系统，研究该模型主要运用了嵌入m a r k o v 链 的方法及m a r k o v 更新过程的基本理论；对于有阻塞的串联排队系统， k o n h e i m & r e i s e r 把概率分布所满足的平稳方程通过z 变换研究了概率分布的 母函数的一些性质，推出该模型平稳的充要条件和给出计算概率分布的算法； 另外，l a t o u c h e n e u t s 运用拟生灭过程和矩阵解析法得出了此模型以及相关模 型的稳态条件。 在国内，也有一些学者对串联排队网络进行了研究，比如：在2 0 0 4 年，聂 盼红对串联开排队网络系统分析中，对两级j a c k s o n 串联开排队模型进行了研 究，并给出了m 级j a c k s o n 串联排队系统的平稳队长分布，此外，该论文还给出 了两类有限容量的级串联开排队系统的稳态结果及忙期分布；刘海方在2 0 0 7 年根据输入过程和服务过程的不同分了四个模型来运用m a r k o v 骨架过程理论 研究了两个等待制服务台的串联排队系统模型的瞬时分布和极限性态，并给出 了部分模型的排队指标。2 0 0 9 年，刘卫国刚用矩阵几何解方法得到 m ( m c m ( 7 1 k 模型的状态转移矩阵、稳态队长及其算法；2 0 1 0 年， 闰俊娜。研究了含特殊类顾客的m ( ，) m c _ ( m ) m n k 有限容量的串联 排队系统，用矩阵解析法得出了系统模型的q 一矩阵，运用拟生灭过程的方法给 出了系统平稳的充要条件、平稳队长分布及其算法，i 级服务系统的忙期分布 及其在忙期内服务完的顾客数的概率母函数，i 级服务系统受阻时间分布的 4 武汉理工大学硕士学位论文 l a p l a c e 变换等。 本文主要用随机过程、矩阵分析法和拟生灭过程的理论来研究有限容量的 两级串联排队模型一m m ，_ m m c k 。 1 3 主要研究思路及内容 本文首先简单介绍排队论的一些基础知识和各种排队系统模型，例如排队 模型m m 1 , m i m i c ，m i g l l , g i m 1 等等，然后提出并具体研究有限容量的 两级串联排队系统模型一m m ，一m m i c l k 及其一些排队指标，最后将 理论结合烟台港西港区锚地规划展开实证研究。目前，大多数人在研究船舶进 入锚地到离开泊位这个过程中，一般只是将泊位看做服务台，而忽略航道容量 的有限性。本课题从实际出发，将锚地也看做服务台，把锚地和泊位看成一个 有限容量的两级串联排队模型来进行研究。总体从四个方面进行讨论： 第一章主要是问题提出的背景，意义及国内外研究进展； 第二章介绍一些与本课题有关的理论知识； 第三章在前人研究的基础上，创新的提出了有限容量的两级串联排队模型一 m m ，_ m m c k ，并利用上面的理论知识，给出其一些排队指标，比 如，它的i 级服务系统的各项排队指标，i 级服务系统的受阻时间及分布等等； 第四章进行实证分析，主要是以烟台港西港区锚地规划为实例来说明所研究的 排队模型具有实际的意义，先将模型理想化，考虑成一个简单的单排队系统进 行仿真，计算出结果，然后应用本文提出的排队模型来研究。 第五章则是对全文的一个总结，并对进一步的研究做出一个展望。 1 4 本章小结 本章为绪论部分，主要从3 个部分来讨论：首先介绍本课题研究的背景及 意义，然后介绍相关知识的一些国内外研究现状，比如：排队论的研究进展和 串联排队系统的研究进展。最后给出本文的主要研究思路及内容，即本文的大 概框架和研究成果。 5 武汉理工大学硕士学位论文 第二章排队论的基础理论 2 1 排队系统的概述 2 1 1 排队系统的概念及基本的排队系统 在日常生活中排队现象已经是司空见惯了，例如，进入银行取号排队取款或 存款，当路口出现红灯时，汽车等机动车停止前进，排队等待。目前排队现象 已渗透到生活中的方方面面，排队现象一般可分为两个方面，顾客即希望得到 服务的一方，服务台是设法提供服务的一方。我们把希望得到服务的人或物统 称为顾客，提供服务的服务人员或服务机构统称为服务员或服务台。我们所说 的排队系统u 驯就是顾客和服务员所构成的系统，由于服务在一般情况下具有一 定的随机性，所以排队系统也被称为随机服务系统。 排队现象包含有形排队和无形排队两种，例如，到电影院、汽车站排队买票 等，这种类型的排队我们称为有形排队。又比如像电话呼叫等待类型的排队我 们称为无形排队。 下面用图形形象的介绍几种基本的排队系统： 1 ) 只有一个服务员的排队系统，其图解如图2 1 所示。 顾客到达队列 一 服务完离去 川oc i 服务员卜一 t 正在接受服务的顾客 图2 - 1 单排队系统 2 ) 有多个服务员的排队系统，其图解如图2 - 2 、2 - 3 、2 - 4 所示。 6 武汉理工大学硕士学位论文 顾客到达 队列 o o 图2 - 2 一个队列的并联排队系统 图2 - 3 多个队列的并联排队系统 去 竺嗡? oc 匝而耐! o c 匝一 o oc | 坠垦! 心) o ( 砸堑星兰卜 图2 - 4 两级串联排队系统 除了上述几种简单的排队系统外，还有多级串联、串并联混合、网络等复杂排 队系统。 2 1 2 排队系统的基本组成部分 上一节我们介绍了几种基本的排队系统，那么，这些排队系统有哪些共性 呢? 是由那些部分组成的呢? 从上面的图解及排队系统的概念可以分析出，它 们主要由三部分构成：输入过程( a r r i v a lp r o c e s s ) 、排队规则( q u e u ed i s c i p l i n e ) 和 服务规则( s e r v i c ed i s c i p l i n e ) 。 7 武汉理工大学硕士学位论文 1 ) 输入过程( a r r i v a lp r o c e s s ) 输入即顾客到达，输入过程是描述顾客来源及顾客是按怎样的方式和规律 到达排队系统的，可用顾客到达时间间隔或单位时间内到达的顾客数来表示。 顾客来源。顾客总体( 称为顾客源) 可能是有限的，也可能是无限的，例如， 微机室内发生故障待修的电脑数是有限的，到火车站排队买票的顾客源是无限 的。顾客到达的方式。顾客到达可以是单个的，也可以是成批的。例如，旅 行团组织去世博会，那么旅行团到达世博会场馆时就是成批到达，而以个人名 义到达世博会就是单个达到。顾客到达时间间隔的概率分布。即顾客相继到 达的间隔时间之间是否相互独立，相继到达的时间间隔服从参数为什么的概率 分布。如果假设r o 0 ，瓦1 ) 表示第n 个( 批) 顾客的到达时间，则 t o 0 正 疋 l 瓦+ l 再令f 。一瓦一瓦小n 之1 ，则f 。表示第刀个( 批) 顾客的到达时间和第n 一1 个( 批) 顾客的到达时间的间隔，称序列忙。，刀1 为顾客相继到达的间隔时间序列。顾 客相继到达的间隔时间可以是确定的，即输入过程为定长输入，指顾客每隔一 段固定的时间到达一个，例如，生产线上的自动包装机，每一分钟包装一袋货 物，公交汽车站按点发出的汽车等。顾客相继到达的间隔时间也可以是随机的， 例如，去超市购物的顾客，到医院看病的病人等等。我们一般研究的是输入过 程为随机型的排队论，在排队论的研究中，一般假定忙。，n 1 相互独立且同分 布。 2 ) 排队规则( q u e u ed i s c i p l i n e ) 排队规则是指服务系统是否允许排队、顾客是否愿意排队、在排队等待的 情形下服务的顺序又是什么? 鉴于此，可将排队系统分为三种类型：损失制： 顾客到达时，若所有服务台均在服务中，服务机构又不允许顾客排队等待，此 时该顾客就自动离去，例如电话系统中呼叫占线时停止呼叫。等待制：顾客 到达时，若所有服务台均在服务，即处于忙期，顾客就需排队等待服务。在等 待制系统中，服务顺序又包含：先到先服务，即顾客按到达的先后顺序接受服 务，这种服务在日常生活中被广泛接受；后到先服务，即越晚到越先服务，例 如建筑工地上的砖块越是上面越先使用；随机服务：即在所有等待的顾客中随 机地挑选一个顾客进行服务，例如，电话接线员在等待通话的顾客中随机的挑 选一位进行服务；有优先权的服务：即在排队等待的顾客中，某些类型的顾客 具有一定的特殊性，在服务顺序上要给予特殊待遇，让他们先得到服务，例如， 病危和急诊病人优先与普通病人接受治疗。混合制：一般允许排队，但不允 8 武汉理工火学硕士学位论文 许队列无限长。它是结合损失制和等待制的一种混合排队规则。包含队长有限、 等待时间有限和逗留时间有限的混合制系统。 3 ) 服务规则( s e r v i c ed i s c i p l i n e ) 刻画服务规则主要有3 个方面：服务台数量及构成形式，有单服务台和 多服务台。例如，单队单服务台式、单队多服务台并联式、单队多服务台串联 式、单队多服务台串并联混合制、多队多服务台串并联混合制等等。服务方 式，指服务台一次接受服务的顾客数，分为单个服务和成批服务。服务时间 的分布，即顾客所需的服务时间服从怎样的概率分布，每个顾客所需的服务时 间是否相互独立。在一般情况下，每个顾客的服务时间是一个随机变量。顾客 的服务时间分布常见的有：定长分布、几何分布、负指数分布、超指数分布、k 阶埃尔朗分布、一般分布等。 2 1 3 经典排队系统的符号表示 一个排队系统通常是由许多条件决定的，但为了简单明了，在经典的排队 系统中，常用3 - 5 个用斜线隔开的英文字母来表示一个排队系统，第一个字母 表示顾客输入过程的分布类型，第二个字母表示服务时间的分布类型，第三个 字母表示服务台的数目，第四个字母表示服务系统的容量，第五个字母表示排 队系统中的顾客数。例如： 膨m c o o 表示输入过程服从p o i s s o n 分布，服务时间相互独立且服从负指 数分布，系统有c ( o c 墨) 个服务台并联服务，系统容量为无穷的等待制系统； m g 1 表示输入过程服从p o i s s o n 分布，顾客所需的服务时间相互独立 且服从一般概率分布，系统中只有一个服务台，且容量无限的等待制系统； 饼m 1 o o 表示输入过程为顾客独立到达且相继到达的间隔时间服从一般 概率分布，服务时间服从负指数分布，且相互独立的，系统中只有一个服务台， 容量为无穷的等待制系统； e k g 1 k 表示输入过程为顾客相继到达的间隔时间相互独立、服从k 阶 e r l a n g 分布，服务时间服从一般概率分布，且相互独立，系统中只有一个服务 台，容量为k ( 1 墨k ) 的混合制系统； d m c k 表示输入过程服从定长分布，且顾客相继到达的间隔时间相互 独立，服务时间相互独立，且服从负指数分布，系统中有c ( o c 墨) 个服务台 并联服务，系统容量为x ( csk ) 的混合制系统； 9 武汉理工大学硕士学位论文 m ( r ) i m l l i 表示输入过程为顾客是成批到达的，且每批到达的顾客人数为 常数，( 1s ， ) ，批与批的到达间隔时间服从负指数分布，且相互独立，服务 时间也服从负指数分布，且相互独立，服务台仅有一个，系统容量为无穷的等 待制系统； m ( x ) m ( ，) 1 1 1 表示输入过程为顾客是成批到达的，且每批到达的顾客数量 x 是服从离散型概率分布律的随机变量，批与批的到达间隔时间服从负指数分 布，且相互独立，系统中只有一个服务台，顾客同样是成批到达接受服务的， 每批被服务的顾客人数为，( 1 ， ) 个，服务时间服从负指数分布，且相互独 立，容量为无穷的等待制系统。 此外，还有一些排队系统不能用以上符号表示，研究中另行说明或引入其它 记法。例如，本文主要研究的两级容量均有限的串联排队系统，记为 m i m1 1 1 n m m c 足，其中，表示i 级服务系统有，个服务台，表示i 级服务系统的容量为，c ，k 表示i i 级服务系统有c 个服务台、容量为k 。 2 1 4 排队系统主要研究指标 排队论研究的问题大致可分为两类：一类是服务设施设置之前，根据输入 过程，结合对系统的一定数量指标和服务过程的要求，确定服务设施的规模； 另一类是对已有的服务系统进行最优控制，改进和提高服务系统效率。 研究排队系统问题的主要目的是研究其运行效率，考核其服务质量，以便据 此提出改进措施。通常用6 项数量指标来评价排队系统优劣。 系统强度p ：它是衡量服务台在承担服务和满足需求方面能力的尺度； 系统空闲概率p o ：系统处于没有顾客到来要求服务的概率； 队长厶：队长是指在系统中的顾客数( 包括正在接受服务的顾客和在队 列中等待接受的顾客) ，它的期望值一般记作； 等待队长三。：等待队长是指在系统中排队等待服务的顾客数，它的期望 值一般记作三。显然，队长厶是等待队长三。与正在接受服务的顾客数的和。一 般情形，三。，三。越大，表明系统的服务效率越低； 逗留时间矿：逗留时间等于顾客在系统中的等待时间与服务时间的和， 它的期望值一般记作矿； 等待时间睨：顾客的等待时间是一个时间段，指顾客开始接受服务的时 刻与进入服务系统的时刻的时间间隔，它的期望值一般记作呒。等待时间和逗 1 0 武汉理工大学硕士学位论文 留时间是顾客最关心的数量指标。 另外，对排队系统还要考虑的指标有： 1 ) 系统的忙期与闲期u 引 忙期是指服务员在2 次空闲之间