排队论QeueingTheory.ppt

排队论课件 排队论（Queueing Theory） 基本模型 M/M/1 模型 M/M/c 模型 其他模型 结束语 基本的排队模型 基本组成 概念与记号 指数分布和生灭过程 基本组成 基本排队模型 － 输入过程 顾客来源 有限/无限 顾客数量 有限 无限 经常性的顾客来源. 顾客到达间隔时间: 到下一个顾客到达的时间. 服从某一概率分布. (指数分布) 顾客的行为假定为: 在未服务之前不会离开; 当看到队列很长的时候离开； 从一个队列移到另一个队列。 基本排队模型－队列/排队规则 队列 队列容量 有限/无限 排队规则 先来先服务（FCFS）；后来先服务； 随机服务；有优先权的服务； 基本排队模型－服务规则 服务机构 服务设施， 服务渠道与服务台 服务台数量 服务时间分布: 指数, 常数, k级Erlang 基本排队模型－记号方案 基本排队模型－记号 基本排队模型－统计平稳条件下的记号 统计平稳条件下的记号 L, W, Lq, Wq 指数分布 指数分布性质1 指数分布性质2 指数分布性质3 指数分布性质4 指数分布性质5 M/M/1/?/? 或 M/M/1 模型 一个基本地排列模型. 一个服务台, 到达率 ? 和服务率 ? 都服从指数分布。 M/M/1 举例 M/M/1/N/?单一服务台，固定长度 固定长度排队意味着若到了最大系统容量顾客将不能进入系统. M/M/1/N/? 举例 增加更多服务台 M/M/c 所有服务台是空的概率P0,和所有服务台都在忙的概率 P?,需要下面比较复杂的公式。 M/M/c 举例 其他模型 M/M/c/K/K 顾客来源是有限的服务系统. 例如： 一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客. M/D/1 服务时间不变的服务系统. D/M/1 确定性到达模式, 及指数分布服务时间. 例如：医生赴约治病的时间表. M/E k/1 服务服从 Erlang 分布. 例如：用相同平均时间去完成一些程序。 结束语 排队论是专门研究带有随机因素，产生拥挤现象的优化理论。也称为随机服务系统。 排队论应用十分广泛。 * * ♂ ※ ♂ 输入来源 队 列 服务机构 排队系统 顾客 服务完离开 排队系统的三个基本组成部分. 输入过程 (顾客按照怎样的规律到达); 排队规则 (顾客按照一定规则排队等待服务); 服务机构 (服务机构的设置,服务台的数量,服务的方式,服务时间分布等) ♂ ♂ ♂ ♂ Server Queue Arrival 顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则 (Kendall 记号) M/M/1/?/?/FCFS M/M/1 /? M: 指数分布 (Markovian) D: 定长分布 (常数时间) Ek: k级Erlang 分布 G: 普通的概率分布 (任意概率分布) 系统状态 = 排队系统顾客的数量。 N(t) = 在时间 t 排队系统中顾客的数量。 队列长度 = 等待服务的顾客的数量。 Pn(t) = 在时间t,排队系统中恰好有n个顾客的概率。 s = 服务台的数目。 ?n = 系统有n个顾客时的平均到达率（单位时间平均到达的顾客人数即是平均到达率） ?n = 系统有n个顾客时的平均到达率 ? = 对任何n都是常数的平均到达率. = 对任何n都是常数的平均到达率. 1/? = 期望到达间隔时间 1/? = 期望服务时间 ? = 服务强度， 或称使用因子, ?/(s?) 平均队长 平均等待队长 平均等待时间 平均逗留时间 Little’s formula ♂ 密度函数 均值 方差 随机变量 T 分布函数 ? fT(t) t ? fT(t) ?t ?t t fT(t) 是一个严格下降函数 无后效性 不管多长时间(?t)已经过去， 逗留时间的概率分布与下一个事件的相同. 几个独立的指数分布的随机变量的最小有一个指数分布 几个独立的指数分布的随机变量的和还是一个指数分数的随机变量 T1(?1) T1(?2) T1(?3) T (?1 +?2 +?3) 指数分布 Poisson分布 服务时间的概率 = t 在t时间内已经服务n个顾客的概率 1/?: 平均服务时间 平均服务率= ? ♂ ♂ ♂ ♂ * * *