排队论模型【高教知识】.ppt

《排队论模型【高教知识】.ppt》由会员分享，可在线阅读，更多相关《排队论模型【高教知识】.ppt（40页珍藏版）》请在三一文库上搜索。

1、排队论模型,排队论是20世纪初由丹麦数学家Erlang应用数学方法在研究电话话务理论过程中而发展起来的一门学科，排队论也称随机服务系统理论，它涉及的是建立一些数学模型，以对随机发生的需求提供服务的系统预测其行为，它已应用于电讯、纺织、矿山、交通、机器维修，可靠性，计算机设计和军事领域，都已取得了显著的成绩。,一、排队论简介,二、实例分析,1,全面分析,一、排队论简介,（一）基本概念 1排队系统 排队是指在服务机构处要求服务对象的一个等待队列 排队系统是指一个具有排队等待现象的服务系统 排队论是指定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。 现实世界中排队的现象比比皆是，但

2、有如下共同特征: (1)有请求服务的人或物，如候诊的病人，请求着陆的飞机等，我们将此称为“顾客”。 (2)有为顾客提供服务的人或物，如医生、飞机跑道等，我们称为“服务员”。由顾客和服务员就组成服务系统。 (3)顾客随机地一个一个(或者一批一批)来到服务系统每位顾客需要服务的时间不一定确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时间服务员又空闲无事。,2,全面分析,2 排队系统的特征 为了描述一个给定的排队系统，必须规定系统的下列组成 (1)输入过程 顾客陆续来到的过程，设N(t):(0，t)时间内来到的顾客数(非负整数值),是随机过程，又设,第i个顾客到达的时间，从,随机变量序列

