运筹学排队论PPT课件

1、1排队结构服务机构顾客源顾客到达排队规则服务规则离去图1 排 队系统示意图 排队系统一般有三个基本组成部分：1.1.输入过程；2.2.排队规则；3.3.服务机构。现分别说明：第1页/共39页2 输入即为顾客的到达，可有下列情况： 1）顾客源可能是有限的，也可能是无限的。 2）顾客是成批到达或是单个到达。 3）顾客到达的间隔时间可能是随机的或确定的。 4）顾客到达可能是相互独立的或关联的。所谓独立就是以前顾客的到达对以后顾客的到达无影响。 5）输入过程可以是平稳的（stationarystationary）或说是对时间齐次的（Homogeneous in timeHomogeneous in t

2、ime），也可以是非平稳的。输入过程是平稳的是指顾客相继到达的间隔时间分布和参数（均值、方差）与时间无关；非平稳的则是与时间相关，非平稳的处理比较困难。 第2页/共39页3 1）顾客到达后接受服务分为即时制（损失制）和等待制。即时制不形成队列，而对于等待制将会形成队列，顾客可以按下规则接收服务：（1）先到先服务 FCFS （2）后到先服务 LCFS （3）随机服务RAND （4）有优先权服务 PR。 2）从队列的空间可分为有容量限制和无容量限制。 3）从队列数可分为单列和多列。第3页/共39页4 1 1）服务机构可以是单服务员和多服务员服务，这种服务形式与队列规则联合后形成了多种不同队列，不同

3、形式的排队服务机构，如：112n. . .12n。单队单服务台多队多服务台（并列)单队多服务台（并列）12n.12312单队多服务台（串列）混合形式第4页/共39页5 上述特征中最主要的、影响最大的是： 顾客相继到达的间隔时间分布 服务时间的分布 服务台数 D.G.KendallD.G.Kendall，19531953提出了分类法，称为KendallKendall记号( (适用于并列服务台) )即：X/Y/Z:A/B/CX/Y/Z:A/B/C 2)服务方式分为单个顾客服务和成批顾客服务。 3)服务时间分为确定型和随机型。 4)服务时间的分布在这里我们假定是平稳的。第5页/共39页6 式中：X顾

4、客相继到达间隔时间分布。 M负指数分布Markov，D确定型分布Deterministic， EkK阶爱尔朗分布Erlang， GI 一般相互独立随机分布(General Independent)， G 一般随机分布。Y填写服务时间分布（与上同）Z填写并列的服务台数A排队系统的最大容量B顾客源数量 C排队规则 如 即为顾客到达为泊松过程，服务时间为负指数分布，单台，无限容量，无限源，先到先服务的排队系统模型。第6页/共39页7 1.排队系统的统计推断:即通过对排队系统主要参数的统计推断和对排队系统的结构分析，判断一个给定的排队系统符合于哪种模型，以便根据排队理论进行研究。 2.系统性态问题:即

5、研究各种排队系统的概率规律性，主要研究队长分布、等待时间分布和忙期分布等统计指标,包括了瞬态和稳态两种情形。 3.最优化问题：即包括最优设计(静态优化)，最优运营（动态优化）。 第7页/共39页8 求解一般排队系统问题的目的主要是通过研究排队系统运行的效率指标，估计服务质量，确定系统的合理结构和系统参数的合理值，以便实现对现有系统合理改进和对新建系统的最优设计等。 排队问题的一般步骤： 1 1. . 确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布( (可实测) )。 2 2. . 研究系统状态的概率。系统状态是指系统中顾客数。状态概率用P Pn n(t)(t)表示, ,即在t t时刻系

