运筹学排队论

《运筹学排队论》由会员分享，可在线阅读，更多相关《运筹学排队论（31页珍藏版）》请在装配图网上搜索。

1、 排队系统的基本知识 组成、排队模型的符号表示、服务系统的组成、排队模型的符号表示、服务系统的运行指标、排队系统的常见分布运行指标、排队系统的常见分布 单服务台指数分布排队系统 多服务台指数分布排队系统 主要内容 排队论是研究服务过程中拥挤现象的数学理论。排队论是研究服务过程中拥挤现象的数学理论。顾客购物、排队上车、汽车加油、病人看病、电话呼叫等顾客购物、排队上车、汽车加油、病人看病、电话呼叫等 需求和服务需求和服务 基本特征基本特征 顾客：请求服务的人或物；顾客：请求服务的人或物； 服务机构（服务员、服务台）：为顾客服务的人或物；服务机构（服务员、服务台）：为顾客服务的人或物； 顾客到达的间

2、隔时间。顾客到达的间隔时间。 顾客源顾客源 排队结构排队结构 服务机构服务机构 离去离去服务服务规则规则1.1.1 1.1.1 组成部分：组成部分：输入过程、排队规则、服务机构1. 输入过程：顾客按怎样的规律到达的。输入过程：顾客按怎样的规律到达的。(1) 顾客源数：可能有限，可能无限；顾客源数：可能有限，可能无限；(2) 顾客到达的方式顾客到达的方式(或类型或类型)：单个或成批；：单个或成批；(3) 顾客相继到达的时间间隔分布：确定或随机。顾客相继到达的时间间隔分布：确定或随机。2. 排队规则：顾客接受服务的先后次序问题。排队规则：顾客接受服务的先后次序问题。(1) 损失制损失制：顾客到达服

3、务系统时，若服务员都不空：顾客到达服务系统时，若服务员都不空闲，则顾客离去，另求服务。闲，则顾客离去，另求服务。(2) 等待制等待制：顾客到达服务系统时，若服务员都不空：顾客到达服务系统时，若服务员都不空闲，则排队等候服务。闲，则排队等候服务。 先到先服务；随机服务；后到先服务：优先权服务(3) 混合制混合制：顾客到达服务系统时，若服务员都不空：顾客到达服务系统时，若服务员都不空闲，两种可能：闲，两种可能：排队长度有限排队长度有限的服务系统、的服务系统、排队排队时间有限时间有限的服务系统。的服务系统。(1) 服务员的个数和结构：服务员的个数和结构：图图1是单服务台、单队列是单服务台、单队列(2

4、) 服务方式：对顾客是服务方式：对顾客是单个或成批服务。单个或成批服务。(3) 服务时间遵循的分布：服务时间遵循的分布：定长分布定长分布(D)、负指、负指数分布数分布(M)、k阶爱尔阶爱尔朗分布朗分布(Ek)、一般分、一般分布布(G)等。等。4. 4. 排队模型的符号表示排队模型的符号表示 特征中最主要的、影响最大的有：特征中最主要的、影响最大的有：（1）顾客相继到达的时间间隔分布顾客相继到达的时间间隔分布(A)；（2）服务时间的概率分布服务时间的概率分布(B) ；（3）服务员（台）的个数）服务员（台）的个数(C ) ；（4）排队系统的容量，即系统内中允许的最大顾客）排队系统的容量，即系统内中

5、允许的最大顾客数数(d) ；（5）顾客源的总体数目）顾客源的总体数目(e) 。 排队模型的符号为：排队模型的符号为：A/B/C/d/e/f，默认默认f先到先服务。先到先服务。例如：例如：M/M/1/ / ； M/M/1/N/ ； M/M/C/ / :1.1.2 1.1.2 排队系统研究的问题排队系统研究的问题 为了估计服务系统的服务质量，判断服务系统的为了估计服务系统的服务质量，判断服务系统的结构是否合理，是否需要采取改进措施，需要提结构是否合理，是否需要采取改进措施，需要提出服务系统的运行指标。出服务系统的运行指标。（1）单位时间内到达的顾客数的期望值）单位时间内到达的顾客数的期望值( )：

