第六章-排队系统建模与仿真(New)课件.ppt

1、一、排队系统的基本概念一、排队系统的基本概念二、到达时间间隔和服务时间分布二、到达时间间隔和服务时间分布三、排队系统的分析三、排队系统的分析四、排队系统的仿真四、排队系统的仿真到达的顾客到达的顾客要求服务内容要求服务内容服务机构服务机构1、不能运转的、不能运转的 机器机器修理修理修理技工修理技工2、病人、病人诊断或手术诊断或手术医生（或手术医生（或手术台）台）3、电话呼唤、电话呼唤通话通话交换台交换台4、提货单、提货单提取存货提取存货仓库管理员仓库管理员5、到达机场的、到达机场的 飞机飞机降落降落跑道跑道6、进入我方阵、进入我方阵 地敌机地敌机我方高射炮进我方高射炮进行射击行射击我方高射炮我方

2、高射炮p 到达模式p服务机构服务机构p排队规则排队规则1 1排队系统的三个基本组成部分排队系统的三个基本组成部分1 1动态实体动态实体排队排队服务机构服务机构到达到达按规则接受服务按规则接受服务离开离开（1）平均到达间隔时间T0nTT 0（2）平均到达速度TnT01（3）到达间隔时间的分布函数A（t）0,00,)(ttetAt（1）平均服务时间TsssnTT（2）平均服务速度TnTss1（3）服务时间的分布函数B（t）0,00,)(ttetBt1 1动态实体到达间隔的时间为常数动态实体到达间隔的时间为常数动态实体接受服务的时间为常数动态实体接受服务的时间为常数2 2满足下列四个条件的到达分布称

3、为泊松到达分布：p 平稳性。p独立性。p普通性。p有限性 对于这种到达分布，在时间t内到达k个动态实体的概率Vk(t)遵从泊松分布，即：1,0!)()(kktetVktk3 3设v1,v2,vk是k个相互独立的随机变量，服从相同参数k的负指数分布，那么T=v1+v2+vk的概率密度为：1)!1()()(ktkktkektf称T服从k阶爱尔朗分布。其数学期望和方差为：1)(TE21varkT f(t)1/k3k2k1kt例如：串列的k个服务台。每台服务时间相互独立，服从相同的负指数分布，那么以动态实体走完这k个服务台总共需要的服务时间就服从k阶爱尔朗分布。4 4xxfx,)(exp21)(221

4、12c多队-多服务台（并列）排队系统单队-多服务台（并列）排队系统12c12C多服务台（组合式）排队系统12c12c多服务台（串列）排队系统系统处于“忙”时，动态实体进入队列的三种处理方法：p 损失制p等待制 先到先服务（FIFO、FCFS）后到先服务（LIFO）随机服务（GIRO）优先权服务（PR）p混合制（1）服务强度（2）实际业务强度u1u（3）服务设备利用率nsTTnns110随机排队系统的运行指标：p在系统中动态实体数量的期望值在系统中动态实体数量的期望值Ls，p在系统队列中等待的动态实体数量（队列长度）的在系统队列中等待的动态实体数量（队列长度）的 期望值期望值Lq。p在系统中动态

5、实体逗留时间的期望值在系统中动态实体逗留时间的期望值Ws，p在队列中动态实体等待时间（排队时间）的在队列中动态实体等待时间（排队时间）的 期望值期望值Wq。其中：其中：X表示顾客相继到达时间间隔的分布表示顾客相继到达时间间隔的分布 Y表示服务时间的分布表示服务时间的分布 Z表示服务台的个数表示服务台的个数 A表示系统容量表示系统容量 B 表示顾客源的数目表示顾客源的数目 C表示服务规则表示服务规则 CBAZYX/在排队系统中一般约定：如果在排队系统中一般约定：如果Kendall记号中略去记号中略去 后后3项时，即是指项时，即是指 M负指数分布负指数分布 M/M/1表示相继到达时间为负指数分布，

6、服务时表示相继到达时间为负指数分布，服务时间为负指数分布，单服务设备的模型。间为负指数分布，单服务设备的模型。FCFSZYX/1 1（1）到达模式。动态实体源是无限的，动态实体单个）到达模式。动态实体源是无限的，动态实体单个 到达，相互独立，一定时间的到达数服从泊松分布。到达，相互独立，一定时间的到达数服从泊松分布。（2）排队规则。单对，且队列长度没有限制，先到先）排队规则。单对，且队列长度没有限制，先到先 服务。服务。（3）服务机构。单服务台，各动态实体的服务时间是相）服务机构。单服务台，各动态实体的服务时间是相 互独立的，服从互独立的，服从相同的指数分布相同的指数分布。(4)到达间隔时间和

7、到达间隔时间和 服务时间是相互独立服务时间是相互独立2 21、分析标准的、分析标准的)(tPn2、因已知到达规律服从参数、因已知到达规律服从参数 的泊松过程，的泊松过程，服务时间服从参数为服务时间服从参数为 的负指数分布，所以的负指数分布，所以在在t,t+t)时间区间内分为：时间区间内分为：（1）有一个顾客到达的概率为）有一个顾客到达的概率为 ；没有顾客到达的概率是没有顾客到达的概率是（2）当有顾客在接受服务时，）当有顾客在接受服务时，1个顾客被个顾客被 服务完了（离去）的概率服务完了（离去）的概率 ，没有离去的概率就是没有离去的概率就是（3）多于一个顾客的到达或离去的概率）多于一个顾客的到达