6、统中有n n个顾客的概率，也称瞬态概率。第8页/共39页9 求解状态概率P Pn n(t)(t)方法是建立含P Pn n(t)(t)的微分差分方程，通过求解微分差分方程得到系统瞬态解，由于瞬态解一般求出确定值比较困难，即便求得一般也很难使用。因此我们常常使用它的极限( (如果存在的话) )：nttnp)(plim稳态的物理意义见右图，系统的稳态一般很快都能达到，但实际中达不到稳态的现象也存在。值得注意的是求稳态概率Pn并不一定求t的极限,而只需求Pn(t)=0 即可。过渡状态稳定状态pnt图3 排队系统状态变化示意图 称为稳态(steady state)解，或称统计平衡状态 (Statisti

7、cal Equilibrium State)的解。第9页/共39页10 3 3. .根据排队系统对应的理论模型求出用以判断系统运行优劣的基本数量指标的概率分布或特征数。 数量指标主要包括: : (1)(1)平均队长（L Ls s）: :系统中的顾客数。 平均队列长（L Lq q）: :系统中排队等待服务的顾客数。 系统中顾客数L Ls s = =系统中排队等待服务的顾客数L Lq q + +正被服务的顾客数c c (2)(2)平均逗留时间(Ws)(Ws): :指一个顾客在系统中的停留时间。 平均等待时间(Wq)(Wq): :指一个顾客在系统中排队等待的时间。 (3)(3)忙期：指从顾客到达空闲

8、服务机构起到服务机构再次为空闲这段时间长度。（忙期和一个忙期中平均完成服务顾客数都是衡量服务机构效率的指标，忙期关系到工作强度） 4. .排队系统指标优化 含优化设计与优化运营。问题1 系统中顾客数=平均队列长（Lq）+1？ 第10页/共39页11 排队系统的组成与特征 排队系统的模型分类 顾客到达间隔时间和服务时间的经验分布与理论分布 稳态概率P Pn n的计算 标准的M/M/1M/M/1模型( (M/M/1:/FCFS)/FCFS) 系统容量有限制的模型M/M/1:N/FCFS/FCFS 顾客源有限模型M/M/1/M/M/ FCFSFCFS 标准的M/M/CM/M/C模型M/M/C:/FC

9、FS/FCFS 第11页/共39页12 M/M/C型系统和C个M/M/1型系统 系 统 容 量 有 限 制 的 多 服 务 台 模 型(M/M/C/N/) 顾客源为有限的多服务台模型(M/M/C/M)(M/M/C/M) 一般服务时间的（M/G/1M/G/1）模型 Pollaczek-Khintchine(P-K) 公式 定长服务时间 M/D/1M/D/1模型 爱尔朗服务时间M/Ek/1模型 排队系统优化 M/M/1 模型中的最优服务率u 标准的M/M/1Model 系统容量为N的情形 M/M/C模型中最优服务台数C第12页/共39页13 一个排队系统的最主要特征参数是顾客的到达间隔时间分布与服

10、务时间分布。要研究到达间隔时间分布与服务时间分布需要首先根据现存系统原始资料统计出它们的经验分布（见P315P315319319），然后与理论分布拟合，若能照应，我们就可以得出上述的分布情况。第13页/共39页14 经验分布是对排队系统的某些时间参数根据经验数据进行统计分析，并依据统计分析结果假设其统计样本的总体分布，选择合适的检验方法进行检验，当通过检验时，我们认为时间参数的经验数据服从该假设分布。 分布的拟合检验一般采用 2检验。由数理统计的知识我们知：若样本量n充分大(n50)，则当假设H0为真时，统计量总是近似地服从自由度为k-r-1的 2分布，其中k为分组数，r为检验分布中被估计的参

11、数个数。第14页/共39页15tnnenttP !)( 式中为常数(0)，称X服从参数为的泊松分布，若在上式中引入时间参数t，即令t代替，则有： 在概率论中，我们曾学过泊松分布，设随机变量为X，则有：!nenxPnn=0,1,2, （1） 与时间有关的随机变量的概率，是一个随机过程，即泊松过程泊松过程。 t0，n=0,1,2, （2）第15页/共39页16)()(,1221ntNtNPttPn（t2t1，n0） 若设N(t)表示在时间区间0,t)内到达的顾客数(t0),Pn(t1,t2)表示在时间区间t1,t2)(t2t1)内有n(0)个顾客到达的概率。即： 在一定的假设条件下 顾客的到达过程