6、单位时：单位时间内的平均到达率。间内的平均到达率。（2）单位时间内服务的顾客数的期望值）单位时间内服务的顾客数的期望值( )：（3）队长）队长(L):系统内顾客数的期望值，即系统内平均系统内顾客数的期望值，即系统内平均顾客数。顾客数。（4）队列长）队列长(Lq):系统内排队顾客数的期望值。系统内排队顾客数的期望值。1.1.2 1.1.2 排队系统研究的问题排队系统研究的问题（5）顾客在系统内停留时间的期望值）顾客在系统内停留时间的期望值(W):等于在系等于在系统内排队等待时间与服务时间。统内排队等待时间与服务时间。（6）顾客在系统内等待时间的期望值）顾客在系统内等待时间的期望值(Wq):从顾客

7、到从顾客到达时刻至开始接受服务时刻止。达时刻至开始接受服务时刻止。顾客最关心的是等待时间（7）忙期分布：服务员在二次空闲之间连续工作的）忙期分布：服务员在二次空闲之间连续工作的时间长度。时间长度。（8）闲期分布：服务员在二次工作之间连续空闲的）闲期分布：服务员在二次工作之间连续空闲的时间长度。时间长度。1.1.2 1.1.2 排队系统研究的问题排队系统研究的问题（9）服务设备利用率：服务设备工作时间占总时间）服务设备利用率：服务设备工作时间占总时间的比例。是衡量服务设备工作强度、磨损和疲劳的比例。是衡量服务设备工作强度、磨损和疲劳程度的指标，应在设计阶段完成。程度的指标，应在设计阶段完成。（1

8、0）顾客损失率：因服务能力不足而造成顾客损）顾客损失率：因服务能力不足而造成顾客损失的比率。损失率过高会减少利润，采用损失制失的比率。损失率过高会减少利润，采用损失制的系统非常重视。的系统非常重视。 忙期及忙期中平均完成服务的顾客数是衡量服务机构效率的指标。1.1.3 1.1.3 排队中常见的几种理论分布排队中常见的几种理论分布1. 泊松分布泊松分布 设设N(t)表示在时间表示在时间0,t内到达的顾客数内到达的顾客数(t0)，令，令 Pn(t1,t2) 表示在表示在 t1,t2 内有内有n个顾客到达的概率，个顾客到达的概率， Pn (t1,t2)= PN (t2)-N(t1)=n。当。当Pn(

9、t1,t2)满足下列三满足下列三个条件时，称顾客到达服从泊松分布。个条件时，称顾客到达服从泊松分布。 a平稳性平稳性: 在（在（ t ，t十十 t）内到达）内到达1个顾客的概率与个顾客的概率与起始时刻起始时刻t无关，而只与无关，而只与 t成正比。并记此概率为：成正比。并记此概率为： P1 ( t，t十十 t )= t十十0 ( t )1.1.3 1.1.3 排队中常见的几种理论分布排队中常见的几种理论分布b无后效性无后效性: 在互不相交的时间区段在互不相交的时间区段 t1， t2内，内，到达的顾客数是相互独立的。例到达的顾客数是相互独立的。例:顾客到商店购顾客到商店购物。物。c普通性普通性:

10、在充分小的间隔时间在充分小的间隔时间 t内，有内，有2个或以上个或以上顾客来系统的概率极小，可忽略。顾客来系统的概率极小，可忽略。 Pn ( t,t十十 t )=0 ( t )，n=2,3, 顾客到达数为顾客到达数为n的概率为的概率为 0,.,1 , 0,! tnenttPtnn 2. 负指数分布负指数分布2.1 定理定理 若顾客到达形成参数为若顾客到达形成参数为 的泊松流，则两顾的泊松流，则两顾客相继到达的间隔时间客相继到达的间隔时间T服从参数为服从参数为 的负指数分布的负指数分布。即即T的分布函数的分布函数 FT(t)=1- e- t 分布密度为分布密度为 f(t)= e- t 负指数分布

