第八章排队论.ppt

运筹帷幄之中,决胜千里之外
运筹学
中原工学院机电学院
主讲:丁剑飞
dingjf06@
Chapter 8 排队论(Queuing Theory)
排队论的基本概念
单服务台系统
多服务台系统
本章主要内容:
引言
在人们生活和生产的实践活动中,经常会遇到拥挤现象,从而产生排队。为了获取较好的经济效益,有必要研究排队现象的规律性。要求得到服务的对象统称为顾客;顾客不仅可以是人,也可以是物。例如等待加工的零件,出故障等待维修的机器等都是顾客。提供服务的对象称为服务机构。顾客和服务机构形成了一个服务系统。例如到医院就医的患者和医院;出现故障的机器和及机器维修班组等,都是服务系统。
顾客到达服务机构,当然是希望立即得到服务。然而服务机构已经占满时,例如理发店的座位已满,维修班组已忙于维修机器,再到的顾客只能排队等候或者消失,这样造成的损失称为排队费用。例如机器的停工损失,在仓库的存储
排队论的基本概念
费用,因等候而降低的价值等,都属于排队费用。排队的时间越长,排队费用越大。另一方面,设立的服务机构越多,服务效率越高,需要支付的费用也越大,然而却可以减少排队时间。如何根据顾客的实际情况,设立适当的服务机构,以使得服务费用和排队费用总和最少,是排队论所要讨论和解决的问题。
排队论的基本概念
顾客到达服务机构,依照一定的规律等待,然后接受服务,服务完毕后离去。这个过程称为服务过程。
引言
如果顾客到达和接受服务的时间都具有随机性,那么这个服务系统就称为随机服务系统,又称为排队系统;服务过程称为排队过程。一个排队过程,大体分为三个基本部分:输入过程、排列规则、服务机构。
输入过程
排队规则
服务机构
排队论的基本概念
一、输入过程
对于排队系统,顾客是输入。输入过程是指顾客按怎样的规律到达服务机构。顾客来源的总体称为顾客源。例如待修机器和维修班组所形成的排队系统,工厂的全部机器是顾客源;对于到理发店来理发的顾客来说,全体居民是顾客源,等等。顾客源可以是无限集合,也可以是有限集合。顾客可能单个到达,也可能是成批到达,或者是接连不断地到达。本章我们主要讨论称为泊松流或者最简单流的到达方式。
1. 泊松流(记为M)
顾客的输入过程如果具备以下三个特点,则称为泊松流。
排队论的基本概念
(1)平稳性对于任何t>0和非负整数k,在区间(a,a+t]内有k个顾客到达系统的概率对任何a≥0都是相等的。也就是说,这个概率只与t和k有关,而与a有关。我们以vk(t)记这个概率,以x(t)记在长为t的时间段内到达的顾客数,则有
(2)无后效性在时间区间(a,a+t]内到达k个顾客的概率与时刻a以前系统的状况无关。就是说,事件(x(t)=k)与a以前系统所发生的事件相互独立。
(3)普通性记为在时间段t内,到达两个和两个以上顾客的概率,即,则有t→0时, 。
排队论的基本概念
实际上,许多排队系统的输入过程都近似满足这些特征。可以证明,凡是具备上述3个特征的输入过程,x(t)都是服从泊松分布的随机变量。即
x(t)的期望值和方差分别为E[x(t)]=λt,Var[x(t)]=λt。若取t=1,则E[x(1)]=λ。这即是说,λ表示单位时间内到达系统顾客数的平均值,λ称为顾客的到达率或输入率。
还可以证明,如果顾客的到达数服从泊松分布,那么它一定满足上述的3个特性。
()
排队论的基本概念
2. 定长输入(记为D)
流水线上定时送往包装机的成品,其输入过程就是定长输入。如果规定的产品到达的间隔时间为c,则相继到达产品间隔时间t的分布函数为
3. k阶爱尔朗分布(记为Ek)
设t1,t2,…,tk是k个相互独立的,且具有相同参数λ的负指数分布随机变量,则随机变量t=t1+t2+…+tk服从k阶爱尔朗分布,t的密度函数为
()
排队论的基本概念
随机变量t的期望值和方差分别为:
例如,如果顾客连续接受串联的k个服务台的服务,各服务台的服务时间相互独立,且均服从参数为λ的负指数分布,则顾客接受k个服务台总共所需的时间就服从k阶爱尔朗分布。
()