第十一章 排队论.ppt

第十一章排队论
§1 排队过程的组成部分
§2 单服务台泊松到达、负指数服务时间的排队模型
§3 多服务台泊松到达、负指数服务时间的排队模型
§4 排队系统的经济分析
§5 单服务台泊松到达、任意服务时间的排队模型
§6 单服务台泊松到达、定长服务时间的排队模型
§7 多服务台泊松到达、任意的服务时间、损失制排队模型
§8 顾客来源有限制排队模型
§9 单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型
§10 多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型
1
一、基本概念
一些排队系统的例子
排队系统顾客服务台服务
电话系统电话呼叫电话总机接通呼叫或取消呼叫
售票系统购票旅客售票窗口收款、售票
设备维修出故障的设备修理工排除设备故障
防空系统进入阵地的敌机高射炮瞄准、射击,敌机被击落或离开

排队的过程可表示为:
排队
服务机构服务
服务后顾客离去
排队系统
顾客到达
§1 排队过程的组成部分
2
根据服务台的数量及排队方式,排队系统可以分为
(1)单服务台单队
(2)多服务台单队
单服务台单队系统
…
…
顾客到达
进入队列
服务台
接受服务
顾客离去
…
…
顾客到达
服务台
顾客离去
服务台
服务台
多服务台单队系统
§1 排队过程的组成部分
3
考虑要点:
1、服务台(或通道)数目:单服务台(单通道)、多服务台(多通道)。
2、顾客到达过程:本教材主要考虑顾客的泊松到达情况。
满足以下四个条件的输入流称为泊松流(泊松过程)。
*平稳性:在时间区间[t, t+t) 内到达k个顾客的概率与t无关,只与t 有关,记为 pk(t);
*无后效性:不相交的时间区间内到达的顾客数互相独立;
*普通性:在足够短的时间内到达多于一个顾客的概率可以忽略;
*有限性:任意有限个区间内到达有限个顾客的概率等于1。
泊松分布为单位时间平均到达的顾客数
P (x) = x e-/ x! (x = 0, 1, 2,……)
§1 排队过程的组成部分
4
§1 排队过程的组成部分
3、服务时间分布: 服从负指数分布,为平均服务率,即单位时间服务的顾客数。
P(服务时间≤ t ) = 1- e- t 。
4、排队规则分类
(1) 等待制: 顾客到达后,一直等到服务完毕以后才离去。


(2) 损失制: 到达的顾客有一部分未接受服务就离去。
①先到先服务(FCFS,e First Serve);
②后到先服务(LCFS,e First Serve);
③有优先权的服务(PR,Priority)
④随机服务(SIRO,Service in Random Order)
5
(3)混合制
这是等待制与损失制相结合的一种服务规则,一般是指允许排队,但又不允许队列无限长下去。大体有以下三种:
①队长有限。当等待服务的顾客人数超过规定数量时,后来的顾客就自动离去,另求服务,即系统的等待空间是有限的。
②等待时间有限。即顾客在系统中的等待时间不超过某一给定的长度T,当等待时间超过时间T时,顾客将自动离去,并不再回来。
③逗留时间(等待时间与服务时间之和)有限。
§1 排队过程的组成部分
6
排队系统的符号表示:
一个排队系统的特征可以用五个参数表示,形式为:
A/B/C/D/E
其中:A ––顾客到达的概率分布,可取M、 D、G 等;
B ––服务时间的概率分布,可取M、D、 G 等;
C ––服务台个数,取正整数;
D ––排队系统的最大容量,可取正整数或;
E ––顾客源的最大容量,可取正整数或。
(M—到达服从泊松分布或服务时间服从指数分布;D—到达或服务时间是确定的或持续不变的;G—到达或服务时间服从某种已知均值和标准差的一般概率分布。)
例如 M / M / 1 / / 
表示顾客到达过程服从泊松分布,服务时间服从负指数分布,一个服务台,排队的长度无限制和顾客的来源无限制。
§1 排队过程的组成部分
7
Ls:平均队长,系统中的平均顾客数;
Lq:平均等待队长,平均排队的顾客数;
Ws:平均逗留时间,顾客在系统中的平均逗留时间;
Wq:平均等待时间,顾客花在排队上的平均等待时间;
λ:顾客到达的平均速率,即单位时间内平均到达的顾客数;
1/λ:平均到达时间间隔;
μ:平均服务速率,即单位时间内服务完毕离去的顾客数;
1/μ:平均服务时间;
ρ:服务强度,即每个服务台单位时间内的平均服务时间,一般有ρ=λ/μ;
N:稳态系统任一时刻的状态(即系统中所有顾客数);
λe:有效平均到达率,即期望每单位时间内来到系统(包括未进入系统)的概率。
§1 排队过程的