11、的数学期望等于均方差负指数分布的数学期望等于均方差: E(t)=1/ = D(t)-1/2 由于由于 表示单位时间内平均到达的顾客数，故表示单位时间内平均到达的顾客数，故1/ 表示相继顾客到达的平均间隔时间。表示相继顾客到达的平均间隔时间。 可以证明，可以证明，相继到达间隔时间是独立的且为负指数相继到达间隔时间是独立的且为负指数分布与输入过程为泊松流是等价的分布与输入过程为泊松流是等价的。2. 负指数分布负指数分布2.2 服务时间的分布：服务时间的分布： 对一个顾客的服务时间就是在忙期中相继离开对一个顾客的服务时间就是在忙期中相继离开系统的两顾客的间隔时间。一般在观察系统的输出系统的两顾客的间

12、隔时间。一般在观察系统的输出时，可以将输出看作输入，若满足泊松流的三个条时，可以将输出看作输入，若满足泊松流的三个条件，则输出形成参数为件，则输出形成参数为 的负指数分布。的负指数分布。 Fv(t)=1- e- t3. K阶爱尔朗分布阶爱尔朗分布 如果服务工作是由如果服务工作是由k个子工作所组成，而每个子工作花费的时个子工作所组成，而每个子工作花费的时间服从参数相同的指数分布，则服务时间服从间服从参数相同的指数分布，则服务时间服从 k阶爱尔朗分布阶爱尔朗分布（kl，2，3，）。如果每项工作平均完成时间是）。如果每项工作平均完成时间是 1/(k )，则，则 k项子工作期望完成时间是项子工作期望完

13、成时间是k/(k ) = 1/ ，这就是整个服务工作的，这就是整个服务工作的期望完成时间。服从期望完成时间。服从 k阶爱尔朗分布的服务时间，其密度函数为：阶爱尔朗分布的服务时间，其密度函数为： E(T)=1/ ，D (T)=1/(k )2 当服务时间服从当服务时间服从k阶爱尔朗分布时，并非实际服务工作一定可阶爱尔朗分布时，并非实际服务工作一定可以分为以分为k个子工作，只不过它的完成时间的概率分布与个子工作，只不过它的完成时间的概率分布与k 个相同个相同指数分布的子工作完成时间的概率分布相当而已。指数分布的子工作完成时间的概率分布相当而已。 tkkkkektktf!112.1 M/M/1/ /

14、模型模型 又称为标准的又称为标准的M/M/1模型，是符合下列条件的排队系统：模型，是符合下列条件的排队系统： 1输入过程：顾客源是无限的，顾客单个到来，相互独立，输入过程：顾客源是无限的，顾客单个到来，相互独立，顾客相继到达的间隔时间服从参数为顾客相继到达的间隔时间服从参数为 的负指数分布。的负指数分布。 2排队规则：单队，且队长没有限制，先到先服务。排队规则：单队，且队长没有限制，先到先服务。 3服务机构：单服务台，各顾客的服务时间是相互独立的，服务机构：单服务台，各顾客的服务时间是相互独立的，服从相同的负指数分布。服从相同的负指数分布。 在求出主要运行指标时，首先要求出系统在任一时刻在求出

15、主要运行指标时，首先要求出系统在任一时刻t的状的状态为态为n（有（有n个顾客）的概率个顾客）的概率Pn(t)。仅讨论。仅讨论Pn(t)的稳态解。的稳态解。 所谓稳态解，是指系统运行时间所谓稳态解，是指系统运行时间t充分大时所得到充分大时所得到的解，此时系统状态的概率分布已不随时间而变化，的解，此时系统状态的概率分布已不随时间而变化，达到达到(统计统计)平衡。也就是说，在运行充分长时间以后，平衡。也就是说，在运行充分长时间以后，在任一时刻系统处于状态在任一时刻系统处于状态n的概率为常数的概率为常数。虽然在理。虽然在理论上，系统要经过无限长的时间才会进入稳态。但论上，系统要经过无限长的时间才会进入

