运筹学课件(4)

1、(Queuing Theory)随机服务系统理论随机服务系统理论 Stochastic Service System Theory 第一节第一节 排队系统的组成及数量指标排队系统的组成及数量指标 第二节第二节 到达及服务时间的分布到达及服务时间的分布 第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析 第四节第四节 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析 第五节第五节 排队系统的经济分析排队系统的经济分析 第六节第六节 M/G/1/G/1排队模型排队模型 主要内容主要内容 顾顾客客源源顾客到达顾客到达排排 队队结结 构构服服 务务机机 构构

2、顾客离去顾客离去排队规则排队规则服务规则服务规则客源有限、无限；客源有限、无限； 单个、成批到达；单个、成批到达； 确定、随机；确定、随机； 相互独立、关联；相互独立、关联； 平稳、非平稳。平稳、非平稳。 容量有限、无限容量有限、无限单列，多列单列，多列 单个、多个服务台单个、多个服务台 并列、串列、混合并列、串列、混合单个、成批服务，单个、成批服务， 确定型、随机型确定型、随机型 平稳、不平稳平稳、不平稳 即时制、即时制、 等待制等待制 有有/无耐性无耐性 允许允许/不允许变队不允许变队后到先服务后到先服务先到先服务先到先服务随机服务随机服务有优先权的服务有优先权的服务 各各种种排排队队系系

3、统统 到到达达的的顾顾客客 要要求求服服务务的的内内容容 服服务务机机构构 1 故故障障的的机机器器 2 病病人人 3 电电话话呼呼唤唤 4 提提货货单单 5 驶驶入入港港口口的的货货船船 6 上上游游河河水水进进入入水水库库 修修理理 诊诊断断或或手手术术等等 通通话话 提提取取存存货货 装装(卸卸)货货 放放水水, 调调整整水水位位 修修理理技技工工 医医生生,床床位位,手手术术台台 交交换换台台 仓仓库库管管理理员员 码码头头(泊泊位位) 水水闸闸(及及管管理理人人员员) 第一节第一节 排队系统的组成及数量指标排队系统的组成及数量指标XYZABC 第一节第一节 排队系统的组成及数量指标排

4、队系统的组成及数量指标排队模型排队模型( DGKendall ) 例：例： M / M / 1 / N / m /FCFS其中其中 X ： 相继到达间隔时间的分布相继到达间隔时间的分布 Y： 服务时间的分布服务时间的分布 Z： 并列的服务台的数目并列的服务台的数目 A： 系统容量限制系统容量限制N B： 顾客源数目顾客源数目m C： 服务规则服务规则(FCFS，LCFS等等) 三、系统运行指标三、系统运行指标 第一节第一节 排队系统的组成及数量指标排队系统的组成及数量指标忙期忙期(Busy Period)：服务机构连续繁忙的时间长度服务机构连续繁忙的时间长度 ， 损失率、服务强度等损失率、服务

5、强度等等待时间等待时间Wq：一个顾客在系统中排队等待的时间：一个顾客在系统中排队等待的时间逗留时间逗留时间Ws ：一个顾客在系统中的停留时间一个顾客在系统中的停留时间排队长排队长(队列长队列长) Lq ：系统中排队等待服务的顾客数：系统中排队等待服务的顾客数队长队长Ls ： 系统中的顾客数系统中的顾客数系统的状态：系统的状态： 系统中的顾客数：系统中的顾客数：n n系统状态的概率系统状态的概率：在时刻在时刻t、系统状态为、系统状态为n的概率的概率 用用 Pn(t) 来表示。来表示。 关于关于Pn(t) 的关系式一般是微分差分方程，的关系式一般是微分差分方程， Pn(t) 是瞬态解，不易求，难应

