服务系统规划(运筹学)

第九章

服务系统规划第11章排队论29.1

基本概念

一。现实生活中的排队现象

排队、顾客、服务台

服务系统、排队系统

到达时刻、

等待时间、排队系统顾客源等待队列(输入)服务台(输出)离去到达到达开始服务离去离去时刻等待时间服务时间逗留时间t服务时间、逗留时间表9-1现实中的各种服务系统顾客服务内容服务台考生报名登记招考登记员病人诊断病情医生电话呼叫通话交换台驶入港口的货船装（卸）货装（卸）货码头（泊位）文件稿打字打字员提货单提取存货仓库管理员不能运转的机器修理修理技工上游河水进入水库放水，调整水位水闸管理员进入我方阵地的敌机我方高射炮进行射击我方高射炮第11章排队论49.1

基本概念二、

排队系统的三个基本特征

(1)

输入过程：指顾客按怎样的规律到达，顾客源情况如何；

(2)

排队规则：指顾客在排队系统中按怎样的规则与次序接受服务；

(3)

服务机构：指同一时刻服务台能容纳多少顾客以及为任一顾客服务的时间服从什么规律。1.输入过程

⑴顾客的总体（顾客源）的组成可能是有限的，也可能是无限的。

⑵顾客到来的方式可能是一个一个的，也可能是成批的。⑶顾客相继到达的间隔时间可以是确定型的，也可以是随机型的。

⑷顾客的到达可以是相互独立的,否则就是有关联的

⑸输入过程可以是平稳的，或称对时间是齐次的，是指描述相继到达的间隔时间分布和所含参数（如期望值、方差等）都是与时间无关的，否则称为非平稳的。第11章排队论69.1

基本概念

(1)定长输入：顾客严格按照固定的间隔时间相继到达。(2)泊松输入：顾客到达过程为泊松流。(3)爱尔朗输入：相继到达间隔时间相互独立且具有相同参数的爱尔朗分布。(4)一般独立输入：相继到达间隔时间相互

独立且同分布。几种常见的输入过程第11章排队论79.1

基本概念

先到先服务：

后到先服务：

随机服务：

有优先权服务：二、排队规则(1)

即时制(损失制)

(2)

等待制

系统容量有限：

等待时间有限：

逗留时间有限：(3)

混合制最普通手枪射击车船卸货停车场电话呼叫生产线上产品抽样检验加急电报特诊患者某些诊室每天挂号有限商店食品药房药品出炉铁水来犯敌机第11章排队论89.1

基本概念

121s⋮

(a)单队—单台系统(b)单队—多台（并联）系统(c)单队—多台（串联）系统3.服务机构常见的几种排队系统的结构如图所示1s…第11章排队论99.1

基本概念

12s(d)多队—多台（并联）系统(e)多队—多台（混联、网络）系统第11章排队论109.1

基本概念

几种常见的随机服务过程(1)

定长服务：为各顾客服务的时间是相同常数(2)

指数服务：为各顾客服务的时间相互独立且具有相同参数的指数分布。(3)

爱尔朗服务：各顾客服务时间相互独立且具有相同参数的爱尔朗分布。(4)

一般独立服务：各顾客服务时间相互独立且同分布。第11章排队论119.1

基本概念三、

排队论的问题及分类1、排队论的问题

(1)

性态问题：

(2)

统计问题：

(3)

优化问题：2、排队系统的分类将Kendall符号扩充为以下标准形式：X/Y/Z/A/B/C或者[X/Y/Z]:[A/B/C]例如：M/M/s/r/∞M/Ek/1/∞稳态系统统计分析优化设计优化运营第11章排队论1211.1

基本概念

L——平均队长

任意时刻系统内顾客数的期望值

Lq——平均等待队长任意时刻系统内等待服务的顾客数的期望值

W——平均逗留时间任一顾客逗留时间的期望值

Wq——平均等待时间任一顾客等待时间的期望值(1)

四项主要性能指标四、排队问题的求解第11章排队论1311.1

基本概念(2)

其他常用数量指标

s

——

系统中并联服务台的数目

λ——平均到达率单位时间内到达系统的顾客平均数

——平均到达间隔

μ——平均服务率单位时间内服务完毕的顾客平均数

——平均服务时间

ρ

——服务强度每个服务台单位时间内的平均服务时间1μ1λ第11章排队论14

N——稳态系统任意时刻的状态(顾客总数)

U——任意顾客在稳态系统中的逗留时间

Q——任意顾客在稳态系统中的等待时间

Pn=P{N=n}:

稳态系统任意时刻状态为n的概率；特别当n=0时，即为P0，而P0即稳态系统所有服务台全部空闲的概率。

λe——

有效平均到达率单位时间内到达并且进入系统的顾客平均数；

