基于排队论的生产流程优化模型研究 - 图文

上海海事大学本科生毕业设计

第三章 排队论模型及算例分析

3.1排队论及其应用

这章节中先简单介绍一下排队论的有关应用，然后讨论一下与排队论模型有关的的随机过程，如泊松过程和生灭过程，然后介绍几种排队系统的具体结构，最后对常见的几种排队规则做一些介绍与分析。

现实生活中，存在着如表3.1所示的各种类型的服务系统。

表3.1 服务系统类型汇总表 顾客 电话呼入 旅客 文件稿 等待着陆的飞机 病人 购买商品的顾客 等待被加工的材料（零件） 进港的船舶 待修的机器 服务内容 通话 购买门票 打字 降落 诊治 收货服务 加工组装 装卸货物 机器维修 服务机构 交换台 售票处 打字机 跑道 医生 服务员 流水线 泊位 机修工 在这些服务系统中，提出某种服务需求的对象统称为“顾客”（离散的或是连续的），实现服务的工具，设备和人员统称为“服务机构”，显然，对某些服务系统来说，如果要求服务的顾客数量超过服务机构的能力，就会发生拥挤现象即顾客为获得某种服务而排队等待。

例如跑道为等待着陆的飞机服务这一服务机构来说，当飞机即将降落时，如果有空闲的跑道，则飞机即可立即降落，也就是立即得到服务；如果每个跑道上已有其他的飞机正在滑翔，这架即将降落的飞机就不得不按照一定的排队规则加入到等待服务的队伍中去，这时候这种等待不仅仅是飞机自身的等待，更是乘坐在飞机上的顾客的等待，直到有空闲的跑道出现，这时此架飞机就得到了服务机构的服务。不同的顾客所花的被服务时间不同，得到服务之后就离开，我们用图-3.1的模型来表示这一过程。

服务系统顾客到达等待服务排队规则接服务服务时间离去图3.1 服务系统模型图

由于在大多数服务系统中，顾客到达的时刻以及所需要的服务时间在实现都无法确定而呈现随机性，因而服务系统的排队状况也是随机的。排队论就是一门研究处理随机服务系统

15

上海海事大学本科生毕业设计

排队现象的学科。它的任务是考察服务系统随机现象的规律，建立数学模型，为决策者正确的设计与有效地运营服务系统而提供必要地科学依据，使决策者在系统服务费用和顾客的有关等待费用之间达到经济上的平衡。

下面了解一下排队论模型中几个主要的随机过程 3.1.1 泊松过程。

一个随机过程{N(t), t≥0}如果满足以下条件，则被称为参数λ的泊松过程 ①独立增量性（即独立时间段上的事件发生的个数是独立的） ②平稳性（在任意一段时间内发生的事件个数的分布是不变的） ③在一小段时间h内发生一个事件的概率为λh+o(h)。 ④在一小段时间h内发生多于一个事件的概率为o(h) λ被称为泊松过程的速率。

由独立增量性可知，在区间[ s,s+t ]内来到k个顾客这一事件与区间[ 0,s ]内来到的顾客的情况是相互独立的，换言之，对在[ 0,s ]内顾客来到的情况所作的任何假定下，计算出来的在[ s,s+t ]内来到k个顾客的条件概率都相等。

平稳性说明在[ s,s+t ]内来到的顾客数只与区间的长度t有关而与起点s无关，换言之，过程的统计规律不随事件的推移而改变，在同样长度的时间间隔内来到k个顾客的概率是一个常数。

普通性表明，在同一瞬间时刻到达两个或两个以上顾客实际上是不可能的，换言之，在充分小的时间间隔中，最多到达一个顾客。

(?t)k??te???0?,k=0,1,2,?? 事实证明P（N(t)=k）=k!泊松过程在排队论中的地位与正态分布在概率论中的地位相同，但是需要指出，独立增量性，平稳性和普通性在实践中并不是经常能够满足的，例如平稳性对电话呼唤流就显然不成立，白天的呼唤就比晚上多，虽然如此，最简单流仍然可以认为是实际现象相当程度上的近似，特别如巴尔姆-辛钦的极限定理断言：大量相互独立小强度的随机流之和近似于一个最简单流，只要每个加项流都是平稳与普通的，同时满足一些足够普通的条件。

