第六章 排队论.ppt

第六章 随机服务系统理论确定型只是随机现象的特例排 队 论Queuing Theory26.1 随机服务系统基础• 系统的输入与输出是随机变量• A.k.Erlang 于1909~1920年发表了一系列根据话务量计算机键配置的方法，为随机服务理论奠定了基础• 又称为排队论(Queuing Theory)或拥塞理论(Congestion Theory)• 应用广泛• 交通行业应用：交叉口/高速收费站/机场航班…3顾客来源队 列服务机构排队系统顾客服务完离开排队系统的三个基本组成部分.•输入过程 (顾客按照怎样的规律到达);•排队规则 (顾客按照一定规则排队等待服务);•服务机构 (服务机构的设置,服务台的数量,服务的 方式,服务时间分布等)6.1.1 基本要素4输入过程• 顾客源 – 有限 – 无限 • 经常性的顾客来源 – 顾客到达间隔时间: 到下一个顾客到达的时间 – 服从某一概率分布（确定型/随机型）• 顾客的行为假定 – 在未服务之前不会离开 – 当看到队列很长的时候离开 – 从一个队列移到另一个队列5排队服务规则– 队列容量• 有限/无限– 排队规则 • 损失制 • 等待制：先到先服务(FCFS)，后到先服务 (LCFS)，随机服务(RS)，优先权服务(PS)• 混合制 • 逐个到达，成批服务；成批到达，逐个服务6– 单通道和多通道 – 并联服务 – 串联服务 – 串并联服务服务机构的组织方式与服务方式123顾客到达顾客离开123顾客到达顾客离开顾客离开顾客离开银行服务-叫号系统123  顾客到达顾客到达顾客到达顾客离开顾客离开顾客离开机场安全检查通道7u常用符号 • M—泊松分布（负指数分布）• Ek—k阶爱尔朗分布• D—确定型分布• G—一般分布• M/M/1/K/∞/FCFS—顾客到达服从泊松分布，顾客的服务时 间服从负指数分布，单通道，系统容量有限（K）而顾客源 无限，先到先服务的排队系统顾客到达时间间隔分布/服务时间分布/服务台数目/排队系统允许的最大顾客容量/顾客总体数量/排队规则 (扩充的Kendall 符号)-- Kendall’s notation 6.1.2 符号表示8Ø队长：系统中的顾客数量的期望值Ø排队长：系统中正在等待的顾客数量期望值Ø逗留时间：顾客在排队系统中的总时间（等待时间与被服务时间之和）的期望值Ø排队时间：顾客的排队等待时间的期望值Ø忙期：服务机构连续繁忙的时间长度Ø服务强度：顾客到达率的期望值与服务率的期望值之比6.1.3 排队系统营运指标9• 服务系统存在来自两个矛盾方面的要求– 顾客希望服务质量好，如排队等待时间短，损失率低– 系统运营方希望设备利用率高• 给用户一个经济上能够承受的满意的质量• 哪些系统特性会影响系统的性能？– 服务机构的组织方式与服务方式– 顾客的输入过程和服务时间分布– 系统采用的服务规则与服务系统性能相关的特性6.2 顾客到达分布和服务时间分布6.2.1 概述•顾客的服务时间由于多种原因具有不确定性，最好的描述 方法就是概率分布；同样顾客到达的间隔时间也服从一定 的概率分布11•若统计区间分得越细，样本越多，则经验分布的轮廓越接 近曲线•经验分布一般采用直方图来表示，如下图–Frequency Distribution•服务时间和到达间隔时间服从什么分布？可以先通过统计 得到经验分布，然后再做理论假设和检验126.3.2 输入过程（顾客到达分布）•可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述– 间隔时间服从定长分布（Deterministic Distribution）– 间隔时间服从爱尔朗分布（Erlang distribution ）– 二项分布（binomial distribution ）– 单位时间 t （或时间区间△t）内到达的顾客数服从泊松分布(法国数学家Poisson, 1836)—最简单流（泊松流）（Poisson Distribution） – 负指数分布（Negative Exponential Distribution）136.3.2.1 最简单流（泊松流） --纯生过程• (1) 泊松流形成条件– 流的平稳性对于任意的t≥0及Δt≥0，在时间区间(t,t+Δt)内有n 个顾客到达的概率只与Δt有关，与时间区间的起点t无 关。

当Δt充分小时，在(t,t+Δt)内有一个顾客到达的概率 与Δt成正比，即其中，O(Δt)是当Δt →0时，关于Δt高阶无穷小；λ为单位时间内的顾客到达平均数14• 在时间轴上，互不相交的时间区段和 内，顾客的到达数是相互独立的，即前一顾客的到达不影响后一顾客的到达– 流的无后效性• 当t 充分小时，在 t 时间内到达一个顾客的概率为  t +o(t )，到达两个或两个以上顾客的概率为 o(t )；即两个顾客不可能同时到达– 流的普遍性• 设把长为Δt的时间区间分成m等分，每段长度为若在dt内，有一个顾客到达，则称被“ 占着”，如果在dt内，没有顾客到达，则称为“空着”u被“占着”的概率近似为u被“空着”的概率近似在长为Δt 的时间区间内，到达n个顾客的概率根据流的无后效性，在m个dt中，有顾客到达与没有顾客到 达可以看成是m次独立的试验 • (2) 泊松流详解16在长为 Δt 的时间区间内，到达n个顾客的概率在m个dt中，有n个dt被顾客“占着”的概率 利用二项定律 17dt0，m18符合最简单流（泊松流）的随机事件发生规律单位时间△t 内有n个顾客到达的概率λ—顾客的平均到达率• (3) 泊松分布19（4） 泊松输入过程及其特点1) 平稳性：顾客到达数只与时间区间长度有关 2) 无后效性：不相交的时间区间内所到达的顾客数是独立的 3) 普遍性：在 t 时间内到达一个顾客的概率为  t +o(t )， 到达两个或两个以上顾客的概率为 o(t )；即两个顾客不可 能同时到达 •泊松过程具有可迭加性 – 即独立的泊松分布变量的和仍为泊松分布20• 泊松过程的到达间隔时间为负指数分布 – 令 h 代表间隔时间，则概率 P{h t}代表时间区间 △t 内没有顾客来的概率；由泊松分布可知： P0(h △t)= P{h △t}=e△t故间隔时间 h 的分布为 P{ h △t}=1e△t（1）推导n=06.3.2.2 负指数分布21（2）负指数分布的特点•负指数分布之所以常用，是因为它有很好的特性，使数学 分析变得方便 •无记忆性。

