运筹学第10章 排队论

等。等待费用是指由于有顾客等待因而对顾客和服务系统带来的费用，包
括顾客等待过程中的损失、系统损失顾客的机会成本以及不得不增加的其 它费用，如车站购票处治安警察的工资和装备费等。
图10.1
二、 排队系统的一般特征
7
（一）总是先有输入过程
输入，即顾客到达排队系统的过程。主要有以下几种情况：
• 顾客总体（即顾客源）：可以是有限的，也可以是无限的。
统的最优设计和最优控制，以最少的费用实现系统的最大效益，使得服务 系统既能在一定程度上满足顾客的需要，又能使得所需总费用为最小（如 图10.1所示）。
在这里，服务水平是一个综合概念，包括较少的排队时间、较高的服 务速度和质量等等。服务费用是指为了达到相应的服务水平所需要付出的
费用，包括增加服务台、提高服务速度和改善管理的费用及服务设施折旧
Ｌ＝Ｌq＋ｓ
（假定服务强度为１）
2. 逗留时间和等待时间：顾客在系统中停留的时间包括等待时间和服
务时间称作逗留时间，其期望值记作ｗ；其排队等待的时间称作等待时间，期
望值记作ｗq。用λ和μ分别表示单位时间到达的顾客数和服务台平均完成服务的
顾客数，则有： Ｌ＝λｗ 或 ｗ＝Ｌ／λ
①
Ｌq＝λｗq 或 ｗq ＝Ｌq／λ
到达的时间间隔相互独立性的检验；服务时间的分布及有关参数的确定等。这 常常需要借助于一些经验分布。
(二)排队系统中的数量指标及其概率规律 即系统的整体性质。
排队论所关心的主要数量指标包括：
1. 系统状态Ｎ(t)：即一个排队系统中的顾客数，包括排队等待的和正在
接受服务的顾客数，在平稳状态下可记作Ｎ（平稳状态与时间无关）。如果记 系统中顾客数为Ｎ的期望值为Ｌ，排队等待者的期望值为Ｌq，服务台数为ｓ （并联串联均可），则有：
（三）少不了服务台
• 服务台是服务设施和服务人员的总称，没有服务台，就没有排队问题。
• 服务台可以是一个，也可以是多个。在多个服务台情况下，它们可以是 串联的，也可以是并联的，还可以是混合式的。
• 服务方式可以是单个进行的，也可以是成批进行的。
• 服务时间的分布可以是确定的，也可以是随机的。如自助洗衣店中全自 动洗衣机的服务就是定长的。在大多数服务系统中，服务时间都是随机的。
5. 顾客损失率：即由于服务能力不足损失的顾客数与最大服务能
力（顾客数）的比率。
η= 损失的顾客数/最大服务能力（顾客数）
探讨排队系统中的数量指标及其概率规律是本章的主要内容。
(三)系统优化问题 又称作系统控制问题或系统运营问题。其基本 6
目的是使系统处于最优或最合理状态。 排队论研究的目的，就是要通过对排队系统中概率规律的研究达到系
4. 系统服务强度: 服务强度即 ρ＝λ／ μ，这是系统的平均服
务强度。服务强度反映服务效率和服务设施及人员的利用情况，是排队论 中一个很重要的数量指标。当系统中有ｎ个顾客时（即系统处于状态ｎ 时），服务强度为ρn＝λn／ μn。服务强度有时也用忙期表示。当ｎ>s时， μn＝ｓ μ 。这时有： ρ＝λ／ (ｓμ)，亦即 λ／ μ ＝ｓρ 。这就证明了当ρ ＝1 时，Ｌ＝Ｌq＋ｓ与Ｌ＝Ｌq＋λ／μ的等价性。
先到先服务（ＦＣＦＳ），这是最普遍的情形。
后到先服务（ＬＣＦＳ），如搭电梯时先上的后下。
依优先权服务（ＰＳ），如急诊者优先、军烈属优先等。
8
随机服务（ＲＳ），如电话交换系统中的服务。
• 从队列所占的空间看，有具体的也有抽象的；有有限排队也有无限排队。
• 从队列的数目看，可以是单列的也可以是多列的。在多列的情况下，有 时各列可能会互相转移，也可能会中途退出。排队轮中一般假定，各列间不 能互相转移，也不能中途退出。
硕士生学位课《运筹学II》第四讲
第10章 排队论
§10.1 排队论概述 §10.2 Ｍ／Ｍ／1模型 §10.3 Ｍ／Ｍ／Ｓ模型
特别提示： 学习本章内容随机过程理论尤其是生灭过
程理论是一个重要的理论基础。
1
2
§10.1 排队论概述
本节内容提要：
10.1.1 排队论及排队系统 一、排队现象与排队论 二、排队系统的一般特征 三、表示排队系统的通用符号 10.1.2 排队系统中随机变量的有关分布 一、经验分布 二、泊松分布（Poisson） 三、负指数分布 四、爱尔朗分布 10.1.3 生灭过程与平稳状态分布
• 顾客到达的方式：可以是单个的，也可以是成批的。
• 顾客相继到达的时间间隔：可以是确定的，也可以是随机的。确定型的
也称作定长分布，如自动装配线上待装配的零部件，进入车站的火车等。 排队轮讨论的主要对象是随机型输入。
（二）有一定的排队规则
• 顾客到达系统后，如服务台占用，可能会离去，也可能排队等候。前者 称即时制，后者称等待制。在等待制条件下，服务规则可以有：
②
ｗ＝ｗq＋１／μ
③
将①、 ②代如③，即得到：
5
Ｌ＝Ｌq＋λ／μ
（其中λ／μ 称作服务强度）
3. 系统状态概率: 系统处于状态ｎ时的概率一般用Ｐn（ｔ）表示，
当系统处于平稳状态时，Ｐn（ｔ）可简写为Ｐn，表示系统中有ｎ个顾客 的概率，于是按照Ｌ和Ｌq的定s) pn n s 1
排队论（Queuing Theory），即研究排队系统的专门数学方法，是运筹
学的一个重要分支。由于在排队系统中顾客的到达常常总是随机的，所以 排队系统一般又称随机服务系统，相应的把排队论又称作随机服务理论。
排队论的研究内容主要包括三个方面：
3
(一)统计推断问题 如关于系统是否达到平稳状态的检验；顾客相继 4
§10.1 排队论概述
10.1.1 排队论及排队系统
一、排队现象与排队论
排队现象在现实中是普遍存在的，在校园里打饭要排队，看病要排队， 理发要排队，办理储蓄也要排队。排队现象也称作拥挤现象。
排队现象面临的共同问题是：增加服务设施，无疑可以减少排队时间， 消除拥挤现象，但如果生意清淡，则会导致设备闲置，造成设备投资浪费。 而如果减少服务设施，则在遇到生意兴隆的情况下常常造成排队和拥挤， 或者顾客会自动离去，使系统丧失服务机会，也会影响到经济效益的提高。 所以，如何在这两者之间保持平衡，使得既不出现拥挤排队，又不致发生 设备闲置和浪费，从而达到既提高服务质量，又降低服务成本的目的，就 构成了排队论研究的对象。