运筹学课件排队论

1第十三章排队论2一、排队系统的一般表示例1各个顾客由顾客源出发，到达服务机构前排队等候服务，服务完了后就离开。排队结构指队列的数目和排列方式排队规则和服务规则是说明顾客在排队系统中按怎样的规则、次序接受服务的。顾客源排队结构排队规则服务规则服务机构离去顾客到来排队系统第一节基本概念3现实生活中的排队系统序号到达的顾客要求服务内容服务机构1不能运转的机器修理修理技工2修理技工领取修配零件发放修配零件的管理员3病人诊断或做手术医生(或包括手术台)4电话呼唤通话交换台5文件搞打字打字员6提货单提取存货仓库管理员7驶入港口的货船装(卸)货装(卸)货码头(泊位)8上游河水进入水库放水，调整水位水闸管理员4二、排队系统的组成和特征输入即指顾客到达排队系统，可能有以下不同情况。1、输入过程

（1）顾客源的组成有限的无限的（2）顾客到来的方式

一个一个的成批的（3）顾客相继到达的间隔时间确定型的随机型的（4）顾客的到来相互独立的关联的（5）输入过程平稳的，或称对时间是齐次的非平稳的52、排队规则顾客在排队系统中按怎样的规则、次序接受服务的。（1）顾客到达时，所有服务台被占用随即离去的称为即时制（损失制）排队等候称为等待制先到先服务后到先服务随机服务有优先权（2）从队列占用空间有限的无限的（3）从队列的数量单列多列63、服务机构（1）服务员数量没有一个或多个（2）多服务台时1单队—单服务台多队—多服务台（并列）单队—多服务台（并列）12c…12c…7（3）服务方式对单个顾客进行对成批顾客进行（4）服务时间确定型随机型（5）服务时间的分布我们总假定是平稳的，即分布的期望值、方差等参数都不受时间的影响多服务台（串列）12312多服务台混合12c……8三、排队模型的分类1、1953年，D.G.Kendall提出第一种分类方法X/Y/ZX处填写表示相继到达间隔时间的分布;Y处填写表示服务时间的分布;Z处填写并列的服务台的数目.表示相继到达间隔时间和服务时间的各种分布的符号:M—负指数分布D—确定型Ek—k阶爱尔朗分布GI—一般相互独立的时间间隔的分布G—一般服务时间的分布92、1971年关于排队论符号的标准化会议上决定，将Kendall符号扩展成为：X/Y/Z/A/B/C前三项意义不变，而A处填写系统容量限制N；B处填写顾客源数m；C处填写服务规则。约定：10四、排队系统的参数1、队长(Ls)：指在系统中的顾客数。2、排队长(Lq)：指系统中排队等候服务的顾客数。3、逗留时间(Ws)：指一个顾客在系统中的停留时间。4、等待时间(Wq)：指一个顾客在系统中排队等待的时间。Ls=Lq+正被服务的顾客数Ws=Wq+服务时间5、忙期：指从顾客到达空闲服务机构起到服务机构再次空闲止这段时间长度，即服务机构连续繁忙的时间长度。6、系统的状态概率[Pn(t)]

：指系统中的顾客数为n的概率。7、稳定状态：limPn(t)→Pn11一、经验分布例2(P356)某服务机构单服务台，先到先服务，对41顾客记录到达时刻和服务时间s（单位：分钟）如下表，表中第1号顾客到达时刻为0。全部服务时间为127（分钟）。(1)

i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi(1)i(2)τi(3)si(4)ti(5)wi10520512271093612022743619435103827036156722346114552041191282631051247423第二节时间分布12(1)i(2)

τi(3)si(4)ti(5)wi(1)

i(2)τi(3)si(4)ti(5)wi(1)

i(2)

