第8章排队论

数的期望值；
Lq——平均队长，稳态系统任一时刻等待服务的
顾客数期望值；
四项主要性能指标(Ws ,Wq ,Ls, Lq)的值越小，说明系
统排队越少，等待时间越少，因而系统性能越好。
显然，它们是顾客与服务系统的管理者都很关注的。
运筹与优化
设 —— 单位时间内顾客的平均到达数； 1/ —— 相邻两个顾客到达的平均间隔时间。
运筹与优化 2.2 服务规则。这是指服务台从队列中选取顾客进行服务 的顺序。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。如果顾客到达排队系统时，所有服务台都已 被占用，那么他们就自动离开系统永不再来。 (2)等待制。当顾客来到系统时，所有服务台都不空，顾 客加入排队行列等待服务。等待制中，服务台在选择顾 客进行服务时，常有如下四种规则： ①先到先服务（FCFS）。按顾客到达的先后顺序对顾客 进行服务，这是最普遍的情形。 ②后到先服务。仓库中迭放的钢材，后迭放上去的都先 被领走，就属于这种情况。
(2) 有提供服务的人或机构。把提供服务的人或机构称为 “服务台”或“服务员”
(3) 顾客的到达、服务的时间至少有一个是随机的，服从 某种分布。
运筹与优化
不同的顾客与服务组成了各式各样的服务系统。顾客为了 得到某种服务而到达系统、若不能立即获得服务而又允许排队 等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。
G——表示一般相互独立的随机分布。
运筹与优化 B—表示服务时间分布：所用符号与表示顾客到达间隔时间 分布相同。 M——表示服务过程为泊松过程或负指数分布； D——表示定长分布； Ek ——表示k阶爱尔朗分布；
G——表示一般相互独立的随机分布。
C—表示服务台(员)个数：
“1”则表示单个服务台，“s”(s＞1)表示多个服务台。
段时间以后，系统的状态将独立于初始状态和经历的时间，这 时称系统处于稳定状态。
由于对系统的瞬时状态研究分析起来很困难，所以排队论
中主要研究系统处于稳定状态的工作情况。由于稳定状态与时 间无关，因此Pn(t)可写为Pn， N(t)可写为N
运筹与优化
三、衡量排队系统工作状况的主要指标
(1)W或Ws—— 平均逗留时间，在任意时刻进入稳态
运筹与优化 例如：某排队问题为 M／M／S／∞／∞／FCFS 则表示顾客到达间隔时间为负指数分布(泊松流)；服务 时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量 无限(等待制)；顾客源无限，采用先到先服务规则。 某些情况下，排队问题仅用上述表达形式中的前3个、4 个、5个符号。如不特别说明则均理解为系统等待空间容量 无限；顾客源无限，先到先服务，单个服务的等待制系统。 如上述例子可简记为M／M／S
替λn ；
运筹与优化
(7) μn——当系统中有n个顾客数，整个系统的平均服务率（单
位时间内服务完毕离去的顾客数），当n≥1， μn是常数时，可 用μ代替μn ； (8) S——排队系统中并联的服务台数； (9) 稳定状态——当一个排队系统开始运转时，系统的状态很
大程度上取决于系统的初始状态和运转经历的时间，但过了一
运筹与优化
一、排队系统的描述
（一）系统特征和基本排队过程 任何一个排队问题的基本排队过程都可以用图6表示。从 图6可知，每个顾客由顾客源按一定方式到达服务系统，首先 加入队列排队等待接受服务，然后服务台按一定规则从队列 中选择顾客进行服务，获得服务的顾客立即离开。 （二）排队系统的基本组成部分 通常，排队系统都有输入过程、服务规则和服务台等3个 组成部分： 2.1 输入过程．这是指要求服务的顾客是按怎样的规律到达排 队系统的过程，有时也把它称为顾客流．一般可以从3个方面 来描述—个输入过程。
图1 单服务台排队系统
图2 单队列——S个服务台并联的排队系统
运筹与优化
图3 S个队列——S个服务台的并联排队系统
图4 单队——多个服务台网络系统
一般的排队系统，都可由下面图6加以描述。
图6 随机服务系统
运筹与优化 • 面对拥挤现象，顾客排队时间的长短与服务设施规模的大小， 就构成了设计随机服务系统中的一对矛盾。 • 如何做到既保证一定的服务质量指标，又使服务设施费用经 济合理，恰当地解决顾客排队时间与服务设施费用大小这对 矛盾，这就是排队论所要研究解决的问题之一。 排队论是1909年由丹麦电话工程师爱尔朗(A. K. Erlang)在 研究电话系统时创立的，几十年来排队论的应用领域越来越广 泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计 算机的飞速发展，更为排队论的应用开拓了宽阔的前景。
运筹与优化 D—表示系统中顾客容量限额，或称等待空间容量： 如系统有K个等待位子，则 0<K<∞，当 K=s 时，说明系统不 允许等待，即为损失制。K=∞ 时为等待制系统，此时∞一般 省略不写。K为有限整数时，表示为混合制系统。 E—表示顾客源限额：分有限与无限两种，∞表示顾客源无 限，此时一般∞也可省略不写。 F—表示服务规则：常用下列符号： FCFS：表示先到先服务； LCFS：表示后到先服务； PR：表示优先权服务。
运筹与优化
二、排队系统的名词、概念及符号
(1) 系统状态——指一个排队服务系统中的顾客数 (排队等待的 顾客数与正在接受服务的顾客数之和)； (2) 队长——是指系统中正在排队等待服务的顾客数； (3) N(t)——在时刻t系统中的顾客数，即系统在时刻t的瞬时状
态；
(4) Nq(t)——时刻t系统中排队的顾客数，即队长； (5) Pn(t)——在时刻t系统中恰好有n个顾客的概率； (6) λn ——当系统中有n个顾客时，信赖顾客的平均到达率（单 位时间内到达的顾客数），当对所有n值λn为常数时，可用λ代
运筹与优化
（三）排队系统的描述符号与分类
为了区别各种排队系统，根据输入过程、排队规则和服 务机制的变化对排队模型进行描述或分类，D.G.Kendall提 出了一种目前在排队论中被广泛采用的“Kendall记号”， 完整的表达方式通常用到6个符号并取如下固定格式： A/B/C/D/E/F 各符号的意义为： A—表示顾客相继到达间隔时间分布，常用下列符号： M——表示到达过程为泊松过程或负指数分布； D——表示定长输入； Ek——表示k阶爱尔朗分布；
运筹与优化
(1)、顾客总体数(又称顾客源、输入源)。这是指顾客的来源。 顾客源可以是有限的，也可以是无限的。例如，到售票处 购票的顾客总数可以认为是无限的，而某个工厂因故障待 修的机床则是有限的。
(2)、顾客到达方式。描述顾客是怎样来到系统的，他们是单 个到达，还是成批到达。病人到医院看病是顾客单个到达 的例子。在库存问题中如将生产器材进货或产品入库看作 是顾客，那么这种顾客则是成批到达的。 (3)、顾客流的概率分布，或称相继顾客到达的时间间隔的分 布。这是求解排队系统有关运行指标问题时，首先需要确 定的指标。这也可以理解为在一定的时间间隔内到达K个顾 客(K=1、2、)的概率是多大。顾客流的概率分布一般有 定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等若 干种。
运筹与优化
• • • • • •
通讯卫星与地面若干待传递的信息； 生产线上的原料、半成品等待加工； 因故障停止运转的机器等待工人修理； 码头的船只等待装卸货物； 要降落的飞机因跑道不空而在空中盘旋等等。 排队的不一定是人，也可以是物：
排队问题的共同特征 (1) 有要求得到某种服务的人或物。排队论里把要求服务 的对象统称为“顾客”
——单位时间内被服务完毕离去的平均顾客数； 1/ —— 对每个顾客的平均服务时间。
Little 公式：
LS WS
WS
LS