12、就是一个泊松过程。 当Pn(t1,t2)符合下述三个条件时，顾客到达过程就是泊松过程(顾客到达形成普阿松流)。第16页/共39页17 无后效性：各区间的到达相互独立,即Markov性。. . . . . . . t0 t1 t2 tn-1 tn|)(|)(11112211)()(,.,)(,)(nnnnxtxnxtxxtxxtxnntxPntxP 也就是说过程在t+t所处的状态与t以前所处的状态无关。平稳性：即对于足够小的t，有：)()(tttttP ，1普阿松流具有如下特性： 在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。第17页/共39页18 普通性：对充分小的t,在时间区间（

13、t,t+t）内有2个或2个以上顾客到达的概率是一高阶无穷小.由此知，在(t，t+t)区间内没有顾客到达的概率为：)(1),(0tottttP 令t1=0,t2=t,则P(t1,t2)=Pn(0,t)=Pn(t) 0 是常数，它表示单位时间到达的顾客数，称为概率强度。2)(),(nntotttP即P0+P1+P2=1在上述假设下，t时刻系统中有n个顾客的概率pn(t)： 第18页/共39页19)()()(1tPtPdttdPnnn0)0(nP(1)()(00tPdttdP1)0(0P(2)当n=0时，则te)t(P 0(3)（没有顾客到达的概率）（n个顾客到达的概率）tnnenttP !)()(

14、（4）瞬态方程（1）、（2）两式求导并令导数为0，得稳态概率：第19页/共39页20级数级数.!nx.!xxenx 212tkke!k)t( 0!)()()(11ntnetnPtNEnntnn )!1()(11 nttennt令k=n-1，则：!)()(0kttetNEkkt tetetNEtt )(ttar )(N(V同理方差为：顾客到达过程是一个泊松过程泊松过程( (泊松流泊松流) )。期望第20页/共39页21 表示单位时间内顾客平均到达数。 1/表示顾客到达的平均间隔时间。对顾客的服务时间 ：系统处于忙期时两顾客相继离开系统的时间间隔，一般地也服从负指数分布， 1TE21 TVar接受

15、服务，然后离开服务时间的分布： 可以证明当输入过程是泊松流时，两顾客相继到达的时间间隔T T独立且服从负指数分布。（等价）tetF 1)(tetf )(，则第21页/共39页22其中：表示单位时间内能被服务的顾客数，即平均 服务率。 1/表示一个顾客的平均服务时间。 设v1, v2，, vk是k个独立的随机变量，服从相同参数 k 的负指数分布，那么：tetF 1)(tetf )(，则 令 ，则称为服务强度。kT 21第22页/共39页23 串联的k个服务台，每台服务时间相互独立，服从相同的负指数分布（参数k ），那么一顾客走完k个服务台总共所需要服务时间就服从上述的k阶Erlang分布。011

16、 te)!k()kt(k)t (ftkkk则称T服从k阶爱尔朗分布。其特征值为： 1TE21 kTVar,其概率密度是1/ k表示一个顾客的一个服务台的平均服务时间。第23页/共39页24 例:有易碎物品500件,由甲地运往乙地,根据以往统计资料,在运输过程中易碎物品按普阿松流发生破碎,其破损率为0.002,现求:1.破碎3件物品的概率;2.破碎少于3件的概率和多于3件的概率;3.至少有一件破损的概率. 解: =0.002500=1 1破碎3件物品的概率为: P(k=3)=( 3/3！)e- =(13/3！)e-1=0.0613 即物品破碎3件的概率为6.13 2.破碎物品少于3件的概率:第2

17、4页/共39页25 破碎物品少于3件的概率为91.97破碎物品多于3件的概率为: 02. 098. 01!1330 kkekp3.至少有一件破碎的概率为 Pk 1=1-(1k/k!)e- =1-(10/0!)e-1=0.632 9197. 021112120 eeknp第25页/共39页26 对排队模型，在给定输入和服务条件下，主要研究系统的下述运行指标： (1)系统的平均队长Ls(期望值)和平均队列长Lq(期望值)； (2)系统中顾客平均逗留时间Ws与队列中平均等待时间Wq； 本节只研究M/M/1模型，下面分三种情况讨论：第26页/共39页27 系统中有n个顾客M/M/1:/FCFS模型 在

18、任意时刻t，状态为n的概率Pn(t)（瞬态概率），它决定了系统的运行特征。 已知顾客到达服从参数为的泊松过程，服务时间服从参数为的负指数分布。现仍然通过研究区间t，t+t）的变化来求解。在时刻t+t，系统中有n个顾客不外乎有下列四种情况（ t，t+t）内到达或离开2个以上没列入）。？ 第27页/共39页28区区间间( (t t, , t+t t) ) 情情况况 时时刻刻t t的的顾顾客客 到到达达 离离去去 时时刻刻t+t t的的顾顾客客 ( (t t, , t+t t) )的的概概率率 0 0, , t+t t 的的概概率率 A n n 1-t+O(t) 1-t+O(t) Pn(1-t+O(

19、t) （1-t+O(t)） B n+1 n 1-t+O(t) t+O(t) Pn+1(1-t+O(t) （t+O(t)） C n-1 n t+O(t) 1-t+O(t) Pn-1(t+O(t) （1-t+O(t)） D n n t+O(t) t+O(t) Pn(t+O(t) （t+O(t)） 由于这四种情况是互不相容的，所以Pn(t+t)应是这四项之和，则有：tttPtttPtttPttPnnnn)1)()()1)(1)()(1)()1 ()(1tOtttPn所有的高阶无穷小合并第28页/共39页29) t(Ot) t (Pt) t (P) tt)(t (Pnnn 111t) t(O) t (

20、P)() t (P) t (Pt) t (P) tt (Pnnnnn 11令t0，得关于Pn(t)的微分差分方程：)()()()()(11tPtPtPdttdPnnnn(1) 当n=0时，只有表中的（A）、（B）两种情况，因为在较小的t内不可能发生（D）（到达后即离去），若发生可将t取小即可。)t()t)(t (P)t)(t (P)tt (P 11100) t (P) t (Pdt) t (dP100 (2)生灭过程瞬态解第29页/共39页30由此可得该排队系统的状态转移图：由（4）得：001PPP 其中服务强度 将其代入（3）式并令n=1,2,(也可从状态转移图中看出状态平衡方程)得：关于P

21、n的差分方程n-1nn+1201 稳态时， 它对时间的导数为0，所以由(1)、(2)两式得：Pn(t)与时间无关,可以写成Pn,011 nnnP)(PP010 PP(3)(4)第30页/共39页310120 P)(PPn=10020 P)(PP0202021PP)(P)(P n=20231 P)(PP00230 P)(PP0303022231PP)(P)(P 第31页/共39页32以此类推，当n=n时，00)(PPPnnn (5)1 10 nnP以及概率性质知：111000 PPnn(数列的极限为 ) 11 10Pnn)(P 1(6)否则排队无限远系统稳态概率系统的运行指标第32页/共39页33 (1) 系统中的队长Ls（平均队长） nnnnsnPnL 001.)(n.)()()(n 11312132.nn.nn 1433223322 132.n(01) 1 Ls即:(7)期望第33页/共39页34(2)