第十章 排队论(Queuing Theory)
1
第十章 排队论(Queuing Theory)
排队论（queuing),也称随机服务系统理论，是 运筹学的一个主要分支。
1909年，丹麦哥本哈根电子公司电话工程师A. K. Erlang的开创性论文“概率论和电话通讯理论” 标志此理论的诞生。排队论的发展最早是与电话， 通信中的问题相联系的，并到现在是排队论的传统 的应用领域。近年来在计算机通讯网络系统、交通 运输、医疗卫生系统、库存管理、作战指挥等各领 域中均得到应用。
为稳态(steady state)解，或称统计平衡状态 (Statistical Equilibrium State)的解。
lim
t
p n
(t )
pn
15
稳态的物理意义见右图， pn 系统的稳态一般很快都 能达到，但实际中达不 到稳态的现象也存在。
过渡状态
稳Байду номын сангаас状态
t
图3 排队系统状态变化示意图
16
8
§1.2 排队系统的模型分类
上述特征中最主要的、影响最大的是： • 顾客相继到达的间隔时间分布 • 服务时间的分布 • 服务台数
D.G.Kendall，1953提出了分类法，称为Kendall 记号(适用于并列服务台)即：[X/Y/Z]:[A/B/C]
9
[X/Y/Z]:[A/B/C]式中：
X——顾客相继到达间隔时间分布。
如 ： [M/M/1]:[∞/∞/FCFS] 即 为 顾 客 到 达 为 泊 松 过程，服务时间为负指数分布，单台，无限容量， 无限源，先到先服务的排队系统模型。
10
系统指标 (1) 队长，指在系统中的顾客数，它的期望值记Ls； (2) 排队长，指在系统中排队等待服务的顾客数，它的 期望值记作Lq
M—负指数分布Markov，D—确定型分布Deterministic， Ek—K阶爱尔朗分布 Erlang， GI— 一般相互独立随机分布(General Independent)， G —一般随机分布。
Y——服务时间分布 Z——并列的服务台数 A——排队系统的最大容量 B——顾客源数量 C——排队规则
17
• M/M/C型系统和C个M/M/1型系统
• 系统容量有限制的多服务台模型(M/M/C/N/∞)
5
2. 排队规则
1）损失制。顾客到达时，如果所有的服务台都被 占用，且服务机构又不允许顾客等待，顾客只能离 去，这种服务规则就是损失制。 2）等待制。当顾客到达时，如果所有服务台都被顾 客占用而无空闲，这时该顾客自动加入队列排队等 待服务，服务完才离开。 （1）先到先服务FCFS （2）后到先服务 LCFS （3）随机服务RAND （4）有优先权服务 PR。
3.最优化问题：即包括最优设计(静态优化)， 最优运营（动态优化）。
13
1.4 排队问题求解(主要指性态问题)
求解一般排队系统问题的目的主要是通 过研究排队系统运行的效率指标，估计服务 质量，确定系统的合理结构和系统参数的合 理值，以便实现对现有系统合理改进和对新 建系统的最优设计等。
14
1.4 排队问题求解(主要指性态问题)
2
§1 排队论的基本概念
§1.1 排队系统的组成与特征
排队系统一般有三个基本组成部分： 1.输入过程； 2.排队规则； 3.服务机构。
顾客源
顾客到达 排队结构 服务规则 服务机构
离去
排队规则
图1 排队系统示意图
3
1. 输入过程
输入即为顾客的到达，可有下列3种情况： 1）顾客来源。顾客总体(称为顾客源)的组成可能是有 限的，也可能是无限的。
12
1.3 排队论研究的基本问题
1.排队系统的统计推断:即通过对排队系统主 要参数的统计推断和对排队系统的结构分析，判 断一个给定的排队系统符合于哪种模型，以便根 据排队理论进行研究。
2.系统性态问题:即研究各种排队系统的概率 规律性，主要研究队长分布、等待时间分布和忙 期分布等统计指标,包括了瞬态和稳态两种情形。
6
3. 服务机构
1）服务机构可以是单服务员和多服务员服务， 这种服务形式与队列规则联合后形成了多种不同队 列，不同形式的排队服务机构，如：
1 单队单服务台
1
2
..
..
n
多队多服务台（并列)
1
2 。。。
n
单队多服务台（并列）
1
2
... n
单队多服务台（串列）
1
1
2
3
2
混合形式
7
2)服务方式分为单个顾客服务和成批顾客服务。 3)服务时间分为确定型和随机型。 4)服务时间的分布在这里我们假定是平稳的。
如：上游河水流入水库可以认为总体是无限的，工 厂内停机待修的机器显然是有限的总体。 2）顾客到达方式。顾客到来的方式可能是一个一个 的，也可能是成批的。 如：到餐厅就餐就有单个到来的顾客和受邀请来参 加宴会的成批顾客。
4
3）顾客流的概率分布。顾客随机一个(批)个(批)来 到排队系统，顾客流的概率分布用来描述相继到达的 顾客之间的间隔时间分布是确定的还是随机的，分布 参数是什么，到达的间隔时间是否独立，分布是随时 间变化的还是平稳的。
§2 排队论主要知识点
• 排队系统的组成与特征 • 排队系统的模型分类 • 顾客到达间隔时间和服务时间的经验分布与
理论分布 • 稳态概率Pn的计算 • 标准的M/M/1模型([M/M/1]:[∞/∞/FCFS]) • 系统容量有限制的模型[M/M/1]:[N/∞/FCFS] • 顾客源有限模型[M/M/1][∞/M/ FCFS] • 标准的[M/M/C]模型[M/M/C]:[∞/∞/FCFS]
排队问题的一般步骤： 1. 确定或拟合排队系统顾客到达的时间
间隔分布和服务时间分布。 2. 研究系统状态的概率。系统状态是指
系统中顾客数。状态概率用Pn(t)表示,即在t 时刻系统中有n个顾客的概率，也称瞬态概率。
求解状态概率Pn(t)方法是建立含Pn(t)的微分差分方程，
通过求解微分差分方程得到系统瞬态解，常常使用它的极限称
系统 中顾 客数
=
在队列中等 待服务的顾
客数
+
正被服 务的顾
客数
一般情形，Ls(或Lq)越大，说明服务效率越低。
11
(3) 逗留时间，指一个顾客在系统中的停留时 间，它的期望值记作Ws； (4) 等待时间，指一个顾客在系统中排队等待的 时间，它的期望值记作Wq；
逗留时间 = 等待时间 + 服务时间