数学建模与--排队论 .ppt

排队论课件 排队论（Queueing Theory） 现实生活中的实例： 进餐馆就餐 一、排队系统的特征及排队论： 顾客为了得到某中服务而到达系统，若不能获得服务而允许排队等待，则加入等待队伍，待获得服务后离开系统。 排队的形式： 随机服务系统： 二、排对系统的描述 系统由三个部分组成： 四、排队系统的主要数量指标和记号 六、M/M/S等待制排队模型 其他模型 M/M/c/K/K 顾客来源是有限的服务系统. 例如： 一个饭店有 X 张桌子和 Y个服务生服务来源有限的顾客. M/D/1 服务时间不变的服务系统. D/M/1 确定性到达模式, 及指数分布服务时间. 例如：医生赴约治病的时间表. M/E k/1 服务服从 Erlang 分布. 例如：用相同平均时间去完成一些程序。 结束语 排队论是专门研究带有随机因素，产生拥挤现象的优化理论。也称为随机服务系统。 排队论应用十分广泛。 * * 到图书馆借书 去售票处购票 在车站等车等等 顾客到达 队列 服务台 服务完成后离去 服务台1 服务台2 服务台s 顾客到达 队列 服务完成后离去 顾客到达 队列1 队列2 队列s 服务台1 服务台2 服务台s 服务完成后离去 服务完成后离去 服务完成后离去 输入来源 队 列 服务机构 排队系统 顾客 服务完离开 输入过程 排队和排队规则 服务机制 1、输入过程 （1）顾客总数量： 有限或者无限 （2）到达方式： 单个到达或成批到达 （3）到达方式： 顾客相继到达时间间隔的分布， 这是刻画 输入过程的最主要内容。 令 表示第n个顾客到达的时刻， 则有： 记 假设： 是独立同分布的，并记其分布函数为 关于 的分布， 排队论中经常用到以下几种： ① 定长分布（D）： 顾客相继到达时间间隔为确定的常数， 如产品通过传输带进入包装箱 ② 最简流（或称poisson分布）（M）： 顾客相继到达时间 间隔 为独立， 同负指数分布，其密度函数为： 2、排队及排队规则 （1）排队 分为有限和无限排队 ①损失制排队系统： 排队空间为零的系统 ②混合制排队系统： 等待制和损失制的结合，是指允许 排队，但是不允许队列无限长下去，具体的又分三种情况： （ⅰ） 队长有限，即等待空间有限 （ⅱ） 等待时间有限，即顾客在系统中等待时间不超过某一 给定的长度T （ⅲ） 逗留时间（等待时间和服务时间之和） （系统只能容纳K个顾客） 不难注意到损失制和等待制可以看成是混合制的特殊情况 如记 为系统中服务台的个数， 当 时， 混合制即为损失制 当 时， 即成为等待制。 (2)排队规则： 先来先服务（FCFS） 3、服务机制 主要包括：服务员的数量及其连接形式（串联或并联）； 顾客是单个还是成批接受服务的；服务时间的分布。 记某服务台的服务时间为V， 其分布函数为B(t), 密度函数 为b(t), 则常见的分布有： ① 定长分布（D）： 每位顾客接受的服务的时间是常数； ② 负指数分布（M）： 每位顾客接受服务时间相互独立， 具有相同的负指数分布： 其中 为一常数。 ③k阶爱尔朗分布 密度函数为 三、排队系统的符号表示 为了方便对众多的模型的描述，D.G.Kendall提出了一种 目前在排队论中被广泛的使用的“Kendall记号”， 一般形式为： X/Y/Z/A/B/C 其中X表示顾客相继到达时间间隔的分布， Y表示服务时间分 布， Z表示服务台的个数； A表示系统的容纳，即可容纳最多顾客数 B表示顾客源的数目； C表示服务规则； 表示了一个顾客的到达时间间隔服从相同的负指数分布， 服务时间为负指数分布、 单个服务台、 系统容量为无限、 顾客量无限、 排队规则为先来先服务的排队模型。 1、队长和排队长 2、等待时间和逗留时间 3、忙期和闲期 下面给出上述一些主要数量指标的常用记法： 时刻 t 系统中的顾客数，即队长 时刻 t 系统中排队的顾客数，即排队长 时刻 t 到达系统的顾客在系统中的逗留时间 时刻 t 到达系统的顾客在系统中的等待时间 上述数量指标与时间有关的随机变量，求它们的瞬时分布 非常困难。 讨论系统处于平衡状态下的性质： 记 为时刻t时系统处于状态n概率，即系统的瞬时分布 根据前面的约定，我们将主要分析系统的平衡分布，即当系统到 达统计平衡时时所处状态 n 概率，记为 又记： 系统处于平衡状态时队长，其均值为L，称为平均队长 系统处于平衡状态时排队长，其均值为 称为平均 排队长； 系统处于平衡状态时顾客的逗留时间， 均值为 称为 逗留时间； 系统处于平衡状态时顾客的等待时间， 其均值记为 称为平均等待时间； 当系统处于状态n时，新来顾客的平均到达率 （单位时 间内来到系统的平均顾客数） 当系统处于状态n时，整个系