当前位置：文档之家 › 第九章 排队论 (1)

第九章 排队论 (1)

  • 格式：ppt
  • 大小：1.40 MB
  • 文档页数：67

下载文档原格式

  / 67

合集下载

排队论

排队论


G：一般分布。表示到达间隔时间或服务时间服从一般分布。G是General的第 一个字母。
EkE：rlkan-爱g 尔朗的分第布一。个表字示母到。达间隔时间或服务时间服从k-爱尔朗分布。E是 D: 定长分布 (常数时间)
H：超几何分布。
L：H项式分布。
Z代表的服务规程典型的有：
FCFS：先来先服务；LCFS：后来先服务；RSS：随机选择服务；
PR：优先权服务。 Ba：集体（批量）服务。 GD：一般规约服务，即通用规约服务。
排队论课件 23
3 基本排队关系
在对排队进行分析时，为了便于分析，经常做一些简化假设。对一个排队系 统，若满足以下三个条件：
（1）排队系统能够进入统计平衡状态；
（2）服务员的忙期与闲期交替出现，即系统不是总处于忙的状态；
泊松分布（Poisson）： P{X = k} = λk e-λ/ k! k=0,1,2,…， μx = σx = λ 泊松分布是最重要的离散型概率分布之一，也是表述随机
现象的一种重要形式。在实际系统模型中，一般都要假定任务 （或顾客）的到来是泊松分布的。实践也证明：这种假设有效。
如果顾客到达的人数是符合泊松分布，即在时间T内到达 有k个顾客到达的概率为：
♂
※
排队论课件
11
基本的排队模型
基本组成 概念与记号 指数分布和生灭过程
♂
排队论课件 12
典型排队系统模型
顾客到达: 在队列中排队 服务台服务 顾客离开
输入源
。。。
输入源的 特性？
到达规律 队列大小？
到达方式？
服务规律？
服务协议？
在本单元中，我们主要介绍排队系统的组成和特征，排队系统 的到达和服务，经典排队模型等内容。顾客到达规律和服务规 律都是通过概率来描述的，所以概率论是排队论的基础。
排队论知识点(一)

排队论知识点(一)

排队论知识点(一)排队论知识点详解什么是排队论排队论是应用概率论、随机过程和数学统计方法来研究队列系统的数学理论。

队列系统是指一些处理实体以确定的方式到达某个系统，被系统以某种方式处理，然后离开系统的系统模型。

排队论研究的目标是为了通过合理的设计和优化队列系统（如银行服务台、电话交换机等）的结构和参数，提高系统的效率和性能。

排队论的主要概念1. 到达过程到达过程是指实体到达队列系统的时间间隔的随机过程。

根据到达的规律性和随机性不同，到达过程可以分为不可预测的泊松到达过程和可预测的非泊松到达过程。

2. 服务过程服务过程是指队列中的实体被处理的时间间隔的随机过程。

根据服务的规律性和随机性不同，服务过程可以分为不可预测的指数服务过程和可预测的非指数服务过程。

3. 队列长度队列长度是指队列中正在等待服务的实体的个数，也可以看作是在系统中等待服务的实体的数学期望。

4. 平均等待时间平均等待时间是指实体在队列系统中等待服务的平均时间。

5. 利用率利用率是指队列系统中服务设备的利用情况，通常用平均到达率与平均服务率的比值来表示。

排队论的基本模型1. M/M/1模型M/M/1模型是排队论中最简单的模型之一，代表了一个单一服务台和一个队列的排队系统。

M/M/1模型的到达过程和服务过程都是泊松过程，服务设备能力为1。

2. M/M/C模型M/M/C模型是M/M/1模型的扩展，代表了含有C个服务台和一个队列的排队系统。

到达过程和服务过程仍然是泊松过程，但是服务设备能力为C。

3. M/G/1模型M/G/1模型是M/M/1模型的变体，代表了一个单一服务台和一个队列的排队系统，但是服务过程是一般分布。

到达过程仍然是泊松过程。

4. G/G/1模型G/G/1模型代表了一个单一服务台和一个队列的排队系统，到达过程和服务过程都是一般分布。

排队论的应用1. 交通拥堵排队论可以用来研究交通拥堵的原因和解决方案，进一步优化交通网络资源的利用和流量的分配。

系统工程---第九章 排队论

系统工程---第九章 排队论


9.1.1 排队论发展简述
最早有关排队论著作一般人共认的是1909年丹麦数学家爱尔朗（A.K. Erlang）所发表的论文，爱尔朗服务于丹麦哥本哈根电话公司，该论文研 究的主题是电话交换机的使用状况，爱尔朗主要的著作成于1909至1920年 间，有关他的生平与作品可参阅布鲁可迈尔（E.Brockmeyer）等人的文章。 爱尔朗之后从事排队论研究的先驱人物有法国数学家勃拉彻（F.Pollaczek） 和前苏联数学家金勤（A.Y.Khintechine），他们在这方面的研究课题都在30年 代完成并载于他们后来撰写的著作里。 第二次世界大战之后，应用概率论，运筹学得到了广泛而深入的发展， 排队论的论述已十分普及了。50年代初期英国人堪道（E.G.Kendall）又系统 地阐述了排队问题，并且利用嵌入马尔柯夫链的方法推动了排队论的进一步 发展。
第一个子服务台系统 输出