3、，,时间间距(隔),一般假设顾客来到时间间隔,相互独立与随机变量,有相同的；,可以根据原始资料，由顾客到达的规律、作出经验分布，,检验法)确定服从哪种理论分布，并,概率分布为负指数分布,(另外有定长分布D， k阶爱尔兰分布,，一般独立分布GI等),而,分布,然后按照统计学的方法(如,估计它的参数值。我们主要讨论,(2)服务机构 服务员对顾客服务过程，服务机构可以是一个服务员或多个服务员的。对顾客可以单独进行服务，也可以对成批顾客进行服务，在我们这儿介绍对顾客单独进行服务。设C为服务机构服务员个数，当C=1时，为单服务系统，当C2，为多服务系统。和,3,全面分析,输入过程一样，服务时间都是随机的

4、，且我们假设，设,表示服务员为n个顾客提供服务所需的时间，则服务,服从相互独立的且与某一随机,有相同分布，其中,根据原始资料判断得到的，主要有的分布为负指数分布(定长分布，一般独立分布等) (3)排队与服务规则 顾客排队和等待的规则，排队规则一般有等待制，消失制和混合制。所谓等待制(系统容量,就是当一个顾客到达时，若所有服务台均被占用时，该顾客便排队等待服务；消失制也称即时制(系统容量D=C)就是服务台被占用时顾客便即时离去；混合制也,时间所构成的序列,变量,的概率分布是已知的可以,),有限制(系统容量D:CDk)就是一顾客到达若系统中顾客,称队长,4,全面分析,(包括排队等待和正在接受服务的

5、)数目小于k则他排队等待，否则他即时离去，等待制服务的次序规则有先到先服务随机服务，有优先权的先服务等，我们主要讨论先到先服务的系统。 3.排队系统的主要指标 研究排队问题的目的，是研究排队系统的运行效率估计服务质量，确定系统参数最优值，以决定系统的结构是否合理，设计改进措施等，所以必须确定用来判断系统运行优劣的基本数量指标，这些数量指标通常是 (1)队长:是指系统中顾客(包括排队等待和正在接受服务的)的数目，它的期望值为,排队等待的顾客数，其期望记为,(队长)=等待服务的顾客数+正被服务的顾客数，所以,越大，,；排队长度则仅指在队列中,. 系统中的顾客数,说明服务效率越低。,5,全面分析,(

6、2)等待时间:是指从顾客到达时间算起到他开始接受,顾客到达时刻算起到他接受服务完毕为止所需要的时间，,逗留时间=等待时间+服务时间 (3)忙期:是指服务台连续繁忙的时间，即顾客从到达空闲服务台算起到服务台再次变为空闲时止的这段时间。这是服务台最关心数量指标，它直接关系到服务员工作强度，与忙期相对应的是闲期，这是指服务台连续保持空闲的时间长度；显然，在排队系统中忙期与闲期，是交替出现的。,服务时止的这段时间，其期望值记,；逗留时间则指从,即是顾客在系统中所花费的总时间，其期望值记,。,排队系统除了上述三个主要数量指标外，另外服务台的利用率(即服务员忙碌的时间在总时间中所占比例)在排队论的研究中也

7、是很重要的指标。,6,全面分析,（二）排队模型的符号表示与几种重要排队模型 1.排队模型的符号一般表示法 一般表示法 A/B/C/D/E/F A:顾客来到时间间隔的分布类型 B:服务时间的分布类型 C:服务员个数 D:系统容量 E:顾客源个数 F:服务规则 先来先服务的等待排队模型主要由三参数法即A/B/C 例“M/M/1/k/,时间均服从负指数分布，一个服务台，系统至多容纳k个顾客潜在的顾客数不限，先来先服务的排队系统。,/F1F0”,表示顾客到达间隔时间和服务,7,全面分析,“M/M/c”即Poisson输入负指数服务时间分布C个服务台的等待制排队模型。 “M/G/1”即Poisson输入

8、，一般服务时间分布，单个服务台的等待制排队模型。,0000,服务机构,2.几种重要的排队模型 (1)单服务台系统,(2)多服务台的平衡系统,8,全面分析,(3)串联排队系统,(4)排队网络模型,9,全面分析,(5)匹配排队模型,另外还有 (6)优先权的排队系统 (7)成批排队模型 (8)有限源排队模型 我们讨论(1)(2)两种,10,全面分析,（三）、建立排队模型步骤 1.确定表达排队问题各个变量并建立它们之间的相互关系。 2.根据现有的数据，运用适当的统计检验，假设检验有关分布。,3.应用已得到的概率分布，确定描述整个系统的运行特征。 4.根据系统的特征，通过应用适当的决策模型，改进系统的功

9、能。 （四）、生灭过程的差分微分方程组 当顾客到达时间间隔为负指数分布(即输入过程具有Poisson特征，N(t)服从Poisson分布)，服务时间为负指数分布，则系统的排队过程是Markov(马尔科夫)过程，而且它具有一类特殊Markov过程的特征，通常称这类随机过程的生灭过程。,11,全面分析,1.生灭过程的定义 设有一个系统，具有有限个状态，其状态集s=0，1，2k或有可数个状态，状态集s=0，1，2，令X(t)为系统在时刻t所处的状态，若在某一时刻t系统的状态数为n，如果对t0有。 (1)到达(生):在(t，t+t)内系统出现一个新的到达的概率为,的常数；没有发生新的到达的概率,；出现

10、多于一个以上的新的到达概率,的常数，没有消失的概率为,消失多于一个以上的概率为0(t)则称系统状态随时间而 变化的过程X(t)为一个生灭过程。,为,为0(t) 。 (2)消失(灭):在(t，t+t)内，系统消失一个的概率的,12,全面分析,2.生灭过程微分差分方程组 设,表示系统在时刻t的状态X(t)=n的概率即,，,状态为n的概率近似于以下四个概率之和。 (1)P系统在时刻t时为n，而在t内没有到达也没有 消失 =,(2)P系统在t时为n-1而在t内有一个到达并且没有一 个消失=,(3)P系统在t时为n+1，而在t内没有到达而有一个 消失=,则系统在时刻t+t的,(4)P系统在t内发生多于一

11、个的到达或消失=0(t) 即应用全概率公式有,13,全面分析,当 时 类似地，当S为有限集时，对 有 令t0得 当系统状态S为有限集时，生灭过程的微分差分方 程组为,14,全面分析,当系统状态S为可数集时，生灭过程微分差分方程组为 (9.2) 若能求解这组方程，则可得到在时刻t系统状态概率分布 称为生灭过程的瞬时解，一般这种瞬时解是难以求得的,15,全面分析,3.统计平衡下的极限解 实际应用中，关心的是 时，方程的解称为生灭过程微分差分方程组的极限解。 令 及(9.1)(9.2)式得当S为有限状态集时，(9.1)式变为 (9.3) 当S为可数状态集时(9.2)式变为 (9.4 从而可以求得概率

12、分布列,16,全面分析,（五）、典型排队模型和理论结果 下面给出满足生灭过程典型排队M/M/1与M/M/C的结果 (一)单服务台等待制M/M/1排队模型 1.M/M/1/ 顾客来到的时间间隔 服从参数 的负指数分布，服务员为顾客服务时间 服从参数 的指数分布，且 与 相互独立，1个服务台，系统容量为 的等待制排队模型。 可理解为:单位时间平均到达的顾客数-平均到达率 可理解为:单位时间平均服务完的顾客数-平均服务率,17,全面分析,(1)顾客输入过程,是平均率为,的Poisson过程即,设M(t)为(0，t)内容去顾客数，则,的Poisson分布即,(2)X(t):时刻t系统中的顾客数 则,L

13、(t):时刻t排队等待顾客数 则,研究X(t)的分布模型 令,18,全面分析,当 依赖于t时，称 是瞬时解 如果 则称 是稳定解。 此系统的状态转移图 图1,从而在生灭过程中取,(9.5),19,全面分析,记 ，称为服务强度 当 时，模型不稳( 时达不到统计) 当 1时，模型稳定，有稳定解 (3)X(t)的分布律 由(9.12)，(1.15)式得此模型的微分差分方程组 (9.6) 当 时，稳态解满足,20,全面分析,(9.7) 求解(9.7)式差分方程，得 (9.8) (4)结论 平均队长 (9.9) 平均等待队长 (9.10) 系统中顾客数的方差 (9.11),21,全面分析,顾客不须等待概

14、率 (9.12) 可以证明，顾客在系统中逗留时间T服从参数为的指数 分布，从而顾客在系统平均逗留时间 (9.13) 顾客在系统平均等待时间 (9.14) 从上结论可以看出，各指标之间有如下关系 (9.15) (9.16),(9.15),22,全面分析,(5)简单例子 例1(病人候诊问题) 某单位医院的一个科室有一位医生值班，经长期观察，每小平均有4个病人，医生每小时平均可诊5个病人，病人的到来服从泊松分布，医生的诊病时间服从负指数分布，试分析该科室的工作状况，如果满足99%以上的病人有座，此科室至少应设多少座位?如果该单位每天24小时上班，病人看病1小时因耽误工作单位要损失30元，这样单位平均

15、每天损失多少元?如果该科室提高看病速度，每小时平均可诊6个病人，单位每天可减少损失多少?可减少多少座位? 解:由题意知， ，从而排队系统的稳态概率为,23,全面分析,该科室平均有病人数为 该科室内排队候诊病人数为 看一次病平均所需的时间为 排队等候看病的平均时间为 为满足99%以上的病人有座，设科室应设m个座位，则m应满足,24,全面分析,所以该科室至少应设20个座位 如果该单位24小时上班，则每天平均有病人244=96人，病人看病所花去的总时间为961=96小时，因看病平均每天损失3096=2880元，如果医生每小时可诊6个病人， ，则,25,全面分析,这样单位每天的损失费为960.530=

16、1440元，因而单位每天平均可减少损失2880-1440=1440元，这时为保证99%以上的病人有座，应设座位数个比原来减少了9个。 2.M/M/1/k 顾客来到的时间间隔服从参数的负指数分布，服务员为顾客服务时间服从参数的指数分布，且相互独立，1个服务台，系统容量为k的等待制排队模型. 因为是单服务台，系统容量为k，即排队等待的顾客最多为k-1，在某时刻一顾客到达时，如系统中已有k个顾客，那么这个顾客就被拒绝进入系统，所以为 在生灭过程差分微分方程组(9.1)式中取,26,全面分析,从而得此排队模型微分差分方程组 (9.17) 在稳态情形下，式(9.3)变为 (9.18),27,全面分析,在

17、条件 下解(9.18)式得到 虽然当 注意到，这里，不假设 条件，由于系统容量有限的限制 下面类似地给出系统的各种指标的计算结果 (9.19),28,全面分析,(9.20) (9.21) (9.22) 应该指出， 的导出过程中不采用平均达到率 ，而是采用有效到达率 ，这主要是由于当系统已满时，顾客的实际到达率为零，因为正在被服务的顾客的平均数为 ，于是,(9.21),29,全面分析,(二)多服务台等待制M/M/C排队模型 1.M/M/C/ 顾客来到的时间间隔服从参数的负指数分布，服务员为顾客服务时间服从参数的指数分布，C个服务台，系统容量为的等待制排队模型。 (1)稳态的概率分布 M/M/C/

18、模型系统状态图为,0 1 2 c-1 c c+1 ,2,图2,30,全面分析,因此在生灭过程微分差分方程组(9.2)式中，令 得到 此模型微分差分方程组 (9.23),显然当,有稳态解，类似地(9.4)式演变,(9.24),31,全面分析,解(9.24)式差分方程得: （9.25) 其中 (9.26),(2)主要结果,(9.27),(9.28),(9.29),（9.30),32,全面分析,2.M/M/c/k 顾客来到的时间间 隔服从参数 的负指数分布服务员为顾客服务时间 服从参数的指数分布，C个服务台，系统容量为k的等待制排队模型. 因为是多服务台，系统容量为 ，即系统状态为 时，当 时， 个

