随机服务系统理论：排队论课件.ppt

1、排队结构服务机构顾客源顾客到达排队规则服务规则离去图1 排 队系统示意图112n.12n。单队单服务台多队多服务台（并列)单队多服务台（并列）12n.12312单队多服务台（串列）混合形式系统中顾客 数在队列中等待服务的顾客数正 被 服务 的 顾客数+=等待时间 服务时间+逗留时间=nttnp)(plim 过渡状态 稳定状态 pn t 图3 排队系统状态变化示意图tnnenttP !)(式中式中为常数为常数(0)0)，称，称X X服从参数为服从参数为的泊松分的泊松分布，若在上式中引入时间参数布，若在上式中引入时间参数t t，即令，即令tt代替代替，则，则有：有：!nenxPn n=0,1,2,

2、（1）与时间有关的随机变量的概率与时间有关的随机变量的概率，是一个，是一个随机过随机过程程，即，即泊松过程泊松过程。t0，n=0,1,2,（2）)()(,1221ntNtNPttPn（t2t1，n0）若设若设N(t)N(t)表示在时间区间表示在时间区间0,t)0,t)内到达的顾客数内到达的顾客数(t0),P(t0),Pn n(t(t1 1,t,t2 2)表示在时间区间表示在时间区间tt1 1,t,t2 2)(t)(t2 2tt1 1)内有内有n(0)n(0)个顾客到达的概率。即：个顾客到达的概率。即：在一定的假设条件下在一定的假设条件下 顾客的到达过程就是顾客的到达过程就是一个泊松过程。一个泊