概率论的中心极限定理告诉我们：足够多的独立随机变量之和近似于正态分布，而不管这些随机变量是什么分布。

而巴尔姆-辛钦极限定理正如中心极限定理一样，阐明了为什么最简单流正如正太分布那样，经常会在实际生活中出现。

（t）3.1.2 生灭过程。若随机过程{?|t??0,A?}的状态集I={0,1,2，??，m}或（t）I={0,1,2，??}.设在时刻t时?=j，那么在时刻t+?t时（j和j+1?I），?(t??t)=j+1的概

率为?j?t??(?t)（其中?j?0为与t无关的常数）；在时刻t??t时（j和j-1?I），?(t??t)=j-1

16

上海海事大学本科生毕业设计

的概率为?j?t??(?t)（其中?j?0也为与t无关的常数）；在时刻t??t时，?(t??t)为I中其

（t）他元素的概率为?(?t)，则称该随机过程{?|t

??0,A?}为生灭过程。因为本篇文章中不会用

到生灭过程，所以更详细的内容就不在此赘述。

3.1.3 负指数分布。若用Vn表示第n位顾客所需的服务时间，则{Vn，n=1,2，??}也是一簇随机变量，假定{

Vn，n=1,2，??}中各个随机变量相互独立，且服从相同的负指数分布：

?e??t,t??0,t?0,f(t)?{?，其中参数>0,因而其概率密度函数为，Vn的数学

1111??E(Vn)?,D(Vn)?2E(Vn)，从而，?为每位顾客所需要的平??，因此期望和方差分别为

均服务时间，即为在单位时间内受到服务的顾客平均数。

若一个顾客的服务时间服从负指数分布，则当顾客开始接受服务后，服务结束的较短的可能性较大，而服务时间较长的可能性确是相当小的，也就是说，如果某种服务的服务时间具有以下性质：有大量的顾客要求较短时间的服务，只有少量麻烦顾客需要长时间服务时，则一般可认为服务时间服从负指数分布。

3.1.4 爱尔郎分布。爱尔郎分布的密度函数为

k?(k?t)k?1k?1)!f(t)?{0,t(?0P(Vn?t)?{1?e??t,t???0,t?0,e?k?t,t?0;

E(Vn)?1,D(Vn)?1k?2。

其中参数?>0，k称为阶数。

若顾客服务时间V服从爱尔郎分布，则V的数学期望和方差为

?由于负指数分布的特性说明顾客服务时间段的可能性比服务时间长的可能性大，所以，在实际应用中负指数分布受到一定的限制，而爱尔郎分布确具有较大的适应性。

f(t)K=∞K=3K=2K=1图3.2 不同k值的服务时间图

17

上海海事大学本科生毕业设计

由图可知，当k=1时，爱尔郎分布就是负指数分布；当k增大时，爱尔郎分布的图形逐渐变为对称的；当k?30时，爱尔郎分布近似于正态分布；当k??时，则D(Vn)?0,因此这时爱尔郎分布化为确定性分布，所以k阶爱尔郎分布可看成完全随机性与完全确定型之间的中间型。

3.2M/M/S/k模型及其适用范围

在了解了排队论的几个基本过程之后，来了解一下关于排队论的几种模型以及他们的使用范围。

一般的排队系统都由三个基本部分组成：

( 1) 输入过程。顾客按什么规律到达, 是有限的还是无限的, 方式是单个来还是成批来; 顾客到达的间隔是确定的, 还是随机的。

( 2) 排队规则。顾客到达后采用什么服务规则: 先到先服务、后到先服务, 随机服务还是有优先权服务。

( 3) 服务机构。服务台的设置、数量, 服务时间的分布。

为后面讨论具体的数学模型的方便，排队论模型中的数量指标的符号如表3.2排队论模型参数汇总表：

表3.2 排队论模型参数汇总表 符号 所表示的意义 单位时间内平均到达的顾客数，即平均到达率 平均到达间隔 单位时间内受到服务的顾客数，即平均服务率 每位顾客的平均服务时间 服务台个数 每个服务台的服务强度，即每个服务台在单位时间内的平均负荷 在统计平衡时，系统中具有j个顾客的概率 18

? 1/? ? 1/? S ? Pj