输入 第 k 个子服务台系统 输出

第 n 个子服务台系统 输出
图 9-5 多队——多服务台系统
山东理工大学管理学院
9.2 排队系统的组成及数量指标

9.2.2 排队问题的分类
按照排队系统的三个主要特征，即 （1）相继顾客到达间隔时间的分布； （2）服务时间的分布； （3）服务台个数。 D.G.Kendall 在 1953 年提出一个目前广泛采用的排队系统的分类方法，其标记 如下
山东理工大学管理学院
9.1 排队论概述
6．生产线问题 在工厂生产线上，机器、工人甚至物料运输设备如何安排以保证生产率 的水平，降低生产过程中原料和半成品的存量往往也可通过排队问题的研究 获得解决。在这类问题里，产品为顾客，机器、工人或者有关生产、运输设 备为服务台。
7．计算机问题
第九章 运筹学排队论

第九章 运筹学排队论

E (T ) = 1
λ
, D(T ) =
1
λ2
三.服务时间v的概率分布 一般总是假定顾客接受服务的时间v也服从负 指数分布 f v (t ) = µe − µt , µ是单位时间能服务完的顾客数,
E (v ) = 1
µ
, D (v ) =
1
µ
2
注意 : E (v) =
1
µ
是一个顾客的平均服务时间.
λ ρ= 是刻划服务效率和服务机构利用程度的 µ
重要标志.当 ρ < 1 时,ρ 越小,表示单位时间 内到达顾客的平均数比服务完的顾客平均数 小得多,顾客到达后可及时得到服务,等待时 ρ 间少,服务员空闲,服务设施利用率低;反之 > 1 ρ 越大,反映的事实与上述相反.
注意:同时满足下面三个条件的流为泊松流 ⒈无后效性:前面到达的顾客数并不影响后面 到达的顾客数; ⒉平稳性:顾客到达的多少只与时间间隔有 关,而与统计时的时刻无关; ⒊普通性:在很短的时间间隔内,到达两个或 两个以上顾客的概率极小,可以忽略不计.
先考虑n=0的状态,状态0的稳定状态概率为0 p 而从状态0进入状态1的平均转换率为 ,因 λ λ 此从状态0进入状态1的输出率为 p0 ,同理,状 态1进入状态0的输入率为 p1 .根据输出率等 µ 于输入率的原则,在系统平衡条件下,对状态0 有以下的状态平衡方程λp0 = µp1 .
λ λ n = 0, p1 = p0 , 又ρ = , 所以p1 = ρp0 . µ µ
一.生灭过程 在排队理论中,通常采用一种名为”生灭过程” 的方法来描述.首先画出生灭图,它的特点是系 统的所有状态看作一系列的点,用0,1,2, …表 示,并用正,反两方向的箭头线将左右状态连接 , , 起来,如下图
运筹学课件：排队论总结

运筹学课件：排队论总结

假定不允许缺货，订购后供货单位能即时供应，求最优订购量、订 购间隔期和单位时间总费用。
Operation Research
模型二：不允许缺货，生产需一定时间（1）
第八讲
该模型最早用于确定生产批量，因此也称为生产批量模型 （Production lot size）
模型假设条件
缺货费用无穷大，C2→∞
存储量随时间的变化情况
-R
Operation Research
第八讲
模型一：不允许缺货，备货时间很短（2）
问题分析
决策的要素： 确定合适的订货时间间隔；确定合适的订货量；
矛盾所在
1. 订货间隔时间短，可以减少每次的订货量，降低存储费用；但在一 个固定时间段内，必然会增加订购次数，使订购费用增加；
第八讲
模型四：允许缺货（需补足缺货），生产需一定时间（2）
存储量随时间的变化情况
Operation Research
解释
第八讲
Operation Research
第八讲
模型四：允许缺货（需补足缺货），生产需一定时间（3）
公式推导
Operation Research 求最小值
第八讲
Operation Research
单位时间内单位缺货的损失，C2为常数
当存货降至零时，允许拖一段时间，然后订货就逐步均匀到货， 到货（生产）速率为P为常数
需求是连续的、均匀的，设需求的速率R（单位时间的需求量）为 常数，并且P>R，则t时间的需求量为Rt
每次订货量不变，订购费不变，C3为常数 单位存储费不变，C1为常数
Operation Research
Operation Research
第八讲
运筹学 排队论(1)

运筹学 排队论(1)

运筹学排队论1. 简介排队论是运筹学中重要的一个分支，它研究了在人员、物品或信息流动过程中产生的排队现象，并通过建立数学模型和分析这些模型来探讨和优化系统中的排队行为。

排队论在各个领域都有广泛的应用，如交通运输、电信网络、生产制造等。

2. 排队模型排队论中常用的模型包括M/M/1模型、M/M/s模型、M/G/1模型等。

其中，M表示到达过程的分布，而G表示服务时间的分布。

而数字1或s则表示系统中的服务通道数。

2.1 M/M/1模型M/M/1模型是排队论中最简单的一个模型，它假设到达过程和服务时间都服从指数分布。

