排队理论-2012

1、l第一节 概论l第二节 基本概念l第三节 排队过程分析l第四节 应用举例第一节 概 论l1905，哥本哈根，爱尔朗，电话自动交换机l排队论也称“随机服务系统理论”，是研究广义“需求”与“供给”关系的一种数学理论；l应用于交通延误、通行能力、交通信号配时、停车场、收费站、加油站等交通设施的设计与管理分析，方案制定。l举例：高速公路排队、电话接线排队、网络数据包传输排队等交通流排队理论交通流排队理论l排队论：以概率论为基础。l排队：单指等待服务的车辆。l排队系统：包括等待服务与 正在接受服务的车辆。收费站车辆排队收费站车辆排队第二节第二节 基本概念基本概念一、一、 排队与排队系统排队与排队系统 1

2、）输入过程 指顾客按怎样的规律到来 定长、泊松输入、爱尔朗输入 2）排队规则 指顾客按怎样的次序接受服务 损失制、等待制（先到先得FCFS，后到先得LCFS，优先服务等）、混合制 3）服务方式 指多少个服务台接纳顾客，服务时间。 定长服务、负指数分布、爱尔朗分布二、排队系统的组成部分二、排队系统的组成部分l等待时间Wq 从顾客到达时起至开始接受服务时为止的这段时间l忙期 服务台连续繁忙的时期，关系到服务台的工作强度l队长（Lq 或 L） 有排队顾客数与排队系统中顾客数之分，这是排队系统提供的服务水平的一种衡量 三、排队系统的主要数量指标三、排队系统的主要数量指标 符号表示: X/Y/ZlX 顾

3、客到达时间间隔分布lY - 服务时间分布lZ - 服务台个数lX, Y 可以是:M - 负指数分布D - 确定性的Ek - k阶Erlang分布GI - 一般相互独立的到达时间间隔分布G - 一般(General)时间分布第三节第三节 排队过程分析排队过程分析 扩展符号表示: X/Y/Z/A/B/ClA - 系统容量lB - 顾客源中顾客的数量lC - 服务规则: FCFS, LCFS, 等等.n若省略后三项，即是指下面的情形：若省略后三项，即是指下面的情形： X/Y/Z/ / /FCFS 顾客源顾客源排队系统排队系统排队排队结构结构服务服务机构机构排队规则服务规则服务规则接受接受服务服务后离

4、去后离去1 1、单通道排队服务系统、单通道排队服务系统 M/M/1M/M/1模型模型无限无限输入过程服从输入过程服从参数为参数为 的的PoissonPoisson过程过程单队单队队长无限队长无限先到先服务先到先服务服务时间服从服务时间服从参数为参数为 的的负指数分布负指数分布顾客平均到达率：系统的服务率：，平均服务时间为1/服务强度（利用系数）= / 。确保单通道排队系统稳定的条件： 1（ ） M/M/1 模型模型举例：食堂排队买饭举例：食堂排队买饭 l已知已知: 顾客到达间隔时间分布顾客到达间隔时间分布, 服务方式、服务方式、 服务时间分布服务时间分布. 求求: 队长: Ls - 系统中的顾

5、客数. 排队长(队列长): Lq - 队列中的顾客数. Ls = Lq + 正在接受服务的顾客数 逗留时间: W S- 顾客在系统中的停留时间 等待时间: Wq - 顾客在队列中的等待时间. WS = Wq + 服务时间 忙期, 损失率, 服务强度.排队问题的求解排队问题的求解M/M/1系统设单位时间到达系统的顾客数为设单位时间到达系统的顾客数为 ，单位时间被服务完的顾客，单位时间被服务完的顾客数为数为。由于是单服务台，且顾客源无限，因此，在各种状态。由于是单服务台，且顾客源无限，因此，在各种状态的情况下，系统的的情况下，系统的“出生率出生率”为为，系统的，系统的“死亡率死亡率”为为。系统在稳

