第12章 排队模型

第12章排队模型§12-1概述§12-2(M/M/1):(∞/∞/FCFS)模型§12-3其他马氏过程排队模型§12-4两个非马氏排队模型§12-1概述一、排队过程的一般表示

到达的顾客要求服务内容服务机构1．不能运转的机器2．修理技工3．病人4．电话呼唤5．交件稿6．提货单7．到达机场上空的飞机8．驶入港口的货船9．上游河水进入水库10．进入我方阵地的敌机修理领取修配零件诊断或动手术通话打字提取存货降落装（卸）货放水，调整水位我方高射炮进行射击修理技工发放修配零件的管理员医生(或包括手术台)交换台打字员仓库管理员跑道装（卸）货码头(泊位)水闸管理员我方高射炮排队系统举例：二、排队系统的组成和特征输入过程、排队规则、服务机构

1.输入过程:指各种类型的“顾客”按怎样的规律到来指数分布(M)：又称最简单流，在长为t的时间区间内到达n个顾客的概率服从波松分布，即或者说顾客相继到达间隔时间T服从负指数分布：k阶爱尔朗输入(Ek):到达间隔相互独立，具有相同的爱尔朗分布密度：

2.排队规则损失制：又称即时制。顾客到达时，若所有服务台被占用，该顾客就自动消失，永不再来等待制：顾客到达时，若所有的服务台被占用，就排队等候:等待服务的次序可以采用下列规则：先到先服务(FCFS):即按照到达次序接受服务，这是最通常的情况后到先服务(LCFS):例如将钢板堆入仓库看成是顾客到来，需要时将它们陆续取走看成是服务，则一般是先取最上面的，也就是最后放上的钢板随机服务(SIRO):服务机构从等待的顾客中随机地选一个进行服务优先权服务(PR):如危重病人可挂急诊、加急电报优先发送等混合制：损失制与等待制兼而有之的情况。假定服务系统的容量有限,最多只能容纳k个顾客,那么当顾客到达时，发现服务系统已经占满,该顾客将自动消失,否则就进入服务系统3.服务机构

服务台的个数可以是一个或几个;几个服务台可以是并联或串联;可以是单位个服务,也可以是成批服务

定长服务(D):每一个顾客的服务时间都是常数β，此时服务时间v的分布函数为负指数分布(M):

即各个顾客的服务时间相互独立，具有相同的负指数分布：K阶爱尔朗分布(Ek)：各个顾客的服务时间相互独立，具有相同的爱尔朗分布，其密度函数为：一般分布（G）：它的到达间隔相互独立，且都具有相同的概率分布三、排队系统的符号表示

1.D.G.Kendall于1953年提出用符号（A/B/C）来表示排队模型的特征A——顾客相继到达间隔时间的概率分布B——服务时间的概率分布C——并列的服务台的数目（或称通道数）例如:M/Ek/1表示相继到达间隔时间为负指数分布，服务时间服从k阶爱尔朗分布，单服务台的模型

A：顾客相继到达间隔时间的概率分布B：服务时间的概率分布C：并列的服务台数d：排队系统的容量，即系统允许的最大顾客数e：顾客总体（顾客源）的数目f：服务规则例如∶(M/M/1):(∞/∞/FCFS)排队模型表示顾客相继到达间隔时间和服务时间服从负指数分布，单服务台，系统能容纳无限个顾客，顾客源为无限源，排队服务规则是先到先服务。2.国际通用形式：

3.排队系统的主要运行指标L——系统期望顾客数(系统中等待服务的顾客数）的期望值，又称队长Lq——系统期望排队顾客数,指一个顾客从到达系统起到接受服务后离开系统为止所花费的时间的期望值,又称排队长W——顾客在系统的期望停留时间

Wq——顾客在系统的期望等待时间§12-2(M/M/1):(∞/∞/FCFS)模型一、生灭过程1.生灭过程的定义(1)假定有一堆细菌,每一细菌在时间内分裂成两个的概率为；而在内死亡的概率为，各个细菌在任何时段内分裂或死亡都是相互独立的。如果将细菌的分裂或死亡都看成发生一个事件的话，当足够小时，发生两个或两个以上事件的概率为。假定初始时刻细菌的个数已知，则经过时间t后，细菌变成了多少？这是生灭过程的例子，不少排队过程是和这个过程相仿的。(2)设为一个随机过程，随机变量的取值集合为或，这个集合也称为状态集，设在时刻t时，在时刻时，的概率为,其中为与t无关的常数；在时刻时，的概率为，其中也是与t无关的常数；在时刻时，为S中其它元素的概率均为。满足上述条件的随机过程称为生灭过程。(3)生灭过程具有无后效性，故也是一个马尔柯夫过程(4)把具有生灭过程特征的排队模型称为马氏过程排队模型。二、M/M/1模型的运行指标1.应满足下列条件：输入过程——顾客源是无限的，顾客按普阿松流到达排队系统

排队规则——单队，队长没有限制，先到先服务

服务机构——一个服务台，各顾客的服务时间相互独立，服从相同的负指数分布

2.系统状态概率分布Pn3.队长Ls4.排队长逗留时间分布为:所以平均停留时间:又因为所以平均等待时间：5.平均停留时间Ws和平均等待时间Wq6.指标参数之间的关系—Little公式三、M/M/1系统举例：

有一火车售票处，设有一个售票窗口，顾客到达为泊松流，平均到达率为0.3人/分。服务时间服从负指数分布，平均服务率为0.4人/分，试求服务系统的各项指标和顾客逗留15分钟以上的概率。解：已知条件1)服务强度和空闲率2）系统状态的概率3）平均队长和平均排队长4）顾客的停留时间和等待时间5）顾客在系统中停留15分钟以上的概率§12-3其他马氏过程排队模型一、M/M/C模型二、M/M/1/N模型三、M/M/C/N模型四、M/M/1/N/N模型(不讲)五、M/M/C/N/N

模型(不讲)一、M/M/C

模型系统的参数为设因此系统状态分布系统无顾客的概率所以顾客到达后需要等待的概率很容易证明顾客到达后立即能得到服务的概率平均空间指标和平均时间指标平均空间指标平均时间指标—Little公式关于Lq的公式的推导关于平均工作服务台数公式的推导二、M/M/1/N模型1.稳态时的状态分布2.M/M/1/N的状态分布3.M/M/1/N系统的空间指标1）平均队长2）平均排队长当时：当=1时：M/M/1/N系统的有效到达率和时间指标1.有效到达率2.平均时间指标指标公式的进一步讨论2)