排队模型课件

*

对于泊松输入—负指数分布服务的排队系统的一般决策过程：1、求出P0

及

Pn。2、计算各项数量运行指标。3、用系统运行指标构造目标函数，对系统进行优化。

泊松输入—指数服务排队模型

*

典型分布——

泊松分布及其性质，负指数分布及其性质

*一．M/M/s/∞系统又称无限队长、无限源系统。

当s=1时为单服务台系统；当s>1时为多服务台系统。

若系统内的顾客数n>s，则有n-s个顾客在等待服务*服务强度：令：则系统的稳态概率为：服务台全部空闲的概率：任意时刻状态为n的概率：*4项主要工作指标：（1）平均等待队长：（2）平均队长：（3）平均逗留时间：（4）平均等待时间：*特别地，当S=1（单服务台系统）时：**

例1、某医院急诊室同时只能诊治一个病人，诊治时间服从指数分布，每个病人平均需要15min，病人按泊松分布到达，平均每小时到达3人。分析此排队系统。解：（1）确定参数：这是单服务台系统，有故服务强度为：（2）计算稳态概率：*病人需要等待的概率为：（3）计算系统主要工作指标：急诊室内外的病人平均数：急诊室外排队等待的病人平均数：病人在急诊室内外逗留的时间：*病人平均等候的时间：（4）为使病人平均逗留时间不超过半小时，那么平均服务时间应减少多少？代入得平均服务时间：平均服务时间至少应减少3min*（5）若医院希望候诊的病人90%以上都有座位，则候诊室至少应安置多少座位？设：应安置x个座位，则有x+1个座位。“要使90%以上的候诊病人有座位”相当于“来诊的病人数不多于x+1个的概率不小于90%”，即：或从而*两边取对数：所以即候诊室应安置6个座位。*

例2、承上例，假设医院增强急诊室的服务能力，使其同时能诊治两个病人，且平均服务率相同，试分析该系统工作情况，并与例1进行比较.解：这相当于增加了一个服务台，从而有：**病人必须等候的概率即系统状态的概率：例1、例2比较见教材P163表6-1*二．M/M/s/r系统又称有限队长、无限源系统当r=s时为损失制系统；当r>s时为混合制系统

当顾客到达系统时，若系统已经满员（N=r）,则后到的顾客就自动消失。不需规定就能保证系统达到稳态。*1、当s=1时服务强度：稳态概率为：*平均队长、平均等待队长：到达的潜在顾客能进入系统的概率为系统的有效平均到达率为：*

例3、某小型美容院只能安置3个座位供顾客等候，一旦满座则后平者不再进店等候。已知顾客到达间隔与美容时间均为指数分布，平均到达间隔80min，平均美容时间为50min。求一顾客期望等候时间及该店潜在顾客的损失率。解：这是一个M/M/s/r系统故服务强度为：**故任一顾客期望等待时间为：该店潜在顾客的损失率：*2、当s>2时服务强度：

与M/M/s/系统一样则：**特别地，当r=s（损失制）时，公式化简为：使用的服务台的平均数：*

例4、某街口汽车加油站可同时为两辆汽车加油，并还可容纳三辆汽车等待，超过此限则不能等待而消失。汽车到达间隔与加油时间均为指数分布，平均每小时到达16辆，平均加油时间为每辆6min。求每辆汽车的平均逗留时间。解：这是一个M/M/2/r系统**系统潜在顾客损失率：每辆汽车平均逗留时间：*三、M/M/s/m/m系统又称有限源系统

典型情况：1、s名电工共同负责m台机器的维修；2、m个车工共同使用s个电动砂轮；3、m个教师共同使用计算机终端；4、一家人共同使用一个卫生间等等。

顾客源即m台机器，机器发生故障表示顾客到达；s名电工即服务台。*顾客源此排队系统是一个循环排队系统：设（1）m台机器质量相同，每台机器连续运转时间相互独立，都服务参数为的指数分布。是1台机器在单位时间内发生故障的平均次数，每台机器连续运转时间为。*（2）s名电工技术程度相同，每人对机器的修复时间相互时间都服从参数为的指数分布。是1工人在单位时间内修复机器的台次，工人修复每台机器的平均时间为。（3）机器的正常运转与修复状态相互独立，修复的机器具有与新机器相同的质量。系统的服务强度：令：*稳态概率为：有效平均到达率：主要指标L等可由公式（4—2）和李特尔公式求得。*特别地，当s=1时：*

例5、一个工人负责照管6台自动机床。当机床需要加料或刀具磨损时就自动停车，等待工人照管。设每台机床平均每小时停车一次，每次需要工人照管的平均时间为0.1h，试分析该系统的运行情况。解：这是M/M/1/6/6系统工人空闲的概率为：*停车机床平均数：等待照管的机床平均数：*平均停车时间：平均等待时间：生产损失率：机床利用率：*

第四节排队系统的优化目标

与最优化问题复习提问：一、常见的排队系统有哪些？如何表示？二、排队系统的主要指标有哪些？三、常见的排队模型分析法四、排队系统的优化*