Lq Wq
1
Wq
Lq

又
WS Wq

LS Lq
运筹与优化 又由于
Ls npn
n 0

Lq
n s 1
(n s ) p
vk (t ) e t
当k=0时，有
( t ) k (k 0,1, 2,...) k!
v0 (t ) et
在什么情况下顾客的到达时最简单流的情况呢？它需要满足下面 三个条件：
运筹与优化 (1) 平稳性：指在长度为t的时段内恰好到达k个顾客的概率 仅与时段长度有关，而与时段起点无关。即对任意∈(0,∞)，在 (,+t]或(0,t)内恰好到达k个顾客的概率相等. (2) 无后效性：指在任意几个不相交的时间区间内，各自到 达的顾客数是相互独立的。通俗地说就是以前到达的顾客情况， 对以后顾客的到来没有影响。否则就是关联的。 (3) 普通性：指在充分小的时段内最多到达一个顾客。 因为泊松流实际应用最广，也最容易处理，因而研究得也较多．
运筹与优化 ③随机服务。即当服务台空闲时，不按照排队序列而随意指 定某个顾客去接受服务，如电话交换台接通呼叫电话就是一 例。 ④优先权服务。如老人、儿童先进车站；危重病员先就诊； 遇到重要数据需要处理计算机立即中断其他数据的处理等， 均属于此种服务规则。 (3)混合制．等待制与损失制相结合的一种服务规则，一般 是指允许排队，但又不允许队列无限长下去。具体说来，大致 有三种： ① 队长有限。当排队等待服务的顾客人数超过规定数量时， 后来的顾客就自动离去，另求服务，即系统的等待空间是有限 的。

n
为什么会有这两个式子？怎么出来的？
平均顾客数和平均队长都是期望值（参考前面定义）
因此只要求得pn即可得Ls, Lq及Ws 和Wq
pn的值当n=0时即为 p0（服务系统空闲的概率），
当s=1时，1- p0就是服务系统的工作强度
运筹与优化
第二节 输入与服务时间的分布
一、最简单流的定义
所谓最简单流。是指在t这段时间内有k个顾客来到服务系 统的概率vk(t)服从泊松分布，即：
运筹与优化
② 等待时间有限。顾客在系统中的等待时间不超过某一 给定的长度T，当等待时间超过T时，顾客将自动离去，并不 再回来。如易损坏的电子元器件的库存问题，超过一定存储 时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了 一定时间后不愿再等而自动离去另找饭店用餐。