对于等待制的排队系统，有λe

=λ。

第11章排队论15稳态系统：假定λ为常数，则有李特尔公式：假定μ为常数，则有(11-1a)(11-1b)(11-1c)(11-1d)(11-2)(11-3)L=

WλeLq=

Wqλe1μW=Wq+L=Lq+λeμ还有L=nPnn=0

∞Lq=(n-s)Pn=nPs+mn=s∞n=0∞第11章排队论169.2

排队系统的常用分布

一、泊松过程

设以X(t)表示在[0,t]时段内到达排队系统的顾客数,则对于每个给定的时刻t,X(t)都是一个随机变量,而{X(t)|t∈[0,∞)}就是一个随机过程。

(1)

无后效性

对任意时刻∈(0,∞)，在时段[,

+t]内到达的顾客数，与时刻以前到达的顾客数无关，即时刻以前到达的顾客数不影响其后到达的顾客数。这意味着：在不相交的各时段内到达的顾客数相互独立。

第11章排队论17(2)平稳性

在长度为t的时段内恰好到达k个顾客的概率，仅跟长度t有关，而跟这段的起始时刻无关。即对任意时刻∈(0,∞)

，在(,

+t]或(0,t]内恰好到达k个顾客的概率相等：

P{X(

+t)-X(t)=k}=

P{X(

t)-X(0)=k}=P{X(

t)=k}Δ=gk(t)(3)普通性：在充分小的时段内最多到达一个顾客。第11章排队论18

泊松过程具有无后效性，因而是一种特殊的马尔科夫过程。泊松过程又称泊松流，在排队论中常称为最简单流。

性质1

设{X(t)|t∈[0，∞)}为泊松过程，λ>0为平均到达率，则X(t)服从参数为λ的泊松分布，即有E[X(t)]

=

tλ=

E[X(t)]/tλ按概率论，有则有(t)kn!Pn(t)=

e-λt

k=0,1,2,…λ(11-4)第11章排队论19

性质2

顾客到达过程{X(t)}是一个具有参数λ的泊松流的充要条件是：相继到达间隔{Tk}是一族相互独立的随机变量，且每个随机变量Tk都具有下述指数分布函数：FTk(t)=1-e-λt,t≥00

,t<0E(Tk)=1λ按概率论，有(11-5)(11-6)k=1,2,…随机变量T的概率密度为数学期望

方差

标准差

第11章排队论21

二、指数服务分布

设以随机变量Vi表示为第i个顾客服务的时间，则{Vi}也是一组随机变量。若各Vi相互独立且具有相同参数μ>0的密度函数：

则称Vi服从参数为μ的指数分布,有

FVi

(t)

=1-e-μt

，t≥0

0，

t<0E(Vi)=1μD(Vi)=1μ2fVi

(t)

=μe-μt

，t≥00，

t<0i=1,2,…(11-7)(11-8)(11-9)第11章排队论22

性质1

设任一顾客的服务时间V服从参数为μ的指数分布，则对任意s>0与t≥0都有

P{T

≥s+t|T≥s}=

P{T≥t}

性质2

密度函数fT(t)对时间t严格递减

第11章排队论23三、爱尔朗分布若随机变量V具有下述密度函数:fk(t)=(kμ)ktk-1(k-1)!e-kμt0t≥0t<0

则称V服从参数为μ的k阶爱尔朗分布,有E(V)=1μD(V)=1μ2k(11-11)k=1,2,…k=1,2,…

(11-12)第11章排队论24

性质1

(1)

当k=1时，爱尔朗分布就成为指数分布；

(2)

当k变大时，方差D(V)=1/kμ2变小，V的取值密集于均值1/μ附近，爱尔朗分布就近似于正态分布；

性质2

设随机变量V1,V2,…,Vk相互独立且服从具有相同参数kμ的指数分布。设爱尔朗分布就转化为定长分布。(3)当k→∞时，D(V)

→

0,V趋近于常数1/μ,则V〜Ek(μ)。

i=1kV=V1+V2+…+Vk=∑Vi25例.到达只有一台加油设备的加油站的汽车为泊松流，平均到达率为60台/小时，由于加油站面积小比较拥挤，到达的汽车中平均每4台中有1台不进入站内而离去。这种情况下排队等待加油的汽车的队列（不计正在加油的）为3.5台，求进入该加油站汽车等待加油的平均时间。Lq=

