1、排队模型及其应用,中北大学理学院数学学科,张 峰,数学建模暑期培训系列讲座,内 容 提 纲,排队系统的优化,1 排队模型简介 （背景）,超市排队,为什么不多开个窗口,银行排队,1 排队模型简介 （背景）,服务效率忒低,购票排队,哥 要 回 家,1 排队模型简介 （背景）,高速公路车辆排队,Where is the toilet?,1 排队模型简介 （背景）,壮哉！,购票排队,1 排队模型简介 （背景）,呼叫中心排队,1 排队模型简介 （背景）,9,为什么会出现排队现象？,假定每小时平均有4位顾客到达，服务人员为每位顾客的平均服务时间为15分钟。如果顾客到达的间隔时间正好是15分钟，而服务人员为
2、每位顾客的服务时间也正好是15分钟，那么，就只需要一名服务人员，顾客也根本用不着等待。在以下情况将出现排队现象： 平均到达率高于平均服务率顾客到达的间隔时间不一样（随机） 服务时间不一样（随机）,1 排队模型简介 （基本概念）,排队论(Queuing Theory)，又称随机服务系统是一门研究拥挤现象(排队、等待)的科学。具体地说，它是在研究各种排队系统概率规律性的基础上，解决相应排队系统的最优设计和最优控制问题。,每个顾客的等待时间多长？,选择哪个队列时间最短？,多开一个窗口？顾客消费收入与超市成本之间博弈怎样设计最优 ；最优运行（）,排队模型简介,1 排队模型简介 （基本概念）,一、排队模
3、型的描述,相似的特征及数学抽象,顾客到达系统的时刻是随机的，为每一位顾客提供服务的时间是随机的，因而整个排队系统的状态也是随机的，因此排队论又称为随机服务系统,顾客-请求服务的人或者物,服务员或服务台-为顾客服务的人或者物,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,排队系统一般有三个基本组成部分： 1.输入过程；2.排队规则；3.服务机构,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,1.输入过程,顾客是按怎样的规律到达排队系统的过程，有时也把它称为顾客流,（1）顾客总数 有限 无限？,（2）到达方式 单个
4、 成批？,（3）顾客流的概率分布族 相继到达的顾客间的概率分布,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,2. 排队规则,服务台以怎样的顺序和方式服务顾客,（1）损失制 如果顾客到达排队系统时，所有服务台都已被先来的 顾客占用，那么他们就自动离开系统。,（2）等待制 当顾客来到系统时，所有服务台都不空，顾客加入排队 行列等待服务 FCFS LCFS PR RO,（3）混合制 等待制与损失制的混合 一般是指允许排队，但又不 允许队列无限长下去,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,3. 服务机构,（1
5、）服务台数量及构成方式 单服务台 多服务台；,（2）服务方式 单个服务，批量服务；,（3）服务时间的概率分布 服务过程是泊松过程？高斯过程？ 一个顾客的服务时间是指数分布还是一般概率分布？,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,3. 服务机构 （结构）,单队多服务台并联 例如 学校内的一些小超市,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,3. 服务机构 （结构）,单队多服务台并联 （银行排队）,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,3. 服务机构 （
6、结构）,多队多服务台并联 大型超市、火车站窗口、医院窗口、 高速公路收费、 多车道路口车辆通行等,排队模型简介,1 排队模型简介 （基本概念）,一、排队模型的描述（组成）,基本排队过程,3. 服务机构 （结构）,单队列多服务台串联 柔性制造业 产品按工序加工,排队模型简介,1 排队模型简介 （基本概念）,二、建模过程及主要指标,建模步骤：1 排队系统的统计推断,确定或拟合排队系统顾客到达的时间间隔分布和服务时间分布。,2 模型的性态,在确定模型的基础上，求解主要性能指标，如队长分布、等待时间分布。,3 模型进行优化,系统的最优设计（参数选择，服务质量评价）如机场跑道数量，呼 叫中心坐席量。 已
7、有系统的最优控制 如从顾客和服务机构双方利益出发，对排队系统进行最优控制,排队模型简介,1 排队模型简介 （基本概念）,二、建模过程及主要指标,主要指标：1 队长: 系统中的顾客数, 平均队长LS,等待队长 : 系统中排队等待服务的顾客数, 平均等待队长Lq,一般情形，Ls(或Lq)越大，说明服务效率越低。,排队模型简介,1 排队模型简介 （基本概念）,二、建模过程及主要指标,主要指标：,2. 逗留时间:一个顾客在系统中的停留时间,平均逗留时间 WS,等待时间: 一个顾客排队等待的时间,平均等待时间Wq,显然，Ws(或Wq)越大，顾客满意度越低。,排队模型简介,1 排队模型简介 （基本概念）,
8、二、建模过程及主要指标,主要指标：,3. 忙期：从顾客到达空闲服务机构起到服务机构再次为空闲这段时间长度。可以衡量服务机构效率的指标，及工作强度,4. 绝对通行能力：单位时间内被服务完的平均顾客数,5. 相对通行能力：单位时间内被服务完顾客数与请求服务的顾客数之比,6. 平均被占服务台数 7 损失率,排队模型简介,1 排队模型简介 （基本概念）,三、排队模型应用,1 排队论在通信领域的应用,从20世纪60年代至今对业务突发性和带有各种网络协议控制的通信系统进行性能评价、仿真及模拟。,20世纪初期 主要研究应用于电话网和远程通信系统等无队列的排队系统(损失制),20世纪中期 主要研究通信系统中有
9、队列(等待制)的排队系统和排队网络,排队模型简介,1 排队模型简介 （基本概念）,三、排队模型应用,2 排队论在资源分配问题中的应用 2005 研究生建模 出租车最佳数量预测,20002005 智能地雷反坦克研究，灭火兵力部署,19902000 码头与船舶的分配，工程土方的创新，停车场面积的计算，图书馆信息处理,20052010 公厕建筑面积的分配，教务处教务员岗位确定 新的前沿应用 社交网络性能 评估 云计算性能指标估计等,1 排队模型简介,三、排队模型应用,3 排队论在医疗领域中应用 2009眼科医院病床合理安排,提高医疗体系的服务效率，提高资源利用率，提高病人满意度以及缓解患者于医院之间
10、的矛盾；提出了一些具体的优化标准如下： 1、以费用作为优化指标计算最优目标值条件下最优的服务水平：总费用= 排队损失费+ 服务费 2、“优先权选择或等级”来优化医院服务 （眼科医院病床） 3、构造合理的调度方式来进行优化 4、建立了“预留病床模型，逐步优先权就诊模式”,1 排队模型简介,三、排队模型应用,排队论在交通领域中应用 2013年 A题 车道被占用对城市道路通行能力的影响,（1） 研究公交车发车间隔与排队长度（2）研究停车场的车辆排队（3）研究车辆排队现象、车辆延误 路口通行能力分析5 排队论在银行中应用,2 排队模型经典排队模型,一 单服务台 排队模型,1 标准的 模型,2 模型条件
11、,模型 表示，顾客到达过程服从泊松分布，服务时间服从负指数分布，单服务台，队长和顾客来源无限.简记为 .,1）已知单位时间平均到达率 和平均服务率 . 2）系统容量无限，顾客源总数无限. 3）排队规则为单队，先到先服务,2 排队模型经典排队模型,一 单服务台 排队模型,3 模型的求解,研究系统状态的概率- 系统中顾客数。状态概率用Pn(t)表示,即在t时刻系统中有n个顾客的概率，也称瞬态概率。,实际中更关心 稳态概率,稳态概率求法 马尔科夫链理论 母函数 递推等,稳态概率求解步骤 1 画出稳态概率转移图,2 列出稳态概率平衡方程组,3 求出稳态概率或者母函数,2排队模型经典排队模型,一 单服务
12、台 排队模型,系统在稳定情况下的状态转移如图,图1.1,可以得到如下平衡方程：,4 稳态概率公式,2 排队模型经典排队模型,一 单服务台 排队模型,5 模型的数量指标公式,由（1.1）和（1.2）可以递推求解，,式中 表示平均到达率与平均服务率 之比，称为服务强度.,2 排队模型经典排队模型,一 单服务台 排队模型,6 模型的性能指标,2 排队模型经典排队模型,一 单服务台 排队模型,4）一位顾客花在系统里的平均逗留时间,5）一位顾客花在排队上的平均时间（等于逗留时间减去服 务时间）6）顾客到达系统时，得不到及时的服务，必须等待服务的 概率7）系统里正好有 个顾客的概率,6 模型的性能指标,2
13、 排队模型经典排队模型,一 单服务台 排队模型 应用举例,库存问题 进货多，保管费用大；存货不足缺货会引起经济损失，假设货物需求量是参数为 的泊松过程，生产一个产品实际是参数为 的指数分布，单位时间库存费用c元，缺货一个产品损失为h元，确定最优库存使得库存费和损失费之和达到最小.,分析 将生产厂看成服务机构，需求看成输入流 M/M/1 排队,平均缺货数,平均库存数,2 排队模型经典排队模型,一 单服务台 排队模型 应用举例,分析 将生产厂看成服务机构，需求看成输入流 M/M/1 排队,单位时间总费用,由边际分析法,由边际分析法,最佳s满足,36,例,一个码头，设待卸货船到达时间间隔服从负指数分
14、布，平均到达 2 艘/小时；服务台是1台吊车，卸货时间服从负指数分布，平均每 20 分钟可卸一艘货船，当被占用时，新到货船只能停在码头等待。求在平稳状态下码头上货船的平均数；等待卸货船只的平均数；每艘货船在码头的平均停留时间；货船平均需等待多长时间可以开始卸货。,2 排队模型经典排队模型,37,解：,这是一个典型的M/M/1排队问题,2 排队模型经典排队模型,38,例,某医院手术室根据病人就诊和完成手术时间的记录，任意抽查100个工作小时，每小时来就诊的病人数n的出现次数如表6所示。又任意抽查了100个完成手术的病例，所用时间t出现的次数如下表所示。试分别用公式、excel和仿真求解：,2 排
15、队模型经典排队模型,39,到达病人数,手术时间,2 排队模型经典排队模型,40,解：,这也是一个M/M/1排队问题 （1）计算平均到达率,平均手术时间,平均服务率,2 排队模型经典排队模型,41,（2）取=2.1，=2.5，通过统计检验方法认为病人到达数服从参数为2.1的泊松分布，手术时间服从参数为2.5的指数分布。,（3）服务设备利用率,这说明服务机构（手术室）有84%的时间是繁忙的（被利用），有16%的时间是空闲的。,42,（4）依次带入公式，算出各指标得：,43,单通道Excel求解,2 排队模型经典排队模型,二 多服务台 排队模型,1 标准的 模型,2 模型描述,模型 表示，顾客到达过
16、程服从泊松分布，服务时间服从负指数分布，C 个服务台，队长和顾客来源无限.,已知单位时间平均到达率 ， C 个服务台，每个服务台的工作相互独立且平均服务率相同，都等于 ，顾客源无限，容量无限，排队规则为等待制,3.系统的状态概率和主要运行指标,(1) 系统的状态概率 系统的空闲概率,4 系统的状态概率和主要运行指标,系统内有n个顾客的概率,2 排队模型经典排队模型,二 多服务台 排队模型,4 主要运行指标,系统平均队长、平均等待时间,平均占用服务台数,系统通行能力,损失率,系统相对通过能力,系统绝对通过能力,48,例,某售票所有三个窗口，顾客的到达服从泊松分布，平均到达速率 = 0.9人/mi
17、n；售票时间服从负指数分布，平均服务速率= 0.4人/min 。现设顾客到达后排成一队，依次向空闲的窗口购票，如图所示。试分别用公式、excel和仿真求解： (1) 整个售票所空闲概率 (2) 平均队列长和平均队长 (3)平均等待时间和逗留时间 (4)顾客到达后必须等待的概率（n3),2 排队模型经典排队模型,49,顾客到达和服务图,2 排队模型经典排队模型,50,解：,这是一个典型的M/M/C 排队问题,(1) 整个售票所空闲概率,2 排队模型经典排队模型,51,(2) 平均排队长度和平均队列长,(3)平均等待时间和逗留时间,2 排队模型经典排队模型,52,(4)顾客到达后必须等待的概率（n
18、3),2 排队模型经典排队模型,53,M/M/3 Excel求解,54,例 银行取号系统有用吗？,就例5，如果其他条件不变，顾客到达后在每个窗口前各排一队，且进入队列后坚持不换，就形成3个队列，如下图所示。试分别用公式、excel求解： (1) 整个售票所空闲概率 (2) 平均队列长度和平均队长 (3) 平均等待时间和逗留时间 (4)顾客到达后必须等待的概率（n3),2 排队模型经典排队模型,55,顾客到达和服务图,2 排队模型经典排队模型,56,解：,这是3个M/M/1同时服务的排队问题,(1) 整个售票所空闲概率(每个窗口空闲),(4)顾客到达必须等待的概率（每个窗口n1),2 排队模型经
19、典排队模型,57,(2) 平均排队长度和平均队列长,(3)平均等待时间和逗留时间,2 排队模型经典排队模型,58,3个M/M/1 Excel求解,2 排队模型经典排队模型,59,结论：银行取号系统是有效的,2 排队模型经典排队模型,二 多服务台 排队模型,眼科医院病床安排,2 排队模型经典排队模型,眼科医院病床安排,简单而言：每一类病人应安排多少床位,2 排队模型经典排队模型,眼科医院病床安排,2 排队模型经典排队模型,眼科医院病床安排,2 排队模型经典排队模型,二 多服务台 排队模型,车道被占用对城市道路通行能力的影响,1 根据视频1（附件1），描述视频中交通事故发生至撤离期间,事故所处横断
20、面实际通行能力的变化过程。2 根据问题1所得结论，结合视频2（附件2），分析说明同一横断面交通事故所占车道不同对该横断面实际通行能力影响的差异。,2 排队模型经典排队模型,二 多服务台 排队模型,车道被占用对城市道路通行能力的影响,2 排队模型经典排队模型,二 多服务台 排队模型,车道被占用对城市道路通行能力的影响,67,排队系统最优设计成本分析 1 概述,排队系统的最优设计和最优控制，即排队系统的最优化问题，其目的在于使排队系统达到最大效益或者说在一定指标下使排队系统最为经济。,3 排队模型排队模型的优化,68,服务成本与等待成本的权衡（成本效益平衡）,排队分析的目的是使顾客等待成本与服务能
21、力成本这两项成本之和最小,3 排队模型排队模型的优化,69,M/M/1模型中的最优服务率u,最佳服务能力是使总成本最小化：,总成本=顾客等候成本+服务能力成本,3 排队模型排队模型的优化,70,M/M/1模型中的最优服务率u,所以M/M/1模型的最优服务率为：,3 排队模型排队模型的优化,71,例,设某服务机构，单服务台，顾客到达率为每小时12位顾客。假定每位接受顾客的顾客其等待费用为每小时5元，服务成本为每位顾客2元，欲使总平均费用最小，服务率应为多少？,3 排队模型排队模型的优化,72,解：,这是一个标准的M/M/1排队问题,3 排队模型排队模型的优化,73,、Lq 、Ls三者的关系-1,
22、当系统利用率增加时，队列平均等候数与顾客排队等候的平均时间呈指数增长。,3 排队模型排队模型的优化,74,、Lq 、Ls三者的关系-2,3 排队模型排队模型的优化,75,、Lq 、Ls三者的关系-3,平均队长（和平均等待时间）与服务台利用率之间的关系不是线性的关系。资产利用率太高会造成服务质量急速下降，因而要权衡利弊。要保证服务质量，就必须保持“过剩的”生产或服务能力。,3 排队模型排队模型的优化,76,M/M/C模型中最优服务台数C,仅讨论标准的M/M/C模型，且在稳态下，单位时间全部费用的期望值为：(包括服务成本与等待费用),式中: 每个服务台单位服务时间成本；每个顾客在系统中停留单位时间
23、成本；L系统中顾客的平均数Ls或队列平均数Lq，是C的函数。 这里Z是C的函数,且C只能取整数解,故不能用微分法求C*, 而只能用边际分析法(Marginal Analysis)：,3 排队模型排队模型的优化,77,因为 z(c*) 是最小值，则有：,将z期望费用公式代入：,合并化简得：,依次求C=1,2,3，的 L值，即可找出符合上式的C*。,78,例6某检验中心，为各用户检验产品，用户每天到达按泊松流=48个/天，每个用户每天停工损失6元，服务时间服从负指数分布=25个/天，每设1个检验台每天服务成本4元，其他条件为标准M/M/C模型，问设几个服务台费用最少？ 解： =4元 Cw=6=48
24、 =25,下面再分别计算当服务台C=1,2,3,时Ls值。计算过程如下：,79,计算 L(C*)-L(C*+1)及 L(C*-1)-L(C*)c=1 -c=2 18.930 （相当于无穷）c=3 0.612 18.930 c=4 0.116 0.612,（见陆书239页队长表达式）,系统容量有限的 模型,系统容量为N，系统中排队等待的顾客数最多为N-1，所以在某一时刻某位顾客到达时，如果系统中已有N位顾客，那么这位顾客被拒绝进入系统，如图2.2,由状态转移图，可以建立系统概率平衡方程如下：,4 排队模型推广,系统容量有限的 模型,模型的各数量指标参数如下：1）系统里没有顾客的概率,4 排队模型
25、推广,系统容量有限的 模型,2）系统里有n个顾客的概率,3）在系统里的平均顾客数,4）平均排队的顾客数,4 排队模型推广,顾客源有限的 模型,由状态转移图，可以建立系统概率平衡方程如下：,以机器维修问题为例：设有m台机器（顾客总体）,每台机器单位时间内发生故障的概率 相同（顾客平均到达率），等待修理及正在修理的机器数为n，工人数为1（单服务台），则对系统的有效到达率 为,4 排队模型推广,顾客源有限的 模型,用递归方法解上述方程组得，,模型中各数量指标：,4 排队模型推广,85,系统容量有限制的情形 （M/M/C/N/）损失制,设系统的容量最大限制为N(C）,当系统中顾客数n已达到N（即队列中
26、的顾客数已达N-C）时，再来的顾客将被拒绝，其他条件与标准的M/M/C型相同。此时的状态概率为：,4 排队模型推广,86,其中：,运行指标为：,4 排队模型推广,87,顾客源为有限的情况 （M/M/C/M）,设顾客源为有限m,且mc，顾客到达率是按每个顾客考虑的。在机器维修模型中就是有m台机器，C个修理工，机器故障率就是每个机器单位运转时间出故障的期望次数，系统中顾客数n就是出故障的机器台数。当nC时，无排队，有c-n个修理工空闲；当cnm时，有（n-c）台机器停机等待修理，系统处于繁忙状态。假定：(1)每个服务台速率均为的负指数分布，（2）故障修复时间与正在生产的机器是否发生故障是相互独立的，则有：,4 排队模型推广,88,4 排队模型推广,4 排队模型推广,在柔性制造系统、电子商务、计算机及通信系统中，系统会对服务设备进行定期保养和维护。维护常常在系统闲期进行。维护时间视为服务员正在休假。,休假排队模型,特点：服务设施在服务完毕后进入休假状态,4 排队模型推广,优先权排队模型,可修排队模型,特点：服务设施在服务过程中可以发生故障，修好后继续为顾客服务,假设系统中顾客分成两类 先服务具有优先权的顾客,4 排队模型推广,重试排队模型,负顾客排队模型,特点：系统中负顾客可以抵消正常顾客,
