排队论的应用综述

[e-mail]2010.12.22排队论应用综述目录排队论的基本概念及典型模型1.排队论在通信领域的应用2.排队论在医疗领域的应用4.排队论在分配问题中的应用3.排队论在交通领域的应用5.排队论在银行领域的应用6.排队论的基本概念及典型模型排队论的基本概念及典型模型(1)•排队论的一般模型•排队论的组成部分•输入过程•排队规则•服务过程排队论的基本概念及典型模型(2)•排队模型的符号表示--X/Y/Z/A•X表示相继到达时间间隔的概率分布•Y表示服务台对单个顾客服务时间的分布，•Z表示服务台个数•A表示系统容量(排队室大小)•排队系统的运行指标•平均队长：指系统内顾客数的数学期望，记作L。•平均排队长:指系统内等待服务的顾客数的数学期望，记作LQ•平均逗留时间：顾客在系统内逗留时间的数学期望，记作W•平均等待时间：指一个顾客在排队系统中排队等待时间的数学期望，记作WQ排队论的基本概念及典型模型(3)•几种典型的排队系统模型M/M/1/•M/M/s/排队论在通信领域的应用排队论在通信领域的应用(1)•排队论在通信领域中应用的发展20世纪初期主要研究应用于电话网和远程通信系统等无队列的排队系统(损失制)20世纪中期主要研究通信系统中有队列(等待制)的排队系统和排队网络，从20世纪60年代至今研究大规模复杂排队系统的理论分析、数值分析和近似分析，尤其注重对业务突发性和带有各种网络控制的排队系统的研究。经典排队理论现代通信技术中主要研究的内容排队论在通信领域的应用(2)•经典排队理论(1)相继到达顾客的到达时间的间隔与服务时间都相互独立(2)由于到达和服务的无后效性的特点，一般可以用生灭过程来描述•近百年以来，经典排队理论在通信领域的主要成果大致可总结如下:(1)得到了单服务台排队模型(M/M/1)在到达间隔和服务时间相互独立条件下的稳态解[4,5](2)对于多服务台排队系统(M/M/s)，得到了在服务时间满足指数分布的稳态解[6,7](3)优先排队模型也得到了比较明确的结果，尤其在输入流满足泊松分布以及优先级固定的情况下的排队[8~10]排队论在通信领域的应用(3)•现代通信技术中的排队论理论•现代通信的发展趋势是业务综合，在同一个网络中实现多种业务的传输，因此输入将是复合业务流，比较复杂，一般不再具有泊松过程无后效性的特点•服务过程与排队策略也变得比较复杂•现代通信研究中常用的排队分析方法显然，经典的排队理论并不能把问题解决Neutes矩阵几何分析法4扩大状态空间法1半马氏分析法2流体流方法3大偏差理论方法5排队论在通信领域的应用(4)•扩大状态空间法[12~15]•将非马尔可夫过程的排队化成一个状态空间为多维的马尔可夫过程求解•半马氏分析方法[13,16]•对于一般服务或一般到达的排队系统，不是在任何时刻系统都具有马尔可夫性质，只是在某些特殊的随机时刻系统具有这种性质，我们称这种随机时刻点为再生点，即从这个时刻起，系统好像又重新开始一样。•利用再生点，一般服务或一般到达的排队系统可化为马尔可夫链，用马尔可夫链的方法予以解决这两个方法的计算复杂度与排队容量大小的立方成正比,显然这是很不利的排队论在通信领域的应用(5)•流体流方法[13,14,17~19]•流体流方法(FluidFlowMethod)是一种排队近似分析法。它忽略到达过程及排队队长的离散性质,将到达及队长变化看成连续变化。•计算简单、物理意义明确,流体流方法的计算复杂度与排队容量大小无关•矩阵几何分析方法[13，20~22]•随机模型有指数分布为可信发展到广泛应用相位型分布•大偏差理论方法[24,25]•一种近似分析方法•没有Markov假设总结：现代通信技术中的排队论分析方法是多种多样的，因此，针对不同的实际情况，需要选择合适的方法，是得到最高的效率及最好的准确率。排队论在分配问题中的应用分配问题•对资源的合理利用•多目标的合理处理•解决的问题：减少资源浪费，防止拥塞，对目标的即时处理，提高系统工作速度效率等等发展历程•1990~1995工程上的应用、医疗上的应用、图书馆信息处理，军事上的应用•1995~2000码头与船舶的分配，工程土方的创新，停车场面积的计算•2000~2005智能地雷反坦克研究，灭火兵力部署•2005~2010新的前沿应用，公测建筑面积的分配，图书馆服务，信息技术中的应用教务员岗位数量确定•教务员数量多，平时人员冗余过多，经济性不好；教务员数量少，忙期工作强度过大，易于出错，工作效率低•以期末等级成绩单的状况为假想考察，将教师上交成绩单和教务员处理成绩单的速度建立为M/M/S/无穷，排队问题•求解比较不同教务员情况下的空闲概率评估系统是否合理•得到最佳的教务员配置方案排队论在公厕面积设计上的应用•由于各方面的原因，男女厕相同面积的设计存在着一定的不合理性•地点、场合的不同影响公厕的使用效率，需要综合分析得到合适的建筑面积分配•将人们入厕这一过程，看成一个随机服务系统的服务过程。每个入厕的人是一个顾客，厕所坑位则为服务台。•收集某一公厕一定时间内到达人次及使用时间数据，建立模型求解最佳等待时间以取得最佳服务满意度。•评估公厕面积分配是否合理，应如何改进排队论解决分配问题的未来展望•宇航相关问题•军事相关问题•医院相关问题•计算机相关问题•民用设施相关问题排队论在医疗领域的应用排队论在医疗领域的应用（1）•医院中存在着各种有形无形的排队现象(如：就诊、挂号、取药、划价，病床医生等资源的调度，等等……)，如何使医院工作既能满足患者的需要,又能让医疗资源得到充分利用，这部分主要说明使用排队理论分析了不同类型医疗过程，并以此优化医疗过程。排队论在医疗领域的应用（2）•近年来旨在提高医疗体系的服务效率，提高资源利用率，提高病人满意度以及缓解患者于医院之间的矛盾；提出了一些具体的优化标准如下：1、以费用作为优化指标计算最优目标值条件下最优的服务水平：总费用=排队损失费+服务费2、“优先权选择或等级”来优化医院服务3、构造合理的调度方式来进行优化4、建立了“预留病床模型，逐步优先权就诊模式”排队论在医疗领域的应用（3）总结及预测•一系列的研究发现，相对于经验的管理方法，排队理论能较为科学，量化地分析医院的排队系统，并提出合理的整改意见，适应了新经济时代的个性化就诊趋势。•运用排队论方法，通过对医院排队系统的研究，科学、量化、准确地描述排队系统的规律性，同时对诊室和医生的安排进行最优化和最优运营提出科学有效的整改意见，为医护工作的安排提供量化、科学的依据，以增加预见性，减少盲目性．从而最大限度得满足患者和家属的要求，同时采用排队论的理论与方法评价门诊服务流程效率合理性和可行性，值得推广。最终目的实现双赢！排队论在交通领域的应用排队论在交通领域的应用（1）•起源：早在1936年亚当斯在一片理论性的论文中讨论了没有交通信号的交叉口的行人延滞问题。他假设行人和车辆达到都是随机的，并且在现场进行性了观测，证明了设想基本正确。他计算出了阻塞的平均延续时间，以及非阻塞延续的时间。现在的研究与应用：•研究公交车发车间隔与排队长度•研究停车场的车辆排队•研究信号交叉口前的车辆排队现象和其所造成的车辆延误排队论在交通领域的应用（2）研究公交车发车间隔与排队长度目的：通过研究公交车发车间隔与排队长度，以此来获得较好的经济收益与顾客满意度.研究现状：考虑到公交排队系统的随机性——交通流的随机性，对交通流情况经行统计分析.发车时间间隔与排队长度关系曲线在我们研究中起着重要作用。在行车时间和顾客排队都是随机的变化的假定下，得出更为符合实际情况的研究。排队论在交通领域的应用（3）研究停车场的车辆排队目的：通过对系统中平均车辆数目的估计更好的规划停车场，设置停车位的数目。研究现状：我们通常设一个M|M|N的具有指数达到和指数服务的多通道模型来研究车辆平均接受服务的时间。实际停车系统是一个有损系统，车主找不到车位自然会离开，增加对系统有损特性的考虑，设计出更加合理的模型。排队论在交通领域的应用（4）研究信号交叉口前的车辆排队现象和其所造成的车辆延误目的：通过对对长和平均阻塞时间的估计，合理设置交叉口的管制形式以减少车辆延误。研究现状：1）假设车辆到达交叉口服从和不服从泊松分布来建立排队模型；2）采用M/M/1排队模型和标准的近似技术,对多车道的交叉口进行研究3）针对实际车辆行驶状态以及车头时距的不规律性,建立了适用于任意车辆到达规律的排队模型,描述信号交叉口的实际排队情况排队论在银行领域的应用传统排队系统是多对列多服务台的M/M/1模型，输入过程为泊松分布，服务时间为指数分布，C个服务台独立运作。客户到达后选最短的队伍排队，每个新到顾客都选择当前时刻最短的队伍，所以总体来看各队列等候人数相近。排队论在银行领域的应用（1）一、排队方式传统方式——多路排队（M/M/1模型）取号机的引入——单路排队（M/M/C模型）多对列多服务台排队模型单对列多服务台模型二、服务窗口数量和弹性排班制度1、服务窗口数量排队论在银行领域的应用（2）M/M/C模型顾客的平均到达速率服务员的平均服务速率适时调整窗口数量2、弹性排班制度弹性排班是针对银行服务需求波动大的特点，通过优化人员配备组合，实行弹性工作安排，根据不同时段顾客流量和业务量的变动情况，动态调整人员工作时间和工作人数的排班制度。应用排队论建立了银行柜员弹性排班制度，在缓解银行排长队现象、应对需求的大幅波动、优化银行柜员资源配置方面很有效，能够满足顾客减少排队等待时间的要求，合理优化柜员工作时间、节省人力成本及排班成本、提高柜员服务效率。三、缩短服务时间，提高服务效率1、缩短服务时间根据排队理论可以得出，如果银行平均服务率低于顾客平均到达率，会使得排队越来越长而只能等到高峰期过后才能得到缓解。因此，缩短服务时间，可以使排队系统能够应付更多的顾客，从而降低顾客的等待时间。2、提高银行服务的效率在最普通，也是最经常为顾客提供服务的储蓄窗口的员工应尽量避免处理其他业务，用最快捷、最有效的方式为顾客提供服务，减少顾客排队的时间；可以对团体客户或者存款数额较大的顾客设立预约服务，并开设一个专门的预约窗口，将这些占用时间较多的服务从业务高峰期中划分出来单独处理。排队论在银行领域的应用（3）排队论在银行领域的应用（4）四、分流客户，减轻服务柜台压力分流客户的措施：各大银行自身应该大力发展电子银行服务，拓展电子化营销渠道，实现柜台分流，有效缩短排队时间。电子银行具有突破时空限制、高效率、低成本等传统服务方式难以比拟的优势，大力推广电子银行业务，能有效降低银行营运成本、分流柜台业务、解决银行排队问题，是解决银行排队问题的根本出路。任务分配排队论基础及排队论在通信领域中的应用----马新悦（组长）PPT设计及排队论在分配问题中的应用----郑献（汇报人）排队论在医院相关问题的应用----赵绒绒排队论在交通问题中的应用----刘英莎排队论在银行问题中的应用----龙海明谢谢