6排队理论-2012.

第6章排队理论及应用第一节概论第二节基本概念第三节排队过程分析第四节应用举例第一节概论1905，哥本哈根，爱尔朗，电话自动交换机排队论也称“随机服务系统理论”，是研究广义“需求”与“供给”关系的一种数学理论；应用于交通延误、通行能力、交通信号配时、停车场、收费站、加油站等交通设施的设计与管理分析，方案制定。举例：高速公路排队、电话接线排队、网络数据包传输排队等交通流排队理论排队论：以概率论为基础。排队：单指等待服务的车辆。排队系统：包括等待服务与正在接受服务的车辆。收费站车辆排队第二节基本概念一、排队与排队系统1）输入过程指顾客按怎样的规律到来定长、泊松输入、爱尔朗输入2）排队规则指顾客按怎样的次序接受服务损失制、等待制（先到先得FCFS，后到先得LCFS，优先服务等）、混合制3）服务方式指多少个服务台接纳顾客，服务时间。定长服务、负指数分布、爱尔朗分布二、排队系统的组成部分等待时间Wq–从顾客到达时起至开始接受服务时为止的这段时间忙期–服务台连续繁忙的时期，关系到服务台的工作强度队长（Lq或L）–有排队顾客数与排队系统中顾客数之分，这是排队系统提供的服务水平的一种衡量三、排队系统的主要数量指标–符号表示:X/Y/ZX–顾客到达时间间隔分布Y--服务时间分布Z--服务台个数X,Y可以是:–M--负指数分布–D--确定性的–Ek--k阶Erlang分布–GI--一般相互独立的到达时间间隔分布–G--一般(General)时间分布第三节排队过程分析–扩展符号表示:X/Y/Z/A/B/CA--系统容量B--顾客源中顾客的数量C--服务规则:FCFS,LCFS,等等.若省略后三项，即是指下面的情形：X/Y/Z///FCFS顾客源排队系统排队结构服务机构排队规则服务规则接受服务后离去1、单通道排队服务系统M/M/1模型无限输入过程服从参数为的Poisson过程单队队长无限先到先服务服务时间服从参数为的负指数分布顾客平均到达率：λ系统的服务率：μ，平均服务时间为1/μ服务强度（利用系数）ρ=λ/μ。确保单通道排队系统稳定的条件：ρ1（λμ）M/M/1模型举例：食堂排队买饭已知:顾客到达间隔时间分布,服务方式、服务时间分布.求:–队长:Ls--系统中的顾客数.排队长(队列长):Lq--队列中的顾客数.Ls=Lq+正在接受服务的顾客数–逗留时间:WS--顾客在系统中的停留时间等待时间:Wq--顾客在队列中的等待时间.WS=Wq+服务时间–忙期,损失率,服务强度.排队问题的求解M/M/1系统设单位时间到达系统的顾客数为λ，单位时间被服务完的顾客数为μ。由于是单服务台，且顾客源无限，因此，在各种状态的情况下，系统的“出生率”为λ，系统的“死亡率”为μ。系统在稳态情况下的状态转移如下图所示012n-1nn+1…P0P1P2Pn-1PnPn+1状态转移图根据以上状态转移图，可以得出如下平衡方程001PP0)(11nnnPPP),2,1(n(6-5)1系统状态概率Pn(t)的计算由(6-5)可以递推求解P1，P2，…，Pn，…，得到01PP02102)1(PPPP0PPnn),2,1(n1设210200,,,nnPPPPPP10PnnP)1(1n01nnP由，有ρ表示平均到达率与平均服务率之比，称为服务强度…………M/M/1系统主要指标在系统中没有顾客的概率在系统中有n个顾客的概率系统中的平均顾客数（即队长Ls）系统中顾客数的方差1n2)1((0)1P()(1)nPn【例1】高速公路收费处设有一个收费通道，汽车到达服从泊松分布，平均到达速率为150辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求(1)收费处空闲的概率；(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)(3)系统中有1辆车的概率为：P(1)=ρ(1－ρ)=0.625×0.375=0.234系统中有2辆车的概率为：P(2)=ρ2(1－ρ)=0.234×0.625=0.146系统中有3辆车的概率为：P(3)=ρ3(1－ρ)==0.146×0.625=0.091队长的计算计算有关指标队列长Lq的计算1)1()1(201n10nssnnnnqLPLPnPPnL计算有关指标–逗留时间:可以证明,Ws服从参数为μ-λ的负指数分布.则:–等待时间1sW1sqWW服务TWWsq计算有关指标平均忙期B,忙期出现的概率平均闲期I,闲期出现的概率(1-)忙期B:闲期I=:(1-)平均闲期I=1/闲期的分布与顾客到达时间间隔的相同----服从参数为的负指数分布计算有关指标忙期与闲期1-P0=Little公式（相互关系）qsqsqqssLL小结1sWqWqLsL平均服务时间平均在忙的服务台数/正在接受服务的顾客数有效到达率例题6.1【解】根据题意,这是一个M/M/1排队系统，=800辆/小时,1/μ=4秒=3600/4（小时/辆）,即μ＝900（辆/小时）ρ＝λ/μ=800/900=0.89，则有(1)系统排队车辆数为：(2)平均排队长度为：(3)非零平均排队长度：(4)系统平均消耗时间LsLq-1Ls-11qw-1Ws(5)系统平均等待时间：1-WsWq例题6.2【解】根据题意,这是一个M/M/1排队系统，=60辆/小时,μ＝100（辆/小时）ρ＝λ/μ=60/100=0.61，系统稳定。因为单一出入道可存车6辆，如果排队车辆超过6辆的概率P(6)很小（一般认为小于5%）则为合适，否则认为不合适。P(6)=1-P(6)=1-P(0)-P(1)…P(6)P(0)=1-ρ=0.4,P(1)=ρP(0)=0.6*0.4=0.24P(2)=ρP(1)=….P(6)=0.03P(6)=0.03计算结果表明排队车辆超过6辆的可能性很小，故该数量是合适的。24二、多通道排队服务系统（M/M/N）单路排队多通道服务多路排队多通道服务（转化为M/M/1系统）排队方式：排队方式服务台(1)一个队列服务台(2)n个队列多通道排队服务系统（M/M/N）：各通道ρ的平均值。主要指标计算参考教材P119～120公式（6.21）～（6.26）1N确保系统稳定的条件：服务方式比较P120例题6.3【解】（1）根据题意,可看成四个平行的M/M/1排队系统，把总车流四等分，于是对每个通道有：=2400/4=600辆/小时,μ＝3600/5=720（辆/小时）ρ＝λ/μ=600/720=5/61，系统稳定。则排队系统主要指标为：系统队长Ls=ρ/(1-ρ)=5(veh/h)排队长Lq=Ls–ρ=5–5/6=4.17逗留时间Ws=1/(μ-λ)=1/120(h)=30(sec)排队时间Wq=Ws–1/μ=30-5=25(sec)(2)如按照M/M/4排队系统计算，则=2400辆/小时=2/3辆/秒,μ＝3600/5=720（辆/小时）=ρ＝λ/μ=3600/720=10/31，系统稳定。对M/M/N系统，先把P(0)，队长Ls计算出来，其它指标可以由这两个指标推算出来。则排队系统主要指标为：系统队长系统队长Lq=Ls–ρ=6.6-3.3=3.3逗留时间Ws=Wq+1/μ=Ls/λ=10排队时间Wq=Lq/λ=50213.0)/1(!!1)0(10NkNkNNkP6.63/20)/1()0(!21NPNNLsN表6.1N相同时，单路排队优于多路排队，系统疏散快。多路排队多通道服务单路排队多通道服务系统中车辆数5*4=20辆6.6辆平均排队长度4.17*4=16.68辆3.3辆系统中消耗时间30秒/辆10秒/辆平均排队时间25秒/辆5秒/辆服务方式服务指标三、一般服务时间M/G/1模型M/G/1------泊松输入、一般分布的服务时间，系统容量和顾客源均无限制的单服务台排队系统。假设服务时间μ的期望E(μ)和方差D(μ)存在，服务强度ρ=λ/E(μ)1,则系统运行指标计算公式如下：）（-12)D(Ls22LsWs)E(-WsWq-LsWqLq定长服务时间M/D/1模型M/D/1------可看作M/G/1排队系统的一种特殊情形，即μ≡E(μ)，D(μ)=0。系统运行指标计算公式如下：）（）（-12-12)D(Ls222LsWs-Ws)E(-WsWq-LsWqLq第四节应用举例一、收费站排队分析例题某公路收费入口设有一个收费亭，收费亭的收费时间服从负指数分布，平均收费时间为7.2s/辆，汽车的到达率为400辆/h，服从柏松分布。试求：–收费亭空闲的概率–收费亭前无车辆排队的概率–收费亭排队长度超过12辆的概率–平均排队长度–车辆通过收费亭花费时间平均值–车辆平均排队时间P(0)P(0)+P(1)P(12）LqWsWq课后作业题1二、道路瓶颈排队分析例题在一条单方向三车道的高速公路基本路段，发生了一起交通事故，导致两条车道堵塞，道路通行能力下降，在事故发生地点引起车辆排队（可用车道通行能力的百分数见下表）。假设上游车辆到达率为918辆/h，求该地点的交通强度，以及排队系统中的平均车辆数、平均排队长度、排队平均等待时间，及系统中车辆数超过5辆的概率（取高速公路单车道基本路段的CB=2000辆/h）。服务强度ρM/M/1模型λ=918μ=？？【解】：根据题意，三车道的高速公路堵塞二车道后，可用车道通行能力为：C=2000*3*0.17=1020（辆/h）因为上游车辆到达率λ为918辆/h，且三车道已堵塞二车道，一次，可以将派排队车辆看作M/M/1队列。该地点的交通强度为：ρ=λ/C=918/1020=0.91,系统稳定系统平均车数Ls，平均排队长度Lq，排队平均等待时间Wq，系统车辆超过5辆的概率P(5)单向车道数路肩故障路肩事故堵塞车道数12320.950.810.350N/A30.990.830.490.170课后作业题2三、延误分析【例】在某高速公路的入口匝道，因意外情况关闭了tr=0.15h。已知车辆以相同的到达率λ=800辆/h到达匝道，而入口开启后排队的车队以相同的离去率μ=1200辆/h离开匝道。试计算由于匝道关闭而引起的：（1）单个车辆的最大延误时间tm；（2）最大排队车辆数Qm；（3）排队疏散时间t0；（4）排队持续时间t1；（5）受阻车辆总数n；（6）平均排队车辆总数Q；（7）单个车辆的平均延误时间d；（8）车时总延误D。车辆到达离去曲线2020年1月12日星期日37离去率μ到达率λt0t1nd总延误D课后作业题3