6、态情况下的状态转移如下图所示系统在稳态情况下的状态转移如下图所示 0 1 2n-1 nn+1P0 P1 P2 Pn-1 Pn Pn+1 状态转移图状态转移图根据以上状态转移图，可以得出如下平衡方程根据以上状态转移图，可以得出如下平衡方程 001 PP0)(11nnnPPP), 2 , 1(n(6-5)1 系统状态概率系统状态概率Pn(t)的计算的计算由由(6-5)可以递推求解可以递推求解P1，P2，Pn，得到，得到 01PP02102)1 (PPPP0PPnn), 2 , 1(n1设210200,nnPP PPPP10PnnP)1 ( 1n01nnP由，有表示平均到达率与平均服务率之比，称为服

7、务强度表示平均到达率与平均服务率之比，称为服务强度 M/M/1系统 主要指标主要指标l在系统中没有顾客的概率在系统中没有顾客的概率 l在系统中有在系统中有n个顾客的概率个顾客的概率l系统中的平均顾客数（即队长系统中的平均顾客数（即队长Ls）l系统中顾客数的方差系统中顾客数的方差 1n2)1 (0)1P( )(1)nP n【例例1】高速公路收费处设有一个收费通道，汽车到达高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为服从泊松分布，平均到达速率为150辆小时，收费时辆小时，收费时间服从负指数分布，平均收费时间为间服从负指数分布，平均收费时间为15秒辆。求秒辆。求(1)收费处空

8、闲的概率；收费处空闲的概率；(2)收费处忙的概率；收费处忙的概率；(3)系统中分别有系统中分别有1，2，3辆车的概率。辆车的概率。思路：这是思路：这是M/M/1排队系统，关键把参数排队系统，关键把参数算出来。算出来。【解解】根据题意根据题意, =150辆辆/小时小时, 1/=15秒秒=3600/15（小时（小时/辆）辆）,即即240（辆（辆/小时）。小时）。/=150/240=5/8，则有，则有(1)系统空闲的概率为：系统空闲的概率为：P0=1=1(5/8)=3/8=0.375(2)系统忙的概率为：系统忙的概率为：1-P0=5/8=0.625P(0)1- P(0)P(1)、P(2)、P(3)(

9、3)系统中有系统中有1辆车的概率为：辆车的概率为：P(1)=(1)=0.6250.375=0.234系统中有系统中有2辆车的概率为：辆车的概率为：P(2)= 2(1)= 0.2340.625=0.146系统中有系统中有3辆车的概率为：辆车的概率为：P(3)=3(1)=0.1460.625=0.091队长的计算队长的计算101.)2(.)32()1 ( 3232321n0nsnnsLnnPL计算有关指标计算有关指标l队列长队列长 Lq的计算的计算1)1 () 1( 201n10nssnnnnqLPLPnPPnL计算有关指标计算有关指标 逗留时间逗留时间: : 可以证明可以证明, Ws服从参数为服

10、从参数为-的负指数分布的负指数分布. 则则: 等待时间等待时间1 sW1 sqWW服务TWWsq 计算有关指标计算有关指标l平均忙期平均忙期 B , 忙期出现的概率忙期出现的概率 l平均闲期平均闲期 I , 闲期出现的概率闲期出现的概率 (1- )n忙期忙期 B : 闲期闲期 I = : (1- )n平均闲期平均闲期 I = 1 / 闲期的分布与顾客到闲期的分布与顾客到达时间间隔的相同达时间间隔的相同-服从参数为服从参数为 的负的负指数分布指数分布计算有关指标计算有关指标n忙期与闲期忙期与闲期 1-P0= lLittle公式（相互关系）公式（相互关系）qsqsqqssLLWWWLWL 1 小小

11、结结1 sWqW qLsL平均服务平均服务时间时间平均在忙的服务平均在忙的服务台数台数/正在接受正在接受服务的顾客数服务的顾客数有效到达率有效到达率l例题例题6.1 l【解解】根据题意根据题意, 这是一个这是一个M/M/1排队系统，排队系统， =800辆辆/小时小时, 1/=4秒秒=3600/4（小时（小时/辆）辆）,即即900（辆（辆/小时）小时）/=800/900=0.89，则有，则有l(1)系统排队车辆数为：系统排队车辆数为： l(2)平均排队长度为：平均排队长度为：l(3)非零平均排队长度：非零平均排队长度：l(4)系统平均消耗时间系统平均消耗时间 Ls Lq-1Ls -11 qw-1

12、 Ws l(5)系统平均等待时间：系统平均等待时间：1- WsWq l例题6.2l【解】根据题意, 这是一个M/M/1排队系统，=60辆/小时, 100（辆/小时）/=60/100=0.66)很小（一般认为小于5%）则为合适，否则认为不合适。P(6)=1- P(6)=0.03l 计算结果表明排队车辆超过6辆的可能性很小，故该数量是合适的。24二、多通道排队服务系统二、多通道排队服务系统（M/M/N）l单路排队多通道服务单路排队多通道服务l多路排队多通道服务（转化为多路排队多通道服务（转化为M M/ /M M/1/1系统）系统）排队方式：排队方式：排队排队方式方式服务服务台台( (1 1) )