Wqλe根据，可得3.5/45=0.077h=4.62min26练习:一个有两名服务员的排队系统，该系统最多容纳4名顾客。当系统处于稳定状态时，系统中恰好有n名顾客的概率为，p0=1/16,p1=4/16,p2=6/16,p3=4/16,p4=1/16。试求（1）系统中的顾客平均数Ls(2)系统中平均排队的顾客数Lq（3）某一时刻正在被服务的顾客的平均数（4）若顾客的平均到达率为2人/h，求顾客在系统中的平均逗留时间Ws（5）若两名服务员具有相同的服务效率，利用（4）的结果求服务员服务一名顾客的平均时间。27练习:顾客按泊松流到达某餐厅,平均每小时20人,该餐厅每天11点开始营业,试求(1)上午11:07餐厅内有18人,到11:12餐厅内有20名顾客的概率.假设就餐的顾客尚未就餐完毕离去。(2)若前一名顾客于上午11:25到达,则下一名于上午11:28至11:30之间到达的概率.28练习:一个有两名服务员的排队系统，各自独立为顾客服务，服务时间均为平均值为5分钟的指数分布。设顾客甲到达时两名服务员均空闲，5分钟后顾客乙到达，这时甲未服务完，再过10分钟后第三名顾客丙到达，这时甲与乙都未服务完毕。试回答下列情况的概率。（1）甲在乙之前结束服务（2）丙在甲之前结束服务（3）丙在乙之前结束服务29练习:一个顾客来到有2名并联服务员的排队系统，服务员的服务时间均为平均值为10分钟指数分布，分别求下列情况的概率。（1）到达时两名服务员均忙碌，则该顾客需要等待时间t1的概率分布f(t1)（2)若该顾客已经等了5分钟，则需等待时间为t2的期望值。（3）若该顾客到达时前面已经有2人在等待，则轮到他被服务时所需时间t3的期望值及标准差。生灭过程

生：一个新顾客的到达灭：一个服务完毕顾客的离去假定：顾客到达是泊松流，服务时间服从负指数分布。圆圈中的数字表示系统的状态（顾客数），箭头表示从一个状态到另一个状态的转移。当系统处于稳态时，对于每个状态来说，转入率应该等于转出率。07/12--31--状态转入率等于转出率012.N-1Nu1p1=λ0p0λ0p0+u2p2=(λ1+u1)p1λ1p1+u3p3=(λ2+u2)p2λn-2pn-2+unpn=(λn-1+un-1)pn-1λn-1pn-1+un+1pn+1=(λn+un)pn

令(n=1,2…..)(n=1,2…..)例:一个具有4个状态的生灭过程的有关数据如表所示,求处于稳态时各状态的概率.n01234λn23210un0341234练习:汽车按泊松分布到达只有一套加油设备的加油站，平均15辆/小时，当加油站已有n台汽车在加油或者等待加油时，新到达汽车将按n/3的概率离去，又每辆车加油时间为平均4分钟的负指数分布，试（1）画出上述排队系统的生灭过程发生率图（2）求处于稳态时系统处于各状态的概率。练:某小型超市有一个收款台.交款顾客按每小时30人的泊松流到达.当收款台前只有一名顾客时,由一名收款员单独服务.收款时间服从平均为15分钟的负指数分布.当有两名或以上顾客时,将增加一名助手用于共同为顾客服务.收款时间缩至平均为1分钟的负指数分布.要求:(1)画出上述排队系统的生灭过程发生率图(2)求收款台前有n名顾客的概率.第三节单服务台排队模型一、标准的M/M/1模型

设平均到达率为λ，平均服务率为u。并设λ＜u（否则队列将排至无限远而使系统不能达到稳态）。

设(否则队列将排至无限长)，由概率的性质可知,将Pn的关系代入，得因此，系统状态为n的概率：由（9-20）式，

=1-P0，它描述了服务机构的繁忙程度；所以又称服务机构的利用率。第三节

单服务台模型第九章服务系统规划以（9-20）式为基础，可以算出系统的各个运行指标。⑴在系统中的平均顾客数（队长期望值）(2)在队列中等待的平均顾客数（队列长期望值）第三节

单服务台模型第九章服务系统规划或者关于顾客在系统中逗留的时间W(随机变量)，在M/M/1情形下，它服从参数为-

的负指数分布，即分布函数

概率密度⑶在系统中顾客逗留的时间的期望值⑷在队列中顾客等待时间的期望值第三节

单服务台模型第九章服务系统规划以上公式总结：第三节

单服务台模型第九章服务系统规划它们之间的关系如下：称为Little(李特尔)公式例9-1在集装箱堆场中的作业集装箱泊位遵从先到先服务，车辆经过作业泊位服从负指数分布，每辆车平均需要15分。车辆进入车道服从泊松分布，平均每小时3辆。解：对此队列分析如下：模型为M/M/1//.(1)先确定参数值：由题意知，这是单服务台模型系统，有=3(辆/小时)=60/15=4(辆/小时)

故服务强度为=/=3/4=0.75(2)

