排队论

4-3排队论模型排队论是20世纪初开始发展的。1905年丹麦哥本哈根电话工程师爱尔朗首先在电话自动交换机设计时应用排队论。使电话机既能满足通话需求而又不致设线过多。第二次世界大战以后，排队论在很多领域内被采用。在交通工程中，对于研究车辆延误、通行能力、信号灯配时以及停车场、加油站等交通设施的设计与管理方面得到广泛的应用。1936年亚当斯（Adams.W.F）用以考虑未设置交通信号交叉口的行人延误问题，1951年唐纳予以推广应用，1954年伊迪（Edie）应用排队模型估计收费亭的延误。同年在摩斯柯维茨的报告中，将其应用于车辆等候交通流空档的实验报告。一、引言排队论是研究“服务”系统因“需求”拥挤而产生等待行列即排队的现象，以及合理协调需求与服务关系的一种数学理论，是运筹学中以概率论为基础的一门重要分支，亦称“随机服务系统理论”。典型的例子——食堂打饭排队、高速公路收费站进出口排队；上下班坐公共汽车,等待公共汽车的排队;顾客到商店购物形成的排队;病人到医院看病形成的排队;售票处购票形成的排队等;另一种排队是物的排队，例如文件等待打印或发送;路口红灯下面的汽车、自行车通过十字路口等等.二、排队论的基本原理1．基本概念1)“排队”与“排队系统”的概念“排队”—单指等待服务的，不包括正在被服务的；“排队系统”—既包括等待服务的，又包括正在被服务的车辆。排队的8辆车排队系统10辆车排队的车辆排队系统中的车辆排队现象是由两个方面构成，一方要求得到服务，另一方设法给予服务。我们把要求得到服务的人或物（设备）统称为顾客,给予服务的服务人员或服务机构统称为服务员或服务台。顾客与服务台就构成一个排队系统，或称为随机服务系统。显然缺少顾客或服务台任何一方都不会形成排队系统.对于任何一个排队服务系统，每一名顾客通过排队服务系统总要经过如下过程：顾客到达、排队等待、接受服务和离去，其过程如下图所示:顾客总体队伍输出输入服务台服务系统2)排队系统的3个组成部分：(1)输入过程就是指各种类型的“顾客(车辆或行人)”按怎样的规律到达。有各式各样的输入过程，例如：定长输入：顾客等时距到达。泊松输入：顾客到达时距符合负指数分布。这种输入过程最容易处理，因而应用最广泛。爱尔朗输入：顾客到达时距符合爱尔朗分布。排队输入输出?爱尔朗分布211)(,1)(0,)!1()()(kTDTEtekktktbktkkkXXX,,,21k为k个相互独立的随机变量；服从相同参数的负指数分布；kXXXT21设，则T的密度函数为如k个服务台串联（k个服务阶段），一个顾客接受k个服务共需的服务时间T，T爱尔朗分布。排队规则损失制排队系统：顾客到达时,若有服务台均被占,服务机构又不允许顾客等待,此时该顾客就自动辞去等待制排队系统：顾客到达时．若所有服务台均被占，他们就排队等待服务。在等待制系统中,服务顺序又分为：先到先服务,即顾客按到达的先后顺序接受服务；后到先服务.混合制排队系统：损失制与等待制的混合，分为队长(容量)有限的混合制系统，等待时间有限的混合制系统，以及逗留时间有限制的混合系统.(2)排队规则是指到达的顾客按怎样的次序接受服务。(3)服务方式(输出):指同一时刻有多少服务台可接纳顾客，每一顾客服务了多少时间。每次服务可以接待单个顾客，也可以成批接待，例如公共汽车一次就装载大批乘客。服务时间的分布主要有如下几种：①定长分布：每一顾客的服务时间都相等（发放物品）；②负指数分布：即各顾客的服务时间相互独立，服从相同的负指数分布(看病)；③爱尔朗分布：即各顾客的服务时间相互独立，具有相同的爱尔朗分布。为叙述方便，引用下列符号，令M代表泊松分布输入或负指数分布服务；D代表定长分布输入或定长分布服务；Ek代表爱尔朗分布的输入或服务。于是泊松输入、负指数分布服务，N个服务台的排队系统可以写成M/M/N；泊松输入、定长服务、单个服务台的系统可以写成M/D/1。同样可以理解M/Ek/N，D/M/N…等符号的含义。如果不附其它说明，则这种符号一般都指先到先服务，单个服务通道的等待制系统。3)排队系统的主要数量指标最重要的数量指标有3个：(1)等待时间即从顾客到达时起到他开始接受服务时止这段时间。(2)忙期即服务台连续繁忙的时期，这关系到服务台的工作强度。(3)队长（顾客数）有排队顾客数与排队系统中顾客之分，这是排队系统提供的服务水平的一种衡量。三、M/M/1系统—单通道服务系统1dw)8nd)711q)6nq)5)1()41n)3)1()()21)0()1//1/1w22排队中的平均等待时间系统中的平均消耗时间非零平均排队长度平均排队长度系统中的平均方差系统中的平均车辆数个顾客的概率为在系统中有率为在系统中没有顾客的概客数。，指的是排队系统的顾系统的状态。所谓状态或交通强度，可以确定叫做服务强度。比率，则平均服务时间为率为服务后通过的平均服务通过接受。排队从单通道服务后，则到达的平均时距为设顾客平均到达率为nnPnP存车量是合理的。认为该出入道的辆的可能性极小，故可数超过计算结果表明排队车辆，，，合适。认为合适，否则认为不），则认为小于辆的概率很小时（一般辆，如果超出因出入道存车量为，系统是稳定的。辆，辆排队系统问题解：这是一个是否合适？辆，问该数量单一的出入车道可存车，服从负指数分布。其辆为场的服务能力为，服从泊松分布。停车辆为今有一停车场，到达率例603.097.01)(1)6(1)6(02.04.06.0)6(03.04.06.0)5(05.04.06.0)4(09.04.06.0)3(14.04.06.0)1()2(24.04.06.0)1()1(4.06.01)1()0(%56616.0100/60//100/601//6/100/60261654322nnPPPPPPPPPPhhMMhh系统，计算公式如下：务的对于单路排队多通道服式亦相同。组成的系统，其计算公系统个况相当于不能随意换队。此种情的一队车辆服务，车辆应队，每个通道只为其相：指每个通道各排一个）多路排队多通道服务服务；道有空就到哪里去接受中头一车辆可视哪条通队条通道服务的情况，排：指排成一个队等待数）单路排队多通道服务的不同，可分为：系统根据车辆排队方式。队长度将趋向于无穷大不稳定，排时系统是稳定的，否则相仿，当为饱和度。和强度，亦可称系统的服务强度或交通称为，则仍记。服务时间是，则每个服务台的平均率为接受服务后的平均输出队行列从每个服务台车辆的平均到达率，排为进入多通道服务系统设服务”系统。条，所以也叫“多通道有排队系统中，服务通道在计算公式NMMMMNNMMNMMNMMNNNMM//1//21//1/1///////1//.1四、M/M/N系统多通道服务方式NkPNNNkPkkPkNNkPNkkkNkNk),0(!),0(.!)2()/1(!!1)0()1(10）（个车辆的概率：系统中有为：系统中没有车辆的概率21)/1()0(.!)3(NPNNnN系统中的平均车辆数：）平均排队长度：（4nq：系统中的平均消耗时间)5(nqd1：排队中的平均等待时间)6(q例3.一加油站，今有2400辆/h的车流量通过4个通道引向4个加油泵，平均每辆车加油时间为5s，服从负指数分布，试按多路多通道系统（4个M/M/1系统）单路多通道系统（M/M/4系统）计算各相应指标。解：按4个M/M/1系统由题意可知：s/6136004/2400辆s/51辆，系统稳定165辆17.46/55nq辆/255301sd辆/306/15snd辆56/516/5)1(n按单路多通道系统M/M/4计算：s/3236002400辆s/51辆310，系统稳定1654310N0213.08642.300617.161651!4310!31010304kkkP）（辆3.36510213.0.4!431025q辆6.63103.3qn辆/5323.3sq辆/10551sd4个M/M/1M/M/4平均车辆数206.6平均排队长16.683.3平均耗时3010平均等候时间255两种系统比较四、简化的排队延误分析方法交通工程师在应用数学上成熟的排队论之外，还对交通拥挤现象以简化的方式作过分析，前提：假定在某一持续时间内车辆的出入是均一的。例：有一公路与铁路的交叉口，火车通过时，栅栏关闭的时间tr=0.1h。已知公路上车辆以均一的到达率＝900(辆／h)到达交叉口，而栅栏开启后排队的车辆以均一的离去率u＝1200(辆／h)离开交叉口。试计算由于关闭栅栏而引起的：单个车辆的最长延误时间tm，最大排队车辆数Q，排队疏散时间t0，排队持续时间tj受限车辆总数n，平均排队车辆数，单个车辆的平均延误时间，车时总延误D。QdhdDhtdQQnhthQrj辆车时总延误为间为单个车辆的平均延误时辆平均排队车辆数辆辆数为受阻车辆总数疏散时间内离去的总车为关闭时间加上疏散时间排队持续时间等于栅栏疏散时净疏散率为向后延长，因此排队的而队尾以到达率疏散离去离去率车排为此栅栏刚开启时排队的只有到达没有离去，因为栅栏刚关1805.036005.01.05.05.0455.036012003.04.03.01.03.0900120090-t间为，-，以队车辆的头栅栏开启后，＝90辆1．0＝900t＝Q车辆数最多栅栏关闭期间，车辆0.1h＝t＝t误时间最长闭时到达的那辆车的延解：0rrm图中虚线为到达车辆累积数，实线为离去车辆累积数。两曲线的水平间隔即为某车的延误时间，垂直间隔为某一时刻的受阻(排队)车数。两曲线围成的面积即为总延误车时数。在此图上用几何方法亦不难求出上例的各项指标。交叉口车辆的排队和延误，但应该指出的是，用此法求出的最大排队车辆数偏低。其原因是：栅栏关闭期间，车辆的停车位置是向上游延伸的，各车的停车时刻早于栅栏开启情形下到达交叉口的时刻，这样，排队的延长率就大于λ，最大排队车辆数也就大于λt.排队论(queuingtheory),或称随机服务系统理论,是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科。也是研究服务系统中排队现象随机规律的学科。总结：排队论广泛应用于计算机网络,生产,运输,库存等各项资源共享的随机服务系统。排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。排队论的意义：利用运筹学之排队论理论可以计算出不同模型下的队长平均等待时间平均逗留时间，能够为服务台数量的确定提供理论依据，既可避免设置过多的服务台导致空闲浪费，也可减少等待时间。理论与实践相互结合，不仅节省了等待的时间，还会得到认同与赞扬，并且对优化排队管理策略，提高的服务水平，提高竞争力以及提高服务营销水平具有重要的指导意义。排队论的应用排队论在通信领域、医疗领域、交通领域、银行领域、图书馆、分配问题中得到了很好的应用。