《理学排队论》ppt课件

1、单队、并列的多服务台（服务台数单队、并列的多服务台（服务台数c），主要），主要包括：包括：标准的标准的M/M/c模型（模型（M/M/c/）；）；系统容量有限制（系统容量有限制（M/M/c/N/M/M/c/N/）；）；有限顾客源（有限顾客源（M/M/c/mM/M/c/m）。）。 4.1 4.1 标准的标准的M/M/cM/M/c模型模型 即：即：M/M/c/FCFSM/M/c/FCFS 标准的标准的M/M/C模型与标准的模型与标准的M/M/1模型的各特征规模型的各特征规定相同，另外，各服务台工作是相互独立且平均服务率定相同，另外，各服务台工作是相互独立且平均服务率相同，即相同，即1=2=3=c=，

2、于是整个服务机构的于是整个服务机构的平均服务率为：平均服务率为：c(nc(nc时时),n(nc),n(nc时时) )令令 ，只有当，只有当 时，才不会形成无限队列。时，才不会形成无限队列。c1c从上图的队列图，分析系统中的状态转移关系，从上图的队列图，分析系统中的状态转移关系，状态转移图见下图。状态转移图见下图。 1 2 c队列队列C个服务台个服务台 由上图知，当由上图知，当nc c时，顾客被服务离去的速率为时，顾客被服务离去的速率为n,n,当当n n c c时，为时，为cc，故可得差分方程：，故可得差分方程：01PPnnnPnPPn)() 1(11nnnPcPPc)(11(1nc c)(n

3、c)012n=c-1n=c cn=c+1c (c-1). .ncn-1ncn+1c nc.c10iiP这里：这里： ， 1 11100)(11!1)(!1cckkckP利用递推法解该差分方程可求得状态概率为：利用递推法解该差分方程可求得状态概率为：0)(!1PnPnn0)(!1PccPncnn当当(nc),=3)=0.57P(n=1)=0.75平均队长平均队长Ls3.959.00（整个系统）（整个系统）平均队列长平均队列长Lq1.702.25（每个子系统）（每个子系统）平均逗留时间平均逗留时间Ws4.39min10min平均等待时间平均等待时间Wq1.89min7.5min4.3 4.3 系统