计算稳态概率

p0=1-=1-0.75=0.25;pn=np0其中，p0是车道空闲的概率，也是车辆不必等待立即就能进入车道的概率。而车辆需要等待的概率，也是车道繁忙的概率为p(n>0)=1-p0==1-0.25=0.75第三节

单服务台模型第九章服务系统规划⑶计算系统的主要工作指标：此模型的平均有效到达率，即是到达率第三节

单服务台模型第九章服务系统规划⑷为使车辆平均逗留时间不超过半小时，车辆经过车道的平均时间应减少到多少？由于将=3代入上式解得：≥5车辆经过车道的平均时间为即车辆经过车道的平均时间至少应减少3分。第三节

单服务台模型第九章服务系统规划练：汽车按泊松流到达某高速公路收费口，平均每小时90辆。每辆车通过收费口的时间服从均值35秒的负指数分布。

（1）在收费口有多于2辆车排队等待的概率是多少？

（2）因司机们抱怨等待时间太长，管理部门拟采用自动收款装置使平均收费时间缩短到30秒，但条件是原收费口平均等待车辆超过6辆，且新装置的利用率不低于75％时才采用，问新装置能否被采用？

解：这是M/M/1排队模型。

（1）λ=90（辆/小时），原收费口平均服务u=3600/35（辆/小时），ρ=λ/u=0.875<1。

在原收费口有多于2辆车排队等待的概率就是系统中有多于3辆车的概率，即等于

1-P0-P1-P2-P3=ρ4=（0.875）4=0.5862

（2）原收费口平均等待车辆数为

Lq=ρ2/（1-ρ）=（0.875）2/（1-0.875）=6.125

采用新装置后的平均服务u'=3600/30=120（辆/小时），相应的利用率ρ'=λ/u'=90/120=0.75.因此新装置能被采用。

练：某场篮球比赛前来到体育馆某售票口买票的观众按泊松分布到达，平均60人/h，设该售票口售票速度服从指数分布，平均售一张票时间为20秒，试回答：（1）如有一个球迷于比赛前2分钟到达，并设买到票后需要1.5min后才能找到座位坐下，求该球迷在比赛开始前找到座位坐下的概率。（2）如该球迷希望99%的把握在比赛开始前找到座位坐下，则他至少应提前多少分钟到达售票口。

二、系统的容量有限的情况（M/M/1/N/）若系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如果系统中已有N个顾客，那么这个顾客就被拒绝进入系统（如图9-4）。第三节

单服务台模型第九章服务系统规划图9-4有容量限制的情形当N=1时，为即时制的情形；当N→

，为容量无限制的情形。若只考虑稳态的情形，各状态间概率强度的转换关系如图9-5。第三节

单服务台模型第九章服务系统规划图9-5状态间概率强度的转换关系根据图9-5列出状态概率的稳态方程：解此方程与解（9-18）与（9-19）是相似的，不同的是令，得第三节

单服务台模型第九章服务系统规划对于的取值略去=1

情形的讨论。当容量没有限制时，设

<1，这既是实际问题的需要，也是无穷级数收敛所必需的。当系统容量为有限数N时，此条件就是多余的。第三节

单服务台模型第九章服务系统规划关于有效到达率e当研究顾客在系统平均逗留时间Ws和队列中平均等待时间Wq时，尽管（9-22）式仍可利用，但要注意平均到达率是在系统中有空时的平均到达率，当系统已满(n=N)时，则到达率为0，因此需要求出有效到达率e=

(1-PN)可验证：,即λe=μ(1-P0)第三节

单服务台模型第九章服务系统规划根据（9-25）可以得出以下指标：(1)队长（期望值）(2)队列长（期望值）(3)顾客逗留时间（期望值）

(4)顾客等待时间（期望值）第三节：单服务台模型第九章服务系统规划此模型系统的性能指标（当1

时）第三节

单服务台模型第九章服务系统规划例9-2集装箱堆场的某作业集装箱泊位共7个。当7个处理台都满时，后来到的集装箱不进入该作业线。集装箱的平均到达率为3个/分钟，处理一个集装箱平均需要15分。解：则N=7为系统中最大的顾客数，=3个/小时，=4个/小时。(1)由题意知，模型为（M/M/1/N/）先确定参数：由题意知，服务强度=/=3/4=0.75(2)求某集装箱一到达就能进行作业的概率。这种情形相当于作业线内没有集装箱，所求概率第三节

单服务台模型第九章服务系统规划(3)求作业线上集装箱的期望值；需要等待的集装箱的期望值(4)求有效到达率λe

λe=μ(1-P0)=4*(1-0.2778)=2.89(个⁄小时)(5)求一集装箱在作业线内逗留的期望时间；等待时间(6)在可能到来的集装箱进入其它作业线的概率(Pn≥7)。这就是求作业线内有7个集装箱的概率第三节

