《排队论及排队系统优化》由会员分享，可在线阅读，更多相关《排队论及排队系统优化（41页珍藏版）》请在金锄头文库上搜索。
1、第六章 排队论及排队系统优化排队现象与排队系统; 排队模型与系统参数; 排队系统时间参数分布规律;排队系统的生灭过程与状态转移方程 ; 排队系统分析;单服务台负指数分布模型多服务台负指数分布模型排队系统优化分析;6.1 排队现象与排队系统一、排队现象到达顾客 服务内容 服务机构病 人 诊断/手术 医生/手术台进港的货船 装货/卸货 码头泊位到港的飞机 降落 机场跑道电话拨号 通话 交换台故障机器 修理 修理技工修理技工 领取修配零件 仓库管理员上游河水 入库 水闸管理员 （1）由于顾客到达和服务时间的随机性，现实中的排队现象几乎不可避免；（2）排队过程，通常是一个随机过程，排队论又称“随机服务
2、系统理论”；二、排队系统（一）排队服务过程排队系统顾客源排队结构 顾客到来排队规则服务规则顾客离去服务机构。（二）排队系统的要素及其特征1、排队系统的要素：（1）顾客输入过程；（2）排队结构与排队规则；（3）服务机构与服务规则；2、排队系统不同要素的主要特征：（1）顾客输入过程顾客源(总体)：有限/无限; 顾客到达方式：逐个/逐批;(仅研究逐个情形) 顾客到达间隔：随机型/确定型; 顾客前后到达是否独立：相互独立/相互关联； 输入过程是否平稳：平稳/非平稳；(仅研究平稳性)顾客到达时刻i相继到达间隔时间ti（2）排队结构与排队规则顾客排队方式：等待制/即时制(损失制); 排队系统容量：有限制/
3、无限制; 排队队列数目: 单列/多列; 是否中途退出: 允许/禁止; 是否列间转移: 允许/禁止;(仅研究禁止退出和转移的情形)（3）服务机构与服务规则服务台(员)数目;单个/多个; 服务台(员)排列形式;并列/串列/混合; 服务台(员)服务方式;逐个/逐批;(研究逐个情形) 服务时间分布;随机型/确定型; 服务时间分布是否平稳:平稳/非平稳;(研究平稳情形)112c12c 12c服务台(员)为顾客服务的顺序:a)先到先服务(FCFS);b)后到先服务(LCFS);c)随机服务;d)优先服务;6.2 排队模型与系统参数一、排队模型(一)排队模型表示方法1、D.G.Kendall(1953)表示
4、法X / Y / Z 依据排队系统3个主要特征： （1） X 顾客到达间隔时间分布； （2） Y 服务台（员）服务时间分布； （3） Z 服务台（员）个数（单个或多个并列） ；2、国际排队论标准化会议(1971)表示法X / Y / Z / A / B / C（1） A 系统容量限制； （2） B 顾客源（总体）数目； （3） C 服务规则（FCFS，LCFS等）；略去后三项，即指 “X/Y/Z/FCFS”； 这里仅研究FCFS的情形；(二)到达间隔和服务时间典型分布（1） 泊松分布 M ； （2） 负指数分布 M ； （3） k阶爱尔朗分布 Ek； （4） 确定型分布 D； （5） 一般服务
5、时间分布 G；M/M/1，M/D/1，M/ Ek /1； M/M/c， M/M/c/m， M/M/c/N/ ，。(三)排队模型示例二、系统参数(一)系统运行状态参数1、系统状态 N(t)指排队系统在时刻t时的全部顾客数 N(t) ，包括“排队顾客数”和“正被服务顾客数 ”；系统状态的可能值如下：（1）系统容量无限制， N(t) =0，1，2，;(2) 系统容量为N时, N(t) =0,1,2,N;(3) 服务台个数为c/损失制, N(t) =0,1,2,c; 一般,系统状态N(t)是随机的。2、系统状态概率：(1)瞬态概率Pn(t) 表示时刻系统状态 N(t)=n 的概率;(2) 稳态概率Pn
6、Pn= Pn(t) ;一般，排队系统运行了一定长的时间后，系统状态的概率分布不再随时间t变化，即初始时刻（t=0）系统状态的概率分布(Pn(0) ，n0）的影响将消失。(二)系统运行指标参数评价排队系统的优劣。1、队长与排队长(1)队长: 系统中的顾客数（n）；期望值 Ls= n*Pn(2)排队长: 系统中排队等待服务的顾客数;期望值 Lq =Lq= Ls-正被服务的顾客数2、逗留时间与等待时间(1)逗留时间:指一个顾客在系统中的全部停留时间；期望值，记为 Ws(2)等待时间:指一个顾客在系统中的排队等待时间；期望值，记为 WqWs = Wq + E服务时间3、其他相关指标(1)忙 期: 指从
7、顾客到达空闲服务机构起到服务机构再次空闲的时间长度；(2)忙期服务量：指一个忙期内系统平均完成服务的顾客数；(3)损失率: 指顾客到达排队系统，未接受服务而离去的概率；(4)服务强度： = /c ；6.3 排队系统时间参数分布规律一、顾客到达时间间隔分布(一)泊松流与泊松分布如果顾客到达满足如下条件,则称为泊松流:(1) 在不相互重叠的时间区间内，到达顾客数相互独立(无后效性).(2) 对于充分小的时间间隔 内，到达1个顾客的概率与t无关，仅与时间间隔成正比 (平稳性)：(3) 对于充分小的时间间隔 ，2个及以上顾客到达的概率可忽略不计 (普通性)。 对泊松流，在时间t系统内有n个顾客的概 率
8、服从如下泊松分布 EN(t)=t ; Var N(t)=t ;单位时间平均到达的顾客数；推导过程：P 319-320 若顾客到达间隔T的概率密度为则称T服从负指数分布，分布函数如下： 若顾客流是泊松流时，顾客到达的时间间隔显然服从上述负指数分布(WHY); ET=1/ ; Var T=1/2 ; T=1/(二)泊松流到达间隔服从负指数分布二、顾客服务时间分布(一)负指数分布(1) 对一个顾客的服务时间Ts，等价于相邻两个顾客 离开排队系统的时间间隔。若Ts服从负指数分布，其概率密度和分布函数分别为则 ETs=1/ ; Var Ts=1/ 2 ; Ts=1/ (2) ETs=1/ ：每个顾客的平
9、均(期望)服务时间；:单位时间服务的顾客数，平均(期望)服务率 ；(二)爱尔朗(Erlang)分布(1) 设v1,v2,vk是k个相互独立的随机变量,服从相同参数1/ k的负指数分布,则:T= v1+v2+vk的概率密度为称T服从k阶爱尔朗分布。(2) ET=1/ ; Var T=1/( k2) (3) T的意义之一: k个串联服务台的总服务时间！6.4 排队系统的生灭过程与状态转移方程一、排队系统的生灭过程(一)生灭过程的背景与定义设某系统具有状态集S=0,1,2,或S=0,1,2,k, N(t)表示系统在时刻 t (t=0) 的状态。若在N(t)=n的条件下，随机过程N(t),t=0满足
10、以下条件:(1) N(t+t)转移到“n+1”的概率为n(t ) ;(2) N(t+t)转移到“n-1”的概率为n(t ) ;(3) N(t+t)转移到其他状态“S-n+1,n-1”的概率为o(t )(高阶无穷小) ;则称随机过程N(t),t=0为生灭过程。n ，n ，t ( ？)(二)生灭过程状态变化的性质(1) 在无穷小t内,系统或生长1个;或灭亡1个;或既 不生长又不灭亡（概率:1- n(t ) -n(t ) ）; (2)系统生长一个的概率n(t )与t有关，而与t无关; 与系统当前状态n有关，而与以前的状态无关 ；(3)系统灭亡一个的概率n(t )与t有关，而与t无关; 与系统当前状态
11、n有关，而与以前的状态无关 ；马尔可夫性质(三) 排队系统的生灭过程 顾客到达“生”； 顾客离开“灭”顾客到达顾客离去n ， n ，(1)生灭过程示意若排队系统具有下列性质:(1) 顾客到达为泊松流，时间间隔服从参 数为n的负指数分布;(2) 顾客服务时间服从参数为 n的负指数分布;则排队系统的随机过程N(t),t=0具有马 尔可夫性质, 为一个生灭过程.(2)生灭过程定义二、排队系统的状态转移方程(一) 排队系统状态的概率及其分布(1)瞬态概率Pn(t) 表示时刻系统状态N(t)=n的概率;(2) 稳态概率PnPn= Pn(t) ;一般，稳态概率Pn的分布，是分析计算排队系统运行优劣的基础。
12、(二) 排队系统状态概率的微分差分方程推导过程：P 323求解可得瞬态概率Pn(t) (三) 排队系统状态转移方程 求解可得稳态概率Pn令则排队系统状态转移方程(四) 排队系统状态转移图在任意状态n达到稳态平衡的条件： 产生该状态的平均速率=该状态转变成其他状态的平均速率 （流入=流出）三、 排队系统稳态概率Pn的求解 对一般排队系统，均有下式成立 其中有效到达率为四、 排队系统性能参数的一般关系 Little 公式6.4 典型排队系统分析6 .4 .1 单服务台负指数分布排队系统6 .4 .2 多服务台负指数分布排队系统6.5 典型排队系统优化分析（1）一般排队系统的优化目标与方法； （2）M/M/1系统中服务率的优化； （3）M/M/C系统中服务台数的优化；6.6 排队系统实例分析（1）银行排队服务系统； （2）人力资源决策系统；
