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