τi(3)si(4)ti(5)wi1349135238662233117447145229324885463412126715611102592137351271231662230269536536129612176515027101242371303371870320281052103813352719724812910613139135241020803103010925040139438218122231114120411421922833323211681013到达间隔分布表服务时间分布表平均间隔时间：=142/40=3.55(分钟/人)平均到达率：41/142=0.28(人/分钟)平均服务率：41/127=0.32(人/分钟)平均服务时间：127/41=3.12(分钟/人)到达间隔(分钟)次数12345678910以上61086322111合计40服务时间(分钟)次数123456789以上10107542111合计4114二、Passion分布设N(t)表示在时间[0,t)内到达顾客数；令Pn(t1,t2)表示在时间区间[t1,t2)（t2>t1）内有n（0）个顾客到达的概率，即Pn(t1,t2)=P{N(t2)–N(t1)=n}（t2>t1，n0）Passion分布的三个条件：无后效性：不相重叠的时间区间内顾客到达数相互独立即在[t,t+△t]内到达一个顾客的概率与t时刻之前到达的顾客数无关。(2)平稳性：在一定的时间间隔内到达一个顾客的概率仅与这段时间间隔的长短有关，而与这段时间的起始时刻无关。(3)普通性：在足够小的时间间隔内只有一个顾客到达，而有两个或以上顾客到达的概率极小。15Pn(t+Δt)=Pn(t)(1-λΔt+o(Δt))+Pn-1(t)λΔt+o(Δt)情况[0,t)[t,t+Δt)[0,t+Δt)个数概率个数概率个数概率(A)(B)(C)nn-1n-2n-3…0Pn(t)Pn-1(t)Pn-2(t)Pn-3(t)…P0(t)0123…n1-λΔt+o(Δt)λΔto(Δt)nnnn…nPn(t)(1-λΔt+o(Δt))Pn-1(t)λΔto(Δt)在上述条件下，研究顾客到达数n

的概率分布16

Pn(t+Δt)=Pn(t)(1-λΔt)+Pn-1(t)λΔt+o(Δt)[Pn(t+Δt)-Pn(t)]/Δt=-λPn(t)+λPn-1(t)+[o(Δt)]/Δt

令Δt0dPn(t)/dt=-λPn(t)+λPn-1(t)Pn(0)=0（n1）dP0(t)/dt=-λP0(t)P0(0)=1（n=0）P0(t)=e

-λt

Pn(t)=[(λt)n

e

-λt

]/nt

>0,n=0，1，2…17三、负指数分布fT（t）=λe-λt

，

t00，t<018一、M/M/1模型1、假设（1）顾客到达的间隔时间满足参数为λ的负指数分布（2）服务时间满足参数为µ的负指数分布（λ<µ）（3）服务机构是单服务台（4）顾客源是无限的，顾客相互独立（5）单队排列，且对队长没有限制第三节单服务台负指数分布排队系统的分析192、Pn的计算O表示发生（1个），×

表示没有发生Pn(t+Δt)=Pn(t)(1-λΔt)(1-μΔt)+Pn+1(t)(1-λΔt)μΔt

+Pn-1(t)λΔt(1-μΔt)+Pn(t)λΔtμΔt情况在时刻t顾客数在区间（t,t+Δt）在时刻t+Δt顾客数到达离去(A)(B)(C)(D)nn+1n-1n××OO×O×Onnnn20整理得：Pn(t+Δt)=Pn(t)(1-λΔt-μΔt)+Pn+1(t)μΔt+Pn-1(t)λΔt+o(t)[Pn(t+Δt)-Pn(t)]/Δt=λPn-1(t)+μPn+1(t)-(λ+μ)Pn(t)(1)Δt0dPn(t)/dt=λPn-1(t)+μPn+1(t)–(λ+μ)Pn(t)考虑P0(t)的情况：P0(t+Δt)=P0(t)(1-λΔt)+P1(t)(1-λΔt)μΔtΔt0dP0(t)/dt=-λP0(t)+μP1(t)(2)由dPn(t)/dt=0得到-λP0+μP1=0(3)λPn-1+μPn+1-(λ+μ)Pn=0(4)21由式(3)得通过求解可得λ——单位时间内到达的平均顾客数μ——单位时间内服务的平均顾客数ρ——服务强度参数意义：223、M/M/1参数计算（1）系统中平均顾客数（Ls）记23（2）队列中等待的平均顾客数（Lq）（3）顾客逗留时间（Ws）（4）队列中顾客等待时间（Wq）24它们的相互关系如下：25例3(P366)100个工作小时内每小时来就诊的病人数n出现次数如下100个完成手术的病例所用时间v(小时)出现的次数如下到达的病人数n出现次数tn0123456102829161061合计100为病人完成手术时间v(小时)出现次数tv0.0-0.20.2-0.40.4-0.60.6-0.80.8-1.01.0-1.21.2以上3825179650合计10026解：27假定系统最大容量为N，单服务台情形排队等待的顾客最多为N-1，下面只考虑稳态情形：二、M/M/1/N/∞模型解得：28根据上式我们可以推导出系统的各项指标：有效到达率λe=λ(1-PN)可以验证：1-P0=λe

/μ(4)顾客等待时间(3)顾客逗留时间(1)队长(2)队列长29例4(P368)单人理发馆有六个椅子接待人们排队等待理发。当6个椅子都坐满时，后来的顾客不进店就离开。顾客平均到达率为3人/小时，理发需时平均15分钟。则：

