排队论的综述与应用文献综述.doc

排队论的综述与应用文献综述 文献综述排队论的综述与应用一、前言部分(说明写作的目的,介绍有关概念、综述范围,扼要说明有关主题争论焦点)1.写作目的 本文主要在于介绍排队论的历史背景,不同的排队模型,以及实际的应用.目的在于对排队论的历史背景,模型等进行综述,并总结排队论在生活各个领域的应用.2.基本概念 排队现象是很常见的,排队论queuing theory也称随机服务系统理论(random service system theory),是一门研究拥挤现象(排队、等待)的科学【1】, 是通过对服务对象到来及服务时间的统计研究,得出这些数量指标(等待时间、排队长度、忙期长短等)的统计规律,然后根据这些规律来改进服务系统的结构或重新组织被服务对象,使得服务系统既能满足服务对象的需要,又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科。也是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络, 生产, 运输, 库存等各项资源共享的随机服务系统。 排队论研究的内容有3个方面:统计推断,根据资料建立模型;系统的性态,即和排队有关的数量指标的概率规律性;系统的优化问题。其目的是正确设计和有效运行各个服务系统,使之发挥最佳效益【2】。3.用排队论来研究排队服务系统,首先要对各种排队系统进行分类描述.任何排队服务系统可以描述为以下四个方面【3】: 1.输入?指顾客到达服务系统的情况.按到达的时间隔分:有确定的时间间隔,有随机的时间间隔;从顾客到达人数的情况看:有按单个到达,有按成批到达的;从顾客来源总体看:有顾客源总数无限及有限两类,但只要顾客源总数足够大时,可以吧顾客源总数有限的情况近似的当成顾客源总数无限的情况处理【4】. 2.输出?是指顾客从得到服务到离开服务机构的情况,有定长的服务时间,一随机的服务时间;按一名服务员同时服务的顾客人数区分,有单个服务,有成批服务等. 3.排队服务规则?有损失制和等待制两种情况. 损失制是指顾客到达时,若所有服务设施均被占用,则顾客自动离去,永不再来.电话服务系统就属于这种情况,当一个电话打不通是需要重新拨号,意味着一个新顾客的到来,而原来的顾客已永远离去.等待制是指顾客到达时如果服务设施已被占用,就留下来等待服务,一直到服务完毕后离去.这里又有两种情况:一种是无限等待的系统,不管服务系统中的顾客已有多少,新来的都进入系统,另一种是有限等待的系统,当排队系统中的顾客超过一定限度时,新来的顾客就不再等待,而是自动离开服务系统.对等待的系统,服务次序一般有:1先到的先服务(FCFS):即按到达先后的次序排成队伍依次接受服务.当有多个服务设施时,一种是顾客分别在每个设施前排成一队,也有排成一个公共的队伍,当任何一个服务设施有空时,排在队首的顾客首先得到服务.(2)后到先服务(LCFS):同先到先服务相反过来,越后到的顾客反而先得到服务.在仓库中后到的零件、材料堆放在最上面先被领走就属于这类服务.(3)带优先服务权(PR):即到达的顾客按重要性进行分类,服务设施优先对重要性级别高的顾客服务,在级别相同的顾客中按到达的先后次序排队.(4)随机服务(SIOR):到达服务系统的顾客不形成队伍,当服务设施有空时,随机选取一名服务,对每一名等待的顾客来说,被选取的概率相等. 4.服务机构?指服务设施的个数、排列及服务方式.按服务设施的个数分,有一个或多个之分(通常称单站服务系统和多站服务系统);按排列形式,多站服务系统有串联和并联之分,对S个服务站的并联系统,一次可以同时服务S个顾客,而串联的情况下,每个顾客要依次经过这S个服务站,就像一个零件经过S道工序加工一样.服务方式上有单个服务,也有成批服务的,如公共汽车就一次装载大批顾客.二、主题部分(阐明有关主题的历史背景、现状和发展方向,以及对这些问题的评述)(一)历史背景日常生活中存在大量有形和无形的排队或拥挤现象,如旅客购票排队,市内电话占线等现象.排队论的基本思想是1910年丹麦电话工程师A.K.埃尔朗在解决自动电话设计问题时开始形成的,当时称为话务理论.他在热力学统计平衡理论的启发下,成功地建立了电话统计平衡模型,并由此得到一组递推状态方程,从而导出著名的埃尔朗电话损失率公式【5】. 自20世纪初以来,电话系统的设计一直在应用这个公式.30年代苏联数学家.欣钦把处于统计平衡的电话呼叫流称为最简单流.瑞典数学家巴尔姆又引入有限后效流等概念和定义.他们用数学方法深入地分析了电话呼叫的本征特性,促进了排队论的研究.50年代初,美国数学家关于生灭过程的研究、英国数学家D.G.肯德尔提出嵌入马尔科夫链理论,以及对排队队型的分类方法,为排队论奠定了理论基础.在这以后,L.塔卡奇等人又将组合方法引进排队论,使它更能适应各种类型的排队问题.70年代以来,人们开始研究排队网络和复杂排队问题的渐近解等,成为研究现代排队论的新趋势【6】.(二)排队模型1.1广义模型的建立是基于排队情形的长期行为,或称为平稳状态行为,这种状态在系统经过了充分长时间的运行后得到的。这种分析和系统初期运行期间所常见的瞬间(或称为热身)行为完全不同.本章不讨论瞬时行为的一个原因是由于对它的解析太复杂,里一个原因是由于对大多数排队系统都是在平稳状态下来研究的【7】. 广义模型假设,到达率和离开率都是与状态相关的,也就是说,它们都依赖于服务设施中的顾客数。例如,在高速公路收费口,在高峰时间收费员通常就会提高收费速度。另一个例子发生在商店,假定收费机的数量一定,随着坏了的机器数量增加,故障率就会减少(因为只有正在工作的机器才可能发生新的故障). 定义 系统中的顾客总数(排队的加上正在接受服务的) 已知系统中的有那n个顾客是的到达率 已知系统中有n个顾客时的离开率 系统中有n个顾客的平稳状态概率广义模型中作为和的函数,然后用这些概率来求出系统行为的度量指标,如平均队长、平均等待时间以及设备平均利用率 概率可以用图中的转移率图来的到。这个排队系统处在状态n,因为这时系统中的顾客数为n. 根据12.3的解释,在一个小时区间h里多于一个事件发生的概率随着0而趋于0.这意味着,对于,状态n只能变成两种可能的状态:当按照离开率离开时变成,当按照到达率到达时变成.状态0按照到达率到达时只能变成状态1.注意到假如系统为空时,因为没有离开发生,没有意义 在平稳的状态条件下,对于,流入和流出状态n的期望速率必相等。根据状态n只能变成状态和的事实,我们得到 流进状态n的期望速率类似地 流出状态n的期望率让这两个速率相等,得到下面的平衡方程对应于的平衡方程为从开始递归求解平衡方程如下:对于n0,有 接下来,对n1,有 用 替换并简化,得到(请验证!) 一般地,可用归纳法得到的值可用从等式求出1.2单服务台模型【8】 我们用肯德尔记号来总结每种情形下的特征.以在记法上我们用了GD(一般排队规则).: 利用广义模型的记法,有并且,因为所有的到达顾客都能加入到系统 令,则广义模型中的表达式就简化成 ,为了求的值,用等式 设,几何级数将有有限和,因此,其中所有的一般公式由下面的几何分布给出:, 的数学推导将用到条件或.若,则几何级数发散,平稳状态概率不存在.这个结果有着直观意义,因为除非服务率大于到达率,否则队列长度将会不断增长,不可能达到平稳状态 排队系统的性能指可以按下面方式得到: 因为对于本情形,剩下的系统性能度量指标用12.6.1节中的关系来计算因此有1.3 排队模型【9】 为泊松输入、负指数分布服务、无限个服务台的服务系统. 假定参数为的最简单流到达无限个服务台的系统,则顾客一到达立即可接受空闲着的服务台的服务.服务时间与到达间隔相互独立,服务时间是参数的负指数分布.得: 其中.于是,可知系统中在服务的服务台平均数 1.4系统的容量有限制的情况()【10】 如果系统的最大容量为N,对于单服务台的情形,排队等待的顾客最多为N-1,在某时刻一顾客到达时,如系统中已有N个顾客,那么这个顾客就被拒绝进入系统. 当N1时为即时制的情形;当,为容量无限制情形. 列出状态概率的稳态方程: 解这差方程,令得 在对容量没有限制的情形下,我们曾设,这不仅是实际问题的需要,也是无穷级数收敛所必需的.在容量为有限数N的情形下,这个条件就没有必要了.不过当时,表示损失率的将是很大的. 我们可以导出系统的各种指标:对长(期望值) (2)队列长(期望值)当研究顾客在系统平均逗留时间和在对列中的平均等待时间时,要注意平均到达率是在系统中有空时的平均到达率,当系统已满时,则到达率为0,因此需要求出有效到达率.可以验证:顾客逗留时间(期望值)(4)顾客等待时间(期望值)1.5排队模型【11】排队模型是1个服务台的等待制服务系统,输入过程是以为参数的最简单流,各顾客的服务时间是相互独立且具有相同分布的随机变量,其数学期望和方差分别为和.服务台的服务强度当时,我们有如下的结论: 同时我们还可以知道,忙期的平均长度 在忙期内被服务的顾客的平均数为.1.6排队模型【12】 在排队模型中,顾客的服务时间V服从爱尔朗分布,此时有 ,因此,当时,则下列各式:(三)排队论的应用 1.排队论在公路收费站服务台设计及管理的应用【13】 在高速公路收费站服务台设计及管理中运用排队论进行定量分析,运用排队论的知识对其进行优化和设计并建立合适的数学模型.通过对模型的优化设计,建立高速公路收费站的服务台与工作人员的配备模型,对避免盲目确定收费亭建设规模大小,提高收费站服务台的服务和管理水平,降低运营成本等有着重要作用. 2.排队论在改进银行服务系统中应用探索【14】 .应用排队论理论对银行服务系统进行了统计调查与分析,从技术的角度分析银行应该采取什么措施使顾客的等待时间最短;并从经济学角度分析成本和损失如何协同,来优化系统,使银行效益达到最大. 3.排队论在高校选课系统服务台模型设计中的应用【15】 在高校网络系统中,随着客户机数量和密集性任务的增加,单个Web服务器受到处理能力的限制,已经成为网络访问的新瓶颈.若增加Web服务器缓解资源的紧张,则可能造成成本增加,设备闲置.因此,Web服务器具备可用性将成为解决这一问题的最佳方法.在综合考虑系统中主要应用的算法基础上,以概率动态分布为基础,综合运筹学中的排队论原理,建立一种应用在高校选课系统中的多道等待服务台模型.实践结果证明,提出的模型应用在高校选课系统中,减少运营成本,提高服务水平效果.三、总结部分(将全文主题进行扼要总结,提出自己的见解并对进一步的发展方向做出预测) 排队论是一个前沿性研究课题. 排队论queuing theory也称随机服务系统理论(random service system theory),是一门研究拥挤现象(排队、等待)的科学【1】, 是通过对服务对象到来及服务时间的统计研究,得出这些数量指标(等待时间、排队长度、忙期长短等)的统计规律,然后根据这些规律来改进服务系统的结构或重新组织被服务对象,使得服务系统既能满足服务对象的需要,又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科。也是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络, 生产, 运输, 库存等各项资源共享的随机服务系统。 排队论研究的内容有3个方面:统计推断,根据资料建立模型;系统的性态,即和排队有关的数量指标的概率规律性;系统的优化问题。其目的是正确设计和有效运行各个服务系统,使之发挥最佳效益【2】。 本文回顾了排队论历史背景,不同的排队模型,以及实际的应用.目的在于对排队论的历史背景,模型等进行综述,并总结排队论在生活各个领域的应用.强调了不同排队模型(例如排队模型、排队模型、排队模型等等)特征下的计算过程,并对提出的实际问题,建立科学的排队模型进行分析,从而使提出的问题达到最优解四、参考文献(根据文中参阅和引用的先后次序按序编排)1王文平.运筹学M.北京:科学出版社,2007.2谷源盛.运筹学M.重庆:重庆大学出版社,2001.3郭志勇.客运专线桥上无缝道盆的设计J.铁道建筑,2007,7.4严智渊.排队论及其应用J.上海交通大学学报,1980,3:157-166.5张蕊.服务行业排队论问题分析J.齐齐哈尔滨大学学报,2002, 6.6Hamdy A.Taha.运筹学(英文版)M.北京:人民邮电出版社,2007.7美 Hamdy. A. Taha. Operations Research An IntroductionM.北京:人民邮电出版社,2007.8江天学,黄劳生.简明运筹学M.南京:东南大学出版社,1991.9