4、容量有限制的情形（系统容量有限制的情形（M/M/C/N/M/M/C/N/） 设系统的容量最大限制为设系统的容量最大限制为N(CN(C）, ,当系统当系统中顾客数中顾客数n n已达到已达到N N（即队列中的顾客数已达（即队列中的顾客数已达N-CN-C）时，再来的顾客将被拒绝，其他条件与）时，再来的顾客将被拒绝，其他条件与标准的标准的M/M/CM/M/C型相同。型相同。 此时的状态概率为：此时的状态概率为：其中：其中：11)(!)(100Ncckckcckcp)Nnc(p! cc)cn(ppnc!n)c(nn000c运行指标为：运行指标为：02()1()(1)!(1)(1)(1)1/cN cN c

5、qsqNqqNsqpcLN ccLLcpLWpWW 4.4 顾客源为有限的情况（顾客源为有限的情况（M/M/C/m） 设顾客源为有限设顾客源为有限m,m,且且mcmc，顾客到达率是按每个顾客考虑的。，顾客到达率是按每个顾客考虑的。 在机器维修模型中，有在机器维修模型中，有m m台机器，台机器，c c个修理工，机器故障率就是每个机器单个修理工，机器故障率就是每个机器单位运转时间出故障的期望次数，系统中顾客数位运转时间出故障的期望次数，系统中顾客数n n就是出故障的机器台数。就是出故障的机器台数。 当当ncnc时，无排队，有时，无排队，有c-nc-n个修理工空间；当个修理工空间；当cnmcnm时，

6、有时，有 (n-c)(n-c)台机器停台机器停机等待修理，系统处于繁忙状态。机等待修理，系统处于繁忙状态。 假定：假定：(1)(1)每个服务台速率均为每个服务台速率均为的负指数分布，（的负指数分布，（2 2）故障修复时间与正）故障修复时间与正在生产的机器是否发生故障是相互独立的，则：在生产的机器是否发生故障是相互独立的，则：1001111!()!()!kkccmnk cccpmk mkmcmkmmc )0(!)!(!0cnpnnmmpnn)1(!)!(!0mncpccnmmpncnn)(seLmeqqesssqeqsmcnnqmnnsLWLWLmuLuLLpcnLnpL)()(,115 5 一

7、般服务时间的（一般服务时间的（M/G/1M/G/1）模型）模型 本节我们研究服务时间任意分布的情形，我们知本节我们研究服务时间任意分布的情形，我们知道，对任何情形下面的关系都正确：道，对任何情形下面的关系都正确： L Ls s=L=Lq q+L+Lsese (L (Lsese-服务机构中顾客数的期望值服务机构中顾客数的期望值) ) W Ws s=W=Wq q+ET +ET （ET-ET-服务平均时间）服务平均时间） L Ls s=W=Ws s ， L Lq q=W=Wq q 当然，对于有容量限制和有限源情形当然，对于有容量限制和有限源情形要换成要换成e.e. 这就是著名的这就是著名的P-K公式

8、，只要知道公式，只要知道,ET, VarT,ET, VarT,无论无论T T服从什么分布，各项运行指标都可算出来。服从什么分布，各项运行指标都可算出来。)1 (222TVarLs 5.1 Pollaczek-Khintchine(P-K)公式公式 对对M/G/1模型模型,只要服务时间的只要服务时间的ET和和VarT存在，存在，其他条件与其他条件与 M/M/1相同，且相同，且1, =ET,ET,则有：则有： 5.2 5.2 定长服务时间定长服务时间 M/D/1M/D/1模型模型 该情况的服务时间是确定的常数，如一条装配线上完该情况的服务时间是确定的常数，如一条装配线上完成一件工作的时间是常数。则

9、成一件工作的时间是常数。则:T=1/ VarT=0:T=1/ VarT=0 L Ls s= =+ +2 2/2(1-) /2(1-) L Lq q=L=Ls s-= 2 2/2(1-) /2(1-) W Ws s=L/=(2-)/2(1-)=L/=(2-)/2(1-) W Wq q=L=Lq q/=/2(1-)/=/2(1-) 例例5 5 某售票口，顾客平均某售票口，顾客平均2.52.5分钟到达一个，窗口对顾客的分钟到达一个，窗口对顾客的平均服务时间是平均服务时间是2 2分钟分钟, ,顾客在售票口前至少要占用顾客在售票口前至少要占用1 1分钟，分钟，且服务时间服从：且服务时间服从：f(y)=

10、ef(y)= e1-y1-y y1 y1 0 y=0 x=0 即即x x是服从均值为是服从均值为1 1的负指数分布。的负指数分布。 Ey=E1+x=2,Vary=Var1+x=Varx=1Ey=E1+x=2,Vary=Var1+x=Varx=1 根据根据P-KP-K公式：公式：)1(2var22TLs8 . 024 . 0yE人8 . 202214 . 08 . 08 . 022sL分74 . 08 . 2ssLW分54 . 02qqLW28 . 08 . 2sqLL人人 5.3 爱尔朗服务时间爱尔朗服务时间M/Ek/1模型模型 如图，若顾客必须经过如图，若顾客必须经过k个服务站，在每个服务站

11、的个服务站，在每个服务站的服务时间服务时间Ti相互独立，并服从相同的负指数分布（参相互独立，并服从相同的负指数分布（参数为数为k），那么），那么 服从服从k阶爱尔朗分布。阶爱尔朗分布。kiiTT1.k12k-1ku kuku ku服务机构kTEi1221varkTi1TE21varkT则则M/Ek/1模型的运行指标为：模型的运行指标为：)1 (2) 1()1 (212222kkkLs)1 (2) 1(2kkLLsqssLW qqLW 6 6 排队系统优化排队系统优化 排队系统优化问题分为两类：系统设计和系统排队系统优化问题分为两类：系统设计和系统控制优化。前者称为静态问题，即研究如何使设备控制

12、优化。前者称为静态问题，即研究如何使设备达到最大效益或机构最为经济；后者称为动态问题，达到最大效益或机构最为经济；后者称为动态问题，研究如何运营可使某个目标达到最优。本节我们只研究如何运营可使某个目标达到最优。本节我们只讨论静态问题。讨论静态问题。 从静态考虑，排队系统主要涉及两项费用：等待从静态考虑，排队系统主要涉及两项费用：等待损失费用和服务费用。损失费用和服务费用。6.1 M/M/1 模型中的最优服务率模型中的最优服务率 1、标准的、标准的M/M/1 模型模型 设：设：Cs为为=1时服务机构的单位时间费用，时服务机构的单位时间费用，Cw为每为每个顾客单位时间等待费用。则单位时间成本个顾客

13、单位时间等待费用。则单位时间成本z为为:wsswsCCLCCz故故根根式式前前取取正正号号。即即注注意意，因因,.CC*s1222101, ()()sssdzCCdCCCC 2、系统容量为、系统容量为N的情形的情形 该系统中顾客到达后在系统中超过该系统中顾客到达后在系统中超过N个时，个时，将被拒绝，拒绝概率为将被拒绝，拒绝概率为PN ，则，则1-PN为接受概为接受概率，所以率，所以(1-(1-PN) )为单位时间内进入系统的为单位时间内进入系统的顾客平均数，也是单位时间内实际服务的平均顾客平均数，也是单位时间内实际服务的平均数。数。 (1-(1-PN)=(1-P)=(1-P0 0).). 设每

14、服务一个顾客收入设每服务一个顾客收入G G元，于是单位时间元，于是单位时间收入期望值为收入期望值为(1-(1-PN)G)G元，纯利润为：元，纯利润为：SNCGPz)1 (SNNCG)111 (1SNNCG)11(1SNNNNCG)11(11SNNNNCG11SNNNNNNCGz111)111111 2(1)()()()NNNNNNNNNNNNdzNNGCsd0)()() 1()()()(2111111)SNNNNNNNNNNNNCNNGGCNNSNNN2111)1()1(整理得：解上式的最优解解上式的最优解* * 6.2 M/M/C模型中最优服务台数模型中最优服务台数C 仅讨论标准的仅讨论标准

15、的M/M/C模型，且在稳态下，单位时间模型，且在稳态下，单位时间全部费用的期望值为：全部费用的期望值为：(包括服务成本与等待费用包括服务成本与等待费用)LCCCzws Cs每个服务台单位服务时间成本；每个服务台单位服务时间成本；Cw每个顾客在系统中停留单位时间成本；每个顾客在系统中停留单位时间成本；L系统中顾客的平均数系统中顾客的平均数Ls或队列平均数或队列平均数 Lq，是是C的函数。的函数。这里这里C是是Z的函数，且的函数，且C只能取整数解，故不能用微分法求只能取整数解，故不能用微分法求C*， 而只能用边际分析法而只能用边际分析法(Marginal Analysis)：因为因为 z(c*)

16、是最小值，则有：是最小值，则有：) 1 () 1() 1()(*CLCCCCLCCCwSwS) 1*(*)(czcz) 1*(*)(czcz将将z期望费用公式代入：期望费用公式代入：) 2() 1() 1()(*CLCCCCLCCCwSwS)() 1(/) 1 (*CLCLCCwS得：由) 1()(/)2(*CLCLCCwS得：由合并化简得：合并化简得：)() 1(/) 1()(*CLCLCCCLCLwS由于由于Cs /Cw w已知，依次求已知，依次求C=1，2，3， 的的 L值，即值，即可找出符合上式的可找出符合上式的C*。 例例6某检验中心，为各用户检验产品，用户每天到某检验中心，为各用户检验产品，用户每天到达按泊松流达按泊松流=48=48个个/ /天，每个用户每天停工损失天，每个用户每天停工损失6 6元，元，服务时间服从负指数分布服务时间服从负指数分布=25=25个个/ /天，设一个检验天，设一个检验台每天服务成本台每天服务成本4 4元，其他条件为标准元，其他条件为标准M/M/CM/M/C模型，模型，问设几个服务台费用最少？问设几个服务台费用最少？ 解：解：C C s s=4=4元，元，C Cw w=6=6元，元，=4