3、松过程。当当P Pn n(t(t1 1,t,t2 2)符合下述三个条件时，顾客到达过程符合下述三个条件时，顾客到达过程就是泊松过程就是泊松过程(顾客到达形成泊松流顾客到达形成泊松流)。无后效性：无后效性：各区间的到达相互独立各区间的到达相互独立,即即MarkovMarkov性。性。.t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP 也就是说过程在也就是说过程在t+tt+t所处的状态与所处的状态与t t以前所处的状以前所处的状态无态无关。关。平稳性：平稳性：即对于足够小的即对于足够小的tt，有：有：)()(t

4、ttttP ，1泊松流具有如下特性：泊松流具有如下特性：在在t,t+tt,t+t内有一个顾客到达的概率与内有一个顾客到达的概率与t t无关无关,而与而与tt成正比。成正比。0 0 是常数，它是常数，它表示单位时间到达的顾客数，称为概率强度。表示单位时间到达的顾客数，称为概率强度。普通性：普通性：对充分小的对充分小的t,t,在时间区间（在时间区间（t,t+tt）内有内有2 2个或个或2 2个以上顾客到达的概率是一高阶无穷小个以上顾客到达的概率是一高阶无穷小.由此知，在由此知，在(t，t+t)t)区间内没有顾客到达的概率为：区间内没有顾客到达的概率为：)(1),(0tottttP 令令t1 1=0

5、,t=0,t2 2=t,=t,则则P(tP(t1 1,t,t2 2)=P)=Pn n(0,t)=P(0,t)=Pn n(t)(t)2)(),(nntotttP 即即 P P0 0+P+P1 1+P+P22=1=1 在在上述假设下，上述假设下，t t时刻系统中有时刻系统中有n n个顾客的概率个顾客的概率p pn(tn(t)：根据排队系统的根据排队系统的状态转移图状态转移图：11nnnnPP 整理后可得：整理后可得：n-1n-1 n n n+1n+1 2 2 0 0 1 1 2 2 n+1n+1 0 0 1 1 2 2 n-2n-2 n-1n-1 n n 1 1 3 3 n-1n-1 n n n+

6、1n+1 n+2n+2 稳态时，稳态时，它 对 时它 对 时间的导数为间的导数为0，所以由，所以由(12.5)、(12.6)两式得：两式得：Pn(t)与时间无关与时间无关,可以写成可以写成Pn,0)(1111nnnnnnnPPP010 PP(12.7)(12.7)(12.8)(12.8)表示单位时间内顾客平均到达数。表示单位时间内顾客平均到达数。1/表示顾客到达的平均间隔时间。表示顾客到达的平均间隔时间。1TE21 TVar（n n个顾客到达的概率）个顾客到达的概率）tnnenttP !)()(（4 4）对排队模型，在给定输入和服务条件下，主要对排队模型，在给定输入和服务条件下，主要研究系统的

7、下述运行指标：研究系统的下述运行指标：(1)(1)系统的系统的平均队长平均队长LsLs(期望值期望值)和和平均队列长平均队列长LqLq(期望值期望值)；(2)(2)系统中系统中顾客平均逗留时间顾客平均逗留时间WsWs与队列中与队列中平均等平均等待时间待时间WqWq；本节只研究本节只研究M/M/1M/M/1模型，下面分三种情况讨论：模型，下面分三种情况讨论：系统中有系统中有n n个顾客个顾客M/M/1:/FCFS/FCFS模型模型 在任意时刻在任意时刻t t，状态为，状态为n n的概率的概率P Pn n(t)(t)（瞬态概率），（瞬态概率），它决定了系统的运行特征。它决定了系统的运行特征。已知顾

8、客到达服从参数为已知顾客到达服从参数为的泊松过程，服务时的泊松过程，服务时间服从参数为间服从参数为的负指数分布。现仍然通过研究区间的负指数分布。现仍然通过研究区间 t，t+tt）的变化来求解。在时刻）的变化来求解。在时刻t+tt，系统中有，系统中有n n个顾客不外乎有下列四种情况（个顾客不外乎有下列四种情况（t，t+tt）内到达）内到达或离开或离开2 2个以上个以上没列入）。没列入）。由此可得该排队系统的由此可得该排队系统的状态转移图状态转移图：由（由（4）得：）得：001PPP 其中其中服务强度服务强度 将其代入（将其代入（3）式并令）式并令n=1,2,(也可从状态转移也可从状态转移图中看出

9、状态平衡方程图中看出状态平衡方程)得：得：关于关于Pn的差的差分方程分方程 n-1n-1 n n n+1n+1 2 2 0 0 1 1 稳态时，稳态时，它 对 时它 对 时间的导数为间的导数为0，所以由，所以由(1)、(2)两式得：两式得：Pn(t)与时间无关与时间无关,可以写成可以写成Pn,011 nnnP)(PP010 PP(3)(3)(4)(4)0120 P)(PP n=1n=10020 P)(PP 0202021PP)(P)(P n=2n=20231 P)(PP00230 P)(PP 0303022231PP)(P)(P 以此类推以此类推，当，当n=n时，时，00)(PPPnnn (5

10、)(5)1 10 nnP 以及概率性质知：以及概率性质知：111000 PPnn(数列的极限为数列的极限为 )11 10Pnn)(P 1(6)(6)否则排队无限远否则排队无限远 系统系统稳态稳态概率概率系统的运行指标系统的运行指标 (1)系统中的队长系统中的队长Ls（平均队长）（平均队长）nnnnsnPnL 001.)(n.)()()(n 11312132.nn.nn 1433223322 132.n(01)1 Ls 即即:(7)(7)期望期望(2)队列中等待的平均顾客数队列中等待的平均顾客数Lq nnnnqnPnL 111)1()1(nnnn)(n 1111 12sL(8)(8)11nn(L

11、ittle Little 公式公式)：ssqsLLLL 1qqssWLWL 顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间Wq )WsLs(1Ws (4)(4)顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间W Wq q Wq)WqLq(利用公式（利用公式（12.2612.26）可求出）可求出W Ws s (3)顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间Ws 利用公式（利用公式（12.2712.27）可求出）可求出W Wq q 系统处于空闲状态的概率：系统处于空闲状态的概率：10P 系统处于繁忙状态的概率：系统处于繁

12、忙状态的概率：010PnP)(服务强度服务强度 表9-4 表9-51.1.参数的确定参数的确定算出每小时病人平均到达率算出每小时病人平均到达率 2.1(2.1(人人/小时小时)每次手术平均时间每次手术平均时间 0.4(0.4(小时小时/人人)每小时完成手术人数每小时完成手术人数(平均服务率平均服务率)2.5(2.5(人人/小时小时)2.2.取取2.12.1，2.52.5，可以通过统计检验的方法，可以通过统计检验的方法(例如例如2 2检检验法验法)，认为病人到达数服从参数为，认为病人到达数服从参数为2.12.1的普阿松分布，手的普阿松分布，手术时间服从参数为术时间服从参数为2.52.5的负指数分

13、布。的负指数分布。3.3.它说明服务机构它说明服务机构(手术室手术室)有有8484的时间是繁忙的时间是繁忙(被利用被利用)，有，有1616的时间是空闲的。的时间是空闲的。2.10.842.5100nnf100vvf4.4.依次算出各指标：依次算出各指标：在病房中病人数在病房中病人数(期望值期望值)排队等待病人数排队等待病人数(期望值期望值)病人在病房中逗留时间病人在病房中逗留时间(期望值期望值)病人排队等待时间病人排队等待时间(期望值期望值)2.15.25()2.52.1sL 人0.84 5.254.41()qL 人12.5()2.52.1sW 小时0.842.1()2.52.1qW 小时排队

14、系统 服务台顾客 N 4 3 2 1被拒绝)()()(100tPtPdttdP(2)(2)对于对于(1)(1)式，当式，当n=1,2,N-1n=1,2,N-1时，也仍能成立。时，也仍能成立。)()()()()(1tPtPtPdttdPnnnn(1)(1)(n=1,2,N-1)(n=1,2,N-1)但当但当n=Nn=N时，有下面两种情况：时，有下面两种情况：对于对于P P0 0(t)(t)，前面的（前面的（2 2）式仍然成立。）式仍然成立。情情况况 时时刻刻 t 的的顾顾客客 区区间间 t,t+t t 时时刻刻 t+t t的的顾顾客客数数 概概率率 A A N N 无无离离去去（肯肯定定不不到到

15、达达）N N P Pn n(t t)(1 1-t t)B B N N-1 1 一一人人到到达达（无无离离去去）N N P Pn n-1 1(t t)t t ttPttPttPNNN)()1()()(1)()()(1tPtPdttdPNNN (8)(8)其状态转移图为其状态转移图为:012n-1nn+1.状态转换图.N-1N 在稳态情况下有：在稳态情况下有：010PP0)(11nnnPPP01 NNPP(9)(9)解（解（9）式得：）式得：01PP022PP0PPNN NnnNnnNnnPPP000001 而等比数列而等比数列10111NnNn1011 NPnNnP 111(1,(1,nN)(1

16、0)nN)(10)(1)平均平均队长队长Ls：nPnLnNnNNnns 01011nNnNn 0111111)1(1 NNN(1)其运行指标：其运行指标：(2)有效到达率有效到达率e 系统容量有限，当满员时，顾客将被拒绝，实际系统容量有限，当满员时，顾客将被拒绝，实际的顾客到达率与的顾客到达率与不一样，不一样，)1(NeP 还可验证：还可验证：esesqLLL esSLW eqqLW 此种情况的公式与此种情况的公式与前类似前类似,只有只有Ls不同不同,e与与 不同。求不同。求e必须必须先求得先求得P0或或PN才行。才行。有效到达率为有效到达率为e。可以证明：可以证明：)1(0Pe 111)1(

17、1 NNN LsLs例例2某单人理发馆共有六把椅子接待顾客排队，无某单人理发馆共有六把椅子接待顾客排队，无座时将离去，顾客平均到达率为座时将离去，顾客平均到达率为3人人/h，理发时间平，理发时间平均为均为15分钟，求：分钟，求：(1)求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率;(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值;(3)求有效到达率求有效到达率;(4)求一顾客在系统中的逗留时间和排队时间求一顾客在系统中的逗留时间和排队时间平均值平均值;(5)在可能到来的顾客中，有百分之几不等待在可能到来的顾客中，有百分之几不等待就离开？就离开？解：解：N=?N=?N=6+1

18、=7，=3=3，=4=411.275.0175.0825.075.01)1(18811 NNsNL39.1)2778.01(11.2)1(11.20 PLLesq2778.075.0175.0111810 NP(1)求某一顾客到达就能理发的概率求某一顾客到达就能理发的概率:(2)求需要等待的顾客数的期望值求需要等待的顾客数的期望值:(3)求有效到达率求有效到达率:89.2)2778.01(4)1(0 Pe(4)求一顾客在系统中的逗留时间和排队时间平均值求一顾客在系统中的逗留时间和排队时间平均值:min8.4373.089.211.2 hLWessmin86.2848.089.239.1 hLW

19、eqq%71.375.075.0175.01117817 NNPP0=0.27780P1=0.20836P2=0.15627P3=0.11720 =0.9629=96.29%P4=0.08790 故拒绝的概率为故拒绝的概率为3.71%P5=0.06593P6=0.04944(5)在可能到来的顾客中，有百分之几不等待就离开？在可能到来的顾客中，有百分之几不等待就离开？顾客为何不等待顾客为何不等待就离去？就离去？因为系统已因为系统已经满员经满员037.0389.23 e顾客源队列.服务台mn 对于有限源应按每个顾客单独考虑，求出其有对于有限源应按每个顾客单独考虑，求出其有效到达率效到达率e。)1(

20、)(0PLmse 这样这样e是随系统内顾客数而变化的。其状态转是随系统内顾客数而变化的。其状态转移图为：移图为：01m2(m-1)(m-2)n-1n(m-n)n+1(m-n-1)(m-n+1).状态转换图m-1m.设系统内顾客数为设系统内顾客数为Ls，则系统外的顾客为则系统外的顾客为m-Ls。设每个顾客的平均到达率是相同的设每个顾客的平均到达率是相同的。(这里这里的含义是单台机器在单位时间里发生故的含义是单台机器在单位时间里发生故障的概率或平均次数障的概率或平均次数)01m2(m-1)(m-2)n-1n(m-n)n+1(m-n-1)(m-n+1).状态转换图m-1m.01PmPnnnPnmPn

21、mP)()1(111mmPP 1nm-1 0 0状态状态 n n状态状态 m m状态状态 这样这样e是随系统内顾客数而变化的。其状态转是随系统内顾客数而变化的。其状态转移方程为：移方程为：用递推方法解此差分方程，并注意条件，用递推方法解此差分方程，并注意条件，可以得到如下公式：可以得到如下公式：1 0 m i i PimiimmP 00)!(!10)()!(!PnmmPnn (1nm)各项运行指标为：各项运行指标为：)1(0PmLs )1)()1(00PmPLLsq)1(1)1(00PLPmmWss )1(10PLWWqsq 例例3 某车间有某车间有5台机器，每台机器的连续运转时间服台机器，每

22、台机器的连续运转时间服从负指数分布。平均连续运转时间从负指数分布。平均连续运转时间15分钟，有一个分钟，有一个修理工，修理时间服从负指数分布，平均每次修理工，修理时间服从负指数分布，平均每次12分分钟。求：钟。求：(1)修理工空闲时间修理工空闲时间 解解:(1)m=5,=1/15,=1/12,=4/5=0.8m=5,=1/15,=1/12,=4/5=0.8100)!(!miiimmP154328.0!0!58.0!1!58.0!2!58.0!3!58.0!4!51 154328.01208.012028.012068.0120248.01201 0073.08.1361 287.00073.0

23、8.01200073.08.0!0!5)!5(!55055 PmmP76.3)0073.01(455)1(0 PmLs 台台77.29927.076.3)1(0 PLLsq 台台(3)出故障的平均台数出故障的平均台数(4)等待修理的平均台数等待修理的平均台数(5)平均停工时间平均停工时间469927.01276.3)1(0 PLWss 分钟分钟(2)五台机器都出现故障的概率五台机器都出现故障的概率349927.01277.2)1(0 PLWqq 分钟分钟 机器等待过长，忙期长，应增加维修工人机器等待过长，忙期长，应增加维修工人或提高效率。或提高效率。(6)平均等待修理时间平均等待修理时间(7)

24、评价这些结果评价这些结果令令 ，只有当，只有当 时，才不会形成无限队列。时，才不会形成无限队列。c1c从右图的队列图分从右图的队列图分析系统中的状态转析系统中的状态转移关系，见下面状移关系，见下面状态转移图。态转移图。uuu。.c个队列 由上图知，当由上图知，当n=cn=c时，为时，为cc，故可得差分方程：，故可得差分方程：1100)(11!1)(!1cckkckP利用递推法解该差分方程可求得状态概率为：利用递推法解该差分方程可求得状态概率为：01PPnnnPnPPn)()1(11nnnPcPPc)(11(1nc=c)10iiP这里：这里：，1 10)(!1PnPnn0)(!1PccPncnn

25、(nc),c),(nc)021)1(!)()(PccPcnLcncnqssLWqqLW 系统的运行指标为：系统的运行指标为：qLsL13200)(11!31)(!1kkkP解解:(1)132)4.09.0(4.039.01161)4.09.0(214.09.010748.0325.211625.2225.225.21132954.34.09.0704.1qsLL704.10748.0)325.21(!3325.2)325.23()1(!)(2302PccLcq(2)39.49.095.3ssLW89.19.070.1qqLW(3)0200210)(211)(13PPPPPPnP57.078.5

26、0748.01)225.225.21(121P(4)为计算简化，现专门根据为计算简化，现专门根据=/c/c值和值和c c值编制值编制了了W Wq q数值表可供使用，其结构为：数值表可供使用，其结构为：服服务务台台数数c W Wq q /c c 1 1 2 2 3 3 4 4 0 0.1 1 0 0.2 2 0 0.3 3 0 0.9 95 5 0 0.1 11 11 11 1 0 0.2 25 50 00 0 0 0.4 42 28 86 6 1 19 9.0 00 00 0 0 0.0 01 10 01 1 0 0.0 04 41 17 7 0 0.0 08 89 98 8 9 9.2 25

27、 56 64 4 0 0.0 00 01 14 4 0 0.0 01 10 03 3 0 0.0 03 33 33 3 6 6.0 04 46 67 7 0 0.0 00 00 02 2 0 0.0 00 03 30 0 0 0.0 01 13 32 2 4 4.4 45 57 71 1 顾客到达后必须等待的概率顾客到达后必须等待的概率例如上题中可查表得：例如上题中可查表得：=0.75,c=3,W =0.75,c=3,Wg=0.756=0.75689.14.0756.0qW70.19.089.1qqWL95.34.09.070.1qsLL39.49.095.3ssLW.=0.91=/c2=/cc=/c模 型指 标M/M/cM/M/1服 务 台 空 闲 概 率 P00.7480.25(每 个 子 系 统)顾 客 必 须 等 待 概 率P(n=3)=0.57P(n=1)=0.75平 均 队 长 Ls3.959.00(整 个 系 统)平 均 队 列 长 Lg1.702.25（每 个 子 系 统）平 均 逗 留 时 间 Lu4.39min10min平 均 等 待 时 间 W q1.89min7.5min从上表可知，从上表可知，M/M/C系统明显比系统明显比C个个M/M/1系统的指标优。系统的指标优。