第14章排队论

管管 理理 运运 筹筹 学学1第十四章排队论第十四章排队论1排队过程的组成部分排队过程的组成部分2单服务台泊松到达、负指数服务时间的排队模型单服务台泊松到达、负指数服务时间的排队模型3多服务台泊松到达、负指数服务时间的排队模型多服务台泊松到达、负指数服务时间的排队模型4排队系统的经济分析排队系统的经济分析5单服务台泊松到达、任意服务时间的排队模型单服务台泊松到达、任意服务时间的排队模型6单服务台泊松到达、定长服务时间的排队模型单服务台泊松到达、定长服务时间的排队模型7多服务台泊松到达、任意的服务时间、损失制排队模型多服务台泊松到达、任意的服务时间、损失制排队模型8顾客来源有限制排队模型顾客来源有限制排队模型9单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型10多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型*11生灭过程及生灭过程排队系统生灭过程及生灭过程排队系统管管 理理 运运 筹筹 学学2一、基本概念一、基本概念一些排队系统的例子一些排队系统的例子排队系统排队系统 顾顾 客客 服务台服务台 服服 务务电话系统电话系统 电话呼叫电话呼叫 电话总机电话总机 接通呼叫或取消呼叫接通呼叫或取消呼叫售票系统售票系统 购票旅客购票旅客 售票窗口售票窗口 收款、售票收款、售票设备维修设备维修 出故障的设备出故障的设备 修理工修理工 排除设备故障排除设备故障防空系统防空系统 进入阵地的敌机进入阵地的敌机 高射炮高射炮 瞄准、射击，敌机被击落或离开瞄准、射击，敌机被击落或离开排队的过程可表示为：排队的过程可表示为：排队排队服务机构服务服务机构服务服务后顾客离去服务后顾客离去排队系统排队系统顾客到达顾客到达1排队过程的组成部分排队过程的组成部分管管 理理 运运 筹筹 学学3考虑要点：考虑要点：1、服务台（或通道）数目：单服务台（单通道）、多服务台（多通道）。、服务台（或通道）数目：单服务台（单通道）、多服务台（多通道）。2、顾客到达过程：本教材主要考虑顾客的泊松到达情况。、顾客到达过程：本教材主要考虑顾客的泊松到达情况。满足以下四个条件的输入流称为泊松流（泊松过程）。满足以下四个条件的输入流称为泊松流（泊松过程）。*平稳性：平稳性：在时间区间在时间区间 t,t+t)内到达内到达k个顾客的概率与个顾客的概率与t无关，只与无关，只与 t 有关，记为有关，记为 pk(t）；）；*无后效性：无后效性：不相交的时间区间内到达的顾客数互相独立；不相交的时间区间内到达的顾客数互相独立；*普通性：普通性：在足够短的时间内到达多于一个顾客的概率可以忽略；在足够短的时间内到达多于一个顾客的概率可以忽略；*有限性：有限性：任意有限个区间内到达有限个顾客的概率等于任意有限个区间内到达有限个顾客的概率等于1。泊松分布泊松分布 为单位时间平均到达的顾客数为单位时间平均到达的顾客数 P(x)=x e-/x!(x=0,1,2,)1排队过程的组成部分排队过程的组成部分管管 理理 运运 筹筹 学学41排队过程的组成部分排队过程的组成部分3、服务时间分布：、服务时间分布：服从负指数分布，服从负指数分布，为平均服务率，即单位时间服务为平均服务率，即单位时间服务的顾客数，的顾客数，P（服务时间（服务时间 t)=1-e-t 。4、排队规则分类、排队规则分类 (1)等待制：等待制：顾客到达后，一直等到服务完毕以后才离去，顾客到达后，一直等到服务完毕以后才离去，先到先服务，后到先服务，随机服务，有优先权的服务；先到先服务，后到先服务，随机服务，有优先权的服务；(2)损失制：损失制：到达的顾客有一部分未接受服务就离去。到达的顾客有一部分未接受服务就离去。5、平稳状态：、平稳状态：业务活动与时间无关。业务活动与时间无关。管管 理理 运运 筹筹 学学5排队系统的符号表示排队系统的符号表示:一个排队系统的特征可以用五个参数表示，形式为：一个排队系统的特征可以用五个参数表示，形式为：ABCDE其中其中A 顾客到达的概率分布，可取顾客到达的概率分布，可取M、D、G、Ek等；等；B 服务时间的概率分布，可取服务时间的概率分布，可取M、D、G、Ek等；等；C 服务台个数，取正整数；服务台个数，取正整数；D 排队系统的最大容量，可取正整数或排队系统的最大容量，可取正整数或；E 顾客源的最大容量，可取正整数或顾客源的最大容量，可取正整数或。例如例如 M/M/1/表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服表示顾客到达过程服从泊松分布，服务时间服从负指数分布，一个服务台，排队的长度无限制和顾客的来源无限制。务台，排队的长度无限制和顾客的来源无限制。1排队过程的组成部分排队过程的组成部分管管 理理 运运 筹筹 学学6M/M/1/单位时间顾客平均到达数单位时间顾客平均到达数 ，单位平均服务顾客数单位平均服务顾客数 ()数量指标公式数量指标公式:1.系统中无顾客的概率系统中无顾客的概率 P0=1 /2.平均排队的顾客数平均排队的顾客数 Lq=2/()3.系统中的平均顾客数系统中的平均顾客数 Ls=Lq+/4.顾客花在排队上的平均等待时间顾客花在排队上的平均等待时间 Wq=Lq/5.顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间 Ws=Wq+1/6.顾客得不到及时服务必须排队等待的概率顾客得不到及时服务必须排队等待的概率 Pw=/7.系统中恰好有系统中恰好有 n 个顾客的概率个顾客的概率 Pn=(/)n P01 排队过程的组成部分排队过程的组成部分2单服务台泊松到达、负指数服务时间的排队模型单服务台泊松到达、负指数服务时间的排队模型管管 理理 运运 筹筹 学学7 2单服务台泊松到达、负指数服务时间的排队模型单服务台泊松到达、负指数服务时间的排队模型 在上面的公式中，我们都认定在上面的公式中，我们都认定 ,即到达率小于服务率，即到达率小于服务率，如果没有这个条件，则排队的长度将如果没有这个条件，则排队的长度将无无限制地增加，服务机构限制地增加，服务机构根本没有能力处理所有到达的顾客，根本没有能力处理所有到达的顾客，也就是也就是 /1,c时时3多服务台泊松到达、负指数服务时间的排队模型多服务台泊松到达、负指数服务时间的排队模型管管 理理 运运 筹筹 学学14 例例 在前例的储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗在前例的储蓄所里多设一个服务窗口，即储蓄所开设两个服务窗口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是口。顾客的到达过程仍服从泊松分布，平均每小时到达顾客仍是36人；储人；储蓄所的服务时间仍服从负指数分布，平均每小时仍能处理蓄所的服务时间仍服从负指数分布，平均每小时仍能处理48位顾客的业务，位顾客的业务，其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。其排队规则为只排一个队，先到先服务。试求这个排队系统的数量指标。解解 C=2，平均到达率平均到达率 =36/60=0.6，平均服务率平均服务率 =48/60=0.8。P0=0.4545,Lq=0.1227 (个个顾客顾客),Ls=Lq+/=0.8727 (个个顾客顾客),Wq=Lq/=0.2045（分钟）（分钟）,Ws=Wq+1/=1.4545（分钟）（分钟）,Pw=0.2045,P1=0.3409,P2=0.1278,P3=0.0479,P4=0.0180,P5=0.0067。系统里有系统里有6个人的概率或多于个人的概率或多于6个人的概率为个人的概率为0.0040。3多服务台泊松到达、负指数服务时间的排队模型多服务台泊松到达、负指数服务时间的排队模型管管 理理 运运 筹筹 学学15 在储蓄所里使用在储蓄所里使用M/M/2模型与使用两个模型与使用两个M/M/1模型，它们的服务台模型，它们的服务台数都是数都是2，服务率和顾客到达率都一样，只是在，服务率和顾客到达率都一样，只是在M/M/2中只排一队，在中只排一队，在2个个M/M/1中排两个队，结果却不一中排两个队，结果却不一 样。样。M/M/2使得服务水平有了很大的提使得服务水平有了很大的提高，每个顾客的平均排队时间从高，每个顾客的平均排队时间从0.75分钟减少到分钟减少到0.2045分钟，每个顾客在系统分钟，每个顾客在系统里逗留时间从里逗留时间从2分钟减少到分钟减少到1.4545分钟，平均排队的人数也从分钟，平均排队的人数也从0.2250人减少到人减少到0.1227人，系统里平均顾客数也从人，系统里平均顾客数也从0.6*2=1.2人减少到人减少到0.8727人。如果把人。如果把M/M/2与原先一个与原先一个M/M/1比较，那么服务水平之间的差别就更大了。比较，那么服务水平之间的差别就更大了。当然在多服务台的当然在多服务台的M/M/C模型中，计算求得这些数量指标是很繁琐的。模型中，计算求得这些数量指标是很繁琐的。管理运筹学软件有排队论的程序，可以由它来计算。管理运筹学软件有排队论的程序，可以由它来计算。我们在第二节与第三节发现公式有三个公式是完全相同的，实际上这三我们在第二节与第三节发现公式有三个公式是完全相同的，实际上这三个公式表示了任一个排队模型（不仅仅是个公式表示了任一个排队模型（不仅仅是M/M/1或或M/M/2）中，）中，Ls,Lq,Ws,Wq之间的关系，也就是说：之间的关系，也就是说：3多服务台泊松到达、负指数服务时间的排队模型多服务台泊松到达、负指数服务时间的排队模型管管 理理 运运 筹筹 学学16 ,(1 4.5),(1 4.6)1,(1 4.7)sqqqsqLLLWWW3多服务台泊松到达、负指数服务时间的排队模型多服务台泊松到达、负指数服务时间的排队模型对任一个排队模型成立，这里对任一个排队模型成立，这里Ls,Lq,Ws,的定义如上所述，而的定义如上所述，而 应为实际应为实际进入系统平均到达率，对于排队长度有限制的模型，我们设因排队长度的进入系统平均到达率，对于排队长度有限制的模型，我们设因排队长度的限制顾客被拒绝的概率为限制顾客被拒绝的概率为PN，则实际进入系统平均到达率应为，则实际进入系统平均到达率应为 这时，原来公式中的这时，原来公式中的 应改为应改为 。1NP1NP管管 理理 运运 筹筹 学学17 我们把一个排队系统的单位时间的总费用我们把一个排队系统的单位时间的总费用TC定义为服务机构的单位时间定义为服务机构的单位时间的费用和顾客在排队系统中逗留单位时间的费用之和。即的费用和顾客在排队系统中逗留单位时间的费用之和。即TC=cw Ls+cs c其中其中 cw为一个顾客在排队系统中逗留单位时间付出的费用；为一个顾客在排队系统中逗留单位时间付出的费用；Ls为在排队系统为在排队系统中的平均顾客数；中的平均顾客数；cs为每个服务台单位时间的费用；为每个服务台单位时间的费用；c为服务台的数目。为服务台的数目。例例 在前两例中，设在前两例中，设储蓄所的每个储蓄所的每个服务台的费用服务台的费用cs=18，顾客在，顾客在储蓄所储蓄所中中逗留一小时的成本逗留一小时的成本cw=10。这样，对。这样，对储蓄所储蓄所M/M/1 模型可知模型可知 Ls=3，c=1，得得TC=cw Ls+cs c=48 元元/每小时。每小时。对对储蓄所储蓄所 M/M/2 模型可知模型可知 Ls=0.8727，c=2，得，得TC=cw Ls+cs c=44.73 元元/每小时。每小时。4排队系统的经济分析排队系统的经济分析管管 理理 运运 筹筹 学学18 M/G/1/单位时间顾客平均到达数单位时间顾客平均到达数 ，单位平均服务顾客数，单位平均服务顾客数 ，一个顾客的平均服务时间一个顾客的平均服务时间 1/，服务时间的均方差，服务时间的均方差。数量指标公式数量指标公式:1.系统中无顾客的概率系统中无顾客的概率 P0=1 /2.平均排队的顾客数平均排队的顾客数 3.系统中的平均顾客数系统中的平均顾客数 Ls=Lq+/4.顾客花在排队上的平均等待时间顾客花在排队上的平均等待时间 Wq=Lq/5.在系统中顾客的平均逗留时间在系统中顾客的平均逗留时间 Ws=Wq+1/6.系统中顾客必须排队等待的概率系统中顾客必须排队等待的概率 Pw=/7.系统中恰好有系统中恰好有 n 个顾客的概率个顾客的概率 Pn)/1(2)/(222qL5单服务台泊松到达、任意服务时间的排队模型单服务台泊松到达、任意服务时间的排队模型管管 理理 运运 筹筹 学学19 例例1 某杂货店只有一名售货员，已知顾客的到达过程服从泊松分布，某杂货店只有一名售货员，已知顾客的到达过程服从泊松分布，平均到达率为每小时平均到达率为每小时20人；不清楚这个系统的服务时间服从什么分布，但人；不清楚这个系统的服务时间服从什么分布，但从统计分析知道售货员平均服务一名顾客的时间为从统计分析知道售货员平均服务一名顾客的时间为2分钟，服务时间的均分钟，服务时间的均方差为方差为1.5分钟。试求这个排队系统的数量指标。分钟。试求这个排队系统的数量指标。解：解：这是一个这是一个 M/G/1 的排队系统，其中的排队系统，其中 =20/60=0.3333 人人/分钟，分钟，1/=2分钟分钟，=0.5 人人/分钟，分钟，=1.5。P0=1 /=0.33334,Lq=1.0412 (人人),Ls=Lq+/=1.7078(人人),Wq=Lq/=2.25/0.6=3.1241（分钟）（分钟）,Ws=Wq+1/=5.1241（分钟）（分钟）,Pw=/=0.6666。5单服务台泊松到达、任意服务时间的排队模型单服务台泊松到达、任意服务时间的排队模型管管 理理 运运 筹筹 学学206单服务台泊松到达、定长服务时间的排队模型单服务台泊松到达、定长服务时间的排队模型 M/D/1/注：它是注：它是 M/G/1/的特殊情况的特殊情况 =0。1.系统中无顾客的概率系统中无顾客的概率 P0=1 /2.平均排队的顾客数平均排队的顾客数 3.系统中的平均顾客数系统中的平均顾客数 Ls=Lq+/4.顾客花在排队上的平均等待时间顾客花在排队上的平均等待时间 Wq=Lq/5.在系统中顾客的平均逗留时间在系统中顾客的平均逗留时间 Ws=Wq+1/6.系统中顾客必须排队等待的概率系统中顾客必须排队等待的概率 Pw=/7.系统中恰好有系统中恰好有 n 个顾客的概率个顾客的概率 Pn)/1(2)/(222qL管管 理理 运运 筹筹 学学21 例例2 某汽车冲洗服务营业部，有一套自动冲洗设备，冲洗每辆车需要某汽车冲洗服务营业部，有一套自动冲洗设备，冲洗每辆车需要6分钟，到此营业部来冲洗的汽车到达过程服从泊松分布，每小时平均到分钟，到此营业部来冲洗的汽车到达过程服从泊松分布，每小时平均到达达6辆，试求这个排队系统的数量指标。辆，试求这个排队系统的数量指标。解：解：这是一个这是一个 M/D/1 排队模型，其中排队模型，其中 =6辆辆/小时，小时，=60/6=10辆辆/小时小时，得，得P0=1 /=0.4,Lq=0.45,Ls=Lq+/=1.05,Wq=Lq/=0.0750，Ws=Wq+1/=0.1750,Pw=/=0.6。6单服务台泊松到达、定长服务时间的排队模型单服务台泊松到达、定长服务时间的排队模型管管 理理 运运 筹筹 学学22 M/G/C/C/注：不存在平均排队的顾客数注：不存在平均排队的顾客数 Lq 和顾客平均的排队等待时间和顾客平均的排队等待时间 Wq。数数量指标公式量指标公式:系统中的平均顾客数系统中的平均顾客数 Ls=/(1 Pc)其中其中Pc 是系统中恰好有是系统中恰好有 c 个顾客的概率，也就是系统里个顾客的概率，也就是系统里c 个服务台都个服务台都被顾客占满的概率。被顾客占满的概率。系统中恰好有系统中恰好有 n 个顾客的概率个顾客的概率 eiinninp0!/)/(!/)/(7多服务台泊松到达、任意的服务时间、损失制排队模型多服务台泊松到达、任意的服务时间、损失制排队模型管管 理理 运运 筹筹 学学23例例3.某电视商场专营店开展了电话订货业务，到达过程服从泊松分布，平某电视商场专营店开展了电话订货业务，到达过程服从泊松分布，平均到达率为每小时均到达率为每小时16个，而一个接话员处理订货事宜的时间是随着订货的个，而一个接话员处理订货事宜的时间是随着订货的产品、规格、数量及顾客的不同而变化的，但平均每个人每小时可以处理产品、规格、数量及顾客的不同而变化的，但平均每个人每小时可以处理8个订货电话，在此电视商场专营店里安装了一台电话自动交换台，它接个订货电话，在此电视商场专营店里安装了一台电话自动交换台，它接到电话后可以接到任一个空闲的接话员的电话上，试问该公司应安装多少到电话后可以接到任一个空闲的接话员的电话上，试问该公司应安装多少台接话员的电话，使得订货电话因电话占线而损失的概率不超过台接话员的电话，使得订货电话因电话占线而损失的概率不超过10%。解：这是一个解：这是一个 M/G/C/C/模型。当模型。当c=3时，即正好有时，即正好有3位顾客的位顾客的情况，情况，30333!3/)/(!3/)/(ip2105.06/)8/16(2/)8/16(1/)8/16(1/)8/16(6/)8/16(321037多服务台泊松到达、任意的服务时间、损失制排队模型多服务台泊松到达、任意的服务时间、损失制排队模型管管 理理 运运 筹筹 学学240.21050.1,所以不符合要求。所以不符合要求。当当c=4时，时，因此，设置四个电话很合适。因此，设置四个电话很合适。40444!4/)/(!4/)/(ip1.00952.00952.024/)8/16(6/)8/16(2/)8/16(1/)8/16(1/)8/16(24/)8/16(43210481.1)0952.01(8/16)1(/4pLs7多服务台泊松到达、任意的服务时间、损失制排队模型多服务台泊松到达、任意的服务时间、损失制排队模型管管 理理 运运 筹筹 学学25 M/M/1/m条件：单位时间顾客平均到达数条件：单位时间顾客平均到达数 单位平均服务顾客数单位平均服务顾客数 关心的项目关心的项目:1.系统中无顾客的概率系统中无顾客的概率 P0 2.系统中平均排队的顾客数系统中平均排队的顾客数 Lq 3.系统中的平均顾客数系统中的平均顾客数 Ls 4.系统中顾客平均的排队等待时间系统中顾客平均的排队等待时间 Wq 5.系统中顾客的平均逗留时间系统中顾客的平均逗留时间 Ws 6.系统中顾客必须排队等待的概率系统中顾客必须排队等待的概率 Pw 7.系统中恰好有系统中恰好有 n 个顾客的概率个顾客的概率 Pn8顾客来源有限制的排队模型顾客来源有限制的排队模型管管 理理 运运 筹筹 学学26 M/M/1/m数量指标公式数量指标公式:1.系统中无顾客的概率系统中无顾客的概率 2.平均排队的顾客数平均排队的顾客数 3.系统中的平均顾客数系统中的平均顾客数 Ls=Lq+(1-p0)4.顾客在排队上的平均花费等待时间顾客在排队上的平均花费等待时间 Wq=Lq/（m-Ls)5.在系统中顾客的平均逗留时间在系统中顾客的平均逗留时间 Ws=Wq+1/6.系统中有系统中有 n 个顾客的概率个顾客的概率mnnnmmp00)()!(!1)1(0pmLq0)()!(!pnmmpnn,n=0,1,2,m8顾客来源有限制的排队模型顾客来源有限制的排队模型管管 理理 运运 筹筹 学学27例例4.某车间有某车间有5台机器，每台机器连续运转时间服从负指数分布，平均连台机器，每台机器连续运转时间服从负指数分布，平均连续运转时间为续运转时间为15分钟，有一个修理工，每次修理时间服从负指数分布，平分钟，有一个修理工，每次修理时间服从负指数分布，平均每次均每次12分钟，求该排队系统的数量指标分钟，求该排队系统的数量指标P0,Lq,Ls,Wq,Ws,以及以及P5。解：这是一个解：这是一个M/M/1/5系统。其中，系统。其中，m=5,=1/15,=1/12,/=0.8。Lq=2.766 ;Ls=3.759Wq=33.43 ;Ws=45.43P5=0.287015432100)8.0(!0!5)8.0(!1!5)8.0(!2!5)8.0(!3!5)8.0(!4!5)8.0(!5!5p=0.00738顾客来源有限制的排队模型顾客来源有限制的排队模型管管 理理 运运 筹筹 学学289单服务台泊松到达、负指数服务时间、系统容量有单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型限制的排队模型 KnKnn,01,.2,1,0,这种模型我们记为这种模型我们记为M/M/1/K/，这个记法中的第四位字母，这个记法中的第四位字母K表示这个表示这个系统的最大容量为系统的最大容量为N，因为这是一个单服务台的情况，所以排队的顾客服，因为这是一个单服务台的情况，所以排队的顾客服务最多为务最多为K-1，在某时刻一顾客到达时，如系统中已有，在某时刻一顾客到达时，如系统中已有N个顾客，那么这个个顾客，那么这个顾客就被拒绝进入系统。顾客就被拒绝进入系统。这个模型可简写为这个模型可简写为M/M/1/K。由于所考虑的排队子系统中最多只能容纳由于所考虑的排队子系统中最多只能容纳K个顾客（等待位置只有个顾客（等待位置只有K-1个），因而有个），因而有:令令 ，有：有：1,111,1110KPK1,21,1)1(111KKLKks1,)1(2)1(1,1)1(11KKKKLKKq1.1.系统里没有顾客的概率系统里没有顾客的概率2.2.在系统里的平均顾客数在系统里的平均顾客数3.3.平均的排队顾客数平均的排队顾客数管管 理理 运运 筹筹 学学299单服务台泊松到达、负指数服务时间、系统容量有单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型限制的排队模型 4.4.有效顾客到达率有效顾客到达率5.5.一位顾客花在排队上的平均时间一位顾客花在排队上的平均时间)1(0)1(KKKePPPeqKqqLPLw)1(6.6.一位顾客在系统中的平均逗留时间一位顾客在系统中的平均逗留时间esKssLPLw)1(7.7.在系统里正好有在系统里正好有n n个顾客的概率个顾客的概率KnPPnn,.,2,1,0管管 理理 运运 筹筹 学学309单服务台泊松到达、负指数服务时间、系统容量有单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型限制的排队模型 例例5 5 某理发店只有一个理发师，且店里最多可容纳某理发店只有一个理发师，且店里最多可容纳4 4名顾客，名顾客，设顾客按泊松流到达，平均每小时设顾客按泊松流到达，平均每小时5 5人，理发时间服从负指数人，理发时间服从负指数分布，平均每分布，平均每1515分钟可为分钟可为1 1名顾客理发，试求该系统的有关指名顾客理发，试求该系统的有关指标。标。解：该系统可以看成一个解：该系统可以看成一个M/M/1/4M/M/1/4排队系统，其中排队系统，其中)/(5小小时时人人4,145)/(41560K，小时小时人人122.0125.1141)45(1451550P44401.250.1220.298PP顾客损失率为：4(1)5(10.298)3.51/eP有效到达率为：（人 小时）管管 理理 运运 筹筹 学学319单服务台泊松到达、负指数服务时间、系统容量有单服务台泊松到达、负指数服务时间、系统容量有限制的排队模型限制的排队模型 111)1(1KKsKL)(44.225.1125.1)14(25.1125.155人人)(56.125.11)25.141(25.125.1125.11)1(1541人人KKqKL)(696.051.344.2小小时时essLw)(44.051.356.1小时小时eqqLw系统里平均顾客数系统里平均顾客数=平均的排队顾客数平均的排队顾客数平均逗留时间平均逗留时间平均排队时间平均排队时间管管 理理 运运 筹筹 学学321010多服务台泊松到达、负指数服务时间、系统多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型容量有限制的排队模型 这种排队模型我们记为这种排队模型我们记为M/M/C/K/M/M/C/K/，这与第九节单服务台模型的，这与第九节单服务台模型的区别，就在于服务台的数量为区别，就在于服务台的数量为C C，我们可以把这个模型简记为，我们可以把这个模型简记为M/M/C/KM/M/C/K。在此系统中到达率与服务率分别为在此系统中到达率与服务率分别为:KnKnn,01,.1,0,KnCCCnnn,0,0,nnKCCn令，则对任意令有：1,)1(!)(!)(1,1)(!)(11011100CKCCnCCCnCPCCnnKCCCnn00(),1,2,.1!,1,.!nnCnCP nCnPCP nC CKC1.1.系统里没有顾客的概率系统里没有顾客的概率 2.2.系统里正好有系统里正好有n n个顾客的概率个顾客的概率管管 理理 运运 筹筹 学学331010多服务台泊松到达、负指数服务时间、系统多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型容量有限制的排队模型KCnnqPcnL)(3.3.平均排队顾客数平均排队顾客数1020()1(1)(1),1!(1)()()(1),12!CK CK CnCP CKCCPP CKC KCC)1(kqsPLL4.4.系统里的平均排队顾客数系统里的平均排队顾客数)1(0)1(kkkePPP5.5.有效到达率有效到达率eqkqqPLW)1(6.6.顾客花在排队上的平均时间顾客花在排队上的平均时间eskssPLW)1(7.7.顾客在系统里的平均逗留时间顾客在系统里的平均逗留时间 特别地，当特别地，当k=ck=c时即为第七节的时即为第七节的M/M/C/C/M/M/C/C/的模型。的模型。管管 理理 运运 筹筹 学学341010多服务台泊松到达、负指数服务时间、系统多服务台泊松到达、负指数服务时间、系统容量有限制的排队模型容量有限制的排队模型 例例6 6 某公司维修服务中心有两名维修工，中心内至多可以停放某公司维修服务中心有两名维修工，中心内至多可以停放6 6台机台机器（包括正在维修的两台机器）。假设待修机器按泊松分布过程到达此中器（包括正在维修的两台机器）。假设待修机器按泊松分布过程到达此中心。平均每小时心。平均每小时3 3台。维修每台机器平均需要台。维修每台机器平均需要2020分钟，试求该系统的各项分钟，试求该系统的各项性能指数。性能指数。解：该子系统可看成一个解：该子系统可看成一个M/M/2/6M/M/2/6排队系统排队系统1510054204666013/3/2022110.50.34!2!(10.5)0.340.510.5(10.5)50.50.282!(10.5)11(1)0.772220.2616(1)3(1)nqsqssqqPnLLLPLWPLWP其中（台 小时）（台 小时），则有：（台）（台）（小时）（分钟）0.096（小时）（分钟）管管 理理 运运 筹筹 学学3511*生灭过程及生灭过程排队系统生灭过程及生灭过程排队系统1.1.生灭过程生灭过程 生灭过程是一类非常简单具有广泛应用的一类随机过程，很多排队生灭过程是一类非常简单具有广泛应用的一类随机过程，很多排队模型中都假设其状态过程为生灭过程；这样的排队子系统如：模型中都假设其状态过程为生灭过程；这样的排队子系统如：M/M/CM/M/C和和M/M/C/RM/M/C/R，我们也可称之为生灭过程的排队系统。在这样的排队系统中，我们也可称之为生灭过程的排队系统。在这样的排队系统中，一个新顾客的到达看作一个新顾客的到达看作“生生”，一个顾客服务完之后离开系统看作是，一个顾客服务完之后离开系统看作是“死死”，设，设N(t)N(t)的任意时刻的任意时刻t t排队系统的状态（即排队子系统中的总顾客排队系统的状态（即排队子系统中的总顾客数），则对数），则对M/M/C/KM/M/C/K系统系统N(t)N(t)具有有限个状态具有有限个状态0 0，1 1，,k,k,对对M/M/CM/M/C来说来说N(tN(t)具有可列个状态具有可列个状态0 0，1 1，22。一般来说，随机过程一般来说，随机过程 满足以下条件，称为生灭过程：满足以下条件，称为生灭过程：1)1)假设假设N(t)=nN(t)=n，则从时刻，则从时刻t t起到下一个顾客到达时刻为止的时间服起到下一个顾客到达时刻为止的时间服从参数为从参数为 的负指数分布，的负指数分布，n=0,1,2,n=0,1,2,2)2)假设假设N(t)=nN(t)=n，则从时刻，则从时刻t t起到下一个顾客离去时刻为止的时间服起到下一个顾客离去时刻为止的时间服从参数为从参数为 的负指数分布，的负指数分布，n=0,1,2,n=0,1,2,3)3)同一时刻时只有一个顾客到达或离去。同一时刻时只有一个顾客到达或离去。0()tN tnn管管 理理 运运 筹筹 学学3611*生灭过程及生灭过程排队系统生灭过程及生灭过程排队系统2.2.生灭过程稳态方程生灭过程稳态方程 1,)(11110011npppppnnnnnnn 11010101nPPPnnn方程为：方程为：由此可求得生灭过程的平稳状态分布：由此可求得生灭过程的平稳状态分布：10nnP110 nPPP10101012010100 PPPXPnn1100101 nnnP由于由于即有即有即有即有即有即有管管 理理 运运 筹筹 学学3711*生灭过程及生灭过程排队系统生灭过程及生灭过程排队系统 1001nnn即当即当时，此生灭过程存在平稳状态分布：时，此生灭过程存在平稳状态分布：110010120011113 1,1,2,nnnnnnnnPPP n 管管 理理 运运 筹筹 学学3811*生灭过程及生灭过程排队系统生灭过程及生灭过程排队系统 M/M/C M/M/C和和M/M/C/KM/M/C/K排队系统，顾客到达间隔服从排队系统，顾客到达间隔服从参数为参数为 的负指的负指数分布，顾客在系统中服务时间服从参数为数分布，顾客在系统中服务时间服从参数为 的负指数分布，并满的负指数分布，并满足生灭过程的其他条件。它们都是生灭过程的排队系统，我们都可以从生足生灭过程的其他条件。它们都是生灭过程的排队系统，我们都可以从生灭过程的平衡方程来推导出这些排队公式。我们以灭过程的平衡方程来推导出这些排队公式。我们以M/M/1M/M/1系统为例进行推系统为例进行推导。在这个系统中，导。在这个系统中，0 0 10110,1,2,0,1,2,13 11111111(1)nnnnnnnnnnPP 令，则由可知：当时管管 理理 运运 筹筹 学学3911*生灭过程及生灭过程排队系统生灭过程及生灭过程排队系统 同时也可计算出此系统的其他性能指标同时也可计算出此系统的其他性能指标:23234001232111(1)(1)(23.)(23.).,011:(1)1()nsnnsqnnnsnnnLnPnLLnPnPPLW q在系统中的平均顾客数：或(2)排队平均顾客数L关于顾客在系统中逗留时间随即变量 在M/M/1情况下，他服从参数为-()()()1,0()()wwF wewf we 的负指数分布，即：分布函数概率密度于是得：管管 理理 运运 筹筹 学学4011*生灭过程及生灭过程排队系统生灭过程及生灭过程排队系统()0(3):1()(4):111swsqqsWwE wwedwWww 在系统中顾客平均逗留时间在系统中顾客花在排队上的平均时间同样我们也可用生灭过程的平衡方程推导出同样我们也可用生灭过程的平衡方程推导出M/M/1/KM/M/1/K系统的公式。系统的公式。在这个系统中在这个系统中,knknn,01,.2,1,0,knn,.,2,1,管管 理理 运运 筹筹 学学4111*生灭过程及生灭过程排队系统生灭过程及生灭过程排队系统1100101000131,0,1,1111,2,1,11111,1,2,.111,1,2,.nnkkjnnjknnnnnkPPPnkkPPP nkPkPP nk令，则由，对任意令，得：；于是当时，该系统的状态分布为：当时，该系统的状态分布为：利用上面给出的平稳状态的分布，即可推出此系统的其他性能指标。利用上面给出的平稳状态的分布，即可推出此系统的其他性能指标。这些指标我们已经在前面告诉大家了（计算过程从略）。这些指标我们已经在前面告诉大家了（计算过程从略）。