服务系统规划(运筹学)课件

第九章第九章服务系统规划第第11章章排排队队论论29.19.1 基本概念基本概念 一。现实生活中的排队现象一。现实生活中的排队现象一。现实生活中的排队现象一。现实生活中的排队现象 排队、顾客、服务台排队、顾客、服务台 服务系统、服务系统、排队系统排队系统排队系统排队系统 到达时刻到达时刻、等待时间等待时间等待时间等待时间、排队系统排队系统排队系统排队系统顾客源顾客源顾客源顾客源等待队列等待队列等待队列等待队列(输入输入)服务台服务台服务台服务台(输出输出)离去离去 到达到达 到到 达达开开开开 始始始始服服服服 务务务务离离 去去离去时刻离去时刻等待时间等待时间等待时间等待时间服务时间服务时间服务时间服务时间逗留时间逗留时间逗留时间逗留时间t服务服务服务服务时间时间时间时间、逗留时间逗留时间逗留时间逗留时间表9-1 现实中的各种服务系统顾客服务内容服务台考生报名登记招考登记员病人诊断病情医生电话呼叫通话交换台驶入港口的货船装（卸）货装（卸）货码头（泊位）文件稿打字打字员提货单提取存货仓库管理员不能运转的机器修理修理技工上游河水进入水库放水，调整水位水闸管理员进入我方阵地的敌机我方高射炮进行射击我方高射炮第第11章章排排队队论论49.19.1 基本概念基本概念二、二、二、二、排排排排队队系系系系统统的的的的三个基本特征三个基本特征三个基本特征三个基本特征(1)输入过程输入过程：指顾客按怎样的规律到达，顾客指顾客按怎样的规律到达，顾客源情况如何；源情况如何；(2)排队规则排队规则：指顾客在排队系统中按怎样的规指顾客在排队系统中按怎样的规则与次序接受服务；则与次序接受服务；(3)服务机构服务机构：指同一时刻服务台能容纳多少顾指同一时刻服务台能容纳多少顾客以及为任一顾客服务的时间服客以及为任一顾客服务的时间服从什么规律。从什么规律。1.输入入过程程 顾客的客的总体（体（顾客源）的客源）的组成可能是有限的，也可成可能是有限的，也可能是无限的。能是无限的。顾客到来的方式可能是一个一个的，也可能是成批客到来的方式可能是一个一个的，也可能是成批的。的。顾客相客相继到达的到达的间隔隔时间可以是确定型的，也可以可以是确定型的，也可以是随机型的。是随机型的。顾客的到达可以是相互独立的客的到达可以是相互独立的,否否则就是有关就是有关联的的 输入入过程可以是平程可以是平稳的，或称的，或称对时间是是齐次的，是次的，是指描述相指描述相继到达的到达的间隔隔时间分布和所含参数（如期分布和所含参数（如期望望值、方差等）都是与、方差等）都是与时间无关的，否无关的，否则称称为非平非平稳的。的。第第11章章排排队队论论69.19.1 基本概念基本概念 (1)定长输入定长输入：顾客严格按照固定的间隔时间顾客严格按照固定的间隔时间相继到达。相继到达。(2)泊松输入泊松输入：顾客到达过程为顾客到达过程为泊松流泊松流。(3)爱尔朗输入爱尔朗输入：相继到达间隔时间相互独立相继到达间隔时间相互独立且具有相同参数的爱尔朗分布。且具有相同参数的爱尔朗分布。(4)一般独立输入一般独立输入：相继到达间隔时间相互相继到达间隔时间相互独立独立且同分布。且同分布。几种常见的输入过程几种常见的输入过程第第11章章排排队队论论79.19.1 基本概念基本概念 先到先服务先到先服务：后到先服务后到先服务：随机服务随机服务：有优先权服务有优先权服务：二二、排队规则排队规则(1)即时制即时制(损失制损失制)(2)等待制等待制 系统容量有限系统容量有限：等待时间有限等待时间有限：逗留时间有限逗留时间有限：(3)混合制混合制最普通最普通手枪射击手枪射击车船卸货车船卸货停车场停车场电话呼叫电话呼叫生产线上产品抽样检验生产线上产品抽样检验加急电报加急电报特诊患者特诊患者某些诊室每天挂号有限某些诊室每天挂号有限商店食品商店食品药房药品药房药品出炉铁水出炉铁水来犯敌机来犯敌机第第11章章排排队队论论89.19.1 基本概念基本概念 121s (a)单队单队单台系统单台系统(b)单队单队多台（并联）系统多台（并联）系统(c)单队单队多台（串联）系统多台（串联）系统3.服服务机构机构常见的几种排队系统的结构如图所示常见的几种排队系统的结构如图所示1s第第11章章排排队队论论99.19.1 基本概念基本概念 12s(d)多队多队多台（并联）系统多台（并联）系统(e)多队多队多台（混联、网络）系统多台（混联、网络）系统第第11章章排排队队论论109.19.1 基本概念基本概念 几种常见的随机服务过程几种常见的随机服务过程(1)定长服务定长服务：为各顾客服务的时间是相同常数为各顾客服务的时间是相同常数(2)指数服务指数服务：为各顾客服务的时间相互独立：为各顾客服务的时间相互独立且具有相同参数的指数分布。且具有相同参数的指数分布。(3)爱尔朗服务爱尔朗服务：各顾客服务时间相互独立：各顾客服务时间相互独立且具有相同参数的爱尔朗分布。且具有相同参数的爱尔朗分布。(4)一般独立服务一般独立服务：各顾客服务时间相互独立：各顾客服务时间相互独立且同分布。且同分布。第第11章章排排队队论论119.19.1 基本概念基本概念三、三、三、三、排排排排队论队论的的的的问题问题及分及分及分及分类类1 1、排队论的问题、排队论的问题 (1)性态问题：性态问题：(2)统计问题统计问题：(3)优化问题优化问题：2 2、排队系统的分类、排队系统的分类将Kendall符号扩充为以下标准形式：X/Y/Z/A/B/C或者X/Y/Z:A/B/C例如：例如：M/M/s/r/M/EM/Ek k/1/1/稳态系统稳态系统稳态系统稳态系统统计分析统计分析统计分析统计分析优化设计优化设计优化设计优化设计优化运营优化运营优化运营优化运营第第11章章排排队队论论1211.111.1 基本概念基本概念 L L平均队长平均队长平均队长平均队长任意时刻系统内顾客数的期望值任意时刻系统内顾客数的期望值L Lq q平均等待队长平均等待队长平均等待队长平均等待队长任意时刻系统内等待服务的顾客数的期望值任意时刻系统内等待服务的顾客数的期望值WW平均逗留时间平均逗留时间平均逗留时间平均逗留时间任一顾客逗留时间的期望值任一顾客逗留时间的期望值WWq q平均等待时间平均等待时间平均等待时间平均等待时间任一顾客等待时间的期望值任一顾客等待时间的期望值(1)四项主要性能指标四项主要性能指标四、排队问题的求解四、排队问题的求解第第11章章排排队队论论1311.111.1 基本概念基本概念(2)其他常用数量指标其他常用数量指标 s 系统中并联服务台的数目系统中并联服务台的数目 平均到达率平均到达率平均到达率平均到达率单位时间内到达系统的顾客平均数单位时间内到达系统的顾客平均数平均到达间隔平均到达间隔平均服务率平均服务率平均服务率平均服务率单位时间内服务完毕的顾客平均数单位时间内服务完毕的顾客平均数平均服务时间平均服务时间 服务强度服务强度服务强度服务强度每个服务台单位时间内的平均服务时间每个服务台单位时间内的平均服务时间1 1 第第11章章排排队队论论14 N稳态系统稳态系统稳态系统稳态系统任意时刻的任意时刻的状态状态(顾客总数顾客总数)U U任意顾客在任意顾客在稳态系统稳态系统稳态系统稳态系统中的中的逗留时间逗留时间逗留时间逗留时间QQ任意顾客在任意顾客在稳态系统稳态系统稳态系统稳态系统中的中的等待时间等待时间 Pn=PN=n:稳态系统稳态系统稳态系统稳态系统任意时刻任意时刻状态为状态为n的的概率概率；特别当特别当n=0时，时，即为即为P0，而，而P0即即稳态系统稳态系统稳态系统稳态系统所有服务台全部空闲所有服务台全部空闲的的概率概率概率概率。e e e e 有效平均到达率有效平均到达率有效平均到达率有效平均到达率单位时间内到达单位时间内到达并且进入并且进入系统的顾客平均数系统的顾客平均数；对于对于等待制等待制等待制等待制的排队系统，有的排队系统，有 e e e e =。第第11章章排排队队论论15稳态系统稳态系统稳态系统稳态系统：假定：假定 为常数，则有为常数，则有李特尔公式李特尔公式：假定假定 为常数，则有为常数，则有(11-1a)(11-1b b)(11-1c c)(11-1d d)(11-2)(11-3)L =WeLq=Wqe1W=Wq +L=Lq +e还有还有L=nPnn=0 Lq=(n-s)Pn=nPs+mn=sn=0第第11章章排排队队论论169.29.2 排队系统的常用分布排队系统的常用分布 一一、泊松过程、泊松过程 设以设以X(t)表示在表示在0,t时段内到达排队系统的顾客数时段内到达排队系统的顾客数,则对于每个给定的时刻则对于每个给定的时刻t,X(t)都是一个随机变量都是一个随机变量,而而X(t)|t0,)就是一个就是一个随机过程随机过程。(1)无后效性无后效性对任意时刻对任意时刻 (0,)，在时段在时段 ,+t内到达的顾客内到达的顾客数，与数，与 时刻以前到达的顾客数无关，即时刻以前到达的顾客数无关，即 时刻以前到达的时刻以前到达的顾客数不影响其后到达的顾客数。这意味着：在不相交的顾客数不影响其后到达的顾客数。这意味着：在不相交的各时段内到达的顾客数相互独立。各时段内到达的顾客数相互独立。第第11章章排排队队论论17(2)平稳性平稳性 在长度为在长度为 t 的时段内恰好到达的时段内恰好到达k个顾客的概率，仅个顾客的概率，仅跟长度跟长度 t 有关，而跟这段的起始时刻无关。即对任意有关，而跟这段的起始时刻无关。即对任意时刻时刻 (0,)，在，在(,+t 或或(0,t内内恰好到达恰好到达k个个顾客顾客的概率的概率相等相等相等相等：P X(+t)-X(t)=k=P X(t)-X(0)=k =P X(t)=k =gk(t)(3)普通性普通性：在充分小的时段内最多到达一个顾客。在充分小的时段内最多到达一个顾客。第第11章章排排队队论论18 泊松过程泊松过程具有具有无后效性无后效性无后效性无后效性，因而是一种特殊的，因而是一种特殊的马尔科夫马尔科夫马尔科夫马尔科夫过程过程过程过程。泊松过程泊松过程又称又称泊松流泊松流泊松流泊松流，在排队论中常称为，在排队论中常称为最简单流最简单流。性质性质1 设设X(t)|t 0，)为泊松过程，为泊松过程，0为平均到达为平均到达率，则率，则X(t)服从参数为服从参数为 的泊松分布的泊松分布，即有即有 E EX(t)=t =E EX(t)/t 按概率论，有按概率论，有则有则有(t)kn!Pn(t)=e-t k=0,1,2,(11-4)第第11章章排排队队论论19 性质性质2 顾客到达过程顾客到达过程X(t)是一个具有参数是一个具有参数 的泊松流的的泊松流的充要条件充要条件是：相继到达间隔是：相继到达间隔Tk是一族相互独立的随机是一族相互独立的随机变量，且每个随机变量变量，且每个随机变量Tk都具有下述指数分布函数：都具有下述指数分布函数：FTk(t)=1-e-t,t0 0 ,t 0的密度函数：的密度函数：则称则称Vi服从服从参数为参数为参数为参数为 的的的的指数分布指数分布,有有 FVi(t)=1-e-t，t0 0，t 0E(Vi)=1 D(Vi)=1 2fVi(t)=e-t，t0 0，t 0与与t0都有都有PTs+t|Ts=PTt性质性质2 密度函数密度函数fT(t)对时间t严格格递减减第第11章章排排队队论论23三、爱尔朗分布三、爱尔朗分布若随机变量若随机变量V具有下述密度函数具有下述密度函数:fk(t)=(k)k t k-1(k-1)!e-kt 0t0t 0)=1-p0=1-0.25=0.75第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划计算系统的主要工作指标：此模型的平均有效到达率，即是到达率第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划为使车辆平均逗留时间不超过半小时，车辆经过车道的平均时间应减少到多少？由于将=3代入上式解得：5车辆经过车道的平均时间为即车辆经过车道的平均时间至少应减少3分。第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划练：汽车按泊松流到达某高速公路收费口，平均每小时90辆。每辆车通过收费口的时间服从均值35秒的负指数分布。（1）在收费口有多于2辆车排队等待的概率是多少？（2）因司机们抱怨等待时间太长，管理部门拟采用自动收款装置使平均收费时间缩短到30秒，但条件是原收费口平均等待车辆超过6辆，且新装置的利用率不低于75时才采用，问新装置能否被采用？解：这是解：这是M/M/1排队模型。排队模型。（1）=90（辆（辆/小时），原收费口平均服务小时），原收费口平均服务u=3600/35（辆（辆/小时），小时），=/u=0.8751。在原收费口有多于在原收费口有多于2辆车排队等待的概率就是系统中有多于辆车排队等待的概率就是系统中有多于3辆车辆车的概率，即等于的概率，即等于1-P0-P1-P2-P3=4=（0.875）4=0.5862（2）原收费口平均等待车辆数为）原收费口平均等待车辆数为Lq=2/（1-）=（0.875）2/（1-0.875）=6.125采用新装置后的平均服务采用新装置后的平均服务u=3600/30=120（辆（辆/小时），相应的利用小时），相应的利用率率=/u=90/120=0.75.因此新装置能被采用。因此新装置能被采用。练：某场篮球比赛前来到体育馆某售票口买票的观众按泊松分布到达，平均60人/h，设该售票口售票速度服从指数分布，平均售一张票时间为20秒，试回答：（1）如有一个球迷于比赛前2分钟到达，并设买到票后需要1.5min后才能找到座位坐下，求该球迷在比赛开始前找到座位坐下的概率。（2）如该球迷希望99%的把握在比赛开始前找到座位坐下，则他至少应提前多少分钟到达售票口。二、系二、系统的容量有限的情况的容量有限的情况（M/M/1/N/）若系统的最大容量为N，对于单服务台的情形，排队等待的顾客最多为N-1，在某时刻一顾客到达时，如果系统中已有N个顾客，那么这个顾客就被拒绝进入系统（如图9-4）。第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划图9-4 有容量限制的情形当N=1时，为即时制的情形；当N，为容量无限制的情形。若只考虑稳态的情形，各状态间概率强度的转换关系如图9-5。第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划图9-5状态间概率强度的转换关系根据图9-5列出状态概率的稳态方程：解此方程与解（9-18）与（9-19）是相似的，不同的是令，得第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划对于的取值略去=1情形的讨论。当容量没有限制时，设1，这既是实际问题的需要，也是无穷级数收敛所必需的。当系统容量为有限数N时，此条件就是多余的。第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划关于有效到达率e当研究顾客在系统平均逗留时间Ws和队列中平均等待时间Wq时，尽管（9-22）式仍可利用，但要注意平均到达率是在系统中有空时的平均到达率，当系统已满(n=N)时，则到达率为0，因此需要求出有效到达率e=(1-PN)可验证：,即e=(1-P0)第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划根据（9-25）可以得出以下指标：(1)队长（期望值）(2)队列长（期望值）(3)顾客逗留时间（期望值）(4)顾客等待时间（期望值）第三节：单服务台模型第三节：单服务台模型第九章第九章服务系统规划服务系统规划此模型系统的性能指标（当1时）第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划例9-2集装箱堆场的某作业集装箱泊位共7个。当7个处理台都满时，后来到的集装箱不进入该作业线。集装箱的平均到达率为3个/分钟，处理一个集装箱平均需要15分。解：则N=7为系统中最大的顾客数，=3个/小时，=4个/小时。(1)由题意知，模型为（M/M/1/N/）先确定参数：由题意知，服务强度=/=3/4=0.75(2)求某集装箱一到达就能进行作业的概率。这种情形相当于作业线内没有集装箱，所求概率第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划(3)求作业线上集装箱的期望值；需要等待的集装箱的期望值(4)求有效到达率ee=(1-P0)=4*(1-0.2778)=2.89(个小时)(5)求一集装箱在作业线内逗留的期望时间；等待时间(6)在可能到来的集装箱进入其它作业线的概率(Pn7)。这就是求作业线内有7个集装箱的概率第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划练：一个有一套洗车设备的洗车店，要求洗车的车辆平均每4分钟到达一辆，洗每辆车平均需要3分钟，以上均服从指数分布。该店现有两个车位，当店内无车时，到达车辆全部进入，当有一辆车时，只有80%进入，当有两辆车时，新到达车辆因无空位而全部离去。试问：（1）对此排队系统画出生灭过程发生率图。（2）求洗车设备平均利用率，及一辆进入该店的车辆在店内的平均逗留时间。（3）为减少顾客流失，店里拟扩大租用第3个车位，这样当店内已有2辆车时，到达车辆有60%进入，有3辆车时，新到达车辆仍全部离去。经计算当租用第3车位时，该洗车店内有n辆车的概率如下P0=0.416,P1=0.312,P2=0.187,P3=0.085如果如果该车店每天店每天营业12小小时，新，新车位租金每天位租金每天100元，洗一元，洗一辆车的的净利利润5元，元，问第第3个个车位是否位是否值得租用。得租用。三、三、顾客源有限的情形客源有限的情形(M/M/1/m)该模型中，设顾客总数为m，当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源。如此循环往复。模型符号的第4项为，表示系统的容量没有限制，但实际上它决不会超过m，所以跟写成(M/M/1/m/m)的意义相同。典型的有限顾客源问题是机器维修问题。有m台机器在运转，单位时间内平均出现故障的机器数即为顾客平均到达率，修理工修理一台设备的平均时间即为平均服务时间，已修复的机器仍可能再出现故障（如图9-6）。第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划图9-6有限顾客源问题关于平均到达率在无限源的情形是按全体顾客来考虑的；在有限源的情形必须按每个顾客来考虑。为简单起见，设各个顾客的到达率都是相同的（的含义是每台机器单位运转时间内发生故障的概率或平均次数），这时在系统外的顾客平均数为m-Ls，对系统的有效到达率e应为e=(m-Ls)第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划对于此模型的分析依然可以沿用前面的方法。在稳态的情况下，考虑状态间的转移率如图9-7所示。第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划图9-7状态转移根据图9-7列出状态概率的稳态方程：解此差分方程，用递推的方法第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划得系统的各项指标:第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划在机器故障问题中Ls就是平均故障台数，而(m-Ls)表示正常运转的平均台数。第三节第三节 单服务台模型单服务台模型第九章第九章服务系统规划服务系统规划第第11章章排排队队论论62例例5一个工人负责照管一个工人负责照管6台自动机床，当机床需要加料、台自动机床，当机床需要加料、发生故障或刀具磨损时就自动停车，等待工人照管。设发生故障或刀具磨损时就自动停车，等待工人照管。设每台机床平均每小时停车一次，每次需要工人照管的平均每台机床平均每小时停车一次，每次需要工人照管的平均时间为时间为0.1小时。试分析该系统运行情况。小时。试分析该系统运行情况。解解m=6=1(台台/小时小时)=1/0.1=10(台台/小时小时)=0.1L=6-10(1-0.4845)=0.845(台台)工人空闲的概率：工人空闲的概率：停车的机床停车的机床(包括正在照管和等待照管包括正在照管和等待照管)的平均数的平均数 P0 =6!(0.1)k(6-k)!-1=0.4845k=06第第11章章排排队队论论63 L=0.845-(1-0.4845)=0.3295(台台)W=L/(1-P0)=0.845/10(1-0.4845)=0.1639(小时小时)=9.83(分钟分钟)Wq=W 1/=0.1639-0.1=0.0639(小时小时)=3.83(分钟分钟)=Lm=0.8456=14.1%14.1%=1-=100%-14.1%14.1%=85.9%85.9%等待照管的机床平均数等待照管的机床平均数：平均停车时间平均停车时间：平均等待时间平均等待时间:生产损失率生产损失率 机床利用率机床利用率单队、并列的多服务台（服务台数为c）的情形，讨论以下三种情形：(1)标准的M/M/c模型(M/M/c/);(2)系统容量有限制(M/M/c/N/)；(3)有限顾客源(M/M/c/m)。第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划一、一、标准的准的M/M/c模型模型(M/M/c/)标准M/M/c模型的各种特征与标准的M/M/1模型的规定相同。另规定各服务台工作是相互独立的（非协作）且平均服务率相同1=1=c=。因此整个服务机构的平均服务率c（当nc时）；n（当nc时，因为只有c个服务台，最多有c个顾客在被服务，n-c个顾客在等候，因此系统的服务率为c，状态的转移率应为cPn。第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划图9-8多服务台服务系统第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划图9-9多服务台服务系统状态转移第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划由图9-9可得：类似的有Pi=1，且1用递推解差分方程（9-29），求得状态概率：系统的运行指标平均队长平均等待时间和逗留时间（由little公式求得）第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划第第11章章排排队队论论70例例1 某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要每个病人平均需要15分钟。病人按泊松分布到达，平均每小时分钟。病人按泊松分布到达，平均每小时 到达到达3人。人。(1)先确定参数值先确定参数值，有有 s=1 =3(人人/小时小时)=60/15=4(人人/小时小时)故故服务强度服务强度服务强度服务强度为为 =/=3/4=0.750.75 (2)计算计算稳态概率稳态概率稳态概率稳态概率：P0=1-=1-0.75=0.250.25 即即急诊室空闲的概率急诊室空闲的概率,也是病人不必等待立即就能就诊的概率。也是病人不必等待立即就能就诊的概率。而而 病人需要病人需要等待的概率等待的概率等待的概率等待的概率则为则为P(P(QQ0)=1-P0=0.750.75这也就是这也就是急诊室急诊室繁忙的概率繁忙的概率繁忙的概率繁忙的概率。第第11章章排排队队论论71 急诊室内外的急诊室内外的病人平均数病人平均数：急诊室外排队急诊室外排队等待的病人平均数等待的病人平均数：Lq=L =30.75=2.25（人）（人）病人在急诊室外病人在急诊室外平均逗留时间平均逗留时间：病人病人平均等候时间平均等候时间:Wq=W =10.75=0.75（小时）（小时）(3)计算系统计算系统主要工作指标主要工作指标主要工作指标主要工作指标-L=1-W=14-3=1（小时）（小时）34 -3=3（人）（人）第第11章章排排队队论论72 (4)为使病人平均逗留时间不超过半小时，则平均为使病人平均逗留时间不超过半小时，则平均服务时间应减少多少？服务时间应减少多少？由于由于1-W=12 5则平均服务时间为则平均服务时间为15 (小时小时)=12(分钟分钟)1 故故1 15-12=3(分钟分钟)即即平均服务时间至少应减少平均服务时间至少应减少3分钟。分钟。代入代入=3，解得解得第第11章章排排队队论论73 (5)若医院希望候诊的病人若医院希望候诊的病人90%以上都能有座位，则以上都能有座位，则候诊室至少应安置多少座位？候诊室至少应安置多少座位？设应安置设应安置 x 个座位；则加上服务台共个座位；则加上服务台共 x+1 个，有个，有 P(N x+1)=1-P(N x+1)0.9 P(N x+1)0.1 (x+1)+1=x+2 0.1两边取对数两边取对数 (x+2)lg lg 0.1因因 0 0)=P P(NN 2)=(0.75)22!(1-0.375)115 0.20另外还常采用另外还常采用顾客时间损失系数顾客时间损失系数=WqE(V)来评估服务质量。来评估服务质量。第第11章章排排队队论论76指指标标S=1系统系统S=2 2系统系统P00.250.45P(QQ0)0.750.20Lq2.25人人0.12人人L3人人0.87人人W60分钟分钟17.4分钟分钟Wq45分钟分钟2.4分钟分钟 33倍倍倍倍16%16%两个系统的比较两个系统的比较.二、系二、系统容量有限的情形容量有限的情形(M/M/c/N/)设系统的容量最大限制为N(Nc)，当系统中顾客数n已到达N（即队列中顾客数已达(N-c)时），以后到达的顾客将被拒绝，其余条件与标准的M/M/c模型相同。此时系统的状态概率:其中（不必对加以限制）第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划系统的运行指标：由于公式复杂，现有一些专门的图表可供查阅。第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划当N=c（即时制）的情形，典型的例子是街头的停车场就不允许排队等待空位。有：当n=c时，即关于Pc的公式，被称为爱尔朗呼唤损失公式，是A.K.Erlang早在1917年发现的，并广泛应用于电话系统的设计中。此时系统的运行指标：第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划第第11章章排排队队论论80 例例4某街口汽车加油站可同时为两辆汽车加油，同时某街口汽车加油站可同时为两辆汽车加油，同时还可容纳三辆汽车等待，超过此限则不能等待而消失。还可容纳三辆汽车等待，超过此限则不能等待而消失。汽车到达间隔与加油时间均为指数分布，平均每小时到达汽车到达间隔与加油时间均为指数分布，平均每小时到达16辆，平均加油时间为每辆辆，平均加油时间为每辆6分钟。求每辆汽车的分钟。求每辆汽车的平均逗留时间平均逗留时间。解解s=2r=2+3=5=16(辆辆/小时小时)=60/6=10(辆辆/小时小时)=1610=1.6 s=1.62=0.8第第11章章排排队队论论81 (1.6)22!220.8(0.82-0.85)2!(1-0.8)P0=-11+1.6+0.1568Lq=0.8(1.6)20.15682!(1-0.8)21-(0.8)5-21+(5-2)(1-0.8)=0.7257(辆辆)P5=(0.8)50.1568=0.10280.102810%10%222!L=0.7257+1.6(1-0.1028)=2.1612(辆辆)W=2.161216(1-0.1028)0.150.15(小时小时小时小时)=9 9(分钟分钟分钟分钟)三、三、顾客源客源为有限的情形有限的情形(M/M/c/m)设顾客源为有限数m（mc），与单服务台情形类似，顾客的到达率是按单个顾客来考虑的，在机器管理问题中，共有m台机器，有c个修理工人，顾客到达就是机器出了故障，而每个顾客的到达率是指每台机器单位运转时间出故障的期望次数。系统中顾客数n就是出故障台数，当nc时，所有的故障机器都在被修理，有(c-n)个修理工人在空闲；当cnm时，有(n-c)台机器在停机等待修理，而修理工都在忙碌状态。假定这c个工人修理技术相同，修理时间都服从参数为的负指数分布，并假定故障的修复时间和正在生产的机器是否发生故障是相互独立的。第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划其中第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划由于由于P P0 0,P,Pn n计算公式算公式过于复于复杂，有，有专门的表格可以供的表格可以供查阅。系统的性能指标平均顾客数（即平均故障台数）：有效的到达率e为每个顾客的到达率乘以在系统外（正常运转）的机器的期望数：e=(m-Ls)；在机器故障问题中，即单位时间m台机器平均出现故障的次数。第四节第四节 多服务台模型多服务台模型第九章第九章服务系统规划服务系统规划本节讨论服务时间是任意分布的情形，当然，对任何情形都有下面的关系：E系统中顾客数=E队列中顾客数+E服务机构中顾客数E在系统中逗留时间=E排队等待时间+E服务时间其中，E.表示求期望值，用符号表示：Ls=Lq+LseWs=Wq+ET第五节第五节 其他服务时间分布模型其他服务时间分布模型第九章第九章服务系统规划服务系统规划一、一般分布模型一、一般分布模型(M/G/1/)该模型的基本条件：(1)输入过程顾客源是无限的，到达过程服从参数为的泊松过程；(2)排队规则单队，队长无限制，先到先服务；(3)服务机构单服务台，G表示服务时间T的分布为任意的概率分布，但已知E(T)和方差Var(T)。此模型被称为单服务台泊松到达、任意服务时间的排队模型。第五节第五节 其他服务时间分布模型其他服务时间分布模型第九章第九章服务系统规划服务系统规划在稳态情况下，当=E(T)1时，可以证明:此公式又称P-K（Pollaczek-Khintchine）公式。只要知道、E(T)、Var(T)，无论服务时间T服从什么分布，均可用P-K公式求出平均队长Ls。其它的运行指标：第五节第五节 其他服务时间分布模型其他服务时间分布模型第九章第九章服务系统规划服务系统规划第第11章章排排队队论论88 例例7某储蓄所有一个服务窗口，顾客按泊松分布平均每小时某储蓄所有一个服务窗口，顾客按泊松分布平均每小时到达到达10人。为任一顾客办理存款、取款等业务的时间人。为任一顾客办理存款、取款等业务的时间V(小时小时)N(0.05,0.012).试求该储蓄所空闲的概率及其主要工作指标。试求该储蓄所空闲的概率及其主要工作指标。解解从而根据从而根据波拉切克波拉切克欣钦欣钦公式，可以导出：公式，可以导出：L q=+2 2(1-)222=0.012(小时小时/人人)2=10(人人/小时小时)1=0.05(小时小时/人人)第第11章章排排队队论论8911.311.3 其他模型选介其他模型选介=0.26 0.26(人人人人)该储蓄所空闲的概率：该储蓄所空闲的概率：=1-0.50.5=0.50.5=10(0.050.05)=0.50.5=P0=1-L=Lq+L q=0.52+102(0.01)22(1-0.5)W=L Wq=Lq 则则主要指标主要指标=0.26+0.5=0.76 0.76(人人人人)=0.760.7610=0.0760.076(小时小时)5 5 (分钟分钟)=0.260.261010=0.0260.026(小时小时)2 2 (分钟分钟)二、定二、定长分布模型分布模型(M/D/1/)服务时间为确定的常数，如在一条装配线上完成一件工作的时间一般都是常数。自动汽车冲洗台，冲洗一辆汽车的时间就是常数，可得：第五节第五节 其他服务时间分布模型其他服务时间分布模型第九章第九章服务系统规划服务系统规划第第11章章排排队队论论91 二、二、M/D/1系统系统该系统对各顾客服务时间相互独立且为同一个常数该系统对各顾客服务时间相互独立且为同一个常数，故有故有E()=1 例例8 某检测站有一台自动检测机器性能的仪器，检测每台某检测站有一台自动检测机器性能的仪器，检测每台机器都需机器都需6分钟。送检机器按泊松分布到达，平均每小时分钟。送检机器按泊松分布到达，平均每小时4台。台。试求该系统的主要工作指标。试求该系统的主要工作指标。D()=0(=2)Lq=2(1-)2第第11章章排排队队论论9211.311.3 其他模型选介其他模型选介 =4台台/小时小时=6分钟分钟/台台=0.1小时小时/台台2=0，L=Lq+=2/15+0.4=8/15(台台)Wq=Lq/=2/4(15)=1/30(小时小时)=2(分钟分钟)W=Wq+1/=2+6=8(分钟分钟)0.422(1-0.4)Lq=2/15(台台)=4(0.1)=0.4解解三、三、爱尔尔朗服朗服务时间(M/Ek/1/)此模型中每一个顾客必须一次经过k个服务台，接受k次服务后才构成一个完整服务过程。在每个服务台的服务时间Ti相互独立，并服从相同的负指数分布（参数为k），那么服从k阶爱尔朗分布。第五节第五节 其他服务时间分布模型其他服务时间分布模型第九章第九章服务系统规划服务系统规划对于(M/Ek/1/)模型（除服务时间外，其它条件与标准的M/M/1/型相同）第五节第五节 其他服务时间分布模型其他服务时间分布模型第九章第九章服务系统规划服务系统规划第第11章章排排队队论论95 例例9 一个质量检查员平均每小时收到一个质量检查员平均每小时收到两件两件送来检查的送来检查的样品，每件样品要一次完成样品，每件样品要一次完成5 5项检验才能判断是否合格。据项检验才能判断是否合格。据统计，每项检验所需时间的期望值都是统计，每项检验所需时间的期望值都是4 4分钟，每项检验的分钟，每项检验的时间和送检产品到到达间隔都为指数分布。问一件样品从时间和送检产品到到达间隔都为指数分布。问一件样品从送到至检查完毕预期要多少时间？送到至检查完毕预期要多少时间？解解 =2件件/小时小时 k k=5 51/(5 )=4(分钟分钟/件件)E(Vi i)=1/(k k)，i=1，2，3，4，51/=20(分钟分钟/件件)=1/31/3(小时小时/件件)由由有有则则第第11章章排排队队论论96=/=2(1/3)=2/3Lq=Wq=Lq/=4/5/2=2/5(小时小时)W=Wq+1/=2/5+1/3=11/15(小时小时)=44(分钟分钟分钟分钟)(5+1)(2/32/3)225(1-2/32/3)=4 45 5(件件件件)一、排一、排队系系统经济分析分析试图完全消除排队现象是不现实的，那样显然会造成服务人员和设施的严重浪费。另一方面，如果设施不足或服务低水平，将导致过多的等待，因而产生生产和社会损失。从经济角度考虑，一般排队系统的费用应该包含于以下两个方面：服务费用。它随着服务水平（反映在服务能力和服务台数量方面）的提高而增加，是服务水平的递增函数。顾客等待的机会损失（费用）。顾客由于等待，产生一系列的损失（时间上、心理上、社会上等）用经济费用进行的估算，称为顾客等待的机会损失。它随服务水平的提高而下降，是服务水平的递减函数。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划这两方面构成的函数呈现为一条如图所示的U型曲线。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划图9-10 费用与服用与服务水平之水平之间的关系的关系F1、F2、Y分别是等待费用函数、服务费用函数、合成费用函数。分别是等待费用函数、服务费用函数、合成费用函数。归纳起来，排队系统常见的优化问题在于：确定服务台的最优平均服务率*；确定最佳服务台数量s*；选择最为合适的服务规则；确定上述几个量得最优组合。研究排队系统的根本目的在于以最少的设备得到最大的效益，或者说，在一定的服务质量的指标下要求机构最为经济。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划二、二、M/M/1系系统的最的最优平均服平均服务率率1标准的M/M/1模型设c1为当=1时服务系统单位时间的平均费用，并且这个平均费用与平均服务率成正比例；cw为平均每个顾客在逗留单位时间的损失；Y为整个系统单位时间的平均总费用。其中c1、cw均为已知（以下情形相同）。目标函数：将M/M/1模型的平均队长公式L=/(-)代入(9-41)式，得：第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划显然，Y是关于决策变量的一元非线性函数。由一阶最优性必要条件（驻点条件）解得驻点取算术平方根是为了保证，这样，系统才能达到稳态。又知二阶充分条件成立：于是，式(9-43)给出的*为(,)上的全局唯一最小点。将*带入(9-42)中，可得最小的总平均费用第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划若设cw为平均每个顾客在队列中等待单位时间的损失，则需要M/M/1模型的平均队列长公式代入式(9-41)中的L，类似可得一阶最优性必要条件：这是一个关于的4次方程，实际中一般采用数值法（如牛顿法）来确定其根（最优服务率）*。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划2.系系统中中顾客最大限制客最大限制为N的情形的情形在这情形下，系统中如已有N个顾客，则后来的顾客即被拒绝，可知：PN被拒绝的概率；1-PN能被接受的概率；(1-PN)单位时间实际进入服务机构顾客的平均数。在稳定状态下，它也等于单位时间内实际服务完成的平均顾客数。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划设每服务1人能收入G元，于是单位时间收入的期望值是(1-PN)G元。纯利润：最优的解*应该符合上式(9-45)。上式中c1、G、N都是给定的，但要由上式中解出*是很复杂的。通常是通过数值计算来求*的，或将上式左方（对一定的N）作为的函数作出图形进行求解。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划3.顾客源客源为有限的情形有限的情形按机械故障问题来考虑。设共有机器m台，各台连续运转时间服从负指数分布。有1个修理工人，修理时间服从负指数分布。当服务率=1时的修理费用c1，单位时间每台机器运转可得收入G元。平均运转台数为m-Ls，所以单位时间纯利润：第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划当给定m、G、c1、，要由上式中解出*是很困难的，通常是利用泊松分布表通过数值计算来求得，或将上式左方（对一定的m）作为的函数作出图形进行求解。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划三、三、M/M/c系系统的最的最优服服务台数台数c设排队系统M/M/c，确定最佳服务台数c的目标函数为：其中：c为待定的共享并联服务台的个数；Y(c)为整个系统单位时间的平均费用，它是关于服务台数c的函数；c2为每个服务台单位时间内的平均费用（各服务台相同）；cw为平均每个顾客在系统中逗留单位时间的损失；L(c)为平均队长，它是关于服务台数c的函数。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划要确定最优服务台数c1,2,，使由于c取值离散，不能采用微分方法或非线性规划的方法，因此，只需要同时满足下式即可：采用差分法，可导出另一关系式。把式(9-50)代入式(9-51)中，得第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划令依次计算时的值，根据落在哪两个差值之间就可确定c*。另外，若设cw为平均每个顾客在队列中等待单位时间的损失，则需要M/M/c模型的平均队列长公式Lq(c)取代式(9-50)中的L(c)，由于在此情况下不需求导数，所以只要把相应公式中的L(c)用Lq(c)取代即可。第六节第六节 服务系统规划的应用服务系统规划的应用第九章第九章服务系统规划服务系统规划第第11章章排排队队论论110 例例10 某市政府的上访接待室每天平均接待来访某市政府的上访接待室每天平均接待来访48次，来访者为泊松次，来访者为泊松流，每天上访所造成的损失为平均每次流，每天上访所造成的损失为平均每次200元。该室每设置一名接待员的元。该室每设置一名接待员的服务成本为平均每天服务成本为平均每天80元，接待时间为指数分布，平均每天可接待元，接待时间为指数分布，平均每天可接待25次。次。则应设置几名接待员？则应设置几名接待员？解解 这是一个这是一个M/M/s/系统，有系统，有 c2=80元元/人天，人天，cw=200元元/天次，天次，=48次次/天，天，=25次次/天。天。按按(11-61)得得 =2 2c2 cw=80200=0.40.4另有另有 =1.92=4825 s=s1.92s=1=1 =1.92ss-1.92s第第11章章排排队队论论111把把 ，1-代入代入(11-14)，得得 k=0s-1 P0=1.92k/k!+1.92s/(s-1)!(s-1.92)-1又由又由(11-16)，(11-17)，得得 s s!(1-)2P0L=+把把 ，1,P0 代入上式代入上式，整理可，整理可得得L(s)=(1.92)s+11.92k/k!+1.92s k=0s-1(s-1)!(s-1.92)(s-1.92)+1.92s=2,3,而当而当 s=1 1时，时，=1.92 1，不，不满足系足系统达到达到稳态的条件的条件 1，这时 L(1 1).第第11章章排排队队论论112 依次计算依次计算s=2,3,时的时的L(s)值及其差值值及其差值 L(s)-L(s+1)，如下表所示：如下表所示：sL(s)L(s)-L(s+1)1234524.4902.64521.845 2.0630.582 1.9520.111 2 2=0.40.4故得故得 4 4s*=4 4f(s*)=804 4 +200+200 2.0632.063=732.60(元元/天天)