该模型中只有一个服务通道。

2.2 M/M/s模型M/M/s模型是M/M/1模型的扩展，它假设到达过程和服务时间仍然服从指数分布，但有s个服务通道。

M/M/s模型适用于有多个并行服务通道的排队系统。

2.3 M/G/1模型M/G/1模型假设到达过程服从泊松分布，而服务时间服从一般分布。

该模型在实际应用中更为常见，因为服务时间往往不服从指数分布。

3. 排队论的性能度量排队论的性能度量是对排队模型进行定量分析和评估的重要手段，常见的性能度量指标包括平均等待时间、平均逗留时间、系统繁忙率等。

3.1 平均等待时间平均等待时间是指在排队系统中，每个顾客平均等待的时间长度。

通过对排队模型的分析和计算，可以得到平均等待时间的具体数值。

3.2 平均逗留时间平均逗留时间是指每个顾客在排队系统中逗留的平均时间长度。

它等于平均等待时间加上服务时间。

3.3 系统繁忙率系统繁忙率是指服务通道在单位时间内处于工作状态的比例。

它可以用来评估系统是否能够满足顾客的需求。

4. 排队论的应用4.1 交通运输排队论在交通运输领域的应用非常广泛。

例如，交通信号灯的控制就可以通过排队论进行优化，以减少车辆的等待时间和交通拥堵。

4.2 电信网络在电信网络中，排队论被用于研究数据包的传输和路由机制。

通过对排队论模型的分析，可以提高网络的传输效率和质量。

《Ch9排队论》课件

《Ch9排队论》课件


重要方向之一。我们将学会如何将排队论
与经济学融会贯通，以解决企业管理中的
3
排队论应用实例分析
实际问题。
本节将结合实际案例，详细介绍排队论在
公共交通、医疗和金融领域等的应用，帮
助大家更好地掌握相关知识。
四、排队论的研究方向
排队论的未来研究方向
本节将介绍排队论未来的研 究方向，包括排队网络、模 糊排队系统等。
《Ch9排队论》PPT课件
本课件将带你领略本章的排队论概述、排队模型及分析、问题求解、研究方 向等知识点，揭示排队论在现实生活中的重要性和应用前景。
一、排队论概述
什么是排队论？
排队论的应用场景
排队论是研究顾客在到达服务设施之前、等待服务 过程中、接受服务时的随机现象及规律的数学工具。
排队论广泛应用于公共交通、医疗、金融、旅游和 娱乐等领域，例如人流控制和乘客服务质量的提高。
排队论与其他学科的交 叉研究
排队论是交叉学科的重要领 域，本节将介绍排队论与其 他学科（如交通工程、运筹 学）的交叉研究。
排队论的发展趋势
本节将探讨排队论的未来发 展趋势，包括应用领域的拓 展、理论方法的提升等方面。
五、总结
排队论的重要性和应用前景
排队论是现代服务行业不可或缺的一部分，学会排 队论对于提高服务质量和顾客满意度至关重要。
超市收银台的排队模型
超市收银台的排队模型是排队论中实际应用最广泛的模型之一，我们将学会如何分析超市收银台的排队模型。
三、排队论中的问题求解
1
排队论中的瓶颈问题
ห้องสมุดไป่ตู้
瓶颈问题是珠联璧合问题中一种常见问题，
排队论与经济学的应用
2
本节将告诉你如何识别瓶颈，以及如何优 化排队系统。
第九章 排队论 (1)PPT课件

第九章 排队论 (1)PPT课件


9.1排队论的基本概念
排队论是通过对服务对象到来及服务时 间的统计研究，得出这些数量指标（等 待时间、排队长度、忙期长短等）的统 计规律，然后根据这些规律来改进服务 系统的结构或重新组织被服务对象，使 得服务系统既能满足服务对象的需要， 又能使服务机构的费用最经济或某些指 标最优。
4
9.1.1排队过程的一般表示
第9章 排队论
1
整体概述
概况一
点击此处输入相关文本内容 点击此处输入相关文本内容
概况二
点击此处输入相关文本内容 点击此处输入相关文本内容
概况三
点击此处输入相关文本内容 点击此处输入相关文本内容
2
排队是我们在日常生活中经常遇到的现象，例如 病人到医院看病、客户到银行汇款、城市拥堵 路段的汽车排队、电话占线等。排队现象产生 的原因之一是要求服务的数量超过了服务机构 的容量，也就是有部分的服务对象不能立即得 到服务；原因之二是系统服务对象到达和服务 时间均存在随机性。前者可以通过增加服务机 构的容量来解决排队现象，但无休止地增加服 务机构的容量会导致追加投资并可能发生系统 资源长时间闲置。后者，也就是系统服务对象 到达和服务时间均存在随机性，致使无法准确 预测估算排队拥堵的具体情况。所以，在服务 系统中3 的排队现象几乎不可避免。
当k=1时爱尔朗分布就是负指数分布；当 k增加时，爱尔朗分布逐渐变为对称的。 当k>30时，爱尔朗分布近似于正态分布。
18
G：一般随机分布。 例如M/M/l表示到达的间隔时间服从负指数 分布，服务时间也服从负指数分布的单服务 台排队系统模型。M/D/2表示到达间隔时间 服从负指数分布，而服务时间为定长分布的 双服务台排队系统模型。
D1
L
E
排队论详解及案例

