六-排队论.ppt

第六章 随机服务系统理论确定型只是随机现象的特例排 队 论Queuing TheoryQueuing Theory1.6.1 随机服务系统基础系统的输入与输出是随机变量A.k.Erlang 于19091920年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础又称为排队论(Queuing Theory)或拥塞理论(Congestion Theory)应用广泛交通行业应用：交叉口/高速收费站/机场航班2.顾客来源队 列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.输入过程(顾客按照怎样的规律到达);排队规则(顾客按照一定规则排队等待服务);服务机构(服务机构的设置,服务台的数量,服务的方式,服务时间分布等)6.1.1 基本要素3.输入过程顾客源有限无限经常性的顾客来源顾客到达间隔时间:到下一个顾客到达的时间服从某一概率分布（确定型/随机型）顾客的行为假定在未服务之前不会离开 当看到队列很长的时候离开从一个队列移到另一个队列4.排队服务规则队列容量有限/无限排队规则损失制等待制：先到先服务(FCFS)，后到先服务(LCFS)，随机服务(RS)，优先权服务(PS)混合制逐个到达，成批服务；成批到达，逐个服务5.单通道和多通道并联服务串联服务串并联服务服务机构的组织方式与服务方式123顾客到达顾客离开123顾客到达顾客离开顾客离开顾客离开银行服务-叫号系统123顾客到达顾客到达顾客到达顾客离开顾客离开顾客离开机场安全检查通道6.u常用符号M泊松分布（负指数分布）Ekk阶爱尔朗分布D确定型分布G一般分布M/M/1/K/FCFSM/M/1/K/FCFS顾客到达服从泊松分布，顾客的服务时间服从负指数分布，单通道，系统容量有限（K K）而顾客源无限，先到先服务的排队系统顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则 (扩充的Kendall Kendall 符号)-)-Kendalls notation 6.1.2 符号表示7.队长：系统中的顾客数量的期望值排队长：系统中正在等待的顾客数量期望值逗留时间：顾客在排队系统中的总时间（等待时间与被服务时间之和）的期望值排队时间：顾客的排队等待时间的期望值忙期：服务机构连续繁忙的时间长度服务强度：顾客到达率的期望值与服务率的期望值之比6.1.3 排队系统营运指标8.服务系统存在来自两个矛盾方面的要求顾客希望服务质量好，如排队等待时间短，损失率低系统运营方希望设备利用率高给用户一个经济上能够承受的满意的质量哪些系统特性会影响系统的性能？服务机构的组织方式与服务方式顾客的输入过程和服务时间分布系统采用的服务规则 与服务系统性能相关的特性9.6.2 顾客到达分布和服务时间分布 6.2.1 概述顾客的服务时间由于多种原因具有不确定性，最好的描述方法就是概率分布；同样顾客到达的间隔时间也服从一定的概率分布10.若统计区间分得越细，样本越多，则经验分布的轮廓越接近曲线经验分布一般采用直方图来表示，如下图Frequency Distribution服务时间和到达间隔时间服从什么分布？可以先通过统计得到经验分布，然后再做理论假设和检验11.6.3.2 输入过程（顾客到达分布）可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述间隔时间服从定长分布（Deterministic Distribution）间隔时间服从爱尔朗分布（Erlang distribution）二项分布（binomial distribution）单位时间 t（或时间区间t）内到达的顾客数服从泊松分布(法国数学家Poisson,1836)最简单流（泊松流）（Poisson Distribution）负指数分布（Negative Exponential Distribution）12.6.3.2.1 最简单流（泊松流）-纯生过程(1)泊松流形成条件流的平稳性 对于任意的t0t0及t0t0，在时间区间(t,t+(t,t+t)t)内有n n个顾客到达的概率只与t t有关，与时间区间的起点t t无关。当t t充分小时，在(t,t+(t,t+t)t)内有一个顾客到达的概率与t t成正比，即其中，O(O(t)t)是当t 0t 0时，关于t t高阶无穷小；为单位时间内的顾客到达平均数。13.在时间轴上，互不相交的时间区段 和 内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达。流的无后效性当 t 充分小时，在 t 时间内到达一个顾客的概率为 t+o(t)，到达两个或两个以上顾客的概率为 o(t)；即两个顾客不可能同时到达流的普遍性14.设把长为t t的时间区间分成m m等分，每段长度为 。若在dtdt内，有一个顾客到达，则称被“占着”，如果在dtdt内，没有顾客到达，则称为“空着”。u被“占着”的概率近似为u被“空着”的概率近似在长为 t t 的时间区间内，到达n n个顾客的概率根据流的无后效性，在m m个dtdt中，有顾客到达与没有顾客到达可以看成是m m次独立的试验 (2)泊松流详解15.在长为 t 的时间区间内，到达n个顾客的概率在m m个dtdt中，有n n个dtdt被顾客“占着”的概率 利用二项定律 16.dt0，m 17.符合最简单流（泊松流）的随机事件发生规律单位时间t 内有n个顾客到达的概率顾客的平均到达率(3)泊松分布18.（4）泊松输入过程及其特点1)平稳性：顾客到达数只与时间区间长度有关2)无后效性：不相交的时间区间内所到达的顾客数是独立的3)普遍性：在 t 时间内到达一个顾客的概率为 t+o(t)，到达两个或两个以上顾客的概率为 o(t)；即两个顾客不可能同时到达泊松过程具有可迭加性即独立的泊松分布变量的和仍为泊松分布19.泊松过程的到达间隔时间为负指数分布令 h 代表间隔时间，则概率 Ph t代表时间区间t 内没有顾客来的概率；由泊松分布 可知：P0(h t)=Ph t=et故间隔时间 h 的分布为 P h t=1 et（1）推导n=06.3.2.2 负指数分布20.（2）负指数分布的特点负指数分布之所以常用，是因为它有很好的特性，使数学分析变得方便无记忆性。指的是不管一次服务已经过去了多长时间，该次服务所剩的服务时间仍服从原负指数分布21.如果顾客的到达过程服从最简单流，则顾客单位时间内的到达数服从泊松分布。如果顾客的到达过程服从最简单流，则顾客到达的时间间隔服从负指数分布。从本质上看，泊松分布与负指数分布是同一个过程的不同表现形式。可适用于服务时间分布6.3.3 小结22.负指数分布泊松分布在单位时间t内，到达n个顾客的概率顾客到达时间间隔大于单位时间t t的概率顾客到达时间间隔小于单位时间t t的概率顾客的平均到达率23.例-1-1 一售货员出售两种商品A和B，每日工作 8 小时。购买每种商品的顾客到达过程为泊松分布，到达率分别为 A=8人/日，B=16人/日，试求：(1)1小时内来到顾客总数为 3 人的概率；(2)三个顾客全是购买B类商品的概率。解：(1)总到达率为 A+B=24人/日，1 小时=1/8 日，故(2)3 个顾客全是购买 B 类商品的概率为24.例-2-2 某铁路与公路相交的平面交叉口，当火车通过交叉口时，横木护栏挡住汽车通行。每次火车通过时，平均封锁公路3min，公路上平均每分钟有4辆汽车到达交叉口。求火车通过交叉口时，汽车排队长度超过100m的概率（即排队汽车超过12辆的概率）。25.HomeworkHomeworkP186 226.研究系统内部状态变化的过程系统状态i i状态i+1i+1状态i-1i-1在t t时刻内发生两个或两个以上事件的概率为O(O(t)t)一个事件一个事件t0t0，O(O(t)0t)06.4 生灭过程（Birth and Death Processes）6.4.1 定义 系统具有0,1,2,0,1,2,个状态。在任何时刻，若系统处于状态i i，并且系统状态随时间变化的过程满足以下条件，称为一个生灭过程：N(t)N(t)表示时刻t t系统中的顾客数。N(t)N(t)，t t0 0为一随机过程。27.(1)(1)在（t,t+t,t+t t）内系统由状态i i转移到状态i+1i+1的概率为 i it+O(t+O(t)t)平稳性条件(2)(2)在（t,t+t,t+t t）内系统由状态i i转移到状态i-1i-1的概率为 i it+O(t+O(t)t)平稳性条件t t内有一个顾客离开的概率t t内有一个顾客到达的概率(3)(3)在（t,t+t,t+t t）内系统发生两次以上转移的概率为 O(O(t)t)，即有2 2个以上顾客到达或离开的概率为普遍性条件排队系统的输入过程和服务过程符合泊松分布，则排队过程符合生灭过程28.状态（Status）顾客到达率（Birth rate）系统服务率（Death rate）可以证明：tt时，P Pi i(t)(t)趋向于常数：系统达到稳定6.4.2 状态转移图29.系统达到稳定后：每个状态转入率的期望值与转出率的期望值相等。对于状态i i：转出率的期望值为转入率的期望值为S0S1S2Si-1SiSi+1Sk-1Sk123i-1ii+1i+2k-1k012i-2i-1ii+1k-2k-1P P0 0P P1 1P P2 2P Pi i6.4.3 状态转移方程30.则对于S S0 0转入转出转入转出对于S Sk kS0S1S2Si-1SiSi+1Sk-1Sk123i-1ii+1i+2k-1k012i-2i-1ii+1k-2k-1P P0 0P P1 1P P2 2P Pi i31.状态转移方程求解该方程，可以获得各状态对应的概率32.对于S S0 0对于S S1 1依次类推且有33.6.4.4满足生灭过程的条件系统的输入过程和服务过程具有平稳、无记忆性和普通性服务台是独立的、相同的、并联的波松输入过程和负指数服务时长就具有这些性质可以用马氏链来描述系统的状态转移这种系统称为生灭服务系统，一般用 M/M/n 表示，又称为标准服务系统；标准服务系统的形式很多，但都是基于生灭方程，关键是找出 j,j 的不同表达式，将它们代入生灭方程标准服务系统的表示法：(X/Y/Z:A/B/C)，X 表示输入过程，Y 表示服务过程，Z 表示并联服务台的个数，A表示系统容量，B表示顾客源，C 表示服务规则(M/M/n:m/FCFS)表示波松输入，负指数服务时长，n 个并联服务台，系统容量为 m,m n，顾客源无穷，先到先服务D 定长分布；Ek k阶爱尔兰分布；G 一般独立分布34.6.4.5 生灭过程推导（补充参考）采用马氏链令 N(t)代表系统在时刻 t 的状态，下一瞬间 t+t 系统的状态只能转移到相邻状态，或维持不变，如图所示三种转移是不相容的，三者必居其一只有具有无记忆性和普通性的过程(分布)才适用马氏链令 Pj(t)=PN(t)=j代表系统在时刻 t 处于状态 j 的概率35.生灭过程的马氏链根据马氏链，应用全概率公式，有状态转移概率方程另有两个边界方程36.生灭方程的推导过程将上述三个差分方程化为微分方程上述三个方程是动态方程，当系统处于稳态时，系统处于统计平衡状态，即状态概率不随时间变化，从而状态概率导数为 0；令上三个方程左侧为 0，得稳态方程组37.生灭过程稳态解方程(1),(2),(3)与稳态状态转移图一一对应；递归解如下：38.例：某排队系统：M/M/1/3/FCFSM/M/1/3/FCFS，=2=2，=3=3。求解各状态对应的概率。首先，做出相应的状态转移图S0S1S2S3222333对于S S0 0对于S S1 1对于S S2 239.6.4.6 纯生过程令生灭过程中所有消亡率 j=0，即只有顾客到达，没有顾客离去令所有 j=，且系统服务台无限，即 n容易得到下列微分方程组该问题没有稳态解，正是泊松过程40.生灭过程求解排队系统各状态概率过程建立状态转移图建立状态转移方程求解状态转移方程各状态转入率期望值与转出率期望值相等各状态概率统计平衡下的“流入=流出”原理生灭平衡41.Homework：利用生灭过程求解以下排队系统各状态的概率。S0S1S2S32 22 23 32 24 43 342.第三节 M/M/1排队系统顾客到达服从泊松分布顾客到达率为服务过程服从泊松分布（负指数分布）系统服务率为单通道，先到先服务（FCFS）最简单的M/M/1M/M/1排队系统：M/M/1/M/M/1/M/M/1/m/M/M/1/m/43.M/M/1/M/M/1/排队系统系统容量无限、顾客源无限最基本的排队系统排队过程为生灭过程过程44.S0S1S2Si-1SiSi+1P P0 0P P1 1P P2 2P Pi i列状态转移方程组求各状态概率45.M/M/1/排队系统各状态概率归结为无穷等比数列求和11 1，数列发散系统稳定系统不稳定称为服务强度，若服务强度大于1 1，说明单位时间内到达的顾客数比完成服务的顾客数多，系统中排队长度越来越大，产生阻塞。46.利用排队系统各状态概率计算运行指标1、队长系统中的顾客数量队长47.2、排队长系统中等待的顾客数量通道数48.3、逗留时间顾客在排队系统中的总时间李太勒公式-1（Little Formula）前后2名顾客到达系统的平均时间间隔适用于任何排队系统。49.4、排队时间顾客在排队系统中的等待时间李太勒公式-2前后2名顾客到达系统的平均时间间隔50.排队系统运营指标及相互关系：51.52.例1 某医院急诊室同时只能诊治一个病人，诊治时间服从负指数分布，每个病人平均需要1515分钟。病人按泊松分布到达，平均每小时到达3 3人。试对此排队队系统进行分析。（1）确定参数值：服务强度：53.急诊室繁忙（需要等待）的概率:（2）稳态概率：这就是急诊室空闲的概率，也是病人不必等待立即就能就诊的概率。54.病人平均等候时间：急诊室内外的病人平均数：急诊室外排队等待的病人平均数：病人在急诊室内外平均逗留时间：55.15123min即平均服务时间至少应减少3min为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？代入=3，解得5，平均服务时间为：56.若医院希望候诊的病人90%以上都能有座位,则候诊室至少应安置多少座位?设应该安置个座位,加上急诊室的一个座位,共有+1个。要使90%以上的候诊病人有座位，相当于使“来诊的病人数不多于+1个”的概率不少于90%，即57.两边取对数（x2）lg lg0.1因 1，故所以 6即候诊室至少应安置6个座位。58.例：某修车店只有一个修理工，来修理的顾客到达过程服从PoissonPoisson流，平均4 4人/小时；修理时间服从负指数分布，平均需要6 6分钟，试求：1 1）修理店空闲的概率；2 2）店内恰有3 3个顾客的概率；3 3）店内至少有1 1个顾客的概率；4 4）在店内的平均顾客数；5 5）每位顾客在店内的平均逗留时间；6 6）等待服务的平均顾客数；7 7）每位顾客平均等待服务时间；8 8）顾客在店内等待时间超过十分钟的概率。59.M/M/1/m/排队系统系统容量有限、顾客源无限60.列状态转移方程组求各状态概率S0S1S2Si-1SiSi+1P P0 0P P1 1P P2 2P Pi i61.并不要求10Q0）0.750.750 05555L Lq q2.252.25人0 01212人L L3 3人0 08787人W W60min60min17174min4minW Wq q45min45min2 24min4min87.例 某储蓄所内，已知忙时顾客到达率 =40人/小时，窗口营业员服务率为 =16人/小时，要求：(1)工时利用率不低于 60%；(2)顾客平均等待时间不超过 5 分钟；问：设几个窗口适当。解：系统是无限源 M/M/s 等待制。=/=40/16=2.5Erl(1)*=/s 0.6，解出 s 4.17，故 s可取值 3，4 (2)n=3 时，p0=(1+2/2!+(3/3!)(3/(3-2.5)1=0.04588.作业（）某售票处有三个窗口，顾客的到达为PoissonPoisson流，平均到达率=0.9=0.9人/分钟；服务（售票）时间服从负指数分布，平均服务率=0.4=0.4人/分钟。现设顾客到达后排成一个队列，依次向空闲的窗口购票，这一排队系统可看成是一个M/M/S/M/M/S/系统。试求：(1)(1)整个售票处空闲的概率；(2)(2)平均队长；(3)(3)平均逗留时间；(4)(4)平均等待时间；(5)(5)顾客到达后的等待概率。89.排队系统设计最优化的目标在于使系统设施达到最大使用效益，或者说，在一定的质量指标下要求服务机构最为经济一般要求系统最优第五节 排队服务系统的最优化问题 90.对于顾客来说，总是要求提高服务水平（如增设服务台数、加快服务时间）以减少排队费用，若要完全满足顾客的要求，则会导致服务机构过大，使用效率降低，造成浪费。从服务机构来说，总是希望服务机构能达到最高的使用效率，每个服务台都不出现空闲状态，这必然导致顾客等候费用的增加，影响顾客的利益。排队系统最优化的目的是综合考虑两者的利益，使二者费用之和为最小，确定达到这个目标的最优服务水平。另一常用的目标函数是使系统的纯收入（服务收入与服务成本之差）为最大 91.服务水平92.排队服务系统的最优化问题通常归结为求极值问题求导（求偏导）迭代法 试算法 常用的求极值方法有：93.其它类型排队系统X/Y/Z/?/?/?有限源？非生灭过程？常见的多种组合形式（详见教材P175）94.Software排队系统运营指标可用既有软件求解；LingoQueuing Toolpad(QTP)-Plus for Excel (http:/www.business.ualberta.ca/aingolfsson/QTP/)Queuing Theory Software(QTS)-Plus/Standard for Excel (http:/