排队论 本章内容重点 基本概念 输入过程和服务时间分布 泊松输入——指数服务排队模型 其他模型选介 排队系统的优化目标与最优化问题.

Presentation on theme: "排队论 本章内容重点 基本概念 输入过程和服务时间分布 泊松输入——指数服务排队模型 其他模型选介 排队系统的优化目标与最优化问题."— Presentation transcript:

1 排队论 本章内容重点 基本概念 输入过程和服务时间分布 泊松输入——指数服务排队模型 其他模型选介 排队系统的优化目标与最优化问题

2 排队论 排队论(Queuing Theory)，又称随机服务系统理论(Random Service System Theory)，是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。排队问题的共同特征: 有要求得到某种服务的人或物。排队论里把要求服务的对象统称为“顾客” 有提供服务的人或机构。把提供服务的人或机构称为“服务台”或“服务员” 顾客的到达、服务的时间至少有一个是随机的，服从某种分布。

3 排队论 不同的顾客与服务组成了各式各样的服务系统。顾客为了得到某种服务而到达系统、若不能立即获得服务而又允许排队等待，则加入等待队伍，待获得服务后离开系统，见图1至图5。 图1 单服务台排队系统 图2 单队列——S个服务台并联的排队系统

4 排队论 图3 S个队列——S个服务台的并联排队系统 图4 单队——多个服务台的串联排队系统 图5 多队——多服务台混联、网络系统

5 排队论 面对拥挤现象，顾客排队时间的长短与服务设施规模的大小，就构成了设计随机服务系统中的一对矛盾。
如何做到既保证一定的服务质量指标，又使服务设施费用经济合理，恰当地解决顾客排队时间与服务设施费用大小这对矛盾，这就是排队论所要研究解决的问题之一。 排队论是1909年由丹麦工程师爱尔朗(A.K.Erlang)在研究电活系统时创立的，几十年来排队论的应用领域越来越广泛，理论也日渐完善。特别是自二十世纪60年代以来，由于计算机的飞速发展，更为排队论的应用开拓了宽阔的前景。

6 排队系统的描述 一、系统特征和基本排队过程
任何一个排队问题的基本排队过程都可以用图6表示。从图6可知，每个顾客由顾客源按一定方式到达服务系统，首先加入队列排队等待接受服务，然后服务台按一定规则从队列中选择顾客进行服务，获得服务的顾客立即离开。 图6 随机服务系统

7 排队系统的描述 二、排队系统的基本组成部分
1.输入过程:这是指要求服务的顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流．一般可以从3个方面来描述一个输入过程。 (1) 顾客总体数(又称顾客源、输入源)。这是指顾客的来源。顾客源可以是有限的，也可以是无限的。 (2)顾客到达方式。描述顾客是怎样来到系统的，他们是单个到达，还是成批到达。 (3)顾客流的概率分布，或称相继顾客到达时间间隔的分布。这是求解排队系统有关运行指标问题时，首先需要确定的指标。也可以理解为在一定的时间间隔内到达K个顾客(K=1、2、…)的概率是多大。顾客流的概率分布一般有定长分布、二项分布、泊松流(最简单流)、爱尔朗分布等。

8 排队系统的描述 二、排队系统的基本组成部分
2.服务规则。这是指服务台从队列中选取顾客进行服务的顺序。一般可以分为损失制、等待制和混合制等3大类。 (1)损失制。如果顾客到达排队系统时，所有服务台都已被占用，那么他们就自动离开系统永不再来。 (2)等待制。当顾客来到系统时，所有服务台都不空，顾客加入排队行列等待服务。等待制中，服务台在选择顾客进行服务时，常有如下四种规则： 1)先到先服务。按顾客到达的先后顺序对顾客进行服务，这是最普遍的情形。 2)后到先服务。仓库中迭放的钢材，后迭放上去的都先被领走，就属于这种情况。

9 排队系统的描述 3)随机服务。即当服务台空闲时，不按照排队序列而随意指定某个顾客去接受服务，如电话交换台接通呼叫电话就是一例。
4)优先权服务。如老人、儿童先进车站；危重病员先就诊；遇到重要数据需要处理计算机立即中断其他数据的处理等，均属于此种服务规则。 (3)混合制。等待制与损失制相结合的一种服务规则，一般是指允许排队，但又不允许队列无限长下去。具体说来，大致有三种： 1)队长有限。当排队等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。