6、用。是瞬态解，不易求，难应用。 第一节第一节 排队系统的组成及数量指标排队系统的组成及数量指标系统状态及其概率系统状态及其概率稳态解稳态解nntPtP)(limPn称为稳态解称为稳态解(Steady state solution) 或称统计平衡状态或称统计平衡状态(Statistical Equilibrium State)的解的解数学期望数学期望: : ET = 1/, 方差方差: : VarT = 1/2 2, ,标准差标准差 S ST = 1/ 第二节第二节 到达及服务时间的分布到达及服务时间的分布 一、一、 负指数分布负指数分布概率密度：概率密度：分布函数分布函数)0(,0)()0(,

7、)(ttftetft)0(,0)()0(,1)(ttFtetFt二、泊松（Poisson）分布0)(limttt01)(kktP(4)有限性：有限性：任意有限区间内到达有限任意有限区间内到达有限个顾客的概率为个顾客的概率为1。 因而有因而有:(3)普遍性：普遍性：若若(t)为时间为时间t内至少有两内至少有两 个以上的顾客到达的概率，个以上的顾客到达的概率， 则当则当t0时时 (t)=0(t), 即即(2)平稳性：平稳性： 在区间在区间(a， a+t)有有k个顾客到来的概率与个顾客到来的概率与 起始时刻起始时刻a无关，而只与无关，而只与t、k有关。有关。 此概率记作此概率记作Pk(t)(1)无后

8、效性：无后效性：在不相交在不相交(不相重迭不相重迭)的时间区间内到达的的时间区间内到达的 顾客数是相互独立的。顾客数是相互独立的。泊松流又称最简单流。满足以下条件的输入叫做最简单流：泊松流又称最简单流。满足以下条件的输入叫做最简单流：第二节第二节 到达及服务时间的分布到达及服务时间的分布 Poisson distribution:Probability density：),2,1 ,0,0(,!)()(ntenttPtnnExpected value: EN(t) = tVariance: VarN(t) = t三、爱尔朗三、爱尔朗( (ErlangErlang) )分布分布tkkkektkk

9、tb)!1()()(1其数学期望和其数学期望和方差分别为：方差分别为：ET = 1/， VarT =1/k2其概率密度为：其概率密度为： 设设v1，v2，vk是是k个相互独立的随机变量，服个相互独立的随机变量，服从相同参数从相同参数k的负指数分布，那么的负指数分布，那么 T = v1 + v2 + + vk 服从服从k阶爱尔朗分布。阶爱尔朗分布。第二节第二节 到达及服务时间的分布到达及服务时间的分布 三种分布的关系三种分布的关系2 若相继两顾客到达时间间隔为随机变量，服若相继两顾客到达时间间隔为随机变量，服从负指数分布，则，一定时间间隔内到达系统从负指数分布，则，一定时间间隔内到达系统的顾客数

10、也是随机变量，服从的顾客数也是随机变量，服从Poisson分布分布。1 k个独立同分布的负指数分布的随机变量和个独立同分布的负指数分布的随机变量和的分布是的分布是k阶阶Erlang分布。分布。第二节第二节 到达及服务时间的分布到达及服务时间的分布 第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析 (1)标准标准 MM1模型（模型（MM1） (2)系统的容量有限制（系统的容量有限制（MM1N） (3)顾客源有限（顾客源有限（MM1N)一、标准的一、标准的 M MM M1 1模型（模型（M MM M1 1)1）输入过程）输入过程顾客源是无限的，顾客单个到来，顾客源是无

11、限的，顾客单个到来， 相互独立，一定时间的到达数服相互独立，一定时间的到达数服 从泊松分布，到达过程是平稳的；从泊松分布，到达过程是平稳的；2）排队规则）排队规则单队，且对队长没有限制，单队，且对队长没有限制， 先到先服务；先到先服务；3）服务机构）服务机构单服务台，各顾客的服务时间是单服务台，各顾客的服务时间是 相互独立的，服从相同的负指数相互独立的，服从相同的负指数 分布；分布；4）到达间隔时间和服务时间是相互独立的。）到达间隔时间和服务时间是相互独立的。1模型条件模型条件第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析 系系统统状状态态的的三三种种情情况况