16、稳态。但实际上，一般总是很快就达到稳态；因而计算系统实际上，一般总是很快就达到稳态；因而计算系统在稳态下的一些运行指标，是能够反映系统的正常在稳态下的一些运行指标，是能够反映系统的正常情况的。后面所给出的都为稳态解。情况的。后面所给出的都为稳态解。2.1.1 系统的稳态解系统的稳态解归纳为：归纳为： P0=1- 0 1 Pn= n (1- ) n1 其中：其中： / = 1/ /(1/ )相同时间间隔内顾客到达的相同时间间隔内顾客到达的平均数与被服务的顾客平均数之比，或是一个顾客的平均服平均数与被服务的顾客平均数之比，或是一个顾客的平均服务时间与顾客相继到达的平均时间间隔之比。它反应了服务务时

17、间与顾客相继到达的平均时间间隔之比。它反应了服务效率和服务机构的利用程度，叫服务强度。效率和服务机构的利用程度，叫服务强度。2.1.2 系统的数量指标系统的数量指标1)服务台空的概率：服务台空的概率： P0=1- 服务台忙的概率：服务台忙的概率： 2)系统中顾客数的期望值：系统中顾客数的期望值：3)排队等待服务顾客数的期望值：排队等待服务顾客数的期望值：4)顾客在系统中排队等待时间的期望值：顾客在系统中排队等待时间的期望值：5)顾客在系统中逗留时间的期望值：顾客在系统中逗留时间的期望值：适合不同的服务规则（优先权服务除外）。适合不同的服务规则（优先权服务除外）。)(122 qL)( qW11s

18、qWW 1sL例例1：1. 理发店空闲的概率理发店空闲的概率2. 店内有店内有3个顾客的概率个顾客的概率3. 店内至少有一个顾客的概率店内至少有一个顾客的概率4. 店内顾客的平均数，等待服务顾客的平均数店内顾客的平均数，等待服务顾客的平均数5. 顾客在店内的平均逗留时间和平均等待时间顾客在店内的平均逗留时间和平均等待时间6. 必须在店内消耗必须在店内消耗15分钟以上的概率分钟以上的概率 某理发店只一名理发师，来理发的顾客按泊松某理发店只一名理发师，来理发的顾客按泊松分布到达，平均每小时分布到达，平均每小时4人，理发时间服从负人，理发时间服从负指数分布，平均需要指数分布，平均需要6分钟，求：分钟

19、，求： 解解 此为此为M/M/1系统，已知系统，已知 =4/60=1/15（人（人/分）分） =1/6（人（人/分），分）， = / =(1/15)/(1/6)=0.4(1) P0 0=1 =1=0.4=0.6(2) P3 3=(1 ) 3=0.6*0.43=0.0384(3) P(n1)0 0=1P(n1)=1P0 0=0.4(4) Ls= /(1 )=0.4/(10.4)=0.667 人人 Lq=Ls 0.6670.40.2270.6670.40.227min101516111)5( sWmin46101 sqWW22. 0)15(1)15()6(15)( eWPWP例例2:某市铁路车票预

20、售所，设有一个售票窗口，在一某市铁路车票预售所，设有一个售票窗口，在一天的服务时间内，平均每小时到达天的服务时间内，平均每小时到达15人，服从泊松人，服从泊松分布，一个顾客的平均售票时间为分布，一个顾客的平均售票时间为3min，服从负指，服从负指数分布。现在计算这个排队系统的有关运行指标。数分布。现在计算这个排队系统的有关运行指标。 15， 60/320)(122 qL)( qW11sqWW 1sL2.1.3 里特公式里特公式)(122 qL)( qW11sqWW 1sL,ssLW ,qqWL sqLL 1,sqWW 2.2 M/M/1/N/ 模型模型01111(),11nnnNNPPPPPn

21、NPP M/M/1/N/ 系统的主要运行指标：系统的主要运行指标：0111111nnNNPP 0(1)qsLLP1qsWW 0(1)ssLWP 11(1)11NsNNL 对于随机排队系统，顾客到达服从泊松流，对于随机排队系统，顾客到达服从泊松流，服务时间服从负指数分布，多服务台并列的服务时间服从负指数分布，多服务台并列的排队系统，且队列为单列。排队系统，且队列为单列。3.1 M/M/C/ / 模型模型 标准的标准的M/M/C 模型，是符合下列条件的排队系统：模型，是符合下列条件的排队系统： C个服务员，一个服务员为一个顾客服务，顾客到达后，个服务员，一个服务员为一个顾客服务，顾客到达后，若有服

22、务员空闲，则立即接受服务，否则参加排队（一个队）。若有服务员空闲，则立即接受服务，否则参加排队（一个队）。服务员服务结束后，若队列中有等待的顾客，即按先到先服务服务员服务结束后，若队列中有等待的顾客，即按先到先服务的原则为下一个顾客服务。每个服务员的工作是相互独立且平的原则为下一个顾客服务。每个服务员的工作是相互独立且平均服务率相同均服务率相同 l C= ，即服从参数为，即服从参数为 的负指数分布。的负指数分布。 可知整个服务机构的平均服务率与系统状态有关：可知整个服务机构的平均服务率与系统状态有关：只有当只有当 /(C ) 1时，才不会排成无限的队列。令时，才不会排成无限的队列。令 /(C

23、) 称称 为这个系统的服务强度或称服务台的平均利用率。为这个系统的服务强度或称服务台的平均利用率。,nnnccnc 3.1.1 系统的数量指标系统的数量指标1)服务台空的概率：服务台空的概率： 服务台忙的概率服务台忙的概率110011!1!1 CnCnCnP CnPCCCnPnPnCnnn00!11!1 2)排队等待服务顾客数的期望值排队等待服务顾客数的期望值(平均队列长平均队列长)：3)平均队长：平均队长：4)平均等待时间：平均等待时间：5)平均逗留时间：平均逗留时间： （例（例3）0220)1( !)()1( !PcccPLcccq qqLW sqqLLLc sLW 例例3:某市铁路车票预

24、售所，设有一个售票窗口，在某市铁路车票预售所，设有一个售票窗口，在一天的服务时间内，平均每小时到达一天的服务时间内，平均每小时到达15人，服人，服从泊松分布，一个顾客的平均售票时间为从泊松分布，一个顾客的平均售票时间为3min，服从负指数分布。为了减少顾客排队等待的时服从负指数分布。为了减少顾客排队等待的时间，增设了一个售票窗口（即增加了一个服务间，增设了一个售票窗口（即增加了一个服务员，其平均服务时间仍为员，其平均服务时间仍为3分钟，服从负指数分钟，服从负指数分布），求这个系统的运行指标。分布），求这个系统的运行指标。M/M/C 型系统与型系统与C 个个M/M/1型系统的比较型系统的比较： 如将例如将例3只有排队方式变为：将两个窗口分设两个地点只有排队方式变为：将两个窗口分设两个地点,顾客到达后在每个窗口前各排一队，就形成了顾客到达后在每个窗口前各排一队，就形成了2个队列，并个队列，并假设每个地点的到达强度为原到达强度的一半即：假设每个地点的到达强度为原到达强度的一半即：7.5人人/h,仍服从泊松分布，在这种情况下，形成了仍服从泊松分布，在这种情况下，形成了2个个M/M/1系统。系统。225.0)5 .720(205 .7)(22 qL)(03.0)5 .720(205 .7)(hWq )(08.05 .720111hWWq 6 .05 .7205 .7 L