10 排队系统的描述 2)等待时间有限。顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离去，并不再回来。如易损坏的电子元器件的库存问题，超过一定存储时间的元器件被自动认为失效。又如顾客到饭馆就餐，等了一定时间后不愿再等而自动离去另找饭店。 3) 逗留时间有限。例如用高射炮射击敌机，当敌机飞越高射炮射击有效区域的时间为t时，若在这个时间内未被击落，也就不可能再被击落了。 损失制和等待制可看成是混合制的特殊情形，如记s为系统中服务台的个数，系统的容量为K，则当K=s时，混合制即成为损失制；当K=∞时，混合制即成为等待制。

11 排队系统的描述 二、排队系统的基本组成部分 3.服务台情况。服务台可以从以下3方面来描述： (1) 服务台数量及构成形式
(2)服务方式。这是指在某一时刻接受服务的顾客数，它有单个服务和成批服务两种。 (3)服务时间的分布。在多数情况下，对每一个顾客的服务时间是一随机变量，其概率分布有定长分布、负指数分布、K级爱尔朗分布、一般分布(所有顾客的服务时间都是独立同分布的)等等。

12 排队系统的描述 三、排队系统的描述符号与分类
为了区别各种排队系统，根据输入过程、排队规则和服务机制的变化对排队模型进行描述或分类，D.G.Kendall提出了一种目前在排队论中被广泛采用的“Kendall记号”，完整的表达方式通常用到6个符号并取如下固定格式： A/B/C/D/E/F 各符号的意义为： A—表示顾客相继到达间隔时间分布，常用下列符号： M—表示到达过程为泊松过程或负指数分布； D—表示定长输入； Ek—表示k阶爱尔朗分布； G —表示一般相互独立的随机分布。

13 排队系统的描述 B—表示服务时间的分布 C—表示服务台(员)个数： “1”则表示单个服务台，“s”(s＞1)表示多个服务台。
D—表示系统中顾客容量限额，或称等待空间容量；如系统有K个等待位子，则 0<K<∞，当 K=s 时，说明系统不允许等待，即为损失制。K=∞ 时为等待制系统，此时∞一般省略不写。K为有限整数时，表示为混合制系统。 E—表示顾客源限额，分有限与无限两种，∞表示顾客源无限，此时一般∞也可省略不写。 F—表示服务规则，常用下列符号： FCFS：表示先到先服务； LCFS：表示后到先服务； PR：表示优先权服务。

14 排队系统的描述 例如：某排队问题为 M／M／S／∞／∞／FCFS
则表示顾客到达间隔时间为负指数分布(泊松流)；服务时间为负指数分布；有s(s＞1)个服务台；系统等待空间容量无限(等待制)；顾客源无限，采用先到先服务规则。 可简记为： M/M/s 某些情况下，排队问题仅用上述表达形式中的前3个、4个、5个符号。如不特别说明则3个符号表示的排队系统理解为系统等待空间容量无限；顾客源无限，先到先服务，单个服务的等待制系统。

15 排队系统的主要数量指标 1.队长和排队长(队列长)
队长是指系统中的顾客数(排队等待的顾客数与正在接受服务的顾客数之和)，排队长是指系统中正在排队等待服务的顾客数。 2.等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待时间，是随机变量。 从顾客到达时刻起到他接受服务完成止这段时间称为逗留时间，也是随机变量。 3.忙期和闲期 忙期是指从顾客到达空闲着的服务机构起，到服务机构再次成为空闲止的这段时间，即服务机构连续忙的时间。这是个随机变量，它关系到服务员的服务强度。 与忙期相对的是闲期，即服务机构连续保持空闲的时间。在排队系统中，忙期和闲期总是交替出现的。

16 排队系统的主要数量指标 N(t)：时刻t系统中的顾客数(又称为系统的状态)，即队长； Nq(t)：时刻t系统中排队的顾客数，即排队长；
T(t)：时刻t到达系统的顾客在系统中的逗留时间； Tq(t)：时刻t到达系统的顾客在系统中的等待时间。 上面数量指标一般都是和系统运行的时间有关的随机变量，求它们的瞬时分布一般很困难。注意到相当一部分排队系统在运行了一定时间后，都会趋于一个平衡状态(或称平稳状态)。 在平衡状态下，这些量与系统所处的时刻无关，而且系统的初始状态的影响也会消失。因此，我们在本章中将主要讨论与系统所处时刻无关的性质，即统计平衡性质。

