《学校数模培训课件新排队论——录像用》由会员分享，可在线阅读，更多相关《学校数模培训课件新排队论——录像用（57页珍藏版）》请在金锄头文库上搜索。
1、西安电子科技大学西安电子科技大学 排队论模型排队论模型 西安电子科技大学数学与统计学院西安电子科技大学数学与统计学院 李李 伟伟 西安电子科技大学西安电子科技大学 排队论排队论-随机服务系统随机服务系统 商店、超市等收款处排队付款商店、超市等收款处排队付款 车站、民航等售票处依次购买车船票车站、民航等售票处依次购买车船票 各种生产系统、存储系统、运输系统等 一系列等待现象比比皆是 各种生产系统、存储系统、运输系统等 一系列等待现象比比皆是 西安电子科技大学西安电子科技大学 排队论模型排队论模型 一、排队论基本概念 二、排队模型的数量指标 三、排队系统中常见的分布 四、排队模型的记号方案 一、排
2、队论基本概念 二、排队模型的数量指标 三、排队系统中常见的分布 四、排队模型的记号方案 五、几种排队论模型五、几种排队论模型 西安电子科技大学西安电子科技大学 一、排队论基本组成一、排队论基本组成 实际上排队的过程可由下面几个图理解实际上排队的过程可由下面几个图理解: 西安电子科技大学西安电子科技大学 西安电子科技大学西安电子科技大学 西安电子科技大学西安电子科技大学 基本组成基本组成 排队系统的三个基本组成部分排队系统的三个基本组成部分 输入过程 (顾客到达规律)输入过程 (顾客到达规律) 排队规则 (顾客按照一定规则排队等待服务)排队规则 (顾客按照一定规则排队等待服务) 服务机构 (服务
3、机构的设置，服务台的数量， 服务的方式，服务时间分布等) 服务机构 (服务机构的设置，服务台的数量， 服务的方式，服务时间分布等) 输入 来源 输入 来源 队 列 队 列 服务机构服务机构 排队系统排队系统 顾客顾客 服务完离开服务完离开 西安电子科技大学西安电子科技大学 基本组成 输入过程基本组成 输入过程 顾客总体（顾客源）数量顾客总体（顾客源）数量 有限无限有限无限 顾客到来方式可能是一个一个也可能是成批顾客到来方式可能是一个一个也可能是成批 顾客到达间隔时间: 到下一个顾客到达的时间顾客到达间隔时间: 到下一个顾客到达的时间 一般是服从某一概率分布（例如：指数分布）一般是服从某一概率分
4、布（例如：指数分布） 顾客的行为假定为:顾客的行为假定为: 在未服务之前不会离开； 在未服务之前不会离开； 当看到队列很长的时候离开；当看到队列很长的时候离开； 从一个队列移到另一个队列。从一个队列移到另一个队列。 西安电子科技大学西安电子科技大学 基本组成排队规则基本组成排队规则 队列容量队列容量 有限/无限有限/无限 排队规则排队规则 先来先服务(FCFS)；后来先服务(LCFS)；随 机服务(RSS)；有优先权的服务(PS)；排队模 型中也用到服务中的“一般规则（GD）”它 先来先服务(FCFS)；后来先服务(LCFS)；随 机服务(RSS)；有优先权的服务(PS)；排队模 型中也用到服
5、务中的“一般规则（GD）”它 包括前三种排队规则。包括前三种排队规则。 西安电子科技大学西安电子科技大学 基本组成服务规则基本组成服务规则 服务机构可以有一个，也可以有多个；服务机构可以有一个，也可以有多个； 对于多个服务台可以是并列、串列、混合排 列； 对于多个服务台可以是并列、串列、混合排 列； 服务方式可以是一个或成批；服务方式可以是一个或成批； 西安电子科技大学西安电子科技大学 二、排队模型的数量指标二、排队模型的数量指标 平均队长：排队系统中顾客数的平均值，平均队长：排队系统中顾客数的平均值， s L 平均队列长：排队系统中等待服务的顾客数平均值，平均队列长：排队系统中等待服务的顾客
6、数平均值， q L 平均逗留时间：一个顾客在系统中停留的时间平均值， 平均等待时间：一个顾客在系统中排队等待的时间平 均值， 平均逗留时间：一个顾客在系统中停留的时间平均值， 平均等待时间：一个顾客在系统中排队等待的时间平 均值， s W q W 西安电子科技大学西安电子科技大学 二、排队模型的数量指标二、排队模型的数量指标 平均到达率：单位时间内到达顾客的平均数平均到达率：单位时间内到达顾客的平均数 平均服务率：单位时间内被服务顾客的平均数 服务强度：单位时间内的服务强度 平均服务率：单位时间内被服务顾客的平均数 服务强度：单位时间内的服务强度 时刻t系统中顾客数为n的概率, 若时刻t系统中
7、顾客数为n的概率, 若 lim( ) nn t P tP 称为稳态解（统计平衡状态解）称为稳态解（统计平衡状态解） 西安电子科技大学西安电子科技大学 三、排队系统中常见的分布三、排队系统中常见的分布 1.泊松分布1.泊松分布 21 12 12 ()21 1221 ( )0, )( , ) , ) () ( , )( )( ) ! . n n tt n N ttP t t t tn tt P t tP N tN tne n 设表示在时间内到达的顾客数， 表示在时间段内有 个顾客到达的概率， 若满足以下三个条件，称顾客的到达形成参数 为 的泊松流 ,: (1)(); (2)1-(); (3)();
8、 t tt tt tt t 在 内有 有一个顾客到达的概率 没有一个顾客到达的概率 多于一个顾客到达的概率 西安电子科技大学西安电子科技大学 2. 负指数分布2. 负指数分布 三、排队系统中常见的分布三、排队系统中常见的分布 当顾客流为泊松流时，两个顾客相继到达的时间间隔 服从负指数分布；同理，系统中一个顾客的服务时间 也服从负指数分布 期望（均值） 分布函数 期望（均值） 分布函数 T V ,: (4)(); (5)1-(); (6)(); t tt tt tt t 若顾客流为泊松分布，服务时间服从于参数 为 的负指数分布，则在 内有 有一个顾客被服务完的概率 没有一个顾客被服务完的概率 多
9、于一个顾客被服务完的概率 12, 1 1 2 1 , : () ( ) (1)! 11 ( ) ,( ) k k k i k ukt k k i i kv vv kTv k ukt fte k E TE vT k k D 阶 记 个顾客到达系统的时间间隔分别为 独立同服从于参数为的负 爱尔 指数分布，则 朗服 且 分从于布 三、排队系统中常见的分布三、排队系统中常见的分布 3. 爱尔郎分布3. 爱尔郎分布 西安电子科技大学西安电子科技大学 四、记号方案四、记号方案 (Kendall 记号) 一般形式：(Kendall 记号) 一般形式：X/Y/Z/A/B/CX/Y/Z/A/B/C X顾客到达时
10、间间隔分布/Y服务时间分布/Z服务台 数目/A排队系统允许的最大顾客容量/B顾客总体 数量/C排队规则 X顾客到达时间间隔分布/Y服务时间分布/Z服务台 数目/A排队系统允许的最大顾客容量/B顾客总体 数量/C排队规则 M/M/1/FCFS M/M/1/FCFS ServerQueue Arrival 西安电子科技大学西安电子科技大学 X表示相继X表示相继到达时间间隔到达时间间隔的分布，Y表示的分布，Y表示服务时间服务时间的分布，X,Y 取值有以下几种情况: M表示泊松过程或负指数分布； D表示确定型分布； 的分布，X,Y 取值有以下几种情况: M表示泊松过程或负指数分布； D表示确定型分布；
11、 E Ek k表示k阶爱尔朗分布； G表示一般服务时间分布; GI表示一般相互独立的时间间隔分布. 表示k阶爱尔朗分布； G表示一般服务时间分布; GI表示一般相互独立的时间间隔分布. 四、记号方案四、记号方案 西安电子科技大学西安电子科技大学 Z表示服务台(员)个数：“1”则表示单个服 务台，“c”。(c1)表示多个服务台。 A表示系统中容量限额，或称等待空间容 量； Z表示服务台(员)个数：“1”则表示单个服 务台，“c”。(c1)表示多个服务台。 A表示系统中容量限额，或称等待空间容 量； B表示顾客源数目，分有限与无限两种， 顾客源无限，此时一般也可省略不写。 C表示服务规则 B表示顾
12、客源数目，分有限与无限两种， 顾客源无限，此时一般也可省略不写。 C表示服务规则 四、记号方案四、记号方案 西安电子科技大学西安电子科技大学 C C表示服务规则，常用下列符号： (1)FCFS：表示先到先服务的排队规则； (2)LCFS：表示后到先服务的排队规则； 表示服务规则，常用下列符号： (1)FCFS：表示先到先服务的排队规则； (2)LCFS：表示后到先服务的排队规则； (3)PR：表示优先权服务的排队规则。 (4)随机服务 省略时代表的是FCFS（先到先服务）。 (3)PR：表示优先权服务的排队规则。 (4)随机服务 省略时代表的是FCFS（先到先服务）。 四、记号方案四、记号方案
13、 西安电子科技大学西安电子科技大学 五、排队论模型五、排队论模型 单服务台模型分为3种 设系统输入过程服从泊松流,服务时间服从负指数分布,单服 务台: 单服务台模型分为3种 设系统输入过程服从泊松流,服务时间服从负指数分布,单服 务台: (1)标准型:M/M/1/ / （M/M/1） (2)系统容量有限型:M/M/1/ N / (3)顾客源有限型:M/M/1/ /m (1)标准型:M/M/1/ / （M/M/1） (2)系统容量有限型:M/M/1/ N / (3)顾客源有限型:M/M/1/ /m 西安电子科技大学西安电子科技大学 (1)标准型:M/M/1(1)标准型:M/M/1 标准型表示顾客
14、源为无限的，顾客的到达相互 独立，到达规律服从参数为的泊松分布：单 标准型表示顾客源为无限的，顾客的到达相互 独立，到达规律服从参数为的泊松分布：单 服务台、队长无限、先到先服务；各顾客的服 务时间相互独立，且同服从于参数为的负指 数分布。 服务台、队长无限、先到先服务；各顾客的服 务时间相互独立，且同服从于参数为的负指 数分布。 西安电子科技大学西安电子科技大学 情 况 时刻t 的顾 客数 在区间(t,t+t) 到达 离去 时刻 (t,t+t) 的顾客 数 Pn(t +t) An0 0nPn(t)(1- t)(1-u t) Bn+1 0 1n Pn+1(t)（1- t）(u t) Cn-11
15、 0n Pn-1(t)（ t）(1-u t) Dn1 1nPn(t)( t)(u t) 现在考虑在t+t时刻系统中有n个顾客（即状态为n）的 概率Pn(t +t)，如下表： 现在考虑在t+t时刻系统中有n个顾客（即状态为n）的 概率Pn(t +t)，如下表： 西安电子科技大学西安电子科技大学 1 1 11 0 01 ()( )(1)( ) ( )() ,0, ( ) ( )( )()( ) ( ) 0( )( ) ( ) 0 nnn n n nnn n P ttP tttPtt Pttt tt dP t PtPtP t dt dP t nP tP t dt dP t t dt 于是我们得到 两端移项除以当时 当时，类似地可有 当时， 01 11 0 ()0, 1 nnn PP PPPn 其稳态概率方程为 西安电子科技大学西安电子科技大学 0 0 00 0 1, :11 1 1,(1),1 n n nn n n P PP PPn n
