随机服务系统理论：排队论

《随机服务系统理论：排队论》由会员分享，可在线阅读，更多相关《随机服务系统理论：排队论（63页珍藏版）》请在金锄头文库上搜索。

1、排队论(Queuing Theory)排队论（queuing),也称随机服务系统理论， 是运筹学的一个主要分支。1909年，丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论”标 志此理论的诞生。排队论的发展最早是与电话，通 信中的问题相联系的，并到现在是排队论的传统的 应用领域。近年来在计算机通讯网络系统、交通运 输、医疗卫生系统、库存管理、作战指挥等各领域 中均得到应用。1 1排队论主要知识点n排队论的基本概念l排队系统的组成与特征l排队系统的模型分类l顾客到达间隔时间和服务时间的经验分布与理论分布l稳态概率Pn的计算nM/M/1模型l标准的M/M/1

2、模型(M/M/1:/FCFS)l系统容量有限制的模型M/M/1:N/FCFSl顾客源有限模型M/M/1/M/ FCFS2 2nM/M/C模型l标准的M/M/C模型M/M/C:/FCFSlM/M/C型系统和C个M/M/1型系统l系统容量有限制的多服务台模型(M/M/C/N/)l顾客源为有限的多服务台模型(M/M/C/M)n一般服务时间的（M/G/1）模型lPollaczek-Khintchine(P-K) 公式l定长服务时间 M/D/1模型l爱尔朗服务时间M/Ek/1模型n排队系统优化lM/M/1 模型中的最优服务率un标准的M/M/1Modeln系统容量为N的情形lM/M/C模型中最优服务台数

3、C3 3排队系统一般有三个基本组成部分：1.输入过程；2. 排队规则；3.服务机构。1 排队论的基本概念1.1 排队系统的组成与特征4 4输入即为顾客的到达，可有下列3种情况： 1）顾客来源。顾客总体(称为顾客源)的组成可能是有 限的，也可能是无限的。如，上游河水流入水库可以 认为总体是无限的，工厂内停机待修的机器显然是有 限的总体。 2）顾客到达方式。顾客到来的方式可能是一个一个 的，也可能是成批的。如，到餐厅就餐就有单个到来 的顾客和受邀请来参加宴会的成批顾客。1. 输入过程5 53 3）顾客流的概率分布。顾客随机一个）顾客流的概率分布。顾客随机一个( (批批) )个个( (批批) )来到

4、来到 排队系统，顾客流的概率分布用来描述相继到达的顾排队系统，顾客流的概率分布用来描述相继到达的顾 客之间的间隔时间分布是确定的还是随机的，分布参客之间的间隔时间分布是确定的还是随机的，分布参 数是什么，到达的间隔时间是否独立，分布是随时间数是什么，到达的间隔时间是否独立，分布是随时间 变化的还是平稳的。变化的还是平稳的。当输入过程是泊松流时，两顾客相继到达的时间间隔T独立且服从负指数分布。（等价）6 61）损失制。顾客到达时，如果所有的服务台都被 占用，且服务机构又不允许顾客等待，顾客只能离 去，这种服务规则就是损失制。 2）等待制。当顾客到达时，如果所有服务台都被顾 客占用而无空闲，这时该

5、顾客自动加入队列排队等 待服务，服务完才离开。 （1）先到先服务 FCFS （2）后到先服务 LCFS （3）随机服务RAND （4）有优先权服务 PR。2. 排队规则7 71）服务机构可以是单服务员和多服务员服务，这种 服务形式与队列规则联合后形成了多种不同队列，不 同形式的排队服务机构，如：3. 服务机构8 8上述特征中最主要的、影响最大的是：n顾客相继到达的间隔时间分布n服务时间的分布n服务台数2)服务方式分为单个顾客服务和成批顾客服务。3)服务时间分为确定型和随机型。4)服务时间的分布在这里我们假定是平稳的。1.2 排队系统的模型分类9 9式中： X填写顾客相继到达间隔时间分布。M负指

6、数分布Markov， D确定型分布Deterministic，EkK阶爱尔朗分布Erlang， G 一般随机分布。 Y填写服务时间分布（与上同） Z填写并列的服务台数 A排队系统的最大容量 B顾客源数量 C排队规则如 M/M/1:/FCFS即为顾客到达为泊松过程，服务时间 为负指数分布，单台，无限容量，无限源，先到先服务的排队系统 模型。D.G.Kendall，1953提出了分类法，称为Kendall记号(适用于 并列服务台)即： X/Y/Z:A/B/C1010系统指标 (1)队长:指在系统中的顾客数，它的期望值记Ls； (2) 排队长:指在系统中排队等待服务的顾客数，它的 期望值记作Lq。

7、系统 中顾 客 数在队列中等 待服务的顾 客数正被服 务的顾 客数+=一般情形，一般情形，Ls(Ls(或或LqLq) )越大，说明服务效率越低。越大，说明服务效率越低。1111(3) 逗留时间，指一个顾客在系统中的停留时间，它的 期望值记作Ws； (4) 等待时间，指一个顾客在系统中排队等待的时间， 它的期望值记作Wq；等待时间服务时间+逗留时间=12121.排队系统的统计推断:即通过对排队系统主要参数 的统计推断和对排队系统的结构分析，判断一个给 定的排队系统符合于哪种模型，以便根据排队理论 进行研究。 2.系统性态问题:即研究各种排队系统的概率规律 性，主要研究队长分布、等待时间分布和忙期

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

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