17 排队系统的主要数量指标 L或Ls—— 平均队长，稳态系统任一时刻的顾客数的期望值
Lq—— 平均等待队长或队列长，稳态系统任一时刻等待服务的顾客数期望值 W或Ws—— 平均逗留时间，在任意时刻进入稳态系统的顾客逗留时间期望值 Wq—— 平均等待时间，在任意时刻进入稳态系统的顾客等待时间期望值。 这四项主要性能指标(又称主要工作指标)的值越小，说明系统排队越少，等待时间越少，因而系统性能越好。显然，它们是顾客与服务系统的管理者都很关注的

18 其它常用数量指标 s —— 系统中并联服务台的数目；  —— 平均到达率； 1/ —— 平均到达间隔。  —— 平均服务率；
1/ —— 平均服务时间。  —— 服务强度，即每个服务台单位时间内的平均服务时间； 一般有      s  ； N —— 稳态系统任一时刻的状态(即系统中的顾客数)； U —— 顾客在稳态系统中的逗留时间； Q —— 顾客在稳态系统中的等待时间。 Pn=P{N=n}：稳态系统任一时刻状态为n的概率；特别当n =0时，Pn即P0，为稳态系统所有服务台全部空闲的概率。

19 输入过程 输入过程是描述各种类型的顾客以怎样的规律到达系统，一般用相继两顾客到达时间间隔来描述系统输入特征。主要输入过程有：
1.定长输入。这是指顾客有规则地等距到达，每隔时间到达一个顾客。这时相继顾客到达间隔的分布函数F(t)为: î í ì < = a x t P F , 1 } { ) (

20 输入过程 2.泊松(poisson)输入。又称最简单流。满足下面3个条件的输入称之为最简单流。
(1) 平稳性。输入过程是平稳的，指在长度为t的时段内恰好到达k个顾客的概率仅与时段长度有关，而与时段起点无关。即对任意∈(0,∞)，在(,+t]或(0,t)内恰好到达k个顾客的概率相等： ) ( } { t V k P a = - + x (2)无后效性。指在任意几个不相交的时间区间内，各自到达的顾客数是相互独立的。通俗说就是以前到达的顾客情况，对以后顾客的到来没有影响。 (3)单个性又称普通性。指在充分小的时段内最多到达一个顾客。

21 输入过程 因为泊松流实际应用最广，也最容易处理，因而研究得也较多．可以证明，对于泊松流，在长度为t的时间内到达K个顾客的概率vk(t)服从泊松分布，即 L , 2 1 ! ) ( = - K t e V k l 其中参数>0为一常数，表示单位时间内到达顾客的平均数，又称为顾客的平均到达率。 对于泊松流，其相继顾客到达时间间隔i，i=1,2,…是相互独立同分布的，其分布函数为负指数分布： î í ì < - = , 1 ) ( t e F i l x

22 输入过程 3.爱尔朗输入。这是指相继顾客到达时间间隔相互独立，具有相同的分布，其分布密度为: )! 1 ( ) ³ - = t e K a
)! 1 ( ) - = t e K a l 4.一般独立输入，即相继顾客到达时间间隔相互独立、同分布，分布函数F(t)是任意分布，因此，上面所述的所有输入都是一般独立分布的特例。 5.成批到达的输入。这时排队系统每次到达的顾客不一定是一个，而可能是一批，每批顾客的数目n是一个随机变量。 到达时间间隔可能是上述几类输入中的一种。

23 服务时间分布 1.定长分布。每一个顾客的服务时间都是常数 ，此时服务时间t的分布函数为： î í ì < ³ = £ b x t P
1 ) ( 2.负指数分布。即各个顾客的服务时间相互独立，具有相同的负指数分布： î í ì < - = , 1 ) ( x e B m

24 服务时间分布 3.爱尔朗分布. 即每个顾客的服务时间相互独立，具有相同的爱尔朗分布。其密度函数为： , )! 1 ( ) ³ - = x e
, )! 1 ( ) - = x e k b m 4.一般服务分布。所有顾客的服务时间都是相互独立具有相同分布的随机变量，其分布函数记B(X)，前面所述的各种服务分布都是一般服务分布的特例。 5.多个服务台的服务分布。可以假定各个服务台的服务分布参数不同或分布类型不同。 6.服务时间依赖于队长的情况。指服务员排队的人愈多，服务的速度也就愈快。