排队论详解及案例

服务时间总和 平均服务时间 =
服务顾客总数 到达顾客总数 平均到达率 =
总时间 平均服务率 = 服务顾客总数
服务时间总和
cmLiu@shufe
Operations Research
9.2.2 泊松分布
泊松分布也称为泊松流，在排队论中称为最简单流。
设 N (t )表示在时间区间 [t0,t0 + ∆t) 内到达的顾客数，是随机变量。
其常用的主要衡量指标如下： 1）队长（Ls）：排队系统中顾客的平均数（期望值），它是正在服务的
顾客和等待接受服务的顾客总数的期望值。 2）队列长（Lq）：排队系统中平均等待服务顾客数的期望值。显然有
队长＝排队长＋正被服务的顾客数 3）逗留时间（Ws）：一个顾客从到达排队系统到服务完毕离去的总停留
时间的期望值。
cmliushufeoperationsresearch913排队论研究的基本问题2统计推断问题的研究在建立实际问题的排队系统模型时首先要对现实数据进行收集处理然后分析顾客相继到达的间隔时间是否相互独立确定其分布的类型和相关参数研究服务时间的独立性以及服务时间的分布等在此基础上选择适合该系统的排队模型再用排队模型进行分析和研究
用F (t ) 表示 t 的概率分布函数，则有
∫ ∫ F
(t)
=P {T
≤
t}
t
= 0
µe−µt dt
=−
t 0
d
e − µt
=1 −
e−µt
cmLiu@shufe
Operations Research
9.2.3 负指数分布
负指数分布具有下列性质：
cmLiu@shufe
Operations Research
• 队长有限，即系统的等待空间是有限的； • 等待时间有限，即顾客在系统中的等待时间不超过某一给定的长度T，
排队论详解及案例

排队论详解及案例

9.2.3 负指数分布
负指数分布具有下列性质：
cmLiu@shufe
Operations Research
9.2.3 负指数分布
负指数分布具有下列性质：
cmLiu@shufe
Operations Research
当 N (t满) 足下列三个条件时，我们说顾客的到达符合泊松分布 （1）平稳性：在时间区间 [t0,t0 + ∆t) 内到达的顾客数 N (t ) ，只与区间长度
有关而与时间起点 t0 无关。
（2）无后效性：在时间区间 [t0,t0 + ∆t) 内到达的顾客。 数 N (t ) ，与 t0 以前
到达的顾客数独立。 （3）普通性：在充分短的时间区间 ∆t 内，到达两个或两个以上顾客的概率
• 如略去后三项，即指X/Y/Z/∞/∞/FCFS的情形。
cmLiu@shufe
Operations Research
9.1.3 排队论研究的基本问题
（1）排队系统工作状况的衡量 一个排队系统运行状况的好坏不仅会影响顾客的利益，也会影响服务 机构的利益，甚至会影响到社会效果的好坏。通过研究运行系统在平 衡状态下的概率分布及其数字特征，了解排队系统运行的效率、服务 质量等等，进而可以判断系统运行状况的优劣。
cmLiu@shufe
Operations Research
第九章
排队论
9.1 基本概念 9.2 几个常用的概率分布 9.3 单服务台负指数分布的排队系统 9.4 多服务台负指数分布排队系统模型 9.5 一般服务时间M/G/1模型 9.6 排队系统的建模与优化 9.7 电子表格建模和求解 9.8 案例分析 办公室设施公司（OEI）服务能力分析
cmLiu@shufe
排队论

排队论

排队论一、引言：日常生活中存在大量有形和无形的排队或拥挤现象，如旅客购票排队，食堂买饭排队，列车调用，计算机进程调用，市内电话占线等现象。

凡是具有公共服务性质的事业和工作，凡是出现拥挤现象的领域，都是排队论的用武之地。

排队论是研究服务系统中排队现象随机规律的学科，广泛应用于计算机网络、生产、运输、库存等各项资源共享的随机服务系统，其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。

排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。

二、排队论的起源与历史：排队论起源于20世纪初的电话通话。

1909年丹麦电话工程师 A.K.埃尔朗：话务理论，导出著名的埃尔朗电话损失率公式，自20世纪初以来，电话系统的设计一直在应用这个公式。

20世纪30年代苏联数学家А.Я.欣钦把处于统计平衡的电话呼叫流称为最简单流，瑞典数学家巴尔姆又引入有限后效流等概念和定义。

20世纪50年代初美国数学家关于生灭过程的研究，英国数学家D.G.肯德尔提出嵌入马尔可夫链理论，以及对排队队型的分类方法， L.塔卡奇等人又将组合方法引进排队论，使它更能适应各种类型的排队问题。

20世纪70年代以来人们开始研究排队网络和复杂排队问题的渐近解等，成为研究现代排队论的新趋势。

三、排队论的定义：排队论(queuing theory), 或称随机服务系统理论, 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。

四、排队系统：（一）、排队系统的构成排队系统又称随机服务系统，是研究服务过程和拥挤现象的随机模型。

