第08章 排队论 运筹学

第八章 排队论排队是日常生活和经济管理经常遇到的问题，如医院等待看病的病人、加油站等待加油的汽车、工厂等待维修的机器、港口等待停泊的船只等。

在排队论中把服务系统中这些服务的客体称为顾客。

由于系统中顾客的到来以及顾客在系统中接受服务的时间等均是随机的，因此排队现象是不可避免的。

对于随机服务系统，若扩大系统设备，会提高服务质量，但会增加系统费用。

若减少系统设备，能节约系统费用，但可能使顾客在系统中等待的时间加长，从而降低了服务质量，甚至会失去顾客而增加机会成本。

因此，对于管理人员来说，解决排队系统中的问题是：在服务质量的提高和成本的降低之间取得平衡，找到最适当的解。

排队论是优化理论的重要分支。

排队论是1909年由丹麦工程师爱尔郎（A.K.Erlang ）在研究电话系统时首先提出，之后被广泛应用于各种随机服务系统。

第一节 排队论的基本概念及所研究的问题一、基本概念（一）排队系统的组成一般的排队系统有三个基本组成部分：顾客的到达（输入过程）、排队规则和服务机构，如图8—1所示。

1．输入过程输入过程指顾客按什么样的规律到达。

包括如下三个方面的内容：（1）顾客总体（顾客源） 指可能到达服务机构的顾客总数。

顾客总体数可能是有限的，也可能是无限。

如工厂内出现故障而等待修理的机器数是有限的，而到达某储蓄所的顾客源相当多，可近似看成是无限的。

（2）顾客到达的类型 指顾客的到达是单个的还是成批的；（3）顾客相继到达的时间间隔分布 即该时间间隔分布是确定的（定期运行的班车、航班等）还是随机的，若是随机的，顾客相继到达的时间间隔服从什么分布（一般为负指数分布）；2．排队规则排队规则指顾客接受服务的规则（先后次序），有以下几种情况。

（1）即时制（损失制） 当顾客来到时，服务台全被占用，顾客随即离去，不排队等候。

这种排队规则会损失许多顾客，因此又称为损失制。

（2）等待制 当顾客来到时，若服务台全被占用，则顾客排队等候服务。

在等待制中，又可按顾客顾客达到排队系统 图8—1服务的先后次序的规则分为：先到先服务（FCFS，如自由卖票窗口等待卖票的顾客）、先到后服务（FCLS，如仓库存放物品）、随机服务（SIRO，电话交换台服务对话务的接通处理）和优先权服务（PR，如加急信件的处理）。

第八章 排队论排队是日常生活和经济管理经常遇到的问题，如医院等待看病的病人、加油站等待加油的汽车、工厂等待维修的机器、港口等待停泊的船只等。

在排队论中把服务系统中这些服务的客体称为顾客。

由于系统中顾客的到来以及顾客在系统中接受服务的时间等均是随机的，因此排队现象是不可避免的。

对于随机服务系统，若扩大系统设备，会提高服务质量，但会增加系统费用。

若减少系统设备，能节约系统费用，但可能使顾客在系统中等待的时间加长，从而降低了服务质量，甚至会失去顾客而增加机会成本。

因此，对于管理人员来说，解决排队系统中的问题是：在服务质量的提高和成本的降低之间取得平衡，找到最适当的解。

排队论是优化理论的重要分支。

排队论是1909年由丹麦工程师爱尔郎（A.K.Erlang ）在研究电话系统时首先提出，之后被广泛应用于各种随机服务系统。

第一节 排队论的基本概念及所研究的问题一、基本概念（一）排队系统的组成一般的排队系统有三个基本组成部分：顾客的到达（输入过程）、排队规则和服务机构，如图8—1所示。

1．输入过程输入过程指顾客按什么样的规律到达。

包括如下三个方面的内容：（1）顾客总体（顾客源） 指可能到达服务机构的顾客总数。

顾客总体数可能是有限的，也可能是无限。

如工厂内出现故障而等待修理的机器数是有限的，而到达某储蓄所的顾客源相当多，可近似看成是无限的。