10、tatistical Equilibrium State)的解的解。15152 到达间隔时间分布和服务时间的分布一个排队系统的最主要特征参数是顾客的到达间隔 时间分布与服务时间分布。要研究到达间隔时间分布 与服务时间分布需要首先根据现存系统原始资料统计 出它们的经验分布，然后与理论分布拟合，若能照应 ，我们就可以得出上述的分布情况。16162.1 经验分布经验分布是对排队系统的某些时间参数根 据经验数据进行统计分析，并依据统计分析结 果假设其统计样本的总体分布，选择合适的检 验方法进行检验，当通过检验时，我们认为时 间参数的经验数据服从该假设分布。分布的拟合检验一般采用2检验。由数理 统计的知

11、识我们知：若样本量n充分大(n50) ，则当假设H0为真时，统计量总是近似地服从 自由度为k-r-1的 2分布，其中k为分组数，r 为检验分布中被估计的参数个数。17172.2 理论分布式中为常数(0)，称X服从参数为的泊松分 布，若在上式中引入时间参数t，即令t代替，则 有： 1.泊松分布在概率论中，我们曾学过泊松分布，设随机变量 为X，则有：n=0,1,2, （1）与时间有关的随机变量的概率，是一个随机过 程，即泊松过程。 t0，n=0,1,2, （2）1818（t2t1，n0）若设N(t)表示在时间区间0,t)内到达的顾客数(t0),Pn(t1,t2)表示在时间区间t1,t2)(t2t1

12、)内有n(0)个顾客到达的概率。即：在一定的假设条件下 顾客的到达过程就是一个泊松过程。当Pn(t1,t2)符合下述三个条件时，顾客到达过程 就是泊松过程(顾客到达形成泊松流)。1919 无后效性：各区间的到达相互独立,即Markov性。也就是说过程在t+t所处的状态与t以前所处的状态 无关。平稳性：即对于足够小的t，有：泊松流具有如下特性：在t,t+t内有一个顾客到达的概率与t无关,而与t成正比。0 是常数，它表示单位时间到达的顾客数，称为概率强度。2020 普通性：对充分小的t,在时间区间（t,t+t）内有2个或2个以上顾客到达的概率是一高阶无穷小.由此知，在(t，t+t)区间内没有顾客到

13、达的概率为：令t1=0,t2=t,则P(t1,t2)=Pn(0,t)=Pn(t)即P0+P1+P2=1在上述假设下，t时刻系统中有n个顾客的概率pn(t)： 2121根据排队系统的状态转移图：整理后可得：n-1 n n+1 2 0 12n+1 012 n-2 n-1 n1 3 n-1nn+1 n+2稳态时，它对时 间的导数为0，所以由(12.5)、(12.6)两式得：Pn(t)与时间无关, 可以写成Pn,(12.7)(12.8)2222表示单位时间内顾客平均到达数。1/表示顾客到达的平均间隔时间。2.负指数分布可以证明当输入过程是泊松流时，两顾客相继到达 的时间间隔T独立且服从负指数分布。（等

14、价）（n个顾客到达的概率） （4）2323对排队模型，在给定输入和服务条件下，主要 研究系统的下述运行指标：(1)系统的平均队长Ls(期望值)和平均队列长 Lq(期望值)； (2)系统中顾客平均逗留时间Ws与队列中平均等 待时间Wq；本节只研究M/M/1模型，下面分三种情况讨论：3. M/M/13. M/M/1模型模型24243.1 3.1 标准的标准的M/M/1M/M/1模型模型 系统中有 n个顾客M/M/1:/FCFS模型 1.1.稳态概率稳态概率P Pn n的计算的计算 在任意时刻t，状态为n的概率Pn(t)（瞬态概率），它决定了系统的运行特征。 已知顾客到达服从参数为的泊松过程，服务时

15、间服从参数为的负指数分布。现仍然通过研究区间 t，t+t）的变化来求解。在时刻t+t，系统中有n个顾客不外乎有下列四种情况（ t，t+t）内到达或离开2个以上没列入）。2525由此可得该排队系统的状态转移图：由（4）得：其中服务强度将其代入（3）式并令n=1,2,(也可从状态转移 图中看出状态平衡方程)得：关于Pn的差 分方程n-1 n n+1 2 0 1 稳态时，它对时 间的导数为0，所以由(1)、(2)两式得：Pn(t)与时间无关, 可以写成Pn,(3)(4)2626n=1n=22727以此类推，当n=n时，(5)以及概率性质知 ：(数列的极限为 )(6)否则排队无限远系统 稳态 概率系统的运行指标28282. 2. 系统的运行指标计算系统的运行指标计算(1) 系统中的队长Ls（平均队长）(0=c时，为c，故可得差分方程：5555利用递推法解该差分方程可求得状态概率为：(1n=c)这里： ， 1(nc),(nc)5656系统的运行指标为：5757例4. 某售票所有三个窗口，一个队列形成M/M/C系 统。顾客到达服从泊松流=0.9人/M，服务时间服从 负指数分布，=0