8、或离去的概率 是可以忽略的。是可以忽略的。)(tt)(1tt)(tt)(1tt)(t情况情况 在时刻在时刻t顾客数顾客数在区间（在区间（t,t+t)在时刻在时刻t顾客数顾客数到达到达离去离去(A)nn(B)n+1n(C)n-1n(D)nn在时刻在时刻t+t，系统中有，系统中有n个顾客（个顾客（n0)存在下列四种情况存在下列四种情况21 Pn(t）表示）表示t时刻系统中恰有时刻系统中恰有n人人。（A）Pn(t)(1t)(1 t）（B）Pn+1(t)(1t)t（C）Pn 1(t)t(1 t）（D）Pn(t)t t以上各式省略了以上各式省略了t的无穷小项的无穷小项。情况t 时刻顾客数在区间t,t+t

9、）t+t 时刻顾客数到达离去An不发生不发生nBn1不发生发生nCn1发生不发生nDn发生发生n 由此可得：Pn(t+t)=Pn(t)(1t t）+Pn+1(t)t+Pn1(t)t+o(t)Pn(t+t)Pn(t)/t=Pn1(t)+Pn+1(t)(+)Pn(t)+o(t)/t 令 t 趋于0，有下列微分差分方程：d Pn(t)/d t=Pn1(t)+Pn+1(t)(+)Pn(t)（当n=0时只有（A）和（B）d P0(t)/d t=-P0(t)+P1(t)在稳定情况下，d Pn(t)/d t=0。有：P0+P1=0 Pn1+Pn+1(+)Pn=0 n1 求解上面两式的递推方程，得到：1022

10、010002331200001111nnPPPPPPPPPPPPPPPP000010111nnPPPPP n由：P则：0 由上式，可得下式：01nnP 令：11110 nPPnn三、基本计算三、基本计算1.队长队长（系统中平均顾客数）Ls Ls =n Pn n=0 =nn nn+1 n=0 n=0 =/(1-)=/(-)(=/)2.排队长排队长（系统中等待服务平均顾客数）L q Lq =(n1)Pn n=1 =Ls=2/(1-)10,)(2 3.逗留时间逗留时间关于顾客在系统中的逗留时间Ws服从为(-)的负指数分布。这样就求到顾客在系统中的平均逗留时间：1sW4.等待时间等待时间：（顾客在系统

11、中平均等待服务时间）W q W q=Ws1/=/(-)以上计算可以看出，满足Little公式：qqWL)(ssWL服务强度：服务强度：系统状态为系统状态为n的概率：的概率：10P1,)1(nPnn101 12 2系统的运行指标(p154)：在系统中的平均顾客数（系统的期望值）在系统中的平均顾客数（系统的期望值）3 31sL在队列中等待的平均顾客数（队列长度期望值）在队列中等待的平均顾客数（队列长度期望值）4 410,)(2qL在系统中顾客逗留时间的期望值在系统中顾客逗留时间的期望值Ws5 51sW在队列中顾客等待时间的期望值在队列中顾客等待时间的期望值6 6)(1qW案例案例1：某修理店只有一

12、个修理工，要求提供服务的顾客到某修理店只有一个修理工，要求提供服务的顾客到达过程为达过程为Poisson流，平均流，平均4人人/h;修理时间服从负指修理时间服从负指数分布，平均需要数分布，平均需要6min。试求试求（1）修理店空闲的概率；（）修理店空闲的概率；（2）店内恰有）店内恰有3个顾个顾客的概率客的概率；（；（3）店内至少有）店内至少有1个顾客的概率；个顾客的概率；（4）在店内的平均顾客数；（在店内的平均顾客数；（5）每位顾客在店内的平均）每位顾客在店内的平均逗留时间；（逗留时间；（6）等待服务的平均顾客数；（）等待服务的平均顾客数；（7）每）每位顾客平均等待服务时间（位顾客平均等待服务

13、时间（8）顾客在店内等待时间）顾客在店内等待时间超过超过10min的概率的概率案例2：假设在一个单座、男女皆宜的美发店中，到达间隔时间和服务时间都服从指数分布。和 的值分别为每小时2个和每小时3个，1、求系统到达稳态后，系统服务强度？2、没有人到达概率，及达到1个、2个、3个人的概率？3、系统中平均顾客数？队列的平均长度？案例：解：3231321110P1,)1(nPnn9232311)(P274232312)(P818332313)(P（人）2232L系统中平均顾客数：队列的平均长度为：（人）34)(2QL（小时）323111wwQ每个顾客在队列中花费的平均时间为：系统中平均逗留时间为：（小

14、时）122Lw例题。到达病人数到达病人数到达的病人数到达的病人数n出现的次数出现的次数fn01012822931641056大于等于大于等于61合计合计100例题。手术时间手术时间完成手术时间完成手术时间t/h出现的次数出现的次数ft0.00.2380.20.4250.40.6170.60.890.81.061.01.25大于大于1.20合计合计100解：（1）计算平均到达速度：小时人/1.2100nnf平均手术时间：人小时/37.0100Ttstf平均服务速度：小时人/5.24.01T1s（2）取=2.1，=2.5，通过统计检验方法的检验，可以认为病人到达数服从参数为2.1的泊松分布，手术时

15、间服从参数为2.5的负指数分布。（3）服务设备利用率84.05.21.2 因为=0.841，表明动态实体到达系统的速度比系统的服务速度慢。所以，到达系统的每一个动态实体都可以得到服务。另外，说明服务机构（手术室）有84%的时间繁忙（被利用），有16%的时间空闲。（4）系统的指标计算在病房中病人数（期望值）：小时人/25.51.25.21.2sL排队等待病人数（期望值）：小时人/41.425.584.0qsLL病人在病房中逗留的时间（期望值）：小时5.21.25.211sW病人在排队列中等待时间（期望值）：小时1.21.25.284.0qW一、排队系统的基本概念一、排队系统的基本概念二、到达时间

16、间隔和服务时间分布二、到达时间间隔和服务时间分布三、排队系统的分析三、排队系统的分析四、排队系统的仿真四、排队系统的仿真单通道排队系统中的事件：p动态实体到达系统p 动态实体离开系统系统状态：p动态实体数，即顾客数p服务员“忙”、“闲”状况。顾客到达时间间隔（Ai）服务员空闲否？开始服务服务完毕顾客离去排队等待经过经过SiYNp仿真方法仿真方法：手工仿真p仿真初始条件仿真初始条件：系统中没有顾客，即：排队的队列中没有顾客等待，服务台无服务对象。p仿真开始仿真开始：以第一个顾客到达时刻为仿真的起始点。?事件何时出现？在仿真中，通过随机数随机数来产生！1 1顾客到达间隔时间服从1-8分钟的均匀分布

17、。到达间隔时间（分钟）概率累计概率随机数区间10.1250.12500112520.1250.25012625030.1250.37525137540.1250.50037650050.1250.62550162560.1250.75062675070.1250.87575187580.1251.000876000（0，1）均匀分布到达事件的产生到达时间间隔的确定顾客随机数到达时间间隔（分钟）顾客随机数到达时间间隔（分钟）1-62903296387988836276883574115191532597881032032 2服务事件：服务时间为16分钟，其概率为0.10,0.20,0.30,0.

18、25,0.10,0.05服务时间（分钟）概率累计概率随机数区间10.100.10011020.200.30113030.300.60316040.250.85618550.100.95869560.051.009600（0，1）均匀分布服务事件的产生服务时间确定顾客随机数服务时间（分钟）顾客随机数服务时间（分钟）174466942011791538448774433399355272105833 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-40040402818

19、8901436414141804541315182136058223232502263426263004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-40040402818890143641414180454131518213605822323250226342626300417853434390548744141450429254345502

20、7010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-400404028188901436414141804541315182136058223232502263426263004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待

21、时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-400404028188901436414141804541315182136058223232502263426263004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-40040402818890143641414180454131518213605822323250226342626

22、3004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-400404028188901436414141804541315182136058223232502263426263004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时

23、间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-400404028188901436414141804541315182136058223232502263426263004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-40040402818890143641

24、4141804541315182136058223232502263426263004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-40040402818890143641414180454131518213605822323250226342626300417853434390548744141450429254345502701033465

25、0534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-400404028188901436414141804541315182136058223232502263426263004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时

26、间时间服务员服务员空闲时间空闲时间1-400404028188901436414141804541315182136058223232502263426263004178534343905487441414504292543455027010334650534704635944183 3顾客顾客到达到达间隔间隔时间时间服务服务时间时间到达到达时刻时刻服务开服务开始时刻始时刻服务结服务结束时刻束时刻等待等待时间时间逗留逗留时间时间服务员服务员空闲时间空闲时间1-40040402818890143641414180454131518213605822323250226342626300417853

27、4343905487441414504292543455027010334650534704635944184 4（1）全部顾客的平均等待时间为分钟顾客总数顾客等待的总时间9.0109（2）顾客必须在队列中等待的概率为3.0103顾客总数排队顾客数到达系统的动态实体中，30%需要排队。（3）服务员空闲概率为34.05318仿真总时间服务员空闲时间 服务员忙的概率为1-0.34=0.66，即服务机构的利用率为66%（4）平均服务时间为分钟顾客总数各顾客服务时间之和5.31035服务时间分布的均值分钟2.305.0*610.0*525.0*430.0*320.0*210.0*1)(0stssstPttETs（5）平均到达间隔时间为分钟顾客总数到达顾客间隔时间之和1.59461（6）在队列中排队顾客的平均等待时间为分钟排队顾客数各顾客排队时间之和339（7）顾客在系统中逗留的平均时间为分钟顾客总数时间之和各顾客在系统中的逗留4.41044一、排队系统的基本概念一、排队系统的基本概念二、到达时间间隔和服务时间分布二、到达时间间隔和服务时间分布三、排队系统的分析三、排队系统的分析四、排队系统的仿真四、排队系统的仿真