运筹学20172课件or06排队论

UniversityofScienceAnd决胜千运筹帷决胜千运筹帷排队论排队论里之外幄之中里之外幄之中M/M/1M/M/c

(SPT规则顾(SPT规则顾(FCFS(FCFS规则)(LCFS规则.–– 顾客相继到达的时间间隔服从k阶Erlang 顾客相继到达的时间间隔服从任意分布系统状态––排队系统顾客的数量N(t)t排队系统中顾客的数量队列长度––等待服务的顾客的数量Pn(t)––在时间t,排队系统中恰好有n个顾客的概率 ––服务台的数目

[M/M/1]：[¥/¥1/l––1/mlimPn(t)＝Pn利益，又涉及到服务机构的利益，还有社会效果好坏的究设计改进措施，必须确定一些基本指标，用以判断系队长＝r 6.2定义 limq(Dt)=Dtfi ¥¥pk(Dt)=定理对于一个参数为l的Poisson流，在[0，t]内到达k (t) (lt)k k=0,1,2 0

l= l= l=x定理在排队系统中，如果单位时间内顾客到f(t)=E(t)=1/Var(t)=1/

t>t£定理设v1，v2，…，vk是k个互相独立的，具有

t>0

6.3M/M/1]:[¥/¥/FCFS]SnSnSn-

t+Dt时Pn(t+Pn(t+Dt)-

=-P

令Dtfi0

=

n= dP dPdPn(t)>dPn(t)=

n=-P(l+m)+ n‡1

=lm ml

lP=mPm = P=mPm l =mPn

= m m¥Pk¥ ll

=l 1+

+P0= 令

m m -

k

=1-r0£r<

n=012 l

l lPn- λ

l

n- mm P(l+

n=l+n+1mn‡例高速公路处设有一个通道，汽车到时，时间服从负指数分布，平均时间为1 处空闲的概率2 处忙的概率3、系统中分别有1，2，3解根据题意,l=100辆/小时,1/m=15秒=1/240（小时/辆）,即m＝240（辆/小时）。L=Lq=L=Lq+r1W=Wqm L=kPk=krk(1-r)=(1-r)krk

=1- Lq=(k-1)Pk=(k-1)rk(1-r)=(1-r)(k- =(1- 1-W=L=lm-W= = lmm-例高速公路处设有一个通道，汽车到达费时间服从负指数分布，平均时间为15秒解L=

= =561-r1-66Lq=rL=5·5=6W 0.025(小时90(秒m-l240-6WqrW5·9075(秒6 lλn-llλn-ln0l1l2l………… =m

k

=

k=1,2,,N N1

Pk=1-11-rN1

0

NN

=

L

NkN

r(N+1)rN=1-r-1-rNNNLq=k

(k- =L

m

le=lPn=-NW=L l(1-PN =

=L-l

=L-1=W- 例解这是一个[M/M/1]:[N/¥/FCFS]系统，其中P0

1-1-

1-= =0.35631-23l=l(1- )=l(1l=l(1- )=l(1-rNP)=4·1-2·=L (NL

2= -

(5+2

361-36

1-

1-

1- 3 =L-le WL1.4230.374(小时)22.4(分le L0.7880.207(小时)12.4(分le 3P5=r5P03

5·0.356=当N=6P0

1-

1-= =0.35431-2363 = ·0.354=3P5-P6=0.0480-的平均顾客数为：l001l001ln-lnnlm-m λ0P0=[λn+μ]Pn=μPn+1+λn-1Pn-

n

mn

n

mn

0

mn = rnP(m-n)! mPi=mP0=

rni=0(m-W -m(1-P0 L=m-m(1-l

00 =W- 例某车间有5台机器，每台机器的连续运转时间服从负指数分布，平均连续运行时间15分钟。有一个修理工，每次12:。解(1)P0

!

+5!

+5!

+5!

+(0.8)5 =

=(2)P5

5!

P0=(3)L=m-1(1-P)=5-1(1-0.0073)= (4)Lq=L-(1-P0)=3.76-(1-0.0073)=(5)W

-1

1546(分

W1461234(分mμμμc

r=nn01c 01c

cm

cm

¥Pn=¥c-

1

c

- P0 =

n=0

+mnn!

c!

m

1-r mn n-

1£n£n>c!c L= + W=l 例某售票处有三个窗口，顾客到达服从Poisson流，到达速率为0.9人／分，售票时间服从负指数分布，每个窗口的平均售票速率为0.4人／分。顾客到达后排解

-P0=

(2.25)3·Lq

L=Lq

m =

W=

11.8914.39(分

01cN 01cNm

cm ¥Pn=¥ cc r(rc-rN)-P0=k=0

k! 1-r

r„(cr)n

==

£ccrn

(c£n£N)

N- =c!(1-r)2-

-(N-

-c(1-L=Lq+cr(1-PNW=L NWqe

=例某旅馆有8个单人房间，旅客到达服从Poisson流，平均速率为6人／天，旅客平均逗留时间；解N=c=8,l=6,1=2,cr=l=

=

(12)8-P0=

+

+

+ +

+

=3.963·10-

8=

P0

=L=cr(1-Pc)=12·(1-0.423)=到达速率(m-运行的机器数m- 1

r

k!(m

r=

c!

(m

l

0£n£ = (m-n)!n!

l(m-n)!c!cn-

c+1£n£mL=nPnmmmLq=(n-效到达速率λe为单位时间内出现故障的λe=λ(m-例车间有5台机器，每台机器的故障率为1次／小时，有2个修理工负责修理这5台机器，工作效率相同，m=

l= m=

c=

r=ml, cr=l=1, m 1P0=

rk=0 k=0

(m

1

1

1

11

11

115=·

=

mLq=(n-c)Pn=P3+2P4+3P5=mmmL=nPn=P1+2P2+3P3+4P4+5P5=le=l(m-L)=1·(5-1.092)=

=

qle qWL1.9020.28(小时16.8(分 费用费用z=csm+cwL将Lldz=cdm

-cw

=ll bm*=l+a

l=3+

3=2

z=c c+