第四节排队系统的优化目标

与最优化问题

以完全消除排队现象为研究目标是不现实的，那会造成服务人员和设施的严重浪费，但是设施的不足和低水平的服务，又将引起太多的等待，从而导致生产和社会性损失。*

从经济角度考虑，排队系统的费用应该包含以下两个方面：一是服务费用，它是服务水平的递增函数；二是顾客等待的机会损失(费用)，它是服务水平的递减函数。

两者的总和呈一条U形曲线。*

系统最优化的目标就是寻求上述合成费用曲线的最小点。在这种意义下，排队系统的最优化问题通常分为两类：一类称之系统的静态最优设计，目的在于使设备达到最大效益，或者说，在保证一定服务质量指标的前题下，要求机构最为经济；另一类叫作系统动态最优运营，是指一个给定排队系统，如何运营可使某个目标函数得到最优。*排队系统常见的优化问题在于：

(1)确定最优服务率

*；

(2)确定最佳服务台数量c*；

(3)选择最为合适的服务规则；

(4)或是确定上述几个量的最优组合。

研究排队系统的根本目的在于以最少的设备得到最大的效益，或者说，在一定的服务质量的指标下要求机构最为经济。*排队系统的最优化问题分为两大类：1、系统的静态最优设计问题2、系统的动态最优控制问题

我们只讨论系统静态的最优设计问题即仅就

，S这两个决策变量的分别单独优化。*

一、M／M／1／∞系统的最优平均服务率

*

设C1——当

=1时服务系统单位时间的平均费CW——平均每个顾客在系统逗留单位时间的损失；y——整个系统单位时间的平均总费用。其中C1，C2均为可知(下同)。则目标函数为

(4-52)*将L=

／(

-

)，代入上式，得易见y是关于决策变量

的一元非线性函数由微分法可求得最小费用：

*由一阶条件解得驻点

(4-53)*

根号前取正号是为了保证

<1，即

*>

，这样，系统才能达到稳态。又由二阶条件

(因

>

）可知(4-53)给出的

*为(

,∞)上的全局唯一最小点。将

*代入

(4-52)中，可得最小总平均费用

（4-54）*

例6:兴建一座港口码头，只有一个装卸船只的泊位。要求设计装卸能力。装卸能力单位为（只/日）船数。已知：单位装卸能力的平均生产费用a=2千元，船只逗留每日损失b=1.5千元。船只到达服从泊松分布，平均速率λ=3只/日。船只装卸时间服从负指数分布。目标是每日总支出最少。应用举例*

解：λ=3μ待定模型M/M/1/∞/∞队长Ls=λ/(μ-λ)总费用C=aμ+bLs=aμ+bλ/(μ-λ)求极值（最小值）令

求导dc/du=a+(-bλ)/(μ-λ)2=0得:μ-λ=+-(bλ/a)1/2（根据题意舍负）所以μ=λ+(bλ/a)1/2=3+(2.25)1/2=4.5(只/日)*

二、M／M／s／∞系统的最优服务台数s*设目标函数为

(4-55)其中：s——并联服务台的个数(待定)；f(s)——整个系统单位时间的平均总费用，它是关于服务台数s的函数；c2——单位时间内平均每个服务台的费用；*cw——平均每个顾客在系统中逗留(或等待)单位时间的损失；L(s)——平均队长(或平均等待队长)，它是关于服务台数s的函数；我们要确定最优服务台数s*∈{1，2，…}，使由于s取值离散，不能采用微分法或非线性规划的方法，因此我们采用差分法。显然有

（4-56）*把式（4-55）代人式(4-56)中，得由此可得令

(4-57)

依次计算s=1，2，…时的L(s)值及每一差值L(s)-L(s+1)，根据

落在哪两个差值之间就可确定s*。*

例7:建造一码头，要求设计装卸船只的泊位数。已知:预计到达λ=3只/天，泊松流；装卸μ=2只/天，负指数分布。装卸费每泊位每天a=2千元，停留损失费b=1.5千元/日。目标是总费用最少。

解:模型M/M/s/∞/∞c待定总费用：F=ac+bLs（s）离散，无法用求导来解。*考虑:M/M/s/∞/∞要求:ρ=λ/(sμ)<1即s>(λ/μ)=1.5讨论s=2,3,4…

s-1

P0=[∑sn/n﹗ρn+ss/s!ρs/(1-ρ)]-1

n=0

Lq=ssρs+1/s!(1-ρ)2P0L=Lq+λ/μ

*

结论：s=3即设计三个装卸泊位可使每天的总费用最少为8.60526千元。ρ=1/2ρ

=3/4ρ=3/8*

例8:某市政府的上访接待室每天平均接待来访48次，来访者为泊松流，每天上访所造成的损失为平均每次20元。该室每设置一名接待员的服务成本为平均每天8元，接待时间为指数分布，平均每天可接待25次。问应设置几名接待员能使平均总费用为最小?

解:由题意知，这是一个M／M／s