单服务台模型第九章服务系统规划练：一个有一套洗车设备的洗车店，要求洗车的车辆平均每4分钟到达一辆，洗每辆车平均需要3分钟，以上均服从指数分布。该店现有两个车位，当店内无车时，到达车辆全部进入，当有一辆车时，只有80%进入，当有两辆车时，新到达车辆因无空位而全部离去。试问：

（1）对此排队系统画出生灭过程发生率图。

（2）求洗车设备平均利用率，及一辆进入该店的车辆在店内的平均逗留时间。

（3）为减少顾客流失，店里拟扩大租用第3个车位，这样当店内已有2辆车时，到达车辆有60%进入，有3辆车时，新到达车辆仍全部离去。经计算当租用第3车位时，该洗车店内有n辆车的概率如下P0=0.416,P1=0.312,P2=0.187,P3=0.085如果该车店每天营业12小时，新车位租金每天100元，洗一辆车的净利润5元，问第3个车位是否值得租用。

三、顾客源有限的情形(M/M/1//m)该模型中，设顾客总数为m，当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源。如此循环往复。模型符号的第4项为，表示系统的容量没有限制，但实际上它决不会超过m，所以跟写成(M/M/1/m/m)的意义相同。典型的有限顾客源问题是机器维修问题。有m台机器在运转，单位时间内平均出现故障的机器数即为顾客平均到达率，修理工修理一台设备的平均时间即为平均服务时间，已修复的机器仍可能再出现故障（如图9-6）。第三节

单服务台模型第九章服务系统规划图9-6有限顾客源问题关于平均到达率在无限源的情形是按全体顾客来考虑的；在有限源的情形必须按每个顾客来考虑。为简单起见，设各个顾客的到达率都是相同的（的含义是每台机器单位运转时间内发生故障的概率或平均次数），这时在系统外的顾客平均数为m-Ls，对系统的有效到达率e应为e=(m-Ls)第三节

单服务台模型第九章服务系统规划对于此模型的分析依然可以沿用前面的方法。在稳态的情况下，考虑状态间的转移率如图9-7所示。第三节

单服务台模型第九章服务系统规划图9-7状态转移根据图9-7列出状态概率的稳态方程：解此差分方程，用递推的方法第三节

单服务台模型第九章服务系统规划得系统的各项指标:第三节

单服务台模型第九章服务系统规划在机器故障问题中Ls就是平均故障台数，而(m-Ls)表示正常运转的平均台数。第三节

单服务台模型第九章服务系统规划第11章排队论62

例5

一个工人负责照管6台自动机床，当机床需要加料、发生故障或刀具磨损时就自动停车，等待工人照管。设每台机床平均每小时停车一次，每次需要工人照管的平均时间为0.1小时。试分析该系统运行情况。

解

m=6λ=1(台/小时)μ=1/0.1=10(台/小时)λμ==0.1L=6-10(1-0.4845)=

0.845(台)工人空闲的概率：停车的机床(包括正在照管和等待照管)的平均数

∑P0=6!(0.1)k(6-k)!-1=

0.4845k=06第11章排队论63

L=0.845-(1-0.4845)=

0.3295(台)W=

L/[μ(1-P0)]

=

0.845/[10(1-0.4845)]

=0.1639(小时)=

9.83(分钟)Wq=

W–

1/μ=

0.1639-0.1

=0.0639(小时)=

3.83(分钟)

ξ=Lm=0.8456=

14.1%η

=1

-ξ=100%-

14.1%

=

85.9%

等待照管的机床平均数：

平均停车时间：

平均等待时间:

生产损失率

机床利用率单队、并列的多服务台（服务台数为c）的情形，讨论以下三种情形：(1)标准的M/M/c模型(M/M/c//);(2)系统容量有限制(M/M/c/N/)；(3)有限顾客源(M/M/c//m)。第四节多服务台模型第九章服务系统规划一、标准的M/M/c模型(M/M/c//)

标准M/M/c模型的各种特征与标准的M/M/1模型的规定相同。另规定各服务台工作是相互独立的（非协作）且平均服务率相同1=1=…=c=。因此整个服务机构的平均服务率c（当n≥c时）；n（当n<c时）。令

，仅当

时才不会排成无限长的队列，

称为此系统的服务强度（或服务机构的平均利用率）（如图9-8）。第四节多服务台模型第九章服务系统规划这个系统的特点是，系统的服务速率与系统中的顾客数有关。当1nc时，系统中的顾客全部在服务台中，系统的服务率为n，状态的转移率nPn；当n>c时，因为只有c个服务台，最多有c个顾客在被服务，n-c个顾客在等候，因此系统的服务率为c，状态的转移率应为cPn。第四节多服务台模型第九章服务系统规划图9-8多服务台服务系统第四节多服务台模型第九章服务系统规划图9-9多服务台服务系统状态转移第四节多服务台模型第九章服务系统规划由图9-9可得：类似的有∑Pi=1，且ρ≤1用递推解差分方程（9-29），求得状态概率：系统的运行指标平均队长平均等待时间和逗留时间（由little公式求得）第四节多服务台模型第九章服务系统规划第11章排队论70例1

某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，

每个病人平均需要15分钟。病人按泊松分布到达，平均每小时

到达3人。

(1)先确定参数值，

有s=1

=3(人/小时)

=

60/15

=

4(人/小时)

故服务强度为

=

/

=

3/4

=

0.75

(2)

计算稳态概率：

P0=1-

=1-0.75=0.25

即急诊室空闲的概率,也是病人不必等待立即就能就诊的概率。

而

病人需要等待的概率则为P(Q>0)

=1-

P0=

=

0.75这也就是急诊室繁忙的概率。

第11章排队论71

急诊室内外的病人平均数：急诊室外排队等待的病人平均数：

Lq=L=3×0.75=2.25（人）病人在急诊室外平均逗留时间：病人平均等候时间:Wq=W=1×0.75=0.75（小时）(3)

计算系统主要工作指标λμ-λL=1μ-

λW=14-

3==1（小时）34

-3==3（人）第11章排队论72

(4)

为使病人平均逗留时间不超过半小时，则平均服务时间应减少多少？由于1μ-λW=12≤μ≥5则平均服务时间为15≤(小时)=12(分钟)1μ故1μ△≥15-12=3(分钟)即平均服务时间至少应减少3分钟。代入λ=3，解得第11章排队论73

(5)

若医院希望候诊的病人90%以上都能有座位，则候诊室至少应安置多少座位？

设应安置

x

个座位；则加上服务台共

x+1个，有

P(N≤

x+1)=

1

-

P(N>

x+1)≥0.9

P(N>

x+1)≤0.1

(x+1)+1

=

x+2

≤0.1两边取对数

(

x+

2)lg≤lg0.1因

<

1，故

x+

2

≥lg0.1

/lg=

-1/lg0.75

=

8

x≥

6即候诊室至少应安置

6

个座位。按(11-28)式有第11章排队论74

例2

承例1，假设医院增强急诊室的服务能力，使其同时能诊治两个病人，且平均服务率相同。试分析该系统工作情况

,并与例1进行比较。

解这相当于增加了一个服务台，故有s=2

=

3(人/小时)

=

4(人/小时)

δ=

/

=0.75

=

/s

=

3/(2×4)

=

0.375按

(11-14)式得P0

=[1+0.75

+]-1(0.75)22!(1-0.375)按

(11-16)式得Lq=(0.75)2×0.3752!(1-

0.375)2×115≈0.12(人)=115=0.45..第11章排队论75故有L=

Lq+δ=

0.12

+

0.75=

0.87(人)Wq

=

Lq/λW

=

L

/λ=

0.87/3=

0.29(小时)=

0.12/3=

0.04(小时)=

17.4(分钟)=

2.4(分钟)

病人必须等待的概率即为系统状态N

≥s(=

2)的概率，由(11-20)式得P(Q>0)

=

P(N

≥2)

=(0.75)22!(1-0.375)×115≈0.20另外还常采用顾客时间损失系数β=WqE(V)来评估服务质量。第11章排队论76指标S=1

系统S=2

系统P00.250.45P(Q>0)0.750.20Lq

2.25人0.12人L3人0.87人W60分钟

17.

4分钟Wq45分钟2.

4分钟β

3倍

16%两个系统的比较..二、系统容量有限的情形(M/M/c/N/)设系统的容量最大限制为N(N≥c)，当系统中顾客数n已到达N（即队列中顾客数已达(N-c)时），以后到达的顾客将被拒绝，其余条件与标准的M/M/c

模型相同。此时系统的状态概率:其中

（不必对

加以限制）第四节多服务台模型第九章服务系统规划系统的运行指标：由于公式复杂，现有一些专门的图表可供查阅。第四节多服务台模型第九章服务系统规划当N=c（即时制）的情形，典型的例子是街头的停车场就不允许排队等待空位。有：当n=c时，即关于Pc的公式，被称为爱尔朗呼唤损失公式，是A.K.Erlang早在1917年发现的，并广泛应用于电话系统的设计中。此时系统的运行指标：第四节多服务台模型第九章服务系统规划第11章排队论80

例4

某街口汽车加油站可同时为两辆汽车加油，同时还可容纳三辆汽车等待，超过此限则不能等待而消失。汽车到达间隔与加油时间均为指数分布，平均每小时到达16辆，平均加油时间为每辆6分钟。求每辆汽车的平均逗留时间。解

s=2r=2+3=5λ=16(辆/小时)μ=60/6=10(辆/小时)λμ

==1610=

1.6λsμρ==1.62=0.8第11章排队论81

(1.6)22!22×0.8(0.82-0.85)2!(1-

0.8)P0=-11+1.6++≈0.1568Lq=0.8(1.6)2×0.15682!(1-

0.8)2{1-

(0.8)5-2[1

+(5-2)(1

-

0.8)]}=

0.7257(辆)P5=

(0.8)5×0.1568=

0.1028≈10%222!L=

0.7257+1.6

(1

-

0.1028

)=

2.1612(辆)W

=2.161216(1-0.1028)≈0.15(小时)

=

9(分钟)三、顾客源为有限的情形

(M/M/c//m)设顾客源为有限数m（m>c），与单服务台情形类似，顾客的到达率λ是按单个顾客来考虑的，在机器管理问题中，共有m台机器，有c个修理工人，顾客到达就是机器出了故障，而每个顾客的到达率

是指每台机器单位运转时间出故障的期望次数。系统中顾客数n就是出故障台数，当n≤c时，所有的故障机器都在被修理，有(c-n)个修理工人在空闲；当c<n≤m时，有(n-c)台机器在停机等待修理，而修理工都在忙碌状态。假定这c个工人修理技术相同，修理时间都服从参数为μ的负指数分布，并假定故障的修复时间和正在生产的机器是否发生故障是相互独立的。第四节多服务台模型第九章服务系统规划其中第四节多服务台模型第九章服务系统规划由于P0,Pn计算公式过于复杂，有专门的表格可以供查阅。系统的性能指标平均顾客数（即平均故障台数）：有效的到达率λe为每个顾客的到达率λ乘以在系统外（正常运转）的机器的期望数：λe=λ(m-Ls)；在机器故障问题中，即单位时间m台机器平均出现故障的次数。第四节多服务台模型第九章服务系统规划本节讨论服务时间是任意分布的情形，当然，对任何情形都有下面的关系：E[系统中顾客数]=E[队列中顾客数]+E[服务机构中顾客数]E[在系统中逗留时间]=E[排队等待时间]+E[服务时间]其中，E[.]表示求期望值，用符号表示：Ls=Lq+LseWs=Wq+E[T]第五节其他服务时间分布模型第九章服务系统规划一、一般分布模型(M/G/1/∞/∞)该模型的基本条件：(1)

输入过程——顾客源是无限的，到达过程服从参数为λ的泊松过程；(2)排队规则——单队，队长无限制，先到先服务；(3)服务机构——单服务台，G表示服务时间T的分布为任意的概率分布，但已知E(T)和方差Var(T)。此模型被称为单服务台泊松到达、任意服务时间的排队模型。第五节其他服务时间分布模型第九章服务系统规划在稳态情况下，当ρ=λE(T)<1时，可以证明:

此公式又称P-K（Pollaczek-Khintchine）公式。只要知道λ、E(T)、Var(T)，无论服务时间T服从什么分布，均可用P-K公式求出平均队长Ls。其它的运行指标：第五节其他服务时间分布模型第九章服务系统规划第11章排队论88

例7

某储蓄所有一个服务窗口，顾客按泊松分布平均每小时到达10人。为任一顾客办理存款、取款等业务的时间

V(小时)～N(0.05,0.012).

试求该储蓄所空闲的概率及其主要工作指标。

解从而根据波拉切克——欣钦公式，可以导出：L

q=ρ+

σ

22(

1-ρ)λ22σ2=0.012(小时/人)2λ=

10

(人/小时)1μ=0.05(小时/人)第11章排队论8911.3

其他模型选介=0.26(人)该储蓄所空闲的概率：

=

1-

0.5

=

0.5=

10(0.05)=

0.5ρ=λμP0

=1-ρL=Lq+ρL

q=0.52+102(0.01)22(1-0.5)W=L

λWq=Lq

λ则主要指标=0.26+0.5=0.76(人)=0.7610=

0.076(小时)≈5

(分钟)=0.2610=

0.026(小时)≈2

(分钟)二、定长分布模型(M/D/1/∞/∞)服务时间为确定的常数，如在一条装配线上完成一件工作的时间一般都是常数。自动汽车冲洗台，冲洗一辆汽车的时间就是常数，可得：第五节其他服务时间分布模型第九章服务系统规划第11章排队论91

二、M/D/1系统

该系统对各顾客服务时间相互独立且为同一个常数，故有

E()==1μ

例8

某检测站有一台自动检测机器性能的仪器，检测每台机器都需6分钟。送检机器按泊松分布到达，平均每小时4台。试求该系统的主要工作指标。D()=0(=σ2)Lq=ρ2(1-ρ)2第11章排队论9211.3

其他模型选介

λ=4台/小时

μ=6分钟/台=0.1小时/台

σ2=0，L=Lq+ρ=

2/15+0.4

=

8/15(台)

Wq=Lq/

=

2/4(15)=1/30(小时)

=

2(分钟)W=Wq+1/μ=

2+6

=

8(分钟)0.422(1-0.4)Lq=

=

2/15(台)λμρ=

=

4(0.1)=

0.4解三、爱尔朗服务时间(M/Ek/1/∞/∞)此模型中每一个顾客必须一次经过k个服务台，接受k次服务后才构成一个完整服务过程。在每个服务台的服务时间Ti相互独立，并服从相同的负指数分布（参数为kμ），那么服从k阶爱尔朗分布。第五节其他服务时间分布模型第九章服务系统规划对于(M/Ek/1/∞/∞)模型（除服务时间外，其它条件与标准的M/M/1/∞/∞型相同）第五节其他服务时间分布模型第九章服务系统规划第11章排队论95

例9

一个质量检查员平均每小时收到两件送来检查的样品，每件样品要一次完成5项检验才能判断是否合格。据统计，每项检验所需时间的期望值都是4分钟，每项检验的时间和送检产品到到达间隔都为指数分布。问一件样品从送到至检查完毕预期要多少时间？解

λ=

2

件/小时

k=5μ1/(5)=

4

(分钟/件)μ

E(Vi)

=1/(k)，i=1，2，3，4，51/μ=20

(分钟/件)=

1/3

(小时/件)由有则第11章排队论96

ρ=

λ/μ=

2(1/3)=

2/3Lq

=Wq=Lq/λ=4/5/2

=

2/5

(小时)W

=Wq+1/μ=

2/5

+

1/3

=

11/15(小时)

=

44(分钟)

(5+1

)(2/3)22×5(1-

2/3)=45(件)一、排队系统经济分析试图完全消除排队现象是不现实的，那样显然会造成服务人员和设施的严重浪费。另一方面，如果设施不足或服务低水平，将导致过多的等待，因而产生生产和社会损失。从经济角度考虑，一般排队系统的费用应该包含于以下两个方面：⑴服务费用。它随着服务水平（反映在服务能力和服务台数量方面）的提高而增加，是服务水平的递增函数。⑵顾客等待的机会损失（费用）。顾客由于等待，产生一系列的损失（时间上、心理上、社会上等）用经济费用进行的估算，称为顾客等待的机会损失。它随服务水平的提高而下降，是服务水平的递减函数。

第六节服务系统规划的应用第九章服务系统规划这两方面构成的函数呈现为一条如图所示的U型曲线。第六节服务系统规划的应用第九章服务系统规划图9-10费用与服务水平之间的关系F1、F2、Y分别是等待费用函数、服务费用函数、合成费用函数。归纳起来，排队系统常见的优化问题在于：①确定服务台的最优平均服务率μ*；②确定最佳服务台数量s*；③选择最为合适的服务规则；④确定上述几个量得最优组合。研究排队系统的根本目的在于以最少的设备得到最大的效益，或者说，在一定的服务质量的指标下要求机构最为经济。第六节服务系统规划的应用第九章服务系统规划二、M/M/1系统的最优平均服务率μ1．标准的M/M/1模型设c1为当μ=1时服务系统单位时间的平均费用，并且这个平均费用与平均服务率μ成正比例；cw为平均每个顾客在逗留单位时间的损失；Y为整个系统单位时间的平均总费用。其中c1、cw均为已知（以下情形相同）。目标函数：将M/M/1模型的平均队长公式L=λ/(μ-λ)代入(9-41)式，得：第六节服务系统规划的应用第九章服务系统规划显然，Y是关于决策变量μ的一元非线性函数。由一阶最优性必要条件（驻点条件）解得驻点取算术平方根是为了保证ρ<1，即μ*>λ，这样，系统才能达到稳态。又知二阶充分条件成立：于是，式(9-43)给出的μ*为(λ,∞)上的全局唯一最小点。将μ*带入(9-42)中，可得最小的总平均费用第六节服务系统规划的应用第九章服务系统规划若设cw为平均每个顾客在队列中等待单位时间的损失，则需要M/M/1模型的平均队列长公式

代入式(9-41)中的L，类似可得一阶最优性必要条件：这是一个关于μ的4次方程，实际中一般采用数值法（如牛顿法）来确定其根（最优服务率）μ*。第六节服务系统规划的应用第九章服务