系统建模与仿真-排队论.ppt

《系统建模与仿真-排队论.ppt》由会员分享，可在线阅读，更多相关《系统建模与仿真-排队论.ppt（39页珍藏版）》请在装配图网上搜索。

1、排队系统 系统建模与仿真1 目前在一些办事大厅如银行、电信、医院等公共服务场所，客户办理业务排长队的现象比较普遍，长时间的站立、拥挤，不仅使客户感到疲惫不堪，而且排队秩序也很难保持，既影响了办事效率也容易使客户产生不满情绪。排队管理系统是为改善办事大厅传统管理所存在的一些混乱、无序等弊端而开发的。 排队论(Queuing Theory)o 研究系统随机聚散现象和随机服务系统工作过程的数学理论和方法，又称随机服务系统理论，为运筹学的一个分支o有形和无形的排队或拥挤现象，如旅客购票排队，市内电话占线等现象 物流信息技术 o日排队论起源于20世纪初的电话通话。o 1909 1920年丹麦数学家、电气

2、工程师爱尔朗（A.K.Erlang）用概率论方法研究电话通话问题，从而开创了这门应用数学学科，并为这门学科建立许多基本原则。o他在热力学统计平衡理论的启发下，成功地建立了电话统计平衡模型，并由此得到一组递推状态方程，从而导出著名的埃尔朗电话损失率公式。 物流信息技术 系统建模与仿真4 o 20世纪30年代中期，当费勒(W.Feller)引进了生灭过程时，排队论才被数学界承认为一门重要的学科。o 20世纪50年代初，堪道尔(D.G.Kendall)对排队论作了系统的研究，他用嵌入马尔柯夫(A.A.Markov)链方法研究排队论，使排队论得到了进一步的发展。是他首先（1951年）用3个字母组成的符

3、号A/B/C表示排队系统。其中A表示顾客到达时间分布，B表示服务时间的分布，C表示服务机构中的服务台的个数。 物流信息技术 排队论课件6 基本组成输入来源队 列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.输入过程 (顾客按照怎样的规律到达);排队规则 (顾客按照一定规则排队等待服务); 服务机构 (服务机构的设置,服务台的数量,服务的方式,服务时间分布等) 排队论课件7 基本排队模型 输入过程o顾客来源 n有限/无限o顾客数量n有限n无限o经常性的顾客来源.n顾客到达间隔时间: 到下一个顾客到达的时间.n服从某一概率分布. (指数分布)o顾客的行为假定为:n在未服务之前不会离开;

4、 n当看到队列很长的时候离开；n从一个队列移到另一个队列。 排队论课件8 基本排队模型队列/排队规则o队列n队列容量o有限/无限n排队规则o先来先服务（FCFS）；后来先服务； 随机服务；有优先权的服务； 排队论课件9 基本排队模型服务规则o服务机构服务设施， 服务渠道与服务台n服务台数量n服务时间分布:o指数, 常数, k级Erlang 排队论课件10 基本排队模型记号方案ServerQueueArrival顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则 (Kendall 记号)M/M/1/ / /FCFS M/M/1 /M: 指数分布 (

5、Markovian)D: 定长分布 (常数时间)E k: k级Erlang 分布G: 普通的概率分布 (任意概率分布) 排队论课件11 基本排队模型记号系统状态 =排队系统顾客的数量。 N(t) =在时间 t 排队系统中顾客的数量。队列长度 =等待服务的顾客的数量。 Pn(t) =在时间t,排队系统中恰好有n个顾客的概率。 s =服务台的数目。 排队论课件12 基本排队模型统计平稳条件下的记号n =系统有n个顾客时的平均到达率（单位时间平均到达的顾客人数即是平均到达率）n =系统有n个顾客时的平均到达率 =对任何n都是常数的平均到达率.m =对任何n都是常数的平均到达率.1/ =期望到达间隔时

