29
• • • •
• • •
•
M/M/C型系统和C个M/M/1型系统 系统容量有限制的多服务台模型(M/M/C/N/∞) 顾客源为有限的多服务台模型(M/M/C/∞/M) 一般服务时间的（M/G/1）模型 – Pollaczek-Khintchine(P-K) 公式 –定长服务时间 M/D/1模型 爱尔朗服务时间M/Ek/1模型 排队系统优化 M/M/1 模型中的最优服务率u – 标准的M/M/1Model – 系统容量为N的情形 M/M/C模型中最优服务台数C 30
一般的排队系统，都可由下 面图加以描述。 “聚”表示顾客的到达，“散”表示顾客的离去。
图8-6
随机服务系统
11
前 言
面对拥挤现象，人们总是希望尽量设法 减少排队，通常的做法是增加服务设施。 但是增加的数量越多，人力、物力的支 出就越大，甚至会出现空闲浪费。 如果服务设施太少，顾客排队等待的时 间就会很长，这样对顾客会带来不良影响。
6
前 言
上述各种问题虽互不相同，但却都有 要求得到某种服务的人或物和提供服务 的人或机构。
排队论里把要求服务的对象统称为“顾 客”, 提供服务的人或机构称为“服务台”或 “服务员”。
7
前 言
不同的顾客与服务组成了各式各样的 服务系统。顾客为了得到某种服务而到 达系统、若不能立即获得服务而又允许 排队等待，则加入等待队伍，待获得服 务后离开系统，见图8-1至图8-5。
1
第8章 排队论(Queuing Theory)
排队论（queuing),也称随机服务系统理论，是 运筹学的一个主要分支。 1909 年，丹麦哥本哈根电子公司电话工程师 A. K. Erlang的开创性论文“概率论和电话通讯理论” 标志此理论的诞生。排队论的发展最早是与电话， 通信中的问题相联系的，并到现在是排队论的传统 的应用领域。近年来在计算机通讯网络系统、交通 运输、医疗卫生系统、库存管理、作战指挥等各领 域中均得到应用。
(3) 混合制．这是等待制与损失制相结合的一 种服务规则，一般是指允许排队，但又不允许队 列无限长下去。具体说来，大致有三种： ① 队长有限。当排队等待服务顾客人数超过 规定数量时，后来顾客就自动离去，另求服务。 如水库的库容、旅馆的床位等都是有限的。
19
2. 排队规则
② 等待时间有限。即顾客在系统中的 等待时间不超过某一给定的长度 T，当等待 时间超过T时，顾客自动离去，不再回来。 如易损坏的电子元器件的库存问题， 超过一定存储时间被自动认为失效。 又如顾客到饭馆就餐，等了一定时间后 不愿再等而自动离去另找饭店用餐。
图8-1 单服务台排队系统
8
前 言Leabharlann 图8-2单队列——S个服务台并联的排队系统
图8-3
S个队列——S个服务台的并联排队系统
9
前 言
图8-4
单队——多个服务台的串联排队系统
图8-5
多队——多服务台混联网络系统
10
前 言
通常称由图8-6表示的系统为一随机聚散服务系统。 任一排队系统都是一个随机聚散服务系统。
20
2. 排队规则
③ 逗留时间 ( 等待时间与服务时间之和 ) 有限。 例如用高射炮射击敌机，当敌机飞越高射 炮射击有效区域的时间为 t 时，若在这个时 间内未被击落，也就不可能再被击落了。 不难注意到，损失制和等待制可看成是 混合制的特殊情形，如记c为系统中服务台 的个数，则当K=c 时，混合制即成为损失制； 当K=∞时，混合制即成为等待制。
14
1. 输入过程
输入即为顾客的到达，可有下列情况：
1）顾客源可能是有限的，也可能是无限的。 2）顾客是成批到达或是单个到达。 3）顾客到达间隔时间可能是随机的或确定的。 4）顾客到达可能是相互独立或关联的。所谓独 立就是以前顾客的到达对以后顾客的到达无影响。 5）输入过程可以是平稳的（stationary）或说 是对时间齐次的（Homogeneous in time），也可以 是非平稳的。输入过程平稳的指顾客相继到达的间 隔时间分布和参数（均值、方差）与时间无关；非 平稳的则是与时间相关，非平稳的处理比较困难。 15
16
2. 排队规则
(2) 等待制。指当顾客来到系统时，所有服务台 都不空，顾客加入排队行列等待服务。 例如，排队等待售票，故障设备等待维修等。 等待制中，服务台在选择顾客进行服务时，常有 如下四种规则：
①先到先服务（FCFS ）。按顾客到达的先后顺 序对顾客进行服务，这是最普遍的情形。
②后到先服务（ LCFS ）。仓库中迭放的钢材， 后迭放上去的都先被领走，就属于这种情况。
排队系统一般有三个基本组成部分：1.输 入过程；2.排队规则；3.服务机构。
¹ Ë ¿ Í Ô ´
¹ Ë ¿ Í µ ½ ´ ï
Å ¶ Ó ½ á ¹
Å ¶ Ó ¹ æ Ô ò
· þ Î ñ ¹ æ Ô ò
· þ Î ñ » ú ¹
À ë È ¥
Í ¼ 1 Å ¶ Ó Ï µ Í ³ Ê ¾ Ò â Í ¼
8-3 到达间隔时间分布和服务时间 的分布
一个排队系统的最主要特征参数是顾客 的到达间隔时间分布与服务时间分布。 要研究到达间隔时间分布与服务时间分 布需要首先根据现存系统原始资料统计 出它们的经验分布，然后与理论分布拟 合，若能照应，我们就可以得出上述的 分布情况。
31
一、经验分布
经验分布是对排队系统的某些时间参数根据 经验数据进行统计分析，并依据统计分析结果假 设其统计样本的总体分布，选择合适的检验方法 进行检验，当通过检验时，我们认为时间参数的 经验数据服从该假设分布。 分布的拟合检验一般采用χ2检验。由数理统 计的知识我们知：若样本量n充分大(n≥50)，则 当假设H0为真时，统计量总是近似地服从自由度 为k-r-1的χ2分布，其中k为分组数，r为检验分布 中被估计的参数个数。
• 顾客相继到达的间隔时间分布
• 服务时间的分布
• 服务台数
D.G.Kendall，1953提出了分类法，称为Kendall
记号(适用于并列服务台)即：[X/Y/Z]:[d/e/f]
23
式中：X——顾客相继到达间隔时间分布。 M—负指数分布Markov， D—确定型分布Deterministic， Ek—K阶爱尔朗分布Erlang， GI— 一般相互独立随机分布(General Independent)， G —一般随机分布。 Y——填写服务时间分布（与上同） Z——填写并列的服务台数 d——排队系统的最大容量 e——顾客源数量 f——排队规则 如 [M/M/1]:[∞/∞/FCFS]即为顾客到达为泊松过 程，服务时间为负指数分布，单台，无限容量，无 限源，先到先服务的排队系统模型。
2. 排队规则
这是指服务台从队列中选取顾客进行服务的顺序。 可以分为损失制、等待制、混合制3大类。 (1)损失制。这是指如果顾客到达排队系统时， 所有服务台都已被先来的顾客占用，那么他们就 自动离开系统永不再来。 典型例子是，如电话拔号后出现忙音，顾客 不愿等待而自动挂断电话，如要再打，就需重新 拔号，这种服务规则即为损失制。
4
前 言
除了上述有形的排队之外，还有大量 的所谓“无形”排队现象。 如几个顾客打电话到出租汽车站要求 派车，如果出租汽车站无足够车辆、则 部分顾客只得在各自的要车处等待，他 们分散在不同地方，却形成了一个无形 队列在等待派车。
5
前 言
排队的不一定是人，也可以是物： 例如，通讯卫星与地面若干待传递的 信息； 生产线上原料、半成品等待加工； 因故障停止运转的机器等待修理；码头 的船只等待装卸货物； 要降落的飞机因跑道不空而在空中盘 旋等等。
26
求解状态概率Pn(t)方法是建立含Pn(t)的微分差 分方程，通过求解微分差分方程得到系统瞬态解，由 于瞬态解一般求出确定值比较困难，即便求得一般也 很难使用。因此常常使用它的极限(如果存在的话)：
lim
t
p n (t ) p n
称为稳态(steady state)解，或称统计平衡状态 (Statistical Equilibrium State)的解。 稳态的物理意义图，系 pn 统的稳态一般很快都能 达到，但实际中达不到 稳态的现象也存在。要 注意的是求稳态概率Pn 并不一定求t→∞的极限, 稳定状态 过渡状态 只需求Pn’(t)=0 。 27
12
前 言
顾客排队时间的长短与服务设施规模的 大小，就构成了设计随机服务系统中的一对
矛盾。
如何做到既保证一定的服务质量指标，
又使服务设施费用经济合理，恰当地解决顾
客排队时间与服务设施费用大小这对矛盾。
这就是随机服务系统理论——排队论所
要研究解决的问题。
13
§8-2 排队系统的基本概念
一、排队系统的组成与特征
17
2. 排队规则
③随机服务（RAND） 。即当服务台空 闲时，不按照排队序列而随意指定某个顾客 去接受服务，如电话交换台接通呼叫电话就 是一例。 ④优先权服务（PR）。如老人、儿童先 进车站；危重病员先就诊；遇到重要数据需 要处理计算机立即中断其他数据的处理等， 均属于此种服务规则。
18
2. 排队规则
2
8 排队论
• • • • • • • 8-1 前言 8-2 基 本 概 念 8-3 输入过程和服务时间分布 8-4 泊松输入—指数服务排队模型 8-5 M/M/1 无限源系统 8-6 系统容量有限的排队系统 8-7 顾客源有限的排队系统
3
前 言
排队是我们在日常生活和生产中经 常遇到的现象。 例如，上、下班搭乘公共汽车； 顾客到商店购买物品； 病员到医院看病； 旅客到售票处购买车票； 学生去食堂就餐等就常常出现排队和等待 现象。
25
排队问题求解(主要指性态问题)
求解一般排队系统问题的目的主要是通过研究 排队系统运行的效率指标，估计服务质量，确定系 统的合理结构和系统参数的合理值，以便实现对现 有系统合理改进和对新建系统的最优设计等。 排队问题的一般步骤： 1. 确定或拟合排队系统顾客到达的时间间隔分 布和服务时间分布(可实测)。 2. 研究分析排队系统理论分布的概率特征。 3. 研究系统状态的概率。系统状态是指系统中 顾客数。状态概率用Pn(t)表示,即在t时刻系统中有 n个顾客的概率，也称瞬态概率。