N=7为系统中最大的顾客数，λ=3人/小时，μ=4人/小时（1）求某顾客一到达就能理发的概率。（2）求需要等待的顾客数的期望值。30（3）求有效到达率。（4）求一顾客在理发馆内逗留的时间。（5）在可能到达的顾客中有百分之几不等待就离开。（人/小时）31机器故障问题：设共有m台机器，机器故障停机表示到达，待修机器形成队列，修理工是服务员。顾客总体虽然只有m个，但每个顾客服务后仍回到总体，仍然可以到来。三、顾客源为有限的情形（M/M/1/∞/m）32根据上式我们可以推导出系统的各项指标：在机器故障问题中Ls就是平均故障台数，而33例5(P371)某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运转时间15分钟，有一个修理工，每次修理时间服从负指数分布，平均每次12分钟。求（1）修理工空闲的概率；（2）五台机器都出故障的概率；（3）出故障的平均台数；（4）等待修理的台数；（5）平均停工时间；（6）平均等待时间；（7）评价这些结果。34解：(7)机器停工时间过长，修理工几乎没有空闲时间，应当提高服务效率以减少修理时间或增加修理工人。(台)(台)(分钟)(分钟)35一、M/M/c第四节多服务台负指数分布排队系统的分析规定各服务台工作相互独立且平均分配服务率相同，即μ1=μ2=…=μc=μ整个服务机构的平均服务率为cμ,

(n≥c)nμ,

(n<c)36用递推法解上述差分方程，可求得状态概率。根据上式我们可以推导出系统的各项指标：37例6(P373)某售票所有三个窗口，顾客到达服从Passion过程，平均到达率每分钟λ=0.9(人),服务(售票)时间服从负指数分布,平均服务率每分钟μ=0.4(人).λ=0.9窗口(1)μ=0.4窗口(2)μ=0.4窗口(3)μ=0.438代入公式得(1)整个售票所空闲的概率（2）平均队长（3）平均等待时间和逗留时间（4）顾客到达后必须等待（即系统中顾客数已有3人）的概率39M/M/c型系统和c个M/M/1系统的比较上例中，排队方式不变，但顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，这就形成3个队列，如下图。每个队列平均到达率为λ=0.9/3=0.3（每分钟），这样原来的系统就变成3个M/M/1型的子系统。窗口(1)μ=0.4窗口(2)μ=0.4窗口(3)μ=0.4λ=0.9λ=0.3λ=0.3λ=0.340现按M/M/1型解决这个问题，并与上表比较：从表中各指标的对比可以看出单队比三队有显著的优越性模型指标(1)M/M/3型(2)M/M/1型服务台空闲的概率顾客必须等待的概率平均队列平均队长平均逗留时间平均等待时间0.0748P(n≥3)=0.571.703.954.39(分钟)1.89(分钟)0.25(每个子系统)0.752.25(每个子系统)9.00(整个系统)10(分钟)7.5(分钟)41系统的状态概率和运行指标如下:二、M/M/c/N/∞42三、M/M/c/∞/m(2)平均故障台数：有效到达率：43（1）等待修理的机器平均数（2）需要修理的机器平均数（3）有效损坏数（4）等待修理时间（5）停工时间例7(P378例8)设有两个修理工人，负责5台机器的正常运行，每台机器平均损坏的概率为每运转一小时1次，两个工人能以相同的平均修复率4（次/小时）修好机器。求:44(1)Lq=P3+2P4+3P5=0.118(3)λe=1×(5-1.094)=3.906(4)Wq=0.118/3.906=0.03小时

(5)Ws=1.094/3.906=0.28小时45服务时间是任意分布的情形：一、M/G/1服务时间T的分布是一般的其它的条件和标准的M/M/1型相同。为了达到稳态，ρ<1这一条件是必要的,其中ρ=λE[T].第五节一般服务时间M/G/1模型46例8(P379例9)有一售票口,已知顾客按平均为2分30秒的时间间隔的负指数分布到达.顾客在售票口前服务时间平均为2分钟.(1)若服务时间也服从负指数分布,求顾客为购票所需的平均逗留时间和等待时间;(2)若经过调查,顾客在售票口前至少要占用1分钟,且认为服从服务时间服从负指数分布是不恰当的;而应服从以下概率密度分布.47(2)令y为服务时间，那么Y=1+X,X服从均值为1的负指数分布。于是48二、M/D/1服务时间是确定的常数，例如在一条装配线上完成一件工作的时间应是常数。自动的汽车的冲洗台，冲洗一台汽车的时间也是常数，