1、排队论模型简介排队论模型简介11ppt课件Outline1. 基本概念基本概念2. 到达时间的间隔分布和服务时间的分布到达时间的间隔分布和服务时间的分布3. 单服务台的排队模型单服务台的排队模型4. 多服务台的排队模型多服务台的排队模型5. 排队模型案例排队模型案例21ppt课件 某维修中心在周末现只安排一名员工为顾客提供服务某维修中心在周末现只安排一名员工为顾客提供服务. 新新来维修的顾客到达后，若已有顾客正在接受服务，则需要排来维修的顾客到达后，若已有顾客正在接受服务，则需要排队等待队等待. 若排队的人数过多，势必会造成顾客抱怨，会影响若排队的人数过多，势必会造成顾客抱怨，会影响到公司产品
2、的销售；若维修人员多，会增加维修中心的支出，到公司产品的销售；若维修人员多，会增加维修中心的支出，如何调整两者的关系，使得系统达到最优如何调整两者的关系，使得系统达到最优.一、基本概念一、基本概念它是一个典型的排队的例子它是一个典型的排队的例子, 关于排队的例子有很多关于排队的例子有很多, 例如：例如：上下班坐公共汽车上下班坐公共汽车, 等待公共汽车的排队等待公共汽车的排队; 顾客到商店购物形顾客到商店购物形成的排队成的排队; 病人到医院看病形成的排队病人到医院看病形成的排队; 售票处购票形成的排售票处购票形成的排队等队等; 另一种另一种排队是排队是物物的排队，例如文件等待打印或发送的排队，例
3、如文件等待打印或发送; 路路口红灯下面的汽车、自行车通过十字路口等等口红灯下面的汽车、自行车通过十字路口等等.1. 引例引例31ppt课件排队现象是由排队现象是由两个方面两个方面构成，一方要求得到服务，构成，一方要求得到服务，另一方设法给予服务另一方设法给予服务. 我们把要求得到服务的人或物（设备）统称为我们把要求得到服务的人或物（设备）统称为顾顾客客, 给予服务的服务人员或服务机构统称为服务员给予服务的服务人员或服务机构统称为服务员或或服务台服务台. 顾客与服务台就构成一个排队系统，或顾客与服务台就构成一个排队系统，或称为称为随机服务系统随机服务系统. 显然缺少顾客或服务台任何一显然缺少顾客
4、或服务台任何一方都不会形成排队系统方都不会形成排队系统.41ppt课件对于任何一个排队服务系统，每一名顾客通过排队服务系对于任何一个排队服务系统，每一名顾客通过排队服务系统总要经过如下过程：顾客到达、排队等待、接受服务和统总要经过如下过程：顾客到达、排队等待、接受服务和离去，其过程如下图所示离去，其过程如下图所示: :输入来源输入来源队队 列列服务机构服务机构排队系统排队系统顾客顾客服务完离开服务完离开51ppt课件排队系统的排队系统的三个三个基本组成部分基本组成部分输入过程输入过程 (顾客按照怎样的顾客按照怎样的规律规律到达到达);排队规则排队规则 (顾客按照一定顾客按照一定规则规则排队等待
5、服务排队等待服务);服务机构服务机构 (服务机构的设置服务机构的设置,服务台的服务台的数量数量, 服务的方式服务的方式,服务时间分布服务时间分布等等)61ppt课件输入输入过程过程顾客源总体：顾客源总体：顾客的来源可能是有限的，也可顾客的来源可能是有限的，也可 能是无限的能是无限的2. 排队服务系统的基本概念排队服务系统的基本概念到达的类型：到达的类型：顾客是单个到达，或是成批到达顾客是单个到达，或是成批到达相继顾客到达的间隔时间：相继顾客到达的间隔时间：通常假定是相互独通常假定是相互独立、同分布的，有的是等距间隔时间，有的是立、同分布的，有的是等距间隔时间，有的是服从服从Poisson分布，
6、有的是服从分布，有的是服从k阶阶Erlang分布分布输入过程输入过程是描述顾客来源及顾客是按怎样的规律抵达排队系统是描述顾客来源及顾客是按怎样的规律抵达排队系统71ppt课件排队排队规则规则损失制损失制排队系统：排队系统：顾客到达时顾客到达时,若有服务台均被占若有服务台均被占,服务机构服务机构 又不允许顾客等待又不允许顾客等待, 此时该顾客就自动辞去此时该顾客就自动辞去等待制等待制排队系统：排队系统：顾客到达时若所有服务台均被占，他们顾客到达时若所有服务台均被占，他们 就排队等待服务。在等待制系统中就排队等待服务。在等待制系统中,服务服务 顺序顺序又分为：先到先服务又分为：先到先服务,即顾客按
7、到达即顾客按到达 的先后顺序接受服务；后到先服务的先后顺序接受服务；后到先服务 .混合制混合制排队系统：排队系统：损失制与等待制的混合，分为队长损失制与等待制的混合，分为队长(容量容量) 有限的混合制系统，等待时间有限的混有限的混合制系统，等待时间有限的混 合制系统，以及逗留时间有限制的混合合制系统，以及逗留时间有限制的混合 系统系统.排队规则排队规则是指服务允许是指服务允许/不允许排队，顾客是否愿意排队不允许排队，顾客是否愿意排队81ppt课件服务服务机构机构服务台的数目服务台的数目: 在多个服务台的情形下，是串在多个服务台的情形下，是串 联或是并联；联或是并联；顾客所需的服务时间顾客所需的
8、服务时间服从什么样的概率分布，服从什么样的概率分布，每个顾客所需的服务时间是否相互独立，是成每个顾客所需的服务时间是否相互独立，是成批服务或是单个服务等批服务或是单个服务等. . 常见顾客的服务时间常见顾客的服务时间分布有：定长分布、负指数分布、超指数分分布有：定长分布、负指数分布、超指数分布、布、k k阶阶ErlangErlang分布、几何分布、一般分布等分布、几何分布、一般分布等. .服务机构服务机构91ppt课件 3.符号表示符号表示排队论模型的记号是排队论模型的记号是2020世纪世纪5050年代初由年代初由D. G. KendallD. G. Kendall引入的，其形式为引入的，其形
9、式为CBAZYX/101ppt课件 3.符号表示符号表示例如：例如：M/M/C/N/m111ppt课件例如例如:(1) M/M/S/ 表示输入过程是表示输入过程是Poisson流流, 服务时间服从负服务时间服从负指数分布指数分布, 系统有系统有S个服务台平行服务个服务台平行服务, 系统容量为无穷的系统容量为无穷的等待制排队系统等待制排队系统.(2) M/G/1/ 表示输入过程是表示输入过程是Poisson流，顾客所需的服务流，顾客所需的服务时间为独立、服从一般概率分布，系统中只有一个服务时间为独立、服从一般概率分布，系统中只有一个服务台，容量为无穷的等待制系统台，容量为无穷的等待制系统.(3)
10、 GI/M/1/表示输入过程为顾客独立到达且相继到达的间表示输入过程为顾客独立到达且相继到达的间隔时间服从一般概率分布，服务时间是相互独立、服从负指隔时间服从一般概率分布，服务时间是相互独立、服从负指数分布，系统中只有一个服务台，容量为无穷的等待制系统数分布，系统中只有一个服务台，容量为无穷的等待制系统121ppt课件(4) Ek/G/1/K表示相继到达的间隔时间独立、服从表示相继到达的间隔时间独立、服从k阶阶Erlang分布，服务时间为独立、服从一般概率分布，系统中只有一分布，服务时间为独立、服从一般概率分布，系统中只有一个服务台，容量为个服务台，容量为K的混合制系统的混合制系统.(5) D
11、/M/S/K表示相继到达的间隔时间独立、服从表示相继到达的间隔时间独立、服从定长分布定长分布、服务时间相互独立、服从负指数分布，系统中有服务时间相互独立、服从负指数分布，系统中有S个服务台个服务台平行服务，容量为平行服务，容量为K的混合制系统的混合制系统.131ppt课件4. 描述排队系统的主要数量指标描述排队系统的主要数量指标 （1）队长与等待队长）队长与等待队长队长队长(通常记为通常记为LS)是指在系统中的顾客的平均数是指在系统中的顾客的平均数(包括包括正在接受服务的顾客正在接受服务的顾客),而等待队长而等待队长(队列长队列长)(通常记为通常记为Lq)是指系统中排队等是指系统中排队等待的顾
12、客的平均数，它们是顾客和服务机构待的顾客的平均数，它们是顾客和服务机构双方双方都十都十分关心的数量指标分关心的数量指标.显然，队长显然，队长等于等于等待队长加上正在被服务的顾客数等待队长加上正在被服务的顾客数.nqsLLLnL其中 为正在接受服务的顾客数 141ppt课件 (2)顾客的顾客的平均平均等待时间与等待时间与平均平均逗留时间逗留时间顾客的平均等待时间顾客的平均等待时间( (通常记为通常记为W Wq q) )是指从顾客进入系是指从顾客进入系统的时刻起直到开始接受服务止的平均时间统的时刻起直到开始接受服务止的平均时间. . 平均逗留时间平均逗留时间( (通常记为通常记为W Ws s) )
13、是指顾客在系统中的平均是指顾客在系统中的平均等待时间与平均服务时间之和等待时间与平均服务时间之和. . 平均等待时间与平均服务时间是平均等待时间与平均服务时间是顾客顾客最关心的数量指标最关心的数量指标.qsWW其中 为服务时间 151ppt课件 (3)系统的忙期与闲期系统的忙期与闲期 从顾客到达空闲的系统，服务立即开始，直到系统再从顾客到达空闲的系统，服务立即开始，直到系统再次变为空闲，这段时间是系统连续繁忙的时间次变为空闲，这段时间是系统连续繁忙的时间(记作 )，我们称为系统的我们称为系统的忙期忙期，它反映了系统中服务机构的工作，它反映了系统中服务机构的工作强度，是衡量服务机构利用效率的指标
14、，即强度，是衡量服务机构利用效率的指标，即与忙期对应的是与忙期对应的是系统的闲期系统的闲期，即系统连续保持空闲的时，即系统连续保持空闲的时间长度间长度.服务机构服务机构工作强度工作强度用于服务顾客的时间用于服务顾客的时间服务设施总的服务时间服务设施总的服务时间用于服务顾客的时间用于服务顾客的时间服务设施总的服务时间服务设施总的服务时间1bT 161ppt课件 (4)损失率与服务强度损失率与服务强度 171ppt课件5. 系统状态的概率系统状态的概率系统状态是求运行指标的基础，所谓系统的状态是指系统状态是求运行指标的基础，所谓系统的状态是指系统中顾客的数量。如果系统中有系统中顾客的数量。如果系统
15、中有n个顾客，则说系个顾客，则说系统的状态为统的状态为n.181ppt课件 二、到达时间的间隔分布和服务时间的分布二、到达时间的间隔分布和服务时间的分布 191ppt课件201ppt课件211ppt课件221ppt课件笔误多多231ppt课件241ppt课件251ppt课件261ppt课件271ppt课件三、单服务台的排队模型三、单服务台的排队模型 281ppt课件291ppt课件301ppt课件, 2 , 1),()()()()(11ntPtPtPdttdPnnnn311ppt课件稳态解稳态解321ppt课件状态转移关系图 331ppt课件341ppt课件351ppt课件顾客不需要等待的概率
16、为顾客不需要等待的概率为 210p606nnpNP361ppt课件NnPPnNnN1,11, 1,11110371ppt课件381ppt课件391ppt课件1100)(11!1)(!1CkckckPcPccPnPncnnnn,)(1!1cn,!100当，当401ppt课件（2）系统容量有限制：）系统容量有限制：M/M/c/N/ 411ppt课件五、排队模型案例五、排队模型案例校园网的设计校园网的设计和和调节收费问题调节收费问题 421ppt课件431ppt课件 考虑系统容量有限制的排队模型：考虑系统容量有限制的排队模型：M/M/c/N/补充补充441ppt课件451ppt课件461ppt课件471ppt课件481ppt课件491ppt课件501ppt课件511ppt课件521ppt课件531ppt课件541ppt课件551ppt课件561ppt课件谢谢大家！谢谢大家！571ppt课件
