校内培训第14章排队论方法

构成．如：医院与、商店与顾客、机场与飞机、火车站与火车、水库与水、网络与用户等“随机服务系统理论”，因此，排队论在实际中有广泛的应用．排队论要研究的内容有三部分：排队服务系统的基本概念排队过程的一般模型．排队规则：服务机构：排队模型的标准形式间的分布，X和Y的取值有下列几种情况：G（General）表示一般服务Z表示服务台的个数，A表示系统的容量限制，B表示顾客源数目，C表示服务规则，可分（FCFS（LCFSMMCNm．排队系统的运行指标排队长（）：指在系统中排队等待服务的顾客数，其期望值记作LqLSLqLnLn逗留时间：指一个顾客在系统中的停留时间，其期望值记作WS其中为服务时间；忙期：服务机构连续工作的时间长度，记作Tb(6）损失率：由于系统的条件限制，使顾客被服务而使服务部门受到损失的概率，(7)服务强度：系统状态的概率个顾客，则说系统的状态为n，即可能的取值为当队长时，则n0,1,2,LNn0,1,2,LN当服务台个数为cn0,1,2,Lc一般说来，状态的取值与时间t有关，因此，在时刻t系统状态取值为n的概率记为Pn(tt 到达时间的间隔分布和服务时间的分布实际中，到达时间的间隔分布和服务时间的分布一般服从于以下三种分布：（Poisson）分布、负指数分布和分布 分N(t表示在时间段[0,t内到达的顾客数，Pn(t1t2表示在时间段[t1t2)(t2t1n(0个顾客到达的概率，即Pn(t1t2P{N(t2N(t1n}，当Pn(t1t2满足如下三平稳性：对于充分小的t，在时间间隔[ttt1个顾客到达的概率只与时间段的长度t有关，而与起时时刻tP1(tttto(t，其中0称为概小，可以忽略不计，即Pn(ttt)o(t如果取时间段的初始时间为t0Pn(0tPn(t，在[ttt Pn(t,tt)P0(t,tt)P1(t,tt)Pn(t,tt)故在[ttt

P0(t,tt)1P1(t,tt)Pn(t,tt)1t将[0,tt分为[0,t和[ttt，则在时间段[0,ttnPn(tt)P{N(tt)N(0)nP{N(tt)N(t)k}P{N(t)N(0)nknPnk(t)Pk(t,tkPn(t)(1t)Pn1(t)t即Pn(tt)Pn(t)P(t) (t) 令t0dPn(t)P(t) P(0)

(n

dP0(t)P

，P2(t)

P(t)

et(n0,1,2,L,t0表示在长为t的时间段内到达n个顾客的概率，即为分布，数学期望和方差分别E[N(t)]t,D[N(t)]t14.2.2负指数分布

(tett0．这里E(T1类似地，设系统对一个顾客的服务时间为（即在忙期内相继离开系统的两个顾客的间隔其中表示平均服务率（即单位时间内被服务完的顾客数E(1因此，T服从于负指数分布，即与概率强度为 率可知：P{TtsTs}P{Tt}，即说明后一个顾客的到来所需时间与前一个顾到来所需时间s无关，故T具有无性．于是，在排队模型的记号中都用M表示，E(T)1,D(T) 14.2.3分k设有如下的顾客流，记k个顾客到达系统的时间间隔序列为1,2,L,k（为相互独立的 量Ti服从于k k布fk(t

(k

(t0,0) E[ik(i1,2,LkE(TE[iD(T2．当k1时，即为负指数分布，因 从于k阶分布．单服务台的排队模型（1）：M/M/1（M/M/1//MM/1/NMM/1/14.3.1：M/M排队模型MM/1表示顾客源为无限的，顾客的到达相互独立，到达规律服从参数的数为确定系统在任意时刻t的状态为n的概率因为已知顾客的到达规律服从参数为 分布，服务时间服从参数为的负指数布，于是在时间间隔[ttt没有一个顾客到达的概率为：1t没有一个顾客被服务完的概率为：1t如表14-1所示．14-时刻t(tt在时刻tPn(t到离nn××√√×√×√Pn(t)(1t)(1t)Pn1(t)(t)(1t)Pn(tt)Pn(t)(1tt)Pn1(t)tPn1(t)t移项整理，两边同除以t，并令t0dPn(t) (t) (t)()P(t),n 当n0dP0(t)P(tP(t dP0(t)P(t)P dP(t)P(t) (t)()P(t),n )P0P1则 (

0,n

P0或 ( 01 n 01 n 14- 1，称为服务强度 11，于 系统的运行指标

P(1

n,n(1（平均顾客数：n，即系统中有n L nP n(1

1 1队列长（等待的平均顾客数Lq(n1)PnLS1

系统中顾客的逗留时间：

F(w)1e()w,f(w)(E(w) 系统中顾客的等待时间：等待时间Wq

1 1其 L ，

，

运行指标之间的关系LSwS，

，

1，

Lq这些关系式称之为Little14.3.2的容量有限MM/1/N系统的状态概率类似于的假设，不同的是队长有限制(N)，即系统中最多允许有N个顾客在排队，多了将被进入系统．假设为平均到达率，为平均服务率，则类似地可得状态转移关系图，如图14-2．01 n N-N01 n N-N14-P1 ( (1nN

N注意到Pn1P1 , 1N1P n,1n注意 11， (2）11，即时，表示系统的运行指标 (N1)N1队长：LSnPn1

,1NNLq(n1)PnLS1P0(3）顾客逗留时间：wS与平均到达率有关，而表示系统表示有空时平均到达率减去满员后顾客的平均数PN，即e(1PN)，由于 1 N

1

1N

e(1PN)1

1

N

1N

和

(1

1N Ne1 1 1N

S S (1P0S

(1PN (4）顾客等待时间：

114.3.3源为有限M/M/1/模型M/M/1/m/m的意义相同．，在系统外的平均顾客数为mLS，故系统的有效到达率为e(mLS14-301m-m (m-1)01m-m14-P1 (mn [(mn) (1nm Pm

m注意 iP i i0(mi)!

P P,1n (mn)! 0LSnPnm (1P0)，0

(1P)，wqwSmLq(n1)Pnm

(1P014.4多服务台的排队模型（1）：M/M/c（M/M/c//MMcN标准型MMcMM/1/，另外，假设顾客流为流，平均到达率为，各服务c（nc）n（nc），令

P (n1)Pn1Pn1(

(1ncPn1Pn1( (n 其中Pn1

11 c P0 当nc11 n!P0k!c!1 ,Pn 1ccncP0当n

k (c)c k LL ,L (nc)P (c P k

k(c)c

k (c)c其中c,knc,wS S ，w P c!(1)2 c!(1)2 思考题MMccMM/1系统容量有限MMcN假设系统内有c个服务台，顾客流为 流，平均到达率为．各服务台的服务时间服从（即系统内有N个顾客）时，有c个接受服务，Nc个在排队，再有顾客到来将被 n时，每个服务台的服务率为，则系统的总服务率：当0nc ；当nc时为 ，令

P1(n1)Pn1Pn1(

(1ncPn1Pn1(

(cnN 其中Pn1

1c11

(cN)

c

, cc

P,当0n k0

1

P

，Pn n ,当cn k0

(Nc1),

NLSLqc(1PN),wSwq,wq(1P)N (c)c N NLq(nc)Pnc!(1)2P0[1 (Nc)(1

cc

特别地,当Nc时,即M/M/C/C/,此时系统为即时务，不允许有顾客在系统c1(c)k (c

P0k

k!

,Pn

1, LqWq

SnPnc(1PcP1(n1)Pn1(mn1)Pn1[(mn) (1ncPn1(mc1)Pn1[(mc)

(cnP0

1

c k c! , k)!m k)!m (mn)!n!

当0nnn

0(m cP 当cn0

mLSm

,

(nm

c)Pn，

LS,

有效到达率为e(mLSLSLqLq(mLSMMcNmMMcmmMMccm排队系统的最优化问题一般排队系统的最优化问最优化问题的分类费用模型机构的服务水平（即增加了服务机构的成

客的等待费用（损，最优化的目标之一是使二者费用之和为最 图14-4模型MM/1中的最优服:M/M其中cS1（单位时间内服务完一个顾客）cW为每个顾 LSzcScw 0，则

cW(

MM/1/N如果系统中已有N个顾客，则后来的顾客将被，于是可设PN为被的概率，1PN即为接受服务的(1PN)表示单位时间内实际进入服务机构的顾客数，在稳设系统服务完1个顾客能收入G元，于是单位时间收入的期(1PN)G，则1 Nz(1PN)GcSG1N1cSGN1N1cS令 0，可解NN

N1N(N1)N! , 1N MM/1/设顾客数为m，单个服务台、服务时间服从负指数分布，当服务率为1时，服构的成本费为cS，单位时间内服务完一个顾客的收入为G元，单位时间内服务完的顾客数为mLS，则单位时间内的纯利润为z(mLS)GcS

mSmGEm1cS Emmm mm

其中E e 和， ，令 0m k mEmmEm mE mm1 m m m1 m1 cm

SS模型MMc中的最优服务台仅对标准的模型进行讨论．在稳态的假设下，单位时间内每服务台的成本费为cS，每zcSccWLSLSLS(c，即与服务台的个数c有关，因此总费用为zz(c)，记c的最优值为c*z(c*是最小费用．由于c只能取整数，即z(c是离散函根据z(c*)为最小值

z(c*)z(c*WWSS

SL(c*)cS(c*1)cWLS(c*

cc*cWLS(c*)cS(c*1)cWLS(c*L(c*)L(c*1)cSL(c*1)L(c*c cW校园网的设计和调节问题问题的提量研究通信端口的设计规模．通常的通信端口分为16口、32口、64口、128口等，实际中随(１)假设有m个用户，每个用户平均每天（按16小时计）上网1.5小时，试确定通信端nmnm；(２)假设m＝150，按所设定的通信端口数n，试讨论平均每天每个用户上网１小时1.5问题的分析与假平均忙期（即一天连续工作时间）16数，虽然实际用户数为m，但我们可以认为顾客总体是无限的．n个通信端口的使用是随机独立的，即任一用户可使用空闲的任一端口，单位时间的平均服务率（上网人数）为；模型的建立与求由上面的分析，假设用户平均上网的人数（即顾客的平均到达率，服从于参数为的/M/n/n/Tn

1.5mn

(小时n1.5

问题(２):由问题(１)的结果，当m=150时，通信端口数n=16．由假设１，用户的平均上网率为15075 ．由假设(２)，各端口的平均服务率 ，即每个用 的平均上网时间为t1（小时kkPk(k0,1,2,Ln,状态转移率为kPk，故得状态的平衡方程为