《ch9排队论》由会员分享，可在线阅读，更多相关《ch9排队论（87页珍藏版）》请在金锄头文库上搜索。
1、Queuing theory,第九章 排队论,运筹学 Operations Research,9.1 排队论的基本概念 9.2 排队系统常用分布 9.3 单服务台模型M/M/1 9.4 多服务台模型M/M/s 9.5 其它服务时间分布模型 9.6 排队系统的优化,9.1 排队论的基本概念,2019年5月21日星期二,9.1.1 排队系统的描述,排队系统的例子,9.1 排队论的基本概念 Basic Concepts of Queuing theory,2019年5月21日星期二,排队的过程可表示为：,9.1 排队论的基本概念 Basic Concepts of Queuing theory,20
2、19年5月21日星期二,根据服务台的数量及排队方式，排队系统可以分为 (1)单服务台单队,(2)多服务台单队,图9-2单服务台单队系统,顾客到达,服务台,顾客离去,服务台,服务台,图9-3 多服务台单队系统,9.1 排队论的基本概念 Basic Concepts of Queuing theory,2019年5月21日星期二,(3)多队多服务台,(4)多服务台串联服务,图9-4 多服务台多队系统,图9-5 多服务台串联系统,9.1 排队论的基本概念 Basic Concepts of Queuing theory,顾客到达,服务台,顾客离去,服务台,服务台,顾客到达,顾客离去,2019年5月2
3、1日星期二,9.1.2排队系统的基本组成,排队系统由输入过程、服务规则和服务台三个部分组成,这是指要求服务的顾客按怎样的规律到达排队系统的过程，有时也称之为顾客流。 （1）顾客总体数，又称顾客源、输入源。顾客源可以是有限的，也可以是无限的。 （2）顾客到达的形式。这是描述顾客是怎样来到系统的，是单个到达，还是成批到达。 （3）顾客流的概率分布，或称顾客相继到达的时间间隔分布。这是首先需要确定的指标。,9.1 排队论的基本概念 Basic Concepts of Queuing theory,1.输入过程,2019年5月21日星期二,(1)先到先服务（FCFS，First Come First
4、Serve）； (2)后到先服务（LCFS，Last Come First Serve）； (3)有优先权的服务（PR，Priority） (4)随机服务（SIRO，Service in Random Order）,9.1 排队论的基本概念 Basic Concepts of Queuing theory,2.排队规则,(1)等待制 指顾客到达系统后，所有服务台都不空，顾客加入排队行列等待服务，一直等到服务完毕以后才离去 ；,(2)损失制 指当顾客到达系统时，所有服务台都已被占用，顾客不愿等待而离开系统。,2019年5月21日星期二,(3)混合制 这是等待制与损失制相结合的一种服务规则，一般是
5、指允许排队，但又不允许队列无限长下去。大体有以下三种： 队长有限。当等待服务的顾客人数超过规定数量时，后来的顾客就自动离去，另求服务，即系统的等待空间是有限的。 等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T，当等待时间超过时间T时，顾客将自动离去，并不再回来。 逗留时间（等待时间与服务时间之和）有限。,9.1 排队论的基本概念 Basic Concepts of Queuing theory,2019年5月21日星期二,(1)服务台数量及构成形式 从数量上说，服务台有单台和多台之分。从构成形式上看，有单队单服务台式、单队多服务台并联式、多队多服务台并联式、单队多服务台串联式等等
6、，如图9-2到9-5所示； (2)服务方式 指在某一时刻接受服务的顾客数，有单个服务和成批服务两种； (3)服务时间的分布 在多数情况下，对某一个顾客的服务时间是一随机变量，与顾客到达的时间间隔分布一样，服务时间的分布有定长分布、负指数分布、爱尔朗分布等等。,3.服务台,9.1 排队论的基本概念 Basic Concepts of Queuing theory,服务台可以从以下三个方面来描述：,2019年5月21日星期二,9.1.3 排队系统的主要数量指标、记号和符号,9.1 排队论的基本概念 Basic Concepts of Queuing theory,（1）队长和队列长(排队长) 队长
7、是指系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和） 队列长是指系统中正在排队等待服务的顾客数。队长和队列长一般都是随机变量 （2）等待时间和逗留时间 从顾客到达时刻起到他开始接受服务止这段时间称为等待时间。从顾客到达时刻起到他接受服务完止这段时间称为逗留时间。两种时间都是随机变量 （3）忙期和闲期 忙期是指从顾客到达空闲着的服务机构起，到服务再次成为空闲止的这段时间，服务机构连续忙的时间。这是个随机变量。与忙期相对的是闲期，即服务机构连续保持空闲的时间。,1. 主要数量指标,2019年5月21日星期二,9.1 排队论的基本概念 Basic Concepts of Queuing
8、theory,2. 记号,时刻 t 系统中的顾客数（又称为系统的状态），即队长； 时刻 t 系统中排队的顾客数，即列队长； 时刻 t 到达系统的顾客在系统中的逗留时间； 时刻 t 到达系统的顾客在系统中的等待时间,L：平均队长，即稳态系统任一时刻顾客数的期望值； Lq：平均等待队长，即稳态系统任一时刻等待服务的顾客数的期望值； W：平均逗留时间，即在任一时刻进入稳态系统的顾客逗留时间的期望值； Wq：平均等待时间，即在任一时刻进入稳态系统的顾客等待时间的期望值；,在平稳状态下:,2019年5月21日星期二,9.1 排队论的基本概念 Basic Concepts of Queuing theor
9、y,：顾客到达的平均速率，即单位时间内平均到达的顾客数； 1/：平均到达时间间隔； ：平均服务速率，即单位时间内服务完毕离去的顾客数； 1/：平均服务时间； s ：系统中服务台的个数； ：服务强度，即每个服务台单位时间内的平均服务时间，一般有/(s)； N：稳态系统任一时刻的状态（即系统中所有顾客数）； U：任一顾客在稳态系统中的逗留时间； Q：任一顾客在稳态系统中的等待时间； PnPN=n：稳态系统任一时刻状态为n的概率；特别当n=0时，PnP0，即稳态系统所有服务台全部空闲的概率； e：有效平均到达率，即期望每单位时间内来到系统（包括未进入系统）的概率。,2019年5月21日星期二,3.排
10、队系统的符号,一个排队系统的特征可以用六个参数表示，形式为： XYZ：ABC 或 X/Y/Z/A/B/C 其中 X 顾客到达的概率分布，可取M、D、Ek、G等； Y 服务时间的概率分布，可取M、D、Ek 、G等； Z 服务台个数，取正整数； A 排队系统的最大容量，可取正整数或； B 顾客源的最大容量，可取正整数或； C 排队规则，可取FCFS、LCFS等。 例如 M/M/1：/FCFS 表示顾客到达的时间间隔是负指数分布，服务时间是负指数分布，一个服务台，排队系统和顾客源的容量都是无限，实行先到先服务的一个服务系统。,9.1 排队论的基本概念 Basic Concepts of Queuin
11、g theory,2019年5月21日星期二,下一节：排队系统常用分布,9.1 排队论的基本概念 Basic Concepts of Queuing theory,9.2 排队系统常用分布,2019年5月21日星期二,9.2.1 负指数分布,随机变量T服从负指数分布，其分布函数为,密度函数为,T的期望值为,T的方差为,9.2 排队系统常用分布,2019年5月21日星期二,负指数分布具有性质,(1)密度函数,对时间t严格递减,(2)无记忆性或马尔柯夫性，即,(3)当顾客到达过程是泊松流时，顾客相继到达的间隔时间T 必服从负指数分布，这个性质将在定理9.1中予以证明。,若随机变量X的概率密度为,9
12、.2.2泊松分布,则称X服从参数为的泊松(Poisson)分布，记为XP()。其均值和方差分别为,9.2 排队系统常用分布,2019年5月21日星期二,【定义9.1】对于随机过程 ,若满足,1.Poisson流的定义,9.2 顾客到达和服务的时间分布,(1)独立增量性(无后效性) 即对任意n个参数 增量 相互独立 或者说不相交的时间区间内到达的顾客数互相独立。,(2)增量平稳性 即在长度为 t 的时间区间内恰好到达k个顾客的概率仅与区间长度t有关，而与区间起始点无关,(3)普遍性 即当t充分小时，有,称 为Poisson过程，N(t)服从泊松分布,2019年5月21日星期二,2排队系统与泊松过
13、程,9.2 顾客到达和服务的时间分布,若N(t)为时间区间0,t）(t0)内到达系统的顾客数，则N(t)是一个随机变量，且 N(t)|t(0,T)为一个随机过程。若该随机过程满足,（1）在不相重叠的区间内，顾客的到达数是相互独立的； （2）在时间区间t,t+t）内有顾客的到达数只与区间长度t有关，而与区间起始点t无关； （3）对于充分小的t，在时间区间t,t+t）内有2个或2个以上的顾客到达的概率极小，以致于可以忽略,则认为顾客到达系统的过程是泊松过程，且,2019年5月21日星期二,9.2 顾客到达和服务的时间分布,如果一个随机变量，概率分布与时间t有关，则称这个随机变量为一随机过程，排队系
14、统中顾客到达的个数就是一个随机过程。,【定理9.1】在排队系统中，如果到达的顾客数服从以t为参数的泊松分布，则顾客相继到达的时间间隔服从以为参数的负指数分布.,证明参看教材。,由定理9.1可以看出，“到达的顾客数是一个以为参数的泊松流”与“顾客相继到达的时间间隔服从以为参数的负指数分布”两个事实是等价的,2019年5月21日星期二,【定理9.2】设X1,X2,，Xk ,是k个互相独立的，具有相同参数的负指数分布随机变量，则随机变量,服从k阶爱尔朗(Erlang)分布，X的密度函数为,记为,或简记为,随机变量X的均值和方差分别为：,9.2 排队系统常用分布,2019年5月21日星期二,为单位时间
15、平均到达顾客数目，亦称平均到达率。顾客到达服从泊松分布，亦称顾客到达形成泊松流（最简单流）。,例1：一台仪表由1000个元件组成，每个元件在一年工作时间内发生故障的概率为0.001，并且与其它元件的状况无关，求在一年内不少于2个元件发生故障的概率。 解： 设X=元件发生故障个数，由于n=1000 P=0.001很小，可视发生故障服从泊松分布，其中=nP=1 因此,9.2 顾客到达和服务的时间分布,2019年5月21日星期二,下一节： 单服务台模型,9.2 顾客到达和服务的时间分布,9.3单服务台模型M/M/1,2019年5月21日星期二,9.3 单服务台模型,9.3.1基本模型,设单位时间到达系统的顾客数为 ，单位时间被服务完的顾客数为。由于是单服务台，且顾客源无限，因此，在各种状态的情况下，系统的“出生率”为，系统的“死亡率”为。系统在稳态情况下的状态转移如图9-6所示,图9-6,根据以上状态转移图，可以得出如下平衡方程,(91),(92),1 系统状态概率Pn(t)的计算,2019年5月21日星期二,9.3 单服务台模型,由(91)和(92)可以递推求解P1，P2，Pn，得到,(93),(94),表示平均到达率与平均服务率之比，称为服务强度,2019年5月21日星期