13、一个一个队列队列服务服务台台( (2 2) ) n n个个队列队列多通道排队服务系统多通道排队服务系统（M/M/N）l ：各通道的平均值。l主要指标计算 参考教材 P119120 公式 （6.216.21）（）（6.266.26）1N确保系统稳定的条件：确保系统稳定的条件：服务方式比较服务方式比较lP120 例题例题6.3l【解】l（1）根据题意, 可看成四个平行的M/M/1排队系统，把总车流四等分，于是对每个通道有：=2400/4=600辆/小时, 3600/5=720（辆/小时）/=600/720=5/61，系统稳定。l则排队系统主要指标为：l系统队长 Ls=/(1- )=5 (veh/h

14、)l排队长 Lq=Ls = 5 5/6=4.17l逗留时间 Ws= 1/ (- ) = 1/120(h)=30 (sec)l排队时间 Wq= Ws 1/ = 30-5=25(sec)l(2)如按照 M/M/4排队系统计算，则=2400 辆/小时=2/3 辆/秒, 3600/5=720（辆/小时）=/=3600/720=10/3 1，系统稳定。l对M/M/N系统，先把P(0)，队长Ls计算出来，其它指标可以由这两个指标推算出来。l则排队系统主要指标为：l系统队长l系统队长 Lq=Ls =6.6-3.3=3.3l逗留时间 Ws=Wq+1/=Ls/ =10l排队时间 Wq= Lq/ =50213.

15、0)/1 ( !1)0(10NkNkNNkP6 . 63/20)/1 ()0(!21NPNNLsN表表6.1lN N 相同时，单路排队优于多路排队，系统疏散快。相同时，单路排队优于多路排队，系统疏散快。多路排队多通道多路排队多通道服务服务单路排队多通道单路排队多通道服务服务系统中车辆数系统中车辆数5 5* *4=204=20辆辆6.66.6辆辆平均排队长度平均排队长度4.174.17* *4=16.684=16.68辆辆3.33.3辆辆系统中消耗时间系统中消耗时间30 30 秒秒/ /辆辆1010秒秒/ /辆辆平均排队时间平均排队时间2525秒秒/ /辆辆5 5 秒秒/ /辆辆服务方式服务方式

16、服务指标服务指标三、一般服务时间三、一般服务时间 M/G/1M/G/1模型模型lM/G/1-泊松输入、一般分布的服务时间，系统容量和顾客源均无限制的单服务台排队系统。l假设服务时间的期望E()和方差D()存在，服务强度= /E() 12）LqWsWq课后作业题课后作业题1二、道路瓶颈排队分析l例题例题 在一条单方向三车道的高速公路基本路段，发生了一起交通事故，导致两条车道堵塞，道路通行能力下降，在事故发生地点引起车辆排队（可用车道通行能力的百分数见下表）。假设上游车辆到达率为918辆/h，求该地点的交通强度，以及排队系统中的平均车辆数、平均排队长度、排队平均等待时间，及系统中车辆数超过5辆的概率（取高速公路单车道基本路段的CB=2000辆/h）。服务强度M/M/1 模型=918=？l【解解】：根据题意，三车道的高速公路堵塞二车道后，可用车道通行能力为：C=2000*3*0.17=1020（辆/h）l因为上游车辆到达率为918辆/h，且三车道已堵塞二车道，一次，可以将派排队车辆看作M/M/1队列。l该地点的交通强度为：= /C=918/1020=0.9 5)单向车道单向车道数数路肩故障路肩故障路肩事故路肩事故堵塞车道数堵塞车道数12320.950.810.350N/A30.990.830.490.170课后作业题课后作业题2三、延误分析l【例例】在