服务系统由服务机构和服务对象（顾客）构成，顾客到达系统的时间是随机的，服务员为每一位客户服务的时间也是随机的，所以整个排队系统的状态也是随机的。

排队论

授 课 内 容 备注、更新第6章 排队论（1）排队是指因车辆数量超过服务设施的容量，致使车辆得不到及时服务而等候的现象。

（2）排队论则是研究排队现象及其规律性的理论。

（3）在交通工程中，排队论被广泛用于车辆延误、通行能力、信号灯配时以及停车场、收费亭、加油站等交通设施设计与管理等方面的研究中。

6.1 概述6.1.1排队系统基本组成1. 输入过程（1）定义：输入过程是指各种类型接受服务的车辆(或行人等)按怎样的规律到达（2）种类：①定长输入：车辆均匀到达，车头时距相同；②泊松输入：车辆到达符合泊松分布，车头时距服从负指数分布；③爱尔朗输入：车辆到达车头时距符合爱尔朗分布。

2. 排队规则（1）定义：排队规则是指到来的车辆按怎样的次序接受服务。

（2）分类：①等待制：车辆到达时，如若所有服务台均被占用，则该车辆便排队等候服务，称为等待制。

②损失制：车辆到达时，如若所有服务台均被占用，则该车辆不排队等候，称为损失制；③ 混合制：如果车辆到达时，若队长小于L，就加入排队队伍；若队长大于等于L，车辆就离去。

3.输出方式（1）定义：是指同一时刻有多少服务台可接纳车辆，每一车辆服务了多少时间。

（2）分类：①定长分布：每一车辆的服务时间都相等；②负指数分布：每一车辆的服务时间相互独立，且都服从相同的负指数分授 课 内 容备注、更新布；③ 爱尔朗分布：每一车辆的服务时间相互独立，具有相同的爱尔朗分布。

6.1.2 排队系统的主要特征指标① 服务率：它为单位时间内被服务的车辆均值。

② 交通强度：单位时间内被服务的车辆数与请求服务的车辆数之比。

③ 系统排队长度：可分为系统内的平均车辆数（Ls ）和排队等待服务平均车辆数（Lq ）。

常用于描述排队系统的服务水平。

④ 等待时间：从车辆到达时起到他开始接受服务时止这段时间。

⑤ 车辆在系统内的时间：等于车辆排队等待时间与接受服务时间之和。

6.1.3排队系统的分类记号（1）肯达尔（Kendall ）于1953年提出了排队系统的分类记号：输入分布/输出分布/并联的服务站数。

排队论



,
Var[T ]
1

, 2

1

16
负指数分布的性质： （ 1 ）无记忆性（或称马尔 柯夫性）。若T表示排队系统中顾客到 达的时间间隔， 则该性质说明一个顾客 到来所需的时间与过去 一个顾客到来所需时间 无关；这 种情形下顾客的到达是 纯随机的。 （2）当输入过程是泊松流 时，顾客相继到达的时 间间隔T必定服从负指数分布。 因此，相继到达的时间 间隔是独立且为同负指 数分布（密度函数为 e t , t 0）， 与输入过程为泊松流（ 参数为）是等价的。故在 Kendall记号中都用M表示。
( t ) n t Pn (t ) e n! t 0, n 0,1,2,
Pn (t )表示长为t的时间区间内到达 n个顾客的概率，并称随 机变量 N (t )服从泊松分布，其数学 期望和方差分别为 E[ N (t )] t Var[ N (t )] t
期望值和方差相等，是 泊松分布的一个重要特 征，可以由此对一个 经验分布是否是泊松分 布进行初步的识别。
13
泊松流的定义： 设N (t )为在时间区间 [0, t )内到达的顾客数 (t 0)，Pn (t1 , t 2 )为在时间区间 [t1 , t 2 )内有n（n 0） 个顾客到达的概率，即 Pn (t1 , t 2 ) P{N (t 2 ) N (t1 ) n} (t1 t 2 , n 0)
利用随机过程的知识可 以得出，在统计平衡状 态下，系统的状态为 n的概率为 P0 1 n Pn (1 ) , n 1 其中，
1
（否则队列将排至无限 1 远） , 其实际意义见下页。
t Leabharlann （statistica l equilibrium state ）的解。

排队论论述


