《运筹汇总素材》由会员分享，可在线阅读，更多相关《运筹汇总素材（79页珍藏版）》请在金锄头文库上搜索。
1、2019/10/3,1,运筹学 OPERATIONS RESEARCH,2019/10/3,2,1 排队服务系统的基本概念 排队论是研究排队系统（又称随机服务系统）的数学理论和方法，是运筹学的一个重要分支。 有形排队现象：进餐馆就餐，到图书馆借书，车站等车，去医院看病，售票处售票，到工具房领物品等现象。,第十章 排队论,2019/10/3,3,无形排队现象：如几个旅客同时打电话订车票；如果有一人正在通话，其他人只得在各自的电话机前等待，他们分散在不同的地方，形成一个无形的队列在等待通电话。 排队的不一定是人，也可以是物。如生产线上的原材料，半成品等待加工；因故障而停止运行的机器设备在等待修理；
2、码头上的船只等待装货或卸货；要下降的飞机因跑道不空而在空中盘旋等。,2019/10/3,4,当然，进行服务的也不一定是人，可以是跑道，自动售货机，公共汽车等。 顾客要求服务的对象。 服务员提供服务的服务者（也称服务机构）。 顾客、服务员的含义是广义的。,2019/10/3,5,随机性顾客到达情况与顾客接受服务的时间是随机的。 一般来说，排队论所研究的排队系统中，顾客相继到达时间间隔和服务时间这两个量中至少有一个是随机的，因此，排队论又称随机服务理论。 随机服务理论研究如何合理的设置服务系统，更好的为顾客服务，减少排队时间，同时又要使得费用尽可能节省。,2019/10/3,6,排队系统类型1：,
3、服务台,顾客到达,服务完成后离开,单服务台排队系统,2019/10/3,7,排队系统类型2：,服务台2,顾客到达,服务完成后离开,S个服务台，一个队列的排队系统,服务台s,服务台1,2019/10/3,8,排队系统类型3：,服务台2,顾客到达,服务完成后离开,S个服务台， S个队列的排队系统,服务台s,服务台1,服务完成后离开,服务完成后离开,2019/10/3,9,排队系统类型4：,服务台1,顾客到达,离开,多服务台串联排队系统,服务台s,2019/10/3,10,排队系统的描述 实际中的排队系统各不相同，但概括 起来都由三个基本部分组成： 1、输入过程; 2、排队及排队规则; 3、服务机构
4、,2019/10/3,11,河流上游流入水库的水量可认为是无限的；车间内停机待修的机器显然是有限的。 到达方式：是单个到达还是成批到达。 库存问题中，若把进来的货看成顾客，则为成批到达的例子。,1、输入过程 顾客总体（顾客源）数：可能是有限，也可能是无限。,2019/10/3,12,顾客（单个或成批）相继到达的时间间隔分布：这是刻划输入过程的最重要内容。 令T0=0，Tn表示第n顾客到达的时刻，则有T0T1 T2 Tn 记Xn= Tn Tn-1 n=1,2,则Xn是第n顾客与第n-1顾客到达的时间间隔。 一般假定Xn是独立同分布，并记分布函数为A(t)。,2019/10/3,13,Xn的分布A
5、(t)常见的有： 定长分布（D）：顾客相继到达的时间间隔为确定的。 如产品通过传送带进入包装箱就是定常分布。 最简单流（或称Poisson)（M）：顾客相继到达的时间间隔Xn为独立的，同为负指数分布，其密度函数为：,f(t)=,e- t t0,0 t 0,2019/10/3,14,2、排队及排队规则 排队 有限排队排队系统中顾客数是有限的。（损失制排队系统，混合制排队系统） 无限排队顾客数是无限，队列可以排到无限长（等待制排队系统）。,2019/10/3,15,有限排队还可以分成： 损失制排队系统：排队空间为零的系统，即不允许排队。（顾客到达时，服务台占满，顾客自动离开，不再回来）（电话系统）
6、 混合制排队系统：是等待制与损失制结合，即允许排队，但不允许队列无限长。,2019/10/3,16,混合制排队系统： 1.队长有限,即系统等待空间是有限的。 例：最多只能容纳K个顾客在系统中，当新顾客到达时，若系统中的顾客数（又称为队长）小于K，则可进入系统排队或接受服务；否则，便离开系统，并不再回来。如水库的库容是有限的，旅馆的床位是有限的。,2019/10/3,17,2. 等待时间有限。即顾客在系统中等待时间不超过某一给定的长度T，当等待时间超过T时，顾客将自动离开，不再回来。 如:易损失的电子元件的库存问题，超过一定存储时间的元器件被自动认为失效。,混合制排队系统：,3. 逗留时间（等待
7、时间与服务时间之和）有限。 例：用高射炮射击飞机，当敌机飞越射击有效区域的时间为t时，若这个时间内未被击落，也就不可能再被击落了。,2019/10/3,18,说明：损失制和等待制可看成是混合制的特殊情形. 如:记s为系统中服务台个数，则 当k=s时，混合制即为损失制； 当k=时，即成为等待制。,2019/10/3,19,排队规则 当顾客到达时，若所有服务台都被占有且又允许排队，则该顾客将进入队列等待。服务台对顾客进行服务所遵循的规则通常有： 先来先服务（FCFS）,2019/10/3,20,后来先服务（LCFS）。在许多库存系统中就会出现这种情况。 如：钢板存入仓库后，需要时总是从最上面取出；
8、又如在情报系统中，后来到达的信息往往更重要，首先要加以分析和利用。,具有优先权的服务（PS）。服务台根据顾客的优先权的不同进行服务。 如：病危的病人应优先治疗；重要的信息应优先处理；出价高的顾客应优先考虑。,2019/10/3,21,3、服务机制 包括：服务员的数量及其连接方式（串联还是并联） 顾客是单个还是成批接受服务； 服务时间的分布 记某服务台的服务时间为V，其分布函数为B(t),密度函数为b(t),则常见的分布有：,定长分布（D）,负指数分布（M）,K阶爱尔朗分布（Ek）,2019/10/3,22,定长分布（D）：每个顾客接受的服务时间是一个确定的常数。 负指数分布（M）：每个顾客接受
9、的服务时间相互独立，具有相同的负指数分布：,f(t)=,e- t t0,0 t0,其中0为一常数。,2019/10/3,23,K阶爱尔朗分布（Ek）：,当k=1时即为负指数分布； k 30,近似于正态分布; 当 k 时，方差 0 即为完全非随机的。,2019/10/3,24,排队系统的符号表示： “Kendall”记号：X / Y/ Z / W 其中： X表示顾客相继到达的时间间隔分布； Y表示服务时间的分布； Z表示服务台个数； W表示系统的容量，即可容纳的最多顾客数。,2019/10/3,25,例1 M /M/ 1 / M表示顾客相继到达的时间间隔服从负指数分布； M表示服务时间为负指数分
10、布；单个服务台；系统容量为无限（等待制）的排队模型 。,例2 M /M/ S / K 顾客到达的时间间隔服从负指数分布； 服务时间为负指数分布；S个服务台；系统容量为K的排队模型。 当 K= S 时为损失制排队模型； 当 K= 时为等待制排队模型。,2019/10/3,26,排队系统的主要数量指标： 系统状态：也称为队长，指排队系统中的顾客数（排队等待的顾客数与正在接受服务的顾客数之和）。 排队长：系统中正在排队等待服务的顾客数。,2019/10/3,27,N(t)：时刻t(t0)的系统状态； pn(t)：时刻t系统处于状态n的概率； S：排队系统中并行的服务台数； n：当系统处于状态n 时，
11、新来的顾客的平均到达率（单位时间内到达的平均顾客数）； n：当系统处于状态n 时，整个系统的平均服务率（单位时间内可以服务完的平均顾客数）；,2019/10/3,28,当n为常数时记为；（单位时间内到达的顾客数） 当每个服务台的平均服务率为常数时，记每个服务台的服务率为， 则当n s 时，有 n=s （单位时间内可以服务完的平均顾客数） 因此， 顾客相继到达的平均时间间隔为E(T1)=1/， 平均服务时间为E(T2)= 1/， 令 = /s， 则 为系统的服务强度。,2019/10/3,29,平稳状态：pn(t)称为系统在时刻t的瞬间分布，一般不容易求得，同时，由于排队系统运行一段时间后，其状
12、态和分布都呈现出与初始状态或分布无关的性质，称具有这种性质的状态或分布为平稳状态或平稳分布。 排队论一般更注意研究系统在平稳状态下的性质。,2019/10/3,30,排队系统在平稳状态时一些基本指标： Pn :系统中恰有n个顾客的概率； Ls：系统中顾客数的平均值，又称为平均队长； Lq：系统中正在排队的顾客数的平均值，又称为平均 排队长； T：顾客在系统中的逗留时间；,Ws =E(T) ：顾客在系统中的平均逗留时间； Tq：顾客在系统中的排队等待时间； Wq=E(Tq)：顾客在系统中的平均排队等待时间。,2019/10/3,31,Little 公式,其中 是单位时间内到达的平均顾客数； 是单
13、位时间内可以服务完的平均顾客数。,系统中平均顾客数 = 单位时间内到达的平均顾客数平均逗留时间,又,如果求得Pn ,则 即可得到。 另外 1-P0 是系统的忙期概率。,2019/10/3,32,排队论研究的基本问题： 通过研究主要数量指标在瞬时或平稳状态下的概率分布及数字特征，了解系统运行的基本特征。 统计推断问题：建立适当的排队模型是排队论研究的第一步，建立模型过程中，系统是否达到平稳状态的检验；顾客相继到达时间间隔相互独立性的检验，服务时间的分布及有关参数的确定等。,2019/10/3,33,排队研究的基本问题： 系统优化问题：又称为系统控制问题或系统运营问题，其基本目的是使系统处于最优的
14、或最合理的状态。包括：最优设计问题和最优运营问题。,2019/10/3,34,2 输入与服务时间的分布,一、最简单流 1、定义; 在时长为 t 的时间段内，有k个顾客到达的概率 服从poisson分布： t时段内平均到达顾客数；,单位时段内平均到达顾客数,2019/10/3,35,2、最简单流的性质 （1）平稳性：在一定时间间隔内，有k个顾客到达的概率只与时长有关，与起始时刻无关； （2）无后效性：a,a+t时段内有k个顾客到达的概率与a时刻之前的客流无关； （3）普通性：在足够小的时段内有2个或个以上顾客到来的概率为零。 说明：1、最简单流的性质可以简化有关计算； 2、假设所研究的问题都是最
15、简单流，或近似最简单流,2019/10/3,36,二、最简单流的有关计算 1、单位时间内到达的顾客数 2、 内没有顾客到达的概率 3、 恰有一个顾客到达的概率 4、若顾客到达数 poisson分布，则相继到达间隔时 间 负指数分布,2019/10/3,37,三、服务时间 设服务时间 负指数分布 1、单位时间内服务完毕，离去的顾客数 2、 内没有顾客离去的概率 3、 恰有一个顾客离去的概率 4、若干负指数分布的最小值也是负指数分 说明： 服务机构中有s个并联服务台，各台 负指数分布，则整个服务时间 负指数分布。,2019/10/3,38,第38页,生灭过程,2019/10/3,39,第39页,2、t时刻有n-1个顾客， 时刻系统中有n个顾客的概率为,1、t时刻有n个顾客， 时刻系统中仍有n个顾客的概率为,时刻系统中有n个顾客的概率,3、t时刻有n+1个顾客， 时刻系统中有n个顾客的概率为,4、t时刻为n,n-1,n+1个顾客之外的情况， 时刻系统中有n个顾客的概率为,2019/10/3,40,第40页,于是,特别的，n=0时,2019/10/3,41,第41页,移项求极限，得差分微分方程,时,平稳状态,推导过程见书P260,2019/10/3,42,