（2）顾客到达的类型 指顾客的到达是单个的还是成批的；（3）顾客相继到达的时间间隔分布 即该时间间隔分布是确定的（定期运行的班车、航班等）还是随机的，若是随机的，顾客相继到达的时间间隔服从什么分布（一般为负指数分布）；2．排队规则排队规则指顾客接受服务的规则（先后次序），有以下几种情况。

（1）即时制（损失制） 当顾客来到时，服务台全被占用，顾客随即离去，不排队等候。

这种排队规则会损失许多顾客，因此又称为损失制。

（2）等待制 当顾客来到时，若服务台全被占用，则顾客排队等候服务。

在等待制中，又可按顾客顾客达到排队系统 图8—1服务的先后次序的规则分为：先到先服务（FCFS，如自由卖票窗口等待卖票的顾客）、先到后服务（FCLS，如仓库存放物品）、随机服务（SIRO，电话交换台服务对话务的接通处理）和优先权服务（PR，如加急信件的处理）。

运筹学排队论引言排队论是运筹学中的一个重要分支，它研究的是如何优化排队系统的设计和管理。

排队论广泛应用于各个领域，如交通流量控制、银行业务流程优化、生产线调度等，对于提高效率和降低成本具有重要意义。

本文将介绍排队论的基本概念、排队模型以及应用案例，帮助读者了解运筹学中排队论的基本原理和应用方法。

什么是排队论排队论是一门研究排队现象的数学理论，它通过定义排队系统的各个要素，如顾客到达率、服务率、队列容量等，建立数学模型分析和优化排队系统的性能指标。

排队论主要研究以下几个方面：•排队系统的模型：包括单服务器排队系统、多服务器排队系统、顾客数量有限的排队系统等。

•排队系统的性能指标：包括平均等待时间、系统繁忙率、系统容量利用率等。

•排队系统的优化方法：包括服务策略优化、系统容量规划等。

排队论的基本概念到达过程排队论中的到达过程是指顾客到达排队系统的时间间隔的随机过程。

常用的到达过程有泊松过程、指数分布等。

到达过程的特征决定了顾客到达的规律。

服务过程排队论中的服务过程是指服务器对顾客进行服务的时间间隔的随机过程。

常用的服务过程有指数分布、正态分布等。

服务过程的特征决定了服务的速度和效率。

排队模型排队模型是排队论中的数学模型，用于描述排队系统的性能和行为。

常用的排队模型有M/M/1模型、M/M/s模型等。

这些模型分别表示单服务器排队系统和多服务器排队系统。

性能指标排队系统的性能指标用于评估系统的性能，常见的性能指标有平均等待时间、系统繁忙率、系统容量利用率等。

这些指标可以帮助决策者优化排队系统的设计和管理。

排队模型与分析M/M/1模型M/M/1模型是排队理论中最简单的排队系统模型，它是一个单服务器、顾客到达过程和服务过程均为指数分布的排队系统。

M/M/1模型的性能指标可以通过排队论的公式计算得出。

M/M/s模型M/M/s模型是排队理论中的多服务器排队模型，它是一个多个服务器、顾客到达过程和服务过程均为指数分布的排队系统。

第八章 排队论排队是日常生活和经济管理经常遇到的问题，如医院等待看病的病人、加油站等待加油的汽车、工厂等待维修的机器、港口等待停泊的船只等。

在排队论中把服务系统中这些服务的客体称为顾客。

由于系统中顾客的到来以及顾客在系统中接受服务的时间等均是随机的，因此排队现象是不可避免的。

对于随机服务系统，若扩大系统设备，会提高服务质量，但会增加系统费用。

若减少系统设备，能节约系统费用，但可能使顾客在系统中等待的时间加长，从而降低了服务质量，甚至会失去顾客而增加机会成本。

因此，对于管理人员来说，解决排队系统中的问题是：在服务质量的提高和成本的降低之间取得平衡，找到最适当的解。

排队论是优化理论的重要分支。

排队论是1909年由丹麦工程师爱尔郎（A.K.Erlang ）在研究电话系统时首先提出，之后被广泛应用于各种随机服务系统。