19、服务台空闲。当 时，服务台正忙着，有 个正等候着，在某一时刻一顾客到达时，系统中已有 个顾客，那么这个顾客就被拒绝进入系统。 根据此模型的特点，在生灭过程微分差分方程组(9.1)式中取,33,全面分析,得此模型微分差分方程组,(9.31),稳态情况差分方程为,(9.32),由,，解式(9.32)差分方程组得,34,全面分析,(9.33),其中,(9.34),(9.35),(9.36),(9.37),(9.38),(9.39),35,全面分析,二、实例分析 机器维修服务 （一）问题提出 机器发生故障后排队等待修理，队伍越长因停产造成的损失越大。提高维修工人和设备的服务速度或增加其数量可以减少队长

20、，但将使修理费用上升选择怎样的服务速度，或者确定几个维修工人和设备使损失和修理的总费用最小。 （二）建模与分析 模型最优服务率 假设: (1)发生故障机器维修服务服从M/M/1，平均到达率(单位时间发生故障的机器数)为,，平均服务率(单位,时间平均修理数)为,，且,。,36,全面分析,(2)每台故障机器单位时间的损失费 为，一台机器平均修理费 为。 由(1)、(2)假设，可得单位时间损失和修理的总费用为 模型即为 (9.40) 由 (9.41) 令 得 而 ，于是 即为最优服务率，这就说明 随着发生故障机器数 和损失费的 增加而增加，随着修理费 的增加而减少，合乎情理。,的增加而减少，合乎情理

21、。,37,全面分析,由于模型是单服务台系统，得到最优服务率为 的理论值，但在实际操作中，设备与工人强度限制达不到此值，所以要讨论模型，根据能达到服务率来确定最佳服务台数。 模型 最佳服务台数 假设 发生故障机器维修服务服从M/M/C，平均到达率为 ，平均服务率为 ，且 。 每台故障机器单位时间的损失费为 ，单位时间每个服务员的服务成本一名维修工人及设备的费用)为 。,。,。,38,全面分析,由假设 、 可得模型 (9.42) 其中 由(9.28)式给出 因为C只取整数值，所以不能用微分法求 的最小值，利用边际分析方法，当 取最小值应满足 (9.43) 将(9.43)式代入式(9.42)并化简得,39,全面分析,(9.44) 对于C=1，2，依次计算,及,当已知数,满足,(9.45) 时即可确定最优值,。,，,40,全面分析,