12、在在时时间间区区间间（t，t+t t） 情情况况 在在时时刻刻 t 的的顾顾客客数数 到到达达 离离去去 在在时时刻刻 t+t t的的顾顾客客数数 A B C n n+1 n-1 0 0 1 0 1 0 n n n 它们的概率分别是它们的概率分别是(略去略去 o(t )：情况情况A： Pn（t）（）（1-t）（）（1-t）情况情况B： Pn+1（t）（）（1-t）t情况情况C： Pn-1（t）t（1-t）2瞬时状态分析瞬时状态分析 一、标准的一、标准的 M MM M1 1模型模型第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析这三种情况互不相容，所以这三种情况互不

13、相容，所以Pn（t+t）应是这三项之和：）应是这三项之和：Pn（t+t）= Pn（t）（）（1-t-t） + Pn+1（t）t + P n-1（t）t令令 t 0，得关于，得关于 Pn（t）的微分差分方程）的微分差分方程 dPn（t）/dt =P n-1（t）+ Pn+1（t）-（+）Pn（t） n = 1，2， Pn（t+t）- Pn（t） = P n-1（t） t + Pn+1（t） t - （+）Pn（t） tPn（t+t）- Pn（t）当当no时，则只有时，则只有A、B两种情况，即：两种情况，即： P0（t+t）= P0（t）（）（1-t）+ P1（t）（）（1-t）t类似地求得：类似

14、地求得： dP0（t）/dt = -P 0（t）+ P1（t）这种系统状态（这种系统状态（n）随时间变化的过程是称为生灭过程的一个特殊情形。）随时间变化的过程是称为生灭过程的一个特殊情形。2瞬时状态分析瞬时状态分析 一、标准的一、标准的 M MM M1 1模型模型第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析t=P n-1（t） + Pn+1（t） - （+）Pn（t） dP0（t）/dt = -P 0（t） + P1（t）由（由（1）可得：）可得： P1 =（/）P 0 ， 将其代入（将其代入（2），令），令 n=1 得：得： P 0+ P2 =（+）（）（/

15、）P 0， 从而有：从而有： P2 =（/）2 P 0 同理依此推得：同理依此推得： Pn =（/）nP 0解如上微分方程是很麻烦的，而且解出的瞬态解也不便于应用，因解如上微分方程是很麻烦的，而且解出的瞬态解也不便于应用，因此，我们只研究稳态的情况。这时，此，我们只研究稳态的情况。这时，Pn（t）与）与t无关，可写成无关，可写成Pn，它对它对t的导数为的导数为0。由前面公式：。由前面公式：3系统平稳状态分析系统平稳状态分析一、标准的一、标准的 M MM M1 1模型模型第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析P 0 = P1 （1）P n-1+ Pn+1

16、=（+）Pn （2）这是关于这是关于Pn的差分方程。的差分方程。它表明了各状态间的转它表明了各状态间的转移关系。移关系。dPn（t）/dt =P n-1（t）+ Pn+1（t）-（+）Pn（t）3系统平稳状态分析系统平稳状态分析一、标准的一、标准的 M MM M1 1模型模型第三节第三节 单服务台负指数分布排队系统的分析单服务台负指数分布排队系统的分析上式中的上式中的有实际意义：从有实际意义：从 =/来看，它是平均到来看，它是平均到达率与平均服务率之比；它也可以表示为达率与平均服务率之比；它也可以表示为 =（1/1/）/ /（1/1/），含义是为一个顾客的服务时间与到达间隔时间），含义是为一个

17、顾客的服务时间与到达间隔时间之比；根据上面的公式之比；根据上面的公式 =1 - =1 - P 0，它反映了服务机构的，它反映了服务机构的繁忙程度，所以又称服务机构的利用率繁忙程度，所以又称服务机构的利用率( (服务强度服务强度) )， 110P求求P0： 令令 =/ =)第四节第四节 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析第四节第四节 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析状态转移差分方程：状态转移差分方程： P1 = P 0 （n+1）Pn+1 +P n-1 =（+ n）Pn ， n=1,2,c-1 cPn+1 +P n-1 = （+ c）