第一节 排队论的基本概念及所研究的问题一、基本概念（一）排队系统的组成一般的排队系统有三个基本组成部分：顾客的到达（输入过程）、排队规则和服务机构，如图8—1所示。

1．输入过程输入过程指顾客按什么样的规律到达。

包括如下三个方面的内容：（1）顾客总体（顾客源） 指可能到达服务机构的顾客总数。

顾客总体数可能是有限的，也可能是无限。

如工厂内出现故障而等待修理的机器数是有限的，而到达某储蓄所的顾客源相当多，可近似看成是无限的。

（2）顾客到达的类型 指顾客的到达是单个的还是成批的；（3）顾客相继到达的时间间隔分布 即该时间间隔分布是确定的（定期运行的班车、航班等）还是随机的，若是随机的，顾客相继到达的时间间隔服从什么分布（一般为负指数分布）；2．排队规则排队规则指顾客接受服务的规则（先后次序），有以下几种情况。

（1）即时制（损失制） 当顾客来到时，服务台全被占用，顾客随即离去，不排队等候。

这种排队规则会损失许多顾客，因此又称为损失制。

（2）等待制 当顾客来到时，若服务台全被占用，则顾客排队等候服务。

在等待制中，又可按顾客顾客达到排队系统 图8—1服务的先后次序的规则分为：先到先服务（FCFS，如自由卖票窗口等待卖票的顾客）、先到后服务（FCLS，如仓库存放物品）、随机服务（SIRO，电话交换台服务对话务的接通处理）和优先权服务（PR，如加急信件的处理）。

排队论例1题目：某火车站的售票处设有一个窗口,若购票者是以最简单流到达,平均每分钟到达1人,假定售票时间服从负指数分布,平均每分钟可服务2人,试研究售票窗口前排队情况解:由题设λ=1(人/分),μ=2(人/分),ρ=λμ=12平均队长L=1ρρ-=1(人)平均等待队长Lq=21ρρ-=12(人)平均等待时间Wq=λμμ（-1）=12(分)平均逗留时间W=1μλ-=1(分)顾客不需要等待的概率为P o=12,等待的顾客人数超过5人的概率为P(N≥6)=1766666111111()(1)()()()()222222n n nnn n n nPρ-∞∞∞∞=====-===∑∑∑∑1例2题目：在某工地卸货台装卸设备的设计方案中,有三个方案可供选择,分别记作甲、乙、丙。

目的是选取使总费用最小的方案，有关费用（损失）如下表所示设货车按最简单流到达，平均每天（按10小时计算）到达15车，每车平均装货500袋，卸货时间服从负指数分布，每辆车停留1小时的损失为10元。

