排队论及排队系统优化.ppt

第六章排队论及排队系统优化,排队现象与排队系统;排队模型与系统参数;排队系统时间参数分布规律;排队系统的生灭过程与状态转移方程;排队系统分析;单服务台负指数分布模型多服务台负指数分布模型排队系统优化分析;,6.1排队现象与排队系统,一、排队现象,（1）由于顾客到达和服务时间的随机性，现实中的排队现象几乎不可避免；（2）排队过程，通常是一个随机过程，排队论又称“随机服务系统理论”；,二、排队系统,（一）排队服务过程,（二）排队系统的要素及其特征,1、排队系统的要素：,（1）顾客输入过程；（2）排队结构与排队规则；（3）服务机构与服务规则；,2、排队系统不同要素的主要特征：,（1）顾客输入过程,顾客源(总体)：有限/无限;顾客到达方式：逐个/逐批;(仅研究逐个情形)顾客到达间隔：随机型/确定型;顾客前后到达是否独立：相互独立/相互关联；输入过程是否平稳：平稳/非平稳；(仅研究平稳性),（2）排队结构与排队规则,顾客排队方式：等待制/即时制(损失制);排队系统容量：有限制/无限制;排队队列数目:单列/多列;是否中途退出:允许/禁止;是否列间转移:允许/禁止;(仅研究禁止退出和转移的情形),（3）服务机构与服务规则,服务台(员)数目;单个/多个;服务台(员)排列形式;并列/串列/混合;服务台(员)服务方式;逐个/逐批;(研究逐个情形)服务时间分布;随机型/确定型;服务时间分布是否平稳:平稳/非平稳;(研究平稳情形),6.2排队模型与系统参数,一、排队模型,(一)排队模型表示方法,1、D.G.Kendall(1953)表示法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）一般服务时间分布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)稳态概率PnPn=Pn(t);一般，排队系统运行了一定长的时间后，系统状态的概率分布不再随时间t变化，即初始时刻（t=0）系统状态的概率分布(Pn(0)，n0）的影响将消失。,(二)系统运行指标参数评价排队系统的优劣。,1、队长与排队长(1)队长:系统中的顾客数（n）；期望值Ls=n*Pn(2)排队长:系统中排队等待服务的顾客数;期望值Lq=,Lq=Ls-正被服务的顾客数,2、逗留时间与等待时间(1)逗留时间:指一个顾客在系统中的全部停留时间；期望值，记为Ws(2)等待时间:指一个顾客在系统中的排队等待时间；期望值，记为Wq,Ws=Wq+E服务时间,3、其他相关指标(1)忙期:指从顾客到达空闲服务机构起到服务机构再次空闲的时间长度；(2)忙期服务量：指一个忙期内系统平均完成服务的顾客数；(3)损失率:指顾客到达排队系统，未接受服务而离去的概率；(4)服务强度：=/c；,6.3排队系统时间参数分布规律,一、顾客到达时间间隔分布(一)泊松流与泊松分布,如果顾客到达满足如下条件,则称为泊松流:(1)在不相互重叠的时间区间内，到达顾客数相互独立(无后效性).(2)对于充分小的时间间隔内，到达1个顾客的概率与t无关，仅与时间间隔成正比(平稳性)：(3)对于充分小的时间间隔，2个及以上顾客到达的概率可忽略不计(普通性)。,对泊松流，在时间t系统内有n个顾客的概率服从如下泊松分布EN(t)=t;VarN(t)=t;单位时间平均到达的顾客数；,推导过程：P319-320,若顾客到达间隔T的概率密度为则称T服从负指数分布，分布函数如下：若顾客流是泊松流时，顾客到达的时间间隔显然服从上述负指数分布(WHY);ET=1/;VarT=1/2;T=1/,(二)泊松流到达间隔服从负指数分布,二、顾客服务时间分布(一)负指数分布,(1)对一个顾客的服务时间Ts，等价于相邻两个顾客离开排队系统的时间间隔。若Ts服从负指数分布，其概率密度和分布函数分别为则ETs=1/;VarTs=1/2;Ts=1/(2)ETs=1/：每个顾客的平均(期望)服务时间；:单位时间服务的顾客数，平均(期望)服务率；,(二)爱尔朗(Erlang)分布,(1)设v1,v2,vk是k个相互独立的随机变量,服从相同参数1/k的负指数分布,则:T=v1+v2+vk的概率密度为称T服从k阶爱尔朗分布。(2)ET=1/;VarT=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满足以下条件:(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无关;与系统当前状态n有关，而与以前的状态无关；,马尔可夫性质,(三)排队系统的生灭过程,顾客到达“生”；顾客离开“灭”,顾客到达,顾客离去,(1)生灭过程示意,若排队系统具有下列性质:(1)顾客到达为泊松流，时间间隔服从参数为n的负指数分布;(2)顾客服务时间服从参数为n的负指数分布;则排队系统的随机过程N(t),t=0具有马尔可夫性质,为一个生灭过程.,(2)生灭过程定义,二、排队系统的状态转移方程,(一)排队系统状态的概率及其分布,(1)瞬态概率Pn(t)表示时刻系统状态N(t)=n的概率;(2)稳态概率PnPn=Pn(t);,一般，稳态概率Pn的分布，是分析计算排队系统运行优劣的基础。,(二)排队系统状态概率的微分差分方程,推导过程：P323,求解可得瞬态概率Pn(t),(三)排队系统状态转移方程,求解可得稳态概率Pn,令,则,排队系统状态转移方程,(四)排队系统状态转移图,三、排队系统稳态概率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）人力资源决策系统；,