25 排队论研究的基本问题 排队论研究的首要问题是排队系统主要数量指标的概率规律，即研究系统的整体性质，然后进一步研究系统的优化问题。
(1)通过研究主要数量指标在瞬时或平稳状态下的概率分布及其数字特征，了解系统运行的基本特征。 (2)统计推断问题，建立适当的排队模型是排队论研究的第一步，建立模型过程中经常会碰到如下问题：检验系统是否达到平稳状态；检验顾客相继到达时间间隔的相互独立性；确定服务时间的分布及有关参数等。 (3)系统优化问题，又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优或最合理的状态。系统优化问题包括最优设计问题和最优运营问题。

26 排队论研究的基本问题 对于一般的排队系统运行情况的分析，通常是在给定输入与服务条件下，通过求解系统状态为n(有n个顾客)的概率Pn(t)，再进行计算其主要的运行指标: 1)系统中顾客数(队长)的期望值L或Ls； 2)排队等待的顾客数(排队长)的期望值Lq； 3)顾客在系统中全部时间(逗留时间)的期望值W或Ws； 4)顾客排队等待时间的期望值Wq。

27 泊松输入—指数服务排队模型 对于泊松输入—负指数分布服务的排队系统的一般决策过程: 1) 根据已知条件绘制状态转移速度图。
2)依据状态转移速度图写出各稳态概率之间的关系。 3) 求出 P0及 Pn 。 4)计算各项数量运行指标。 5)用系统运行指标构造目标函数，对系统进行优化。

28 泊松输入—指数服务排队模型 Õ n 1 2 3 λ0 λ2 λ1 λn-1 λn μ1 μn μ3 μ2 μn+1 转入率=转出率
n 1 2 3 λ0 λ2 λ1 λn-1 λn μ1 μn μ3 μ2 μn+1 转入率=转出率 n=0时，λ0P0=μ1P1 n=1时，λ0P0+ μ2P2 = λ0P0 +μ1P1 一般n >0，λn-1Pn-1+μn+1Pn+1=(λn+μn)Pn 1 P n j i Õ + = m l L

29 泊松输入—指数服务排队模型 å å 系统的运行指标：(稳态时) KP L 1.系统中顾客数的期望值： - = P L ) (
= k K KP L 1.系统中顾客数的期望值： å > - = C k K P L ) ( 2.排队等待的顾客数的期望值： 3.系统达到稳态时，假定平均到达率为常数λ，则有下列李特尔公式： q e W L l = 又假定平均服务时间为常数μ，则有： m l e q L W + = 1

30 M/M/1系统 μ N 1 2 N-1 λ 稳态概率方程： Pn= (λ/μ)Pn-1=……= (λ/μ)nP0 ，令ρ =λ/μ
N 1 2 N-1 λ μ 稳态概率方程： Pn= (λ/μ)Pn-1=……= (λ/μ)nP0 ，令ρ =λ/μ 当ρ  1时, ∑ρn不收敛，故应ρ<1, λ<μ P0=1-λ/μ=1-ρ， Pn=ρn(1-ρ) L=λ/(μ-λ) =ρ/(1-ρ)， Lq=λ2/[μ(μ-λ)] =Lρ W=L/λe=1/(μ-λ)，Wq=λ/[μ(μ-λ)]=Wρ 系统内顾客数多于k个的概率 P( N > k ) = ρk+1 顾客逗留时间超过t的概率 P( U > t ) = e -μt(1-ρ)

31 M/M/1系统 例9-1:某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15分钟。病人按泊松分布到达，平均每小时到达3人。 (1)计算急诊室空闲的概率 (2)计算系统的主要指标 (3)为使病人平均逗留时间不超过半小时，平均服务时间应减少多少？ (4)若医院希望候诊的病人90%以上都能有座位，则候诊室至少应安置多少座位？

32 M/M/S系统 å å μ sμ 2μ 3μ (s-1)μ N 1 2 N-1 λ C C-1 C+1 ) ( ! ú û ù ê ë é
N 1 2 N-1 λ μ sμ 2μ C C-1 C+1 3μ (s-1)μ 1 ) ( ! - = ú û ù ê ë é + å r d s k P m l d r = , s l d r q n L W P s = + - , ) 1 ( ! 2 ï î í ì > = - ) ( ! 1 s n P d ) 1 ( ! P k N n r d - = > å

33 M/M/1系统 例9-2:上例中假设医院增强急诊室的服务能力，使其同时能诊治两个病人，且平均服务率相同，试分析系统的工作情况，并与例9-1进行比较。 指 标 S=1系统 S=2系统 P0 0.25 0.45 P(Q>0) 0.75 0.2 Lq 2.25人 0.12人 L 3人 0.87人 Wq 60分钟 17.4分钟 W 45分钟 2.4分钟 β 3倍 16%