6、间1/ =期望服务时间 =服务强度， 或称使用因子, /(s ) 排队论课件13 统计平稳条件下的记号L qLqWW平均队长平均等待队长平均等待时间平均逗留时间 排队论课件14 L, W, Lq, WqLittles formulaWL qq WL 1 qWW 到达间隔时间与服务时间的分布 o泊松分布 o负指数分布 o爱尔朗分布 o统计数据的分布判断 物流信息技术 排队论课件16 指数分布密度函数 0for t0 0 )( tforetf tT 均值1)( TE方差21)( TVar随机变量 T分布函数 tetTP 1)( fT(t) t1)( TE 排队论课件17 指数分布性质1 )()0(

7、 ttTtPtTP fT(t) t ttfT(t) 是一个严格下降函数 排队论课件18 指数分布性质2 )()/( tTPtTttTP 无后效性)()( ) ( )( ) ( )/( )( )( tTPee eeeetTP ttTP tTP tTandttTP tTttTP tt ttttt 不管多长时间( t)已经过去， 逗留时间的概率分布与下一个事件的相同. 排队论课件19 指数分布性质3指数分布 0for t0 0 )( tforetf tT 1)( TE !)()( netntXP tn Poisson分布 ttXE )(服务时间的概率 = t在t时间内已经服务n个顾客的概率 1/ :

8、 平均服务时间平均服务率= 排队论课件20 M/M/1/ / 或 M/M/1 模型o一个基本地排列模型.o一个服务台, 到达率 和服务率 都服从指数分布。 2 ,1 1 1,(1 ) (1 )(1 )qq nnL LW WP 等待队长等待时间 排队论课件21 M/M/1 举例 M/M/s queuing computations Arrival rate 5 Service rate 6 Number of servers 1 Utilization 83.33% P(0), probability that the system is empty 0.1667Lq, expected que

9、ue length 4.1667 L, expected number in system 5.0000Wq, expected time in queue 0.8333 W, expected total time in system 1.0000 0 0.05 0.1 0.15 0.2 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40NUMBER IN SYSTEM Pro bab ility 物流信息技术 物流信息技术 物流信息技术 物流信息技术 物流信息技术 物流信息技术 物流信息技术 系统建模与仿真29 排队论课件30

10、 M/M/1/N/单一服务台，固定长度o固定长度排队意味着若到了最大系统容量顾客将不能进入系统. 1 1 10 01 , 21 1 ( 1)(1 ) , ,1 (1 )(1 )(1 ), 1 1,(1 ) N Nn nN Nq qN NNP L a N a Naa aa a aL L P PLW W WP 排队论课件31 M/M/1/N/ 举例 M/M/s with Finite Queue Arrival rate 5 Service rate 6 Number of servers 1 Maximum queue length 4 Utilization 74.94% P(0), prob

11、ability that the system is empty 0.2506Lq, expected queue length 1.2294 L, expected number in system 1.9788Wq, expected time in queue 0.2734 W, expected total time in system 0.4401Probability that a customer waits 0.7494 Probability that a customer balks 0.1007 00.05 0.10.15 0.2 0.250.3 0 2 4 6 8 10

12、 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40NUMBER IN SYSTEM Pro bab ility 排队论课件32 增加更多服务台 M/M/co所有服务台是空的概率P0,和所有服务台都在忙的概率 P ,需要下面比较复杂的公式。110 0 0 ( ) ( ), ! !(1 )( )!(1 ),1 11, n ccncq q c cPc n cc PP c P PL L cLW W W 排队论课件33 M/M/c 举例 M/M/s queuing computationsArrival rate 10 Service rate 6Number o

13、f servers 2 Utilization 83.33% P(0), probability that the system is empty 0.0909Lq, expected queue length 3.7879 L, expected number in system 5.4545Wq, expected time in queue 0.3788 W, expected total time in system 0.5455 00.02 0.040.06 0.080.1 0.120.14 0.16 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 3

14、0 32 34 36 38 40NUMBER IN SYSTEM Pro bab ility 物流信息技术 物流信息技术 物流信息技术 排队论课件37 其他模型o M/M/c/K/Kn顾客来源是有限的服务系统. 例如： 一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客.o M/D/1n服务时间不变的服务系统.o D/M/1n确定性到达模式, 及指数分布服务时间. 例如：医生赴约治病的时间表.o M/E k/1n服务服从 Erlang 分布. 例如：用相同平均时间去完成一些程序。 排队论课件38 结束语o排队论是专门研究带有随机因素，产生拥挤现象的优化理论。也称为随机服务系统。o排队论应用十分广泛。 系统建模与仿真39