第8章排队论剖析.ppt

1 排队论（Queuing Theory） 一些排队系统的例子 排队系统 顾 客 服务台 服 务 电话系统 电话呼叫 电话总机 通呼叫或取消呼叫 售票系统 购票旅客 售票窗口 收款、售票 设备维修 出故障的设备 修理工 排除设备故障 防空系统 进入阵地的敌机 高射炮 瞄准、射击直至 敌机被击落或离开 飞机降落 达到机场上空的飞机 跑道 降落 诊疗系统 病人 医生或设备 诊断（或治疗） 排队可以是有形的队列，也可以是无形的队列。排队可以是人，也可以是物。 常见排队系统结构图 常见排队系统结构图 基本的排队模型 基本组成 概念与记号 常用概率分布（指数分布等） 基本组成 排队系统的三大要素描述 一、输入过程 说明顾客按怎样的规律达到系统，通常从 3 方面刻画： （a ）顾客总体（顾客源）数，（b ）达到方式，（c ）顾客相继达到的时间间隔分布。 二、排队及排队规则 排队:(a)损失制排队 （b）等待制排队（c）混合制排队 排队规则:（a）先到先服务FCFS（b）后到先服务LCFS，（c）有优先权服务PS，（d）随机服务RF。 三、服务机制 说明顾客按怎样的规律接受服务，通常从 3方面刻画： （a ）服务台数目及其连接形式（并联或串联），（b ）顾客接受服务的方式（单个或成批），（c ）服务时间分布。 基本排队模型－记号方案 排队论研究的基本问题 基本排队模型－记号 基本排队模型－统计平稳条件下的记号 统计平稳条件下的记号 关心的项目 关心的项目: 1、系统中无顾客的概率 P0 2、系统中平均排队的顾客数 Lq 3、系统中的平均顾客数 L 4、系统中顾客平均的排队等待时间 Wq 5、系统中顾客的平均逗留时间 W 6、系统中顾客必须排队等待的概率 Pw 7、系统中恰好有 n 个顾客的概率 Pn 定长分布（D） 负指数分布（M） 指数分布性质 Poisson 过程（又称为 Poisson 流、最简单流）是排队论中最为常见的一种描述顾客到达规律的特殊随机过程。 定义：设 N(t)为时间 ? 0,t ? 内达到系统的顾客数，如果满足下面三个条件： 平稳性：在 ?t ， t +? t ? 内有一个顾客达到的概率为 ? ? t + ?( ?t ) ； 独立性：在任意两个不相交时间区间内顾客达到相互独立； 普通性：在 ?t , t +? t ? 内多于一个顾客达到的概率为 ?( ?t ) 。 则称 ｛N（t），t ≥0 ｝为Poisson 过程。 Poisson 过程与负指数分布 定理1 设 N(t)为时间 [0,t]内达到系统的顾客数，则{N(t),t≥0 }为Poisson 过程的充要条件是： 定理2 设 N(t)为时间 [0,t] 内达到系统的顾客数，则{N(t),t≥0 }为参数为 ? 的Poisson 过程的充要条件是：相继达到时间间隔服从相互独立的参数为 ? 的负指数分布。 上述定理阐述了Poisson 过程与负指数分布的等价性。 总结 M/M/1 / ?举例（1） M/M/1 / ?举例（1） M/M/1 / ?举例（2） M/M/c 举例 其他模型 M/M/c/K/K 顾客来源是有限的服务系统. 例如： 一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客. M/D/1 服务时间不变的服务系统. D/M/1 确定性到达模式, 及指数分布服务时间. 例如：医生赴约治病的时间表. M/E k/1 服务服从 Erlang 分布. 例如：用相同平均时间去完成一些程序。 M/M/1/?系统 M/M/1/?系统的几个重要指标 Little公式 M/