18、Pn， n =c,c+1，c+2，用递推方法解此差分方程用递推方法解此差分方程(并注意到概率和等于并注意到概率和等于1)得得: )()(!1)()(!1)(11!1)(!1001100cnPccpcnPnpckPncnnnnckck系统运行指标求得如下系统运行指标求得如下: /,/,/)1(!)()(021LqWqLsWsLqLsPccPcnLqccnn所有服务员都忙的概率和所有服务员都忙的概率和平均忙的服务员的个数：平均忙的服务员的个数： /)1( !)/(0ccPcnPc第四节第四节 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析 例例 4 某某售售票票处处有有三三个个窗

19、窗口口, 顾顾客客到到达达服服从从泊泊松松流流，平平均均到到达达率率每每分分钟钟为为0 0. .9 9( (人人) )，服服务务（售售票票）时时间间服服从从负负指指数数分分布布，平平均均服服务务率率 = 0.4(人人)。现现设设顾顾客客到到达达后后排排成成一一队队， 依依次次向向空空闲闲的的窗窗口口购购票票 （如如图图 8-7A） 。 这这是是一一个个标标准准的的 M/M/c 排排队队模模型型。其其中中 c = 3, / /= 2.25, = =/ /c c= = 2 2. .2 25 5/ /3 3. . = =0 0. .3 3 = =0 0. .3 3 = =0 0. .9 9 图图8-

20、7A M/M/c 排排队队系系统统 图图8-7B M/M/1 排排队队系系统统 窗口 =0.4 窗口 =0.4 窗口 =0.4 窗口 =0.4 窗口 =0.4 窗口 =0.4 第四节第四节 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析 解：解：1）整个售票处空闲的概率：）整个售票处空闲的概率： 2）平均排队长度：）平均排队长度： 3）顾客到达后必须等待的概率：）顾客到达后必须等待的概率： 4）其它指标：）其它指标： Ls = Lq +/ / = 1.70 + 2.25 = 3.95 = 1.70 + 2.25 = 3.95 Ws = Ls/ Ws = Ls/ = 3.95/

21、0.9 = 4.39 = 3.95/0.9 = 4.39 Wq = Lq/ Wq = Lq/ = 1.70/0.9 = 1.89 = 1.70/0.9 = 1.89 0748. 03/25. 211! 3)25. 2(! 2)25. 2(! 1)25. 2(! 0)25. 2(132100P70.1)4/1(!34/3)25.2(23Lq57.00748.04/1! 3)25.2()3(3nP第四节第四节 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析两两种种排排队队模模型型的的比比较较 M/M/3 模模型型 M/M1 模模型型 服服务务台台空空闲闲的的概概率率 P0 顾顾客

22、客必必须须等等待待的的概概率率 平平均均排排队队长长度度 Lq 系系统统中中的的平平均均顾顾客客数数 Ls 平平均均逗逗留留时时间间 Ws(分分钟钟) 平平均均等等待待时时间间 Wq(分分钟钟) 0.0748 0.57 1.70 3.95 4.39 1.89 0.25(每每个个子子系系统统) 0.75 2.25(每每个个子子系系统统) 9.00(整整个个系系统统) 10 7.5 第四节第四节 多服务台负指数分布排队系统的分析多服务台负指数分布排队系统的分析设单位时间系统成本的期望值为设单位时间系统成本的期望值为Z。它应是等侯成本。它应是等侯成本与服务成本之和。即与服务成本之和。即 ZCw Ls

23、 + Cs1 其中其中 Cw每一顾客在系统中停留单位时间的费用；每一顾客在系统中停留单位时间的费用； Cs11时服务机构单位时间的费用。时服务机构单位时间的费用。第五节第五节 排队系统的经济分析排队系统的经济分析 MM1排队模型的最优服务率排队模型的最优服务率如果服务率为连续变量，则求系统成本最低的最优服务如果服务率为连续变量，则求系统成本最低的最优服务率可通过以下过程实现：率可通过以下过程实现： CsCwCwCsddZCwCsLsCwCsZ/*0)/()/(2K Ls ZCw Ls + Cs1 3 4 5 6 2 2 2 2 3 4 5 6 2 1 0.67 0.5 202 + 53 = 5

24、5 201 + 54 = 40 200.67 + 55 = 38.3* 200.5 + 56 = 40. 例例 设某机械化装料系统为货车装料。货车平均到达率为设某机械化装料系统为货车装料。货车平均到达率为2辆时，等辆时，等侯成本为侯成本为20元辆元辆时；装料设备的平均服务率为时；装料设备的平均服务率为l辆辆/台台时，服务成本时，服务成本为为5元台元台时。求装料点的最优服务速率，即应配备多少台装料设备。时。求装料点的最优服务速率，即应配备多少台装料设备。 解解：令：令 K为装料点的设备台数；为装料点的设备台数；等候成本等候成本Cw20元辆元辆时；时； 服务成本服务成本Cs =5元台元台时；时；到

25、达率到达率2辆时；辆时； 服务率服务率K(1辆台辆台时时)。为使系统正常运转，应使为使系统正常运转，应使。设。设K3，4，5进行计算，所得结进行计算，所得结果列表中。根据计算结果，装料点配五台设备比较合理。果列表中。根据计算结果，装料点配五台设备比较合理。 MM1排队模型的最优服务率排队模型的最优服务率设单位时间系统成本的期望值为设单位时间系统成本的期望值为Z： ZCwLs + Cs C 其中：其中：Cw每一顾客在系统中停留单位时间的费用；每一顾客在系统中停留单位时间的费用； Cs每一服务机构单位时间的费用；每一服务机构单位时间的费用； C服务机构数；服务机构数；鉴于鉴于C只取整数，按只取整数

26、，按Z（C*）最小这一规定可知：）最小这一规定可知： Z（C*） Z（C*-1）, Z（C*） Z（C*+1）代入代入Z（C）的表达式，有：）的表达式，有： Cs C* + Cw L（C*）Cs（C*-1）+Cw L（C*-1） Cs C* + Cw L（C*）Cs（C*+1）+Cw L（C*+1）合并以上两式得：合并以上两式得： L（C*）- L（C*+1） Cs/CW L（C* - 1）- L（C*）只要依此求出只要依此求出C = 1,2,3, 时的值，并算出相邻的时的值，并算出相邻的L值之差，看已值之差，看已知比值知比值Cs/Cw落在不等式的哪一区间，即可定出落在不等式的哪一区间，即可定

27、出C*的值。的值。 M/M/cM/M/c模型中最优服务机构数模型中最优服务机构数c c 例例 车辆检验中心正在为使用的车辆进行年检。设车车辆检验中心正在为使用的车辆进行年检。设车辆到达是完全随机的，平均到达率辆到达是完全随机的，平均到达率30辆辆/天。因停车检修天。因停车检修使车主损失使车主损失60元，检验时间服从负指数分布，平均服务率元，检验时间服从负指数分布，平均服务率每天每天15辆。每一检验员的服务成本每天辆。每一检验员的服务成本每天40元。问应设几个元。问应设几个检验员？检验员？ 解：解：Cs = 40元，元， Cw = 60元，元，/ = 30/15 = 2， =/C =2/C ，

28、Cs/Cw = 40/60 =0.667 根据根据M/M/c排队模型的相应公式计算排队模型的相应公式计算P0，Ls。M/M/cM/M/c模型中最优服务机构数模型中最优服务机构数c c检车人检车人数数 C车辆数车辆数 Ls(C)L(C)-L(C+1)L(C-1)-L(C)系统成本系统成本Z(C)34*562.892.172.042.020.72-0.130.720.02-0.13293.4290.2*322.4361.2Cs/Cw = 40/60 =0.667, 落在区间落在区间0.130.72之间之间, 故故C* = 4.因为要求因为要求 = 2/C 1， 故从故从C = 3 开始计算。开始计算。计算结果见表。计算结果见表。M/M/cM/M/c模型中最优服务机构数模型中最优服