解：平均到达率λ=1.5车/小时,服务率μ依赖于方案μ甲=1000/500/袋小时袋车=2车/小时μ乙=2000/500/袋小时袋车=4车/小时μ丙=6000/500/袋小时袋车=12车/小时由(7.2.6),1辆车在系统内平均停留时间为W甲=12-1.5=2(小时/车)W乙=14-1.5=0.4(小时/车)W丙=112-1.5=0.095(小时/车)每天货车在系统停留的平均损失费为W⨯10⨯15,每天的实际可变费用(如燃料费等)为(可变操作费/天)⨯设备忙的概率=c p(元/天)而ρ甲=0.75 , ρ乙=0.375 , ρ丙=0.125,所以每个方案的费用综合如下表所示:23例3 题目：要购置计算机,有两种方案.甲方案是购进一大型计算机,乙方案是购置n 台小型计算机.每台小型计算机是大型计算机处理能力的1n设要求上机的题目是参数为λ的最简单流,大型计算机与小型计算机计算题目的时间是负指数分布,大型计算机的参数是μ.试从平均逗留时间、等待时间看，应该选择哪一个方案 解：设ρ=λμ，按甲方案，购大型计算机 平均等待时间 q W 甲=ρμρ（1-）=λμμλ（-）平均逗留时间 W 甲=1μλ- 按乙方案，购n 台小型计算机，每台小计算机的题目到达率为n λ，服务率为nμ, ρ=//n n λμ=λμ平均等待时间 W q 乙=nρμρ（1-）=n ρμρ（1-）=nW q 甲平均逗留时间 W 乙=1n nμλ-=n μλ-=nW 甲所以只是从平均等待时间，平均逗留时间考虑，应该购置大型计算机4例4题目：设船到码头，在港口停留单位时间损失c 1 元，进港船只是最简单流，参数为λ，装卸时间服从参数为μ的负指数分布，服务费用为c μ2，c 2是一个正常数.求使整个系统总费用损失最小的服务率μ 解:因为平均队长L λμλ=-,所以船在港口停留的损失费为1c λμλ-,服务费为c μ1,因此总费用为 1c F c λμμλ=+-2 求μ使F 达到最小,先求F 的导数12()c dF c d λμμλ=-+-2 让dF d μ=0,解出2μλ=因为 22F u μμ*=∂∂=22()c λμλ*-1>0 (μ>λ) 最优服务率是μ*,当μμ*=时, 12()[c F c c λμλ*=+5例5题目：一个理发店只有一个理发师,有3个空椅供等待理发的人使用,设顾客以最简单流来到,平均每小时5人,理发师的理发时间服从负指数分布,平均每小时6人.试求L ,q L ,W ,q W解:λ=5(人/小时) , μ=5(人/小时) , k =4 , 56ρ= 用公式(7.2.10),(7.2.11),(7.2.12),(7.2.13)得到565555[16()5()]666 1.9715[1()]66L -+==- 5555(1)[16()]66 1.97 1.2251()6q L -=+=- 55555()[1()]660.101()6P -==- 5(1)z LLW P λλ==-=1.9750.9=0.438(小时)0.271qq zL W λ==(小时)6例6题目：给定一个//1/M M k 系统,具有λ=10(人/小时), μ=30（人/小时），k =2.管理者想改进服务机构.方案甲是增加等待空间,使k =3.方案乙是将平均服务率提高到μ=40(人/小时),设服务每个顾客的平均收益不变,问哪个方案获得更大收益,当λ增加到每小时30人,又将有什么结果?解:由于服务每个顾客的平均收益不变,因此服务机构单位时间的收益与单位时间内实际进入系统的平均人数k n 成正比(注意,不考虑成本)!(1)(1)1k k k k n p λρλρ+-=-=- 方案甲:k=3, λ=10, μ=3033411()310[]11()3n -=-=9.75 方案乙: k=2, λ=10, μ=40223110(1())311()4n -=-=9.5 因此扩大等待空间收益更大 当λ增加到30人/小时时,λρμ==1.这时方案甲有3330()31n =+=22.5(人/小时) 而方案乙是把μ提高到μ=40人/小时. λρμ==3040<1, k=2 2233(1())430[]31()4n -=-=22.7(人/小时) 所以当λ=30人/小时时,提高服务效益的收益比扩大等待空间的收益大7例7题目：一个大型露天矿山,考虑建设矿山卸矿场,是建一个好呢?还是建两个好.估计矿车按最简单流到达,平均每小时到达15辆,卸车时间也服从负指数分布,平均卸车时间是3分钟,每辆卡车售价8万元,建设第二个卸矿场需要投资14万元解:平均到达率 λ=15(辆/小时) 平均服务率 μ=20(辆/小时) 只建一个卸矿场的情况:1ρρ==1520=0.75 在卸矿场停留的平均矿车数0,,,,,,q q q q p p L L W W λμL λμλ=-=152015-=3(辆)建两个卸矿场的情况:ρ=0.75,2μ=2λμ=0.375 2101220[10.75(0.75)]0.452!22015P -=++=- 220.451520(0.75)0.750.120.750.871!(22015)L +=+=+=-因此建两个卸矿场可减少在卸矿场停留的矿车数为:3-0.87=2.13辆.就是相当于平均增加2.13辆矿车运矿石.而每辆卡车的价格为8万元,所以相当于增加2.13⨯8=17.04万元的设备,建第二个卸矿场的投资为14万元,所以建两个卸矿场是合适的.8例8题目：有一个///M M c ∞系统,假定每个顾客在系统停留单位时间的损失费用为c 1元,每个服务设备单位时间的单位服务率成本为c 2元.要求建立几个服务台才能使系统单位时间平均总损失费用最小解:单位时间平均损失费为F c L c c μ=+12要求使F 达到最小的正整数解c *,通常用边际分析法:找正整数c *,使其满足{()(1)()(1)F c F c F c F c ****≤+≤-由()(1)F c F c **≤+,得到122()(1)(1)c L c c c c L c c c μμ****+≤+++所以 21()(1)c L c L c c μ**-+≤ 同样,由()(1)F c F c **≤-得到21(1)()c L c L c c μ**--≥因此c *必须满足不等式21()(1)c L c L c c μ**-+≤≤(1)()L c L c **-- 取c =1,2,…,计算()L c 与(1)L c +之差,若21c c μ落在()(1)L c L c **-+,(1)()L c L c **--之间,c *就是最优解9例9题目：某公司中心实验室为各工厂服务,设做实验的人数按最简单流到来.平均每天48(人次/天),1c =6(元).作实验时间服从负指数分布,平均服务率为μ=25(人次/天),2c =4(元),求最优实验设备c *,使系统总费用为最小. 解:λ= 48(人次/天)，μ=25(人次/天)，λμ＝1.92 按///M M c ∞计算0P ,()L c 等(注意以下公式只对0 1.92cρ=<1成立). 201100(1.92)(1.92)[]!(1)!( 1.92)n P n c c ρ--==+--∑12(1.92)() 1.92(1)!( 1.92)c L c P c c +=+-- 将计算结果列成下表21c c μ=1006=16.67 所以取c *=3,总费用最小10例10题目：设有2个工人看管5台自动机,组成//2/5/5M M 系统,λ=1(次/运转小时),μ=4(次/小时),求平均停止运转机器数L 、平均等待修理数q L 以及每次出故障的平均停止运转时间W 、平均等待修理时间q W解：14λμ=，18c λμ=由（7.3.1）,(7.3.2)有 0P =0.3149 1P =0.391 2P =0.197 由（7.3.3）,(7.3.4)有 q L =0.118,L =1.094,c λ=3.906 由（7.3.5）,(7.3.6)有W =0.28(小时),q W =0.03(小时)实际上,这些数量指标有表可查例11题目：设某厂有自动车床若干台,各台的质量是相同的,连续运转时间服从负指数分布,参数为λ,工人的技术也差不多,排除故障的时间服从负指数分布,参数为μ.设λμ=0.1,有两个方案.方案一:3个工人独立地各自看管6台机器.方案二,3个工人共同看管20台机器,试比较两个方案的优劣解:方案一.因为是分别看管,可以各自独立分析,是3个//1/6M M 系统.由上面的公式可求出01P -=0.5155,c =0.5155, a =5.155Lq =0.3295, L =0.845,(1)q =0.4845,(1)r =0.0549方案二.m =20,c =3,λμ=0.1,可求得c =1.787,a =17.87,q L =0.339 L =2.126,(3)q =0.4042,(3)r =0.01695机器损失系数,修理工人损失系数都小于方案一,所以方案二较好11例12题目：某露天铁矿山,按设计配备12辆卡车参加运输作业(每辆载重160吨,售价72万元),备用车8辆,要求保证同时有12辆车参加运输的概率不低于0.995.设每辆平均连续运输时间为3个月,服从负指数分布.有两个修理队负责修理工作,修理时间服从负指数分布.平均修复时间为5天.问这个设计是否合理.解:由假设知,这是////M M c m N m +系统,m =12,1λ=3,1μ=6(月)c =2我们有m c λμ=0.3333,c μλ=36用c N ≤的公式,求N ,要求00.995Nn n p =≥∑设N =2,有Nnn p=∑=0.9474,当N =3时,有Nnn p=∑=0.9968.所以3辆备用车就能达到要求,原设计用的备用车太多当N =3时,卡车的利用律(2)q =0.793712例13题目：假定例2.1中工人的到达服从泊松分布，λ=8人/小时，试分别计算1h 内到达4，5，6，…，12个工人的概率。