8-1，2

null排队常常是件很令人恼火的事情…… 尤其是在我们这样的人口大国排队常常是件很令人恼火的事情…… 尤其是在我们这样的人口大国第八章 排队论基础理论基础：数理统计和随机过程排队论(queuing theory)研究内容： 由于随机因素的影响而产生的拥挤现象， 也称为随机服务系统理论。排队论是研究排队服务系统的数学理论和方法。第8章 排队论基础第8章 排队论基础 随机服务系统概论 无限源的排队系统 §8.1 随机服务系统概论§8.1 随机服务系统概论 起源和发展 生活中的排队现象 随机服务系统的基本组成部分 几个常用的概率分布和最简单流 排队系统的符号示（模型分类）1 起源和发展1 起源和发展起源： 1909年丹麦的数学家电话工程师爱尔朗 （Erlang）用随机过程理论研究电话网中的排队问题。 发展：二战后，开始了对机器管理、陆空交通等 方面的研究，1951年以后，理论工作有了新的进展，逐 渐奠定了排队论（现代随机服务系统）的理论基础。 上世纪七十年代，排队论开始应用于计算机系统和计算机网络领域。 2 生活中的排队现象2 生活中的排队现象生活中排队现象：购买物品，看病，上车，…. 广义的排队现象：电话的占线，等待装船的货物，等待加工的原料，等待修理的出故障的机器….. 一般而言，如果要求服务的对象的数量超过了服务机构的数量便产生排队现象。“顾客” (client) ：得到服务的对象 “服务台” (server) ：给与服务的系统 顾客与服务台就构成了一个排队系统。2 生活中的排队现象2 生活中的排队现象3 随机服务系统的基本组成部分3 随机服务系统的基本组成部分输入（顾客到达服务系统的规律） 排队规则（顾客按怎样的规则排队等待服务） 服务机构（服务机构的设置,服务台的数量,服务的方式,服务时间的分布等） 这是排队系统的三个基本组成部分。顾客源顾客到达服务台离去排队服务系统3 随机服务系统的基本组成部分(1)3 随机服务系统的基本组成部分(1)到达时间间隔确定的 随机的到达人数情况单个到达 成批到达顾客源总数无限 有限输入3 随机服务系统的基本组成部分(2)3 随机服务系统的基本组成部分(2)排队规则1.损失制：当顾客到达时，若所有服务设施均被占用，则自动离去。 2.等待制：顾客到达时，若所有服务设施均被占用，就留下来等待服务，一直到服务完毕才离去。先到先服务（FCFS） 后到先服务（LCFS） 带优先权的服务（PR） 随机服务（SIRO）3 随机服务系统的基本组成部分(2)3 随机服务系统的基本组成部分(2)队长有限：系统中等待的空间有限。 等待时间有限：顾客在系统中等待的时间不超过某一个给定的长度。 逗留时间:（等待时间与服务时间之和）有限。3.混合制：损失制和等待制的结合，允许排队，但不允许队列无限长下去。3 随机服务系统的基本组成部分(3)3 随机服务系统的基本组成部分(3)服务机构服务设施的数量连接方式服务方式单台 多台串联 并联 混联单个 成批4 几个常用的概率分布和最简单流4 几个常用的概率分布和最简单流顾客到达时间间隔:服务时间:4 几个常用的概率分布和最简单流4 几个常用的概率分布和最简单流（1）定长分布（D）：4 几个常用的概率分布和最简单流（2）负指数分布（M）：4 几个常用的概率分布和最简单流负指数分布是在排队理论使用的最多的一种分布，常用来表示各种寿命的分布，它具有无记忆性，即:无论现在多大年龄，剩余寿命的分布不受已有年龄的影响。4 几个常用的概率分布和最简单流(1)4 几个常用的概率分布和最简单流(1)（1）定长分布（D）：顾客到达时间间隔为确定的。顾客到达时间间隔分布:4 几个常用的概率分布和最简单流(1)最简单流（即Poisson流）（M）特点： 在某个时段内，到达的顾客数量只和时间长度有关，而和时间的起点无关（平稳性）。 在某个时段内，到达的顾客数量和这个时间段之前到达的顾客数量无关（无后效性）。 在充分小的时间区间内，到达两个或者两个以上的顾客的概率是时间长度的高阶无穷小（普通性）。4 几个常用的概率分布和最简单流(1)4 几个常用的概率分布和最简单流(1)4 几个常用的概率分布和最简单流(1)一般地，大量的稀有事件流，如果每一事件流在总事件流中起的作用很小，而且相互独立，则总的合成流可以认为是最简单流。1/λ ——顾客的平均到达时间间隔 λ—— 单位时间内平均到达的顾客数4 几个常用的概率分布和最简单流(2)4 几个常用的概率分布和最简单流(2)服务时间分布: 设某服务台的服务时间为V，其密度函数为f(t)， 常见的分布有：1/μ ——每个顾客的平均服务时间 μ——单位时间平均服务完成的顾客数5 排队系统的符号表示（模型分类）排队系统通常用下述符号形式表示： ？/？/？/？ 其中：第一个符号表示顾客到达时间间隔的分布； 第二个符号表示服务时间分布； 第三个符号表示服务台数目； 第四个符号表示服务系统允许的最大顾客容量。 注：1971年，排队论的标准符号被为： ？/？/？/？ /？/？ 第五个表示顾客源数目，第六个表示服务规则5 排队系统的符号表示（模型分类）5 排队系统的符号表示（模型分类）M/M/1/∞系统：顾客到达时间间隔和服务时间服从负指数分布； 服务台数目为1； 系统的顾客容量没有限制；M/M/1/k系统：顾客到达时间间隔和服务时间服从负指数分布； 服务台数目为1； 系统的顾客容量为k；5 排队系统的符号表示（模型分类）M/M/c/∞系统?M/M/c/k系统?6 评价排队问题的指标已知: 顾客到达间隔时间分布, 服务时间分布. 求: 队长: L -- 系统中的顾客数. 排队长(队列长): Lq -- 队列中的顾客数. L = Lq + 正在接受服务的顾客数 逗留时间: W-- 顾客在系统中的停留时间 等待时间: Wq -- 顾客在队列中的等待时间. W= Wq + 服务时间 忙期, 损失率, 服务强度6 评价排队问题的指标§8.2 无限源的排队系统§8.2 无限源的排队系统M/M/1/∞系统 M/M/1/k系统1 M/M/1/∞系统1 M/M/1/∞系统无限单队 队长无限 先到先服务1 M/M/1/∞系统1 M/M/1/∞系统生灭过程：设有某个系统，具有状态集S={0,1,2,…}，若系统的 状态随时间t变化的过程{N(t):t>=0}满足以下条件，则称为一个 生灭过程。 设在时刻t系统处于状态n的条件下，再经过长为△t的时间： （1）转移到n+1(0≤n<∞)的概率为 （2）转移到n-1(1≤n<∞)的概率为 （3）转移到S-{n-1,n,n+1}的概率为 其中 为与t无关的固定常数1 M/M/1/∞系统1 M/M/1/∞系统 系统中没有顾客的概率； 服务台空闲状态的概率； 顾客到达即可得到服务的概率。 1 M/M/1/∞系统关于 的几点说明：——服务强度系统中至少有一个顾客的概率； 服务台处于忙的状态的概率； 反映系统繁忙程度。 即顾客的平均到达率小于顾客平均服务率时，系统才能达到统计平稳。1 M/M/1/∞系统1 M/M/1/∞系统1 M/M/1/∞系统 计算有关指标 平均队长1 M/M/1/∞系统1 M/M/1/∞系统平均等待列长 1 M/M/1/∞系统1 M/M/1/∞系统平均等待时间 平均逗留时间 1 M/M/1/∞系统Little公式（相互关系）小结：1 M/M/1/∞系统1 M/M/1/∞系统例：某火车站的售票处设有一个窗口。若购票者是以最简单流到达，平均每分钟到达1人，假定售票时间服从负指数分布，平均每分钟可服务2人，试研究售票窗口前的排队情况。并求等待顾客数超过5人的概率.1 M/M/1/∞系统null例在某工地卸货台装卸设备的中,有三个方案可供选择,分别记为甲乙丙,目的是选取使总的费用 最小的方案,有关费用如下表:设货车按简单流到达,平均每天(10小时)到达15车,每车平均 装货500袋,装卸时间服从负指数分布,每辆车停留1小时的损失 为10元2 M/M/1/k系统2 M/M/1/k系统无限单队 队长有限 先到先服务2 M/M/1/k系统2 M/M/1/k系统2 M/M/1/k系统2 M/M/1/k系统2 M/M/1/k系统计算有关指标 平均队长 平均等待列长 2 M/M/1/k系统2 M/M/1/k系统平均等待时间 平均逗留时间 2 M/M/1/k系统2 M/M/1/k系统2 M/M/1/k系统例：一个理发店只有一个理发师，有3个空椅子供等待理发的人员使用。设顾客以最简单流来到，平均每小时5人。理发师的理发时间服从负指数分布，平均每小时6人。试求L，Lq，W，Wq。