运筹学17-排队论II-11培训资料.ppt

第17讲 排队论II 本讲提纲 1.生灭过程 2.单服务台负指数分布排队系统分析 2.1标准M/M/1模型(M/M/1/∞/∞) 2.2系统容量有限的M/M/1模型(M/M/1/N/∞) 2.3顾客源有限的M/M/1模型(M/M/1/∞/m) 1. 生灭过程(birth and death process ) 生灭过程是常用的随机过程之一，常用来描述生物体的增长和灭亡规律，排队系统中顾客人数的变化规律等。 以N(t)表示t时刻排队系统中的顾客人数(系统状态)，其状态空间J={0,1,2,…}，若满足： 给定N(t) = n，到下一个顾客到达(生)的间隔时间服从参数为 的负指数分布； 给定N(t) = n，到下一个顾客离去(灭)的间隔时间服从参数为 的负指数分布； 在同一时刻只可能发生一个生或一个灭。 则随机过程{N(t)，t≥0}为生灭过程。 根据定义，当系统处于N(t) = n时，下一个顾客到达的平均间隔时间为 ，也即单位时间内到达顾客的平均数为 ，如果单位时间足够小(即t时刻)，则 表示的就是在t时刻下一个顾客到达系统的概率。 类似地， 表示的是在t时刻一个顾客离开系统的概率。 根据上述分析，可画出生灭过程的状态转移图： 要求出系统瞬时状态N(t)的概率分布是很困难的，但当t足够大时，即系统运行一段时间后，达到平衡状态(稳态)，在稳态下，系统的每一状态满足统计平衡规律，即“流入=流出” 0 1 2 n-1 n n+1 2.1 M/M/1/∞/∞模型(标准的M/M/1模型) 问题的一般提法： 设：参数为 的泊松输入(M)/参数为 的负指数服务时间分布(M)/单服务台(1)/系统容易无限制(∞)/顾客源无限(∞)/先到先服务(FCFS) 求：(1) 稳态条件下，系统状态概率Pn ； (Pn表示系统中有n个顾客的概率) (2) 系统运行指标L，Lq，W，Wq 稳态条件下，系统状态概率的推导 (1) 画出状态转移图 状态转移图是处理稳态排队系统的一种工具，顾客到达率为 ，服务台的服务率为 ，当系统处于稳态时，应该满足统计平衡，对于每个状态n (n=0,1,2,...)，流出应等于流入。 (2) 根据状态转移图，列出平衡方程 对于状态0： 对于状态1： 对于每个状态n (n=0,1,2,...)，流入应等于流出 ......... 对于状态n： (3) 根据平衡方程，求排队系统稳态概率Pn 关于 的几点说明： ——服务强度 即顾客的顾客平均到达率 小于顾客平均服务率时， 系统才能达到统计平稳。 系统中至少有一个顾客的概率； 服务台处于忙的状态的概率； 反映系统繁忙程度 例：高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为100辆／小时，收费时间服从负指数分布，平均收费时间为15秒／辆。求 (1)、收费处空闲的概率； (2)、收费处忙的概率； (3)、系统中分别有1，2，3辆车的概率。 根据题意, =100辆/小时,1/=15秒=1/240（小时/辆）,即＝240（辆/小时）。 因此，=/=100/240=5/12。 系统空闲的概率为： P0=1-=1-(5/12)=7/12=0.583 系统忙的概率为： 1-P0=1-(1-)==5/12=0.417 系统中有1辆车的概率为： P1=(1-)=0.417×0.583=0.243 系统中有2辆车的概率为： P2=2(1-)=0.417 2×0.583=0.101 系统中有3辆车的概率为： P3=3(1-)=0.417 3×0.583=0.0421 系统运行指标 (1) 系统中的期望顾客数L 由期望的定义 (2) 队列中(排队等待)的期望顾客数Lq Little 公式 注：在一般的little 公式中， 应为 ，称为有效到达率，即顾客实际进入系统率，在本模型中，由于系统容量无限制，故 (3) 顾客在系统中逗留时间的期望值W (4) 顾客在队列中等待时间的期望值Wq 由Little公式： 由Little公式： 例： 高速公路入口收费处设有一个收费通道，汽车到达服从Poisson分布，平均到达速率为200辆/小时，收费时间服从负指数分布，平均收费时间为15秒/辆。求L、Lq、W和Wq。 解：根据题意，=200辆/小时，