1971年，一次关于排队论符号标准化会议， 将kendall符号扩充为：
X /Y /Z / A/B/C
前三项意义不变， A处填写系统容量限制， B处填写顾客源数目， C处填写服务规则
表示相继到达间隔时间和服务时间 的各种分布的符号：
M：负指数分布，（M 是 Markov 的字头，因为负指数分布具有 无记忆性，即：Markov 性） D：确定型（Deterministic）
13
2. 排队规则
③随机服务（RAND） 。即当服务台空闲时， 不按照排队序列而随意指定某个顾客去接受 服务，如电话交换台接通呼叫电话就是一例。
④优先权服务（PR）。如老人、儿童先进车站； 危重病员先就诊；遇到重要数据需要处理计 算机立即中断其他数据的处理等，均属于此 种服务规则。
14
2. 排队规则
在[t,t+Δt]内有一个顾客到达的概率与t无关,而 与Δt成正比。
30
λ>0 是常数，它表示单位时间到达的顾客数，称 为概率强度。
③ 普通性：对充分小的Δt,在时间区间（t,t+Δt） 内有2个或2个以上顾客到达的概率是一高P0+阶P1无+P穷≥2=小1 .
即 Pn (t, t t) o(t) n2
12
2. 排队规则
(2)等待制。指当顾客来到系统时，所有服务台 都不空，顾客加入排队行列等待服务。
例如，排队等待售票，故障设备等待维修等。 等待制中，服务台在选择顾客进行服务时，常有 如下四种规则：
①先到先服务（FCFS ）。按顾客到达的先后顺 序对顾客进行服务，这是最普遍的情形。
②后到先服务（LCFS）。仓库中迭放的钢材， 后迭放上去的都先被领走，就属于这种情况。
数学期望:(离散) E(ξ)=

(完整版)排队论公式1

M/M/1/∞/∞标准模型M/M/1/N/∞
系统容量有限模型
N=队伍容量+1
M/M/1/∞/m
顾客源有限模型
m=系统只有m+1种状态
M/M/C/∞/m
多服务台模型
单队，并列C个服务台
系统空闲的概率
ρ
系统有n个顾客的概率（顾
客损失率）
系统至少有1个顾客的概率1-
顾客的有效到达率
系统（每小时）顾客平均数
（每小时）等待服务的平均
顾客数
=
（每位）顾客在店内的平均
逗留时间
（每位）顾客平均修理时间
λ：每小时到达店内人数λ：每小时到达店内人数
µ：每小时可以服务的人数，1/每名客户服务时间的分钟数µ：每小时可以服务的人数，1/每名客户服务时间的分钟数
排队论公式一
排队论公式二
ρ：系统忙着的概率，ρ：系统忙着的概率，
M/G/1/∞/∞M/D/1/N/∞M//1/∞/m 系统（每小时）顾客平均数
（每小时）等待服务的平均
顾客数
（每位）顾客在店内的平均
逗留时间
（每位）顾客平均修理时间
λ：每小时到达店内人数
µ：每小时可以服务的人数，1/每名客户服务时间的分钟数E(v):服务时间v的期望
D(v):方差
ρ：系统忙着的概率，λ：每小时到达店内人数
µ：每小时可以服务的人数，1/每名客户服务时间的分钟数
:服务时间v的期望
D(v):方差
ρ：系统忙着的概率，。

排队论

实用排队论排队论又称随机服务系统，它应用于一切服务系统，包括生产管理系统、通信系统、交通系统、计算机存储系统。

它通过建立一些数学模型，以对随机发生的需求提供服务的系统预测。

现实生活中如排队买票、病人排队就诊、轮船进港、高速路上汽车通过收费站、机器等待修理等等。

一、排队论的基本构成（1）输入过程输入过程是描述顾客是按照怎样的规律到达排队系统的。

包括①顾客总体：顾客的来源是有限的还是无限的。

②到达的类型：顾客到达是单个到达还是成批到达。

③相继顾客到达的时间间隔：通常假定是相互独立同分布，有的是等间隔到达，有的是服从负指数分布，有的是服从k 阶Erlang 分布。

（2）排队规则排队规则指顾客按怎样的规定的次序接受服务。

常见的有等待制，损失制，混合制，闭合制。

当一个顾客到达时所有服务台都不空闲，则此顾客排队等待直到得到服务后离开，称为等待制。

在等待制中，可以采用先到先服务，如排队买票；也有后到先服务，如天气预报；也有随机服务，如电话服务；也有有优先权的服务，如危重病人可优先看病。

当一个顾客到来时，所有服务台都不空闲，则该顾客立即离开不等待，称为损失制。

顾客排队等候的人数是有限长的，称为混合制度。

当顾客对象和服务对象相同且固定时是闭合制。

如几名维修工人固定维修某个工厂的机器就属于闭合制。

(3)服务机构服务机构主要包括：服务台的数量；服务时间服从的分布。

常见的有定长分布、负指数分布、几何分布等。

二、排队系统的数量指标(1)队长与等待队长队长（通常记为s L ）是指系统中的平均顾客数（包括正在接受服务的顾客）。

等待队长（通常记为q L ）指系统中处于等待的顾客的数量。

显然，队长等于等待队长加上正在服务的顾客数。

(2)等待时间等待时间包括顾客的平均逗留时间（通常记为s W ）和平均等待时间（通常记为q W ）。

顾客的平均逗留时间是指顾客进入系统到离开系统这段时间，包括等待时间和接受服务的时间。

