运筹学基础 课件 第7章.pptx

第7章排队系统分析;

7.1排队现象及范例

排队系统可以看作是一个黑盒。顾客为了获得某种服务而来(到达),由于顾客多而需要等待,在达成目的之后离开系统(见图7-1)。;

在排队系统中,来排队请求服务的称为顾客,提供服务的称为服务台。顾客的主体可以是人,也可以是物,还可以是信息以及抽象的待处理任务等,如表7-1所示。;;

7.2排队系统分类;

X:表示顾客相继到达间隔时间分布;

Y:表示服务时间分布;

Z:表示服务台个数;

A:表示系统的容量限制;

B:表示顾客源数目;

C:表示排队规则。

其中有顾客到达时间间隔分布和服务时间分布,常用的有负指数分布用M标识,定长输入(确定型分布)用D标识,k阶爱尔朗分布用Ek标识,一般相互独立的随机分布用G标识。;

例如,某排队问题记为M/M/S/∞/∞/FCFS,表示此排队系统满足以下特征:顾客到达间隔时间为指数分布,服务时间为负指数分布,有S个服务台,系统等待空间容量无限(等待制),顾客源无限,采用先到先服务规则。;

排队规则代表排队系统对队列中排队顾客调度策略,经常会碰到的排队规则有以下几种:

(1)先进先出:这一原则也被称为先到先得,即顾客一次只能得到一个服务,先来的顾客也就是等待时间最长的顾客先得到服务。

(2)后进先出:这个原则也可以一次服务一个顾客,但是最后一个到达的,也就是等待时间最短的顾客会先得到服务。这在算法中会经常用到,其利用的数据结构常为堆栈。

(3)优先级:优先考虑的顾客是第一位的。优先级队列可以分为两种类型,非抢占(服务中的作业不能被中断)和抢占(服务中的作业可以被高优先级作业中断)。;

7.3Little定律;

下面首先通过一个直观的例子来理解Little定律的正确性。

首先在图7-2(a)中,横坐标表示时间,纵坐标表示系统中的顾客数量,则随着时间的推进,系统中的顾客数量会随着顾客的到达或者离开而变化。图7-2(b)显示了各个顾客在系统中的逗留时间。图7-2(c)使用不同的颜色具体标识了不同的顾客对于阴影部分面积的贡献。;

;

??以很容易得出结论,这两个图的阴影部分的面积是相等的。在更一般化的例子中,这两部分的面积相等也是成立的。在一般的问题中,在时间区间[0,T]内,设阴影部分的面积为S,系统中顾客的平均数量为L,总共到达的顾客数量为N,系统中顾客逗留的平均时间为W,则有

即得;

例7-1假设某高速收费站车辆的平均到达数量为每小时200辆,车辆排队的平均队长为5,请计算车辆在收费站的平均逗留时间。

根据已知,L=5,λ=200,根据Little公式得

车辆的平均逗留时间为0.025小时,即1.5分钟,和车辆到达时间间隔分布没有关系。;

7.4排队系统的解析;

所谓某个变量t(如顾客到达时间间隔或者服务时间)服从指数分布,指的是t的概率密度函数为

因此,我们可以计算其期望值及累积概率分布如下:;

指数分布有一个非常著名的性质,被称为遗忘性或者无记忆性。所谓无记忆性,是指顾客在未来一段时间内到达的概率仅与这段时间间隔有关系,与顾客以前的到达事件没有

关系。如果一个设备的可靠性服从指数分布,则它将来一年发生故障的概率与它已经故障了几次以及什么时间故障的没有关系。;

假设上一个顾客到达到现在已经过了时间S0,下一个顾客到达还需要经过的时间T与S没有关系。指数分布具有如下关系:

证明:;

例7-2假设某部有两部同型号雷达A和B,A雷达刚刚修理好,B雷达上次故障是在一年前,两部雷达的故障间隔时间服从指数分布,平均值均为2000小时,请问未来半年内两部雷达发生故障的概率分别是多少?未来一年内发生故障的概率是多少呢?

因为故障间隔时间服从指数分布,且平均值为2000,因此;

假设一年为365天,也就是8760小时,则根据指数分布的无记忆性可知,未来一段时间发生故障的概率和上一次故障发生的时间没有关系。

对于A雷达和B雷达,未来半年内发生故障的概率均为

未来一年内发生故障的概率均为;

7.4.2生灭过程

1.生灭过程图

令排队系统中顾客的数量为系统的状态,在同一时刻最多只有一名顾客到达或者离开的假设下,系统的状态只在相邻的状态之间转移,并且设λk为系统中有k个顾客的时候顾

客的到达率,也即单位时间内到达顾客数量的期望;μk为系统中有k个顾客的时候顾客的离开率,也即单位时间内离开顾客数量的期望。则可以建立排队系统的生灭过程图如图7-3所示。;

;

2.平衡方程及状态概率

对于顾客到达时间间隔及服务时间是随机分布的排