指的是不管一次服务已经过去了多长时间，该 次服务所剩的服务时间仍服从原负指数分布22• 如果顾客的到达过程服从最简单流，则顾客单 位时间内的到达数服从泊松分布• 如果顾客的到达过程服从最简单流，则顾客到 达的时间间隔服从负指数分布• 从本质上看，泊松分布与负指数分布是同一个 过程的不同表现形式• 可适用于服务时间分布6.3.3 小结23负指数分布泊松分布在单位时间Δt内，到达 n个顾客的概率顾客到达时间间隔大于 单位时间Δt的概率顾客到达时间间隔小于 单位时间Δt的概率λ—顾客的平均到达率24例-1一售货员出售两种商品A和B，每日工作 8 小时购买 每种商品的顾客到达过程为泊松分布，到达率分别为 A=8人/日， B=16人/日，试求：(1) 1小时内来到顾客 总数为 3 人的概率；(2) 三个顾客全是购买B类商品的 概率 解：(1)总到达率为 A+ B=24人/日，1 小时=1/8 日，故(2) 3 个顾客全是购买 B 类商品的概率为25例-2某铁路与公路相交的平面交叉口，当火车通过交叉口时，横木护栏挡住汽车通行每次火车 通过时，平均封锁公路3min，公路上平均每分 钟有4辆汽车到达交叉口。

求火车通过交叉口 时，汽车排队长度超过100m的概率（即排队汽 车超过12辆的概率）26HomeworkP186 227• 研究系统内部状态变化的过程系统状态i状态i+1状态i-1在Δt时刻内发生两个或两个以上 事件的概率为O(Δt)一个事件一个事件Δt→0， O(Δt) →06.4 生灭过程（Birth and Death Processes）6.4.1 定义系统具有0,1,2,……个状态在任何时刻，若系统处于状态i，并且系统状态随时间变化的过程满足以下条件，称 为一个生灭过程：N(t)表示时刻t系统中的顾客数 ｛ N(t) ，t≥0｝为一随机过程28(1) 在（t,t+Δt）内系统由状态i转移到状态i+1的概率为 λiΔt+O(Δt)——平稳性条件(2) 在（t,t+Δt）内系统由状态i转移到状态i-1的概率为μiΔt+O(Δt)——平稳性条件Δt内有一个顾客离开的概率Δt内有一个顾客到达的概率(3) 在（t,t+Δt）内系统发生两次以上转移的概率为O(Δt)，即有2个以上顾客到达或离开的概率为普遍性条件排队系统的输入过程和服务过程符合泊松分布，则排队过程符合生灭过程29S0S1S2Si-1SiSi+1Sk-1Sk μ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1 ……状态（Status ）顾客到达率（Birth rate）系统服务率（Death rate）可以证明： t→∞时，Pi(t)趋向于常数：系统达到稳定6.4.2 状态转移图30• 系统达到稳定后：每个状态转入率的期望值与转出率的 期望值相等。

对于状态i：转出率的期望值为转入率的期望值为S0S1S2Si-1SiSi+1Sk-1Sk μ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1 ……P0P1P2Pi6.4.3 状态转移方程31则对于S0转入转出转入转出对于SkS0S1S2Si-1SiSi+1Sk-1Sk μ1μ2μ3μi-1μiμi+1μi+2μk-1μkλ0λ1λ2λi-2λi-1λiλi+1λk-2λk-1 ……P0P1P2Pi32状态转移方程求解该方程，可以获得各状态对应的概率33对于S0对于S1依次类推且有346.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 一般独立分布356.4.5 生灭过程推导（补充参考）•采用马氏链 – 令 N(t)代表系统在时刻 t 的状态，下一瞬间 t+t 系统的 状态只能转移到相邻状态，或维持不变，如图所示 – 三种转移是不相容的，三者必居其一 – 只有具有无记忆性和普通性的过程(分布)才适用马氏链– 令 Pj(t)=P{N(t)=j}代表系统在时刻 t 处于状态 j 的概率36生灭过程的马氏链•根据马氏链，应用全概率公式，有状态转移概率方程• 另有两个边界方程37生灭方程的推导过程•将上述三个差分方程化为微分方程•上述三个方程是动态方程，当系统处于稳态时，系统处于 统计平衡状态，即状态概率不随时间变化，从而状态概率 导数为 0；令上三个方程左侧为 0，得稳态方程组38生灭过程稳态解•方程(1), (2), (3) 与稳态状态转移图一一对应；递归解如下：39例：某排队系统： M/M/1/3/∞/FCFS，λ=2，μ=3。