顾客的平均等待时间是指顾客进入系统到接受服务这段时间。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
（4）服务强度ρ。每个服务台单位时间内平均服务 时间。
其中Ls、Lq、ws和wq通常称之为重要的运行指标 。它们取值越小，说明系统队长越短，顾客等候时 间越少，因此系统的性能就越好。
我们在稳态下，讨论单服务台排队系统和多服务台 排队系统。
9.2单服务台排队系统分析
本节讨论输入过程为泊松流，服务时间 服从负指数分布的单服务台的排队系统。 其中有：
9.1排队论的基本概念
排队论是通过对服务对象到来及服务时 间的统计研究，得出这些数量指标（等 待时间、排队长度、忙期长短等）的统 计规律，然后根据这些规律来改进服务 系统的结构或重新组织被服务对象，使 得服务系统既能满足服务对象的需要， 又能使服务机构的费用最经济或某些指 标最优。
9.1.1排队过程的一般表示
第9章 排队论
南京航空航天大学
排队是我们在日常生活中经常遇到的现象，例如 病人到医院看病、客户到银行汇款、城市拥堵 路段的汽车排队、电话占线等。排队现象产生 的原因之一是要求服务的数量超过了服务机构 的容量，也就是有部分的服务对象不能立即得 到服务；原因之二是系统服务对象到达和服务 时间均存在随机性。前者可以通过增加服务机 构的容量来解决排队现象，但无休止地增加服 务机构的容量会导致追加投资并可能发生系统 资源长时间闲置。后者，也就是系统服务对象 到达和服务时间均存在随机性，致使无法准确 预测估算排队拥堵的具体情况。所以，在服务 系统中的排队现象几乎不可避免。
标准的M/M/1/∞/∞系统； 有限等待空间系统M/M/1/N/∞； 顾客为有限源系统M/M/1/∞/m。
9.2.1 标准的M/M/1/∞/∞系统
M/M/1系统状态转移图:
系统状态从0转移到l的转移率为λP0， 而系统状态从1转移到0的转移率为μP1。
因此对状态0而言，必须满足以下平衡 方程：
对系统的任何状态n 1，系统状态从 n转移到n+1和n-1的转移率为 λPn+μPn，而系统状态从n+1和n-1 转移到n的转移率为μPn+1+λPn-1。
E
D2
L
…
Dn
L
单队列多服务台（并列）
D1
D’1 L
D2
D3
D’2 L
多服务台混合形式
服务台的服务时间一般也分成确定型和随机型 两种。例如，自动冲洗汽车的装置对每辆汽车 冲洗（服务）时间是相同的，因而是确定型的。 但大多数情况下服务时间是随机型的，对于随 机型的服务时间，我们需要知道服务时间V的概 率分布。如果服务时间V服从负指数分布，则其 分布函数是
常用于分析排队系统效率的有以下指标：
平均队长Ls和平均排队长Lq 平均逗留时间ws和平均等待时间wq 忙期和闲期 服务强度ρ
（1）平均队长Ls和平均排队长Lq。平均队 长Ls指一个排队系统的顾客平均数（其中包 括正在接受服务的顾客）。而平均排队长Lq 则是指系统中等待服务的顾客平均数；
如M/M/1/ ∞ / ∞ / FCFS:表示顾客到达的时间间 隔服从负指数分布、服务时间服从负指数分布
、单服务台、系统容量为无限、顾客源为无限
、排队规则为先来先服务的排队模型。我们这
一章的模型只讨论先到先服务的情形，因此后 面都略去第六项。
9.1.3排队系统的衡量指标
构建了排队系统的模型后，需要对排队系统 的运行效率和服务质量进行研究和评估，以确定 系统的结构是否合理。任何排队系统开始运行时， 其状态在很大程度上取决于系统的初始状态和运 转的时间。但系统运行了一段时间后，系统将进 入稳定状态（即稳态，系统运行充分长时间后， 初始状态的影响基本消失，系统状态不再随时间 变化）。对排队系统进行分析主要是指对其稳定 状态的运行效率指标进行分析。
式中μ为平均服务率，1/μ为平均服务时间。
9.1.2排队系统的分类
Kendall符号的形式X/Y/Z。各符号的含 义如下：
X指顾客相继到达间隔时间的分布 Y为服务时间的分布 Z为并列的服务台数目
表示相继到达的间隔时间和服务时间分布符号常用以下符 号表示
M：负指数分布，表示每个顾客接受服务的时间相互独立， 具有相同的负指数分布；
9.2.2有限等待空间系统M/M/1/N/∞
对M/M/1/N/∞来说，系统状态是有限
集合，即 :
M/M/1/N/∞排队系统的状态转移图如
下：
在稳态条件下，可得如下状态平衡方 程：
得
Pn
n
P0
， n 1,2,, N
由于 所以
由此可以计算系统的有关运行指标：
(1)平均队长Ls
当 N （ 1) 时
当等候空间有限、且ρ<1时，真正进入服务 系统的顾客平均输入率小于顾客平均到达 率λ的有效到达率为 。
由于系统容量为N，所以
故
1-P0 =
（2）平均排队长 （3）平均逗留时间 （4）平均等候时间
例.单人理发馆有4个椅子供人们排队等 待理发。当4个椅子都坐满时，后来的 顾客就自动离开。若顾客按泊松流到达 ，平均间隔时间20分钟，顾客理发时间 服从负指数分布，平均理发时间为15分 钟。试求任一顾客的平均等待时间等相 关参数。
排队系统示意图
一般的排队系统有三个基本组成 部分：
①输入过程
②排队及排队规则
③服务机构
① 输入过程
主要包括：
顾客相继到达系统的时间间隔 顾客到达系统的方式（顾客可能单个
到达，也可能成批到达） 顾客源情况
输入过程说明顾客按怎样的规律到达服务系统
的。它可用一定时间内顾客到达的数量或前后两 个顾客相继到达的间隔时间来描述。按照一定时 间内顾客到达数量或前后两个顾客相继到达的间 隔时间类型的不同，输入过程可以划分为确定型 和随机型两种：如在自动装配线上装配的各部件 就必须是按确定时间间隔到达装配点，定期的航 班、长途客车等都是确定型的；顾客到商店购买 商品、到医院就诊的病人等都是随机型的。在排 队论中，讨论的输入过程主要是随机型的。
由平衡条件可得：
令 可解得
Pn nP0 ， n 1,2,
在 ρ<1的条件下，标准M/M/l系统的重要运行指 标如下：
(1)在平衡条件 下系统中顾客数为n 的概率Pn
由于
，所以
故
Pn (1 ) n ， n 1,2,
(2)系统在平稳状态下的平均队长(包括等待
和接受服务的顾客数)Ls为：
或
(3)系统在平稳状态下平均排队长(系统排队
9.3多服务台排队系统分析
对于多服务台排队系统，本节假定：
（1）N个完全相同的服务台并联工作；
（2）只有一队顾客； （3）顾客随机到达；
（4）随机的服务时间长度； （5）服务规则为“先到先服务”； （6）系统可以达到稳定状态； （7）对于队列中的顾客数量没有限制； （8）对于接受服务的顾客数量没有限制； （9）所有到来的顾客都等待服务。
et
t 0
b(t)
0
t 0
负指数分布描述的随机现象对于过去的事件具有无记忆性， 即Markov性，因此用Markov开头字母M表示；
D：定长分布，表示每个顾客接受服务的时间是一个确定 的常数；
Ek：k阶爱尔朗分布〔Erlang)，表示每个 顾客接受服务的时间服从k阶爱尔朗分布，
其密度函数为
当k=1时爱尔朗分布就是负指数分布；当 k增加时，爱尔朗分布逐渐变为对称的。 当k>30时，爱尔朗分布近似于正态分布。
G：一般随机分布。
例如M/M/l表示到达的间隔时间服从负指数 分布，服务时间也服从负指数分布的单服务 台排队系统模型。M/D/2表示到达间隔时间 服从负指数分布，而服务时间为定长分布的 双服务台排队系统模型。
1971年有关排队论符号的标准化会议将 Kendall符号扩展为X/Y/Z/A/B/C，其中A指排 队系统的容量，取非负整数或∞；B表示顾客源 的数目，取非负整数或∞；C表示服务规则（先 来先服务FCFS、后来先服务LCFS，具有优先 权的服务PS，随机服务SIRO等）。
排队论的系统输入还要关注顾客源是有限集还是无 限集。如工厂内待修的机器数显然是有限集，而到某 航空售票处购票的顾客源则可以认为是无限的。
顾客的到达可以是相互独立的，也就是说，以前的 到达情况对以后顾客的到达没有影响，否则就是有关 联的。如工厂内的机器在一个短的时间区间内出现故 障（顾客到达）的概率就受已经待修或被修理机器数 目的影响。我们主要讨论的是相互独立的情形。
等待的顾客数) Lq为
平均排队人数等于系统的平均人数减去平均 的正在接受服务的人数：
或
设每个顾客在系统中平均逗留时间为Ws。顾 客在系统中逗留的时间T服从参数为μ-λ的负 指数分布，即顾客在系统中逗留时间超过t
的概率为:
P T t e()t ， t 0
因此顾客在系统中平均逗留时间为：
或
每个顾客在系统中平均等待时间为Wq，平均
（2）平均逗留时间ws和平均等待时间wq。 平均逗留时间ws指进入系统的顾客逗留时间 的平均值（包括接受服务的时间），而平均 等待时间wq则是指进入系统的顾客等待时 间的平均值；
（3）忙期和闲期。忙期是指服务机构两次空闲的 时间间隔，这是一个随机变量，是服务员最关心的 指标，因为它关系到服务员的服务强度；与忙期相 对的是闲期，它是服务机构连续保持空闲的时间。 在排队系统中，忙期和闲期总是交替出现的。
输入过程可以是平稳的，或称为对时间是齐次的， 是指描述相继到达的时间间隔分布和所含参数（如期 望、方差）都是与时间无关的，否则成为非平稳的。 我们主要讨论的是平稳的情形。
② 排队及排队规则
（1）排队
排队规则是指顾客来到排队系统后如何排队等候服务的 规则，一般有即时制、等待制和混合制三大类。其中即 时制(损失制)是指当顾客到达时，如果所有服务台都已 被占用，顾客可以随即离开系统。等待制指顾客到达系 统时，所有服务台被占用，顾客就加入排队队列等待服 务。而混合制是即时制和等待制相结合的一种排队服务 规则。混合制主要分为两种情况：一是队长有限制的情 况，即当顾客排队等侯服务的人数超过规定数量（等待 空间有限）时，后来的顾客就自动离开，另求服务；二 是排队等侯时间有限制的情况，即当顾客排队等候超过 一定时间就会自动离开，不能再等。