排队理论模型

1、 排队论是排队论是20世纪初由丹麦数学家世纪初由丹麦数学家Erlang应用数学应用数学方法在研究电话话务理论过程中而发展起来的一门学方法在研究电话话务理论过程中而发展起来的一门学科，排队论也称随机服务系统理论，它涉及的是建立科，排队论也称随机服务系统理论，它涉及的是建立一些数学模型，以对随机发生的需求提供服务的系统一些数学模型，以对随机发生的需求提供服务的系统预测其行为，它已应用于电讯、纺织、矿山、交通、预测其行为，它已应用于电讯、纺织、矿山、交通、机器维修，可靠性，计算机设计和军事领域，都已取机器维修，可靠性，计算机设计和军事领域，都已取得了显著的成绩。得了显著的成绩。一、排队论简介一、排队

2、论简介二、实例分析二、实例分析（一）基本概念（一）基本概念 1排队系统排队系统 排队是指在服务机构处要求服务对象的一个等待队列排队是指在服务机构处要求服务对象的一个等待队列 排队系统是指一个具有排队等待现象的服务系统排队系统是指一个具有排队等待现象的服务系统 排队论是指定量的研究排队问题，寻找系统内在规律，寻找排队论是指定量的研究排队问题，寻找系统内在规律，寻找供求关系平衡的最优方案。供求关系平衡的最优方案。 现实世界中排队的现象比比皆是，但有如下共同特征现实世界中排队的现象比比皆是，但有如下共同特征: (1)有请求服务的人或物，如候诊的病人，请求着陆的飞机等，有请求服务的人或物，如候诊的病人

3、，请求着陆的飞机等，我们将此称为我们将此称为“顾客顾客”。 (2)有为顾客提供服务的人或物，如医生、飞机跑道等，我们有为顾客提供服务的人或物，如医生、飞机跑道等，我们称为称为“服务员服务员”。由顾客和服务员就组成服务系统。由顾客和服务员就组成服务系统。 (3)顾客随机地一个一个顾客随机地一个一个(或者一批一批或者一批一批)来到服务系统每位顾来到服务系统每位顾客需要服务的时间不一定确定的，服务过程的这种随机性造成客需要服务的时间不一定确定的，服务过程的这种随机性造成某个阶段顾客排长队，而某些时间服务员又空闲无事。某个阶段顾客排长队，而某些时间服务员又空闲无事。 2 排队系统的特征排队系统的特征

4、为了描述一个给定的排队系统，必须规定系统的下列组成为了描述一个给定的排队系统，必须规定系统的下列组成 (1)输入过程输入过程 顾客陆续来到的过程，设顾客陆续来到的过程，设N(t):(0，t)时间内来到的顾客数时间内来到的顾客数(非负非负整数值整数值)0),(ttN是随机过程，又设是随机过程，又设iT第第i个顾客到达的时间，从个顾客到达的时间，从iT随机变量序列，随机变量序列，1iiiTT时间间距时间间距(隔隔) ,max)(1jiitjtN一般假设顾客来到时间间隔一般假设顾客来到时间间隔i相互独立与随机变量相互独立与随机变量有相同的；有相同的；可以根据原始资料，由顾客到达的规律、作出经验分布，

5、可以根据原始资料，由顾客到达的规律、作出经验分布，x2检验法检验法)确定服从哪种理论分布，并确定服从哪种理论分布，并概率分布为负指数分布概率分布为负指数分布M(另外有定长分布另外有定长分布D， k阶爱尔兰分布阶爱尔兰分布Ek，一般独立分布，一般独立分布GI等等)而而分布分布然后按照统计学的方法然后按照统计学的方法(如如估计它的参数值。我们主要讨论估计它的参数值。我们主要讨论 (2)服务机构服务机构 服务员对顾客服务过程，服务机构可以是一个服务员或多个服服务员对顾客服务过程，服务机构可以是一个服务员或多个服务员的。对顾客可以单独进行服务，也可以对成批顾客进行服务，务员的。对顾客可以单独进行服务，

6、也可以对成批顾客进行服务，在我们这儿介绍对顾客单独进行服务。设在我们这儿介绍对顾客单独进行服务。设C为服务机构服务员个为服务机构服务员个数，当数，当C=1时，为单服务系统，当时，为单服务系统，当C2，为多服务系统。和，为多服务系统。和输入过程一样，服务时间都是随机的，且我们假设，设输入过程一样，服务时间都是随机的，且我们假设，设n表示服务员为表示服务员为n个顾客提供服务所需的时间，则服务个顾客提供服务所需的时间，则服务n服从相互独立的且与某一随机服从相互独立的且与某一随机有相同分布，其中有相同分布，其中根据原始资料判断得到的，主要有的分布为负指数分根据原始资料判断得到的，主要有的分布为负指数分

7、布布(定长分布，一般独立分布等定长分布，一般独立分布等) (3)排队与服务规则排队与服务规则 顾客排队和等待的规则，排队规则一般有等待制，顾客排队和等待的规则，排队规则一般有等待制，消失制和混合制。所谓等待制消失制和混合制。所谓等待制(系统容量系统容量D 就是当一个顾客到达时，若所有服务台均被占用时，该就是当一个顾客到达时，若所有服务台均被占用时，该顾客便排队等待服务；消失制也称即时制顾客便排队等待服务；消失制也称即时制(系统容量系统容量D=C)就是服务台被占用时顾客便即时离去；混合制也就是服务台被占用时顾客便即时离去；混合制也 时间所构成的序列时间所构成的序列变量变量的概率分布是已知的可以的

8、概率分布是已知的可以)有限制有限制(系统容量系统容量D:CD0有。有。 (1)到达到达(生生):在在(t，t+t)内系统出现一个新的到达的概内系统出现一个新的到达的概率为率为nntt00(),的常数；没有发生新的到达的概率的常数；没有发生新的到达的概率10ntt()；出现多于一个以上的新的到达概率；出现多于一个以上的新的到达概率nntt00();的常数，没有消失的概率为的常数，没有消失的概率为10ntt();消失多于一个以上的概率为消失多于一个以上的概率为0(t)则称系统状态随时间而则称系统状态随时间而变化的过程变化的过程X(t)为一个生灭过程。为一个生灭过程。为为为为0(t) 。 (2)消失

9、消失(灭灭):在在(t，t+t)内，系统消失一个的概率的内，系统消失一个的概率的 2.生灭过程微分差分方程组生灭过程微分差分方程组 设设pn t ( )表示系统在时刻表示系统在时刻t的状态的状态X(t)=n的概率即的概率即pp X tnn t ( )( ) ns，t 0状态为状态为n的概率近似于以下四个概率之和。的概率近似于以下四个概率之和。 (1)P系统在时刻系统在时刻t时为时为n，而在，而在t内没有到达也没有内没有到达也没有消失消失 =ptutptttn tnnn tnn( )( )()()()1110 (2)P系统在系统在t时为时为n-1而在而在t内有一个到达并且没有一内有一个到达并且没

10、有一个消失个消失=pttpttntnnntn1111110( )( )()() (3)P系统在系统在t时为时为n+1，而在，而在t内没有到达而有一个内没有到达而有一个消失消失=pttpttntnnntn1111110( )( )()()则系统在时刻则系统在时刻t+t的的 (4)P系统在系统在t内发生多于一个的到达或消失内发生多于一个的到达或消失=0(t)即应用全概率公式有即应用全概率公式有)()()()1)()(1111tOttpttptttpttPnnnnnnnn0n)()()1)()(11000tOttpttpttpkn )()()1)()(11tOttpttpttpkkkkkppppnk

11、ppppppn tnntnnn tnnttttk tkktkk t( )( )( )( )( )( )( )( )( )( )()| 11110001111ppppnppp tn tnntnnn tnnttt( )( )( )( )( )( )()( )1111000111,( )pnsn tt tn tnn tppplim( )( )由00010)(1111001111kkkknnnnnnnppppknpppnnnnnnnpppnpp11110011010()pn (1)顾客输入过程顾客输入过程:,()( )( )NtNt000是平均率为是平均率为的的Poisson过程即过程即Ntt ( )

12、() 设设M(t)为为(0，t)内容去顾客数，则内容去顾客数，则 :( )Mtt 0 是平均率为的的Poisson分布即分布即 Mtt ( )() (2)X(t):时刻时刻t系统中的顾客数系统中的顾客数 则则XNMttt( )( )( ) L(t):时刻时刻t排队等待顾客数排队等待顾客数 则则LXtt( )( )max, 10 研究研究X(t)的分布模型的分布模型 令令PP XnPpn ttn tn tj( )( )( )( )(,)显然010 pn t ( ), ,( )pnn t 012ntntpp)(lim, 1 , 0,npn 0 1 2 n-1 n n+1 从而在生灭过程中取从而在生

13、灭过程中取 nns, , ,012 (9.5)1时 队列越来越长,;dpdtpppndpdtppn tntn tntttt( )( )( )( )( )( )( )() 1100111010)(1011ppnpppnnn1)(00pppnn1)(tXELssqLtLEL1)(2022)(jtXEj()12p01()ssLTEW1)(WWqs1sqssWLWL, (9.15) LLwwsqsq,14545081,.pnnn0208012., , Ls1081084.()人LLqs40832. ()人WLss441()小时WWqs111508. ()小时Pm.医务室病人数 099nmnm().11

14、09910 m1001. m ln .ln0 0112023LLWLsqsq2430513()(). ()()人人小时小时nnnknk00dpdtpppnkdpdtppdpdtppn tntntn ttttk rktk t( )( )( )( )( )( )( )( )( )( )() 1100110pppnkppppnnnkk110110000()pnnk10时时1,111111knkpnkn0,npkn时1Lkkskk21111111,(),Lkkkkqkk21111111,WLpss ()10(9.21) WWqs1W Wsq,e1peep()10 0 1 2 c-1 c c+1 2 c

15、 图图2cnnnnccnc1ppnpnpncppcpc pncpppn tntn tntn tntn tntttt( )( )( )( )( )( )( )( )( )( )( )()()()111101011显然当显然当 cc1有稳态解，类似地有稳态解，类似地(9.4)式演变式演变 pnpnpncpcpc pncppnnnnnn11110110100()()()(9.24)pnpncc Cpncnnncn1100!pncnccnc00111111! (2)主要结果主要结果 Lccpqcccc()!()120 (9.27)cqsmLL (9.28)WLqq(9.29)WWLsqs1（9.30)

16、kncn ncknccnknnknk00 nnnccnc1得此模型微分差分方程组得此模型微分差分方程组)()()()()()()()()()()(1),() 1()()()()(1 10 011 11 tpctptptptptpknctpctpctptpcntpntpntptpkkknnnnnnnn(9.31) 稳态情况差分方程为稳态情况差分方程为pnpnpncpcpc pcnkpppc pnnnnnnkk1111011101000()()()(9.32) 由由 piik10，解式，解式(9.32)差分方程组得差分方程组得kncpCCnkkcnpnnkkpncnnn1,!)!(!0,!)!(!

17、00(9.33) 其中其中 pki kicCCkicici ckciic0101111 !()!()!(9.34) Ln pLnc psnqnn cknk ,()1(9.35) eskL()(9.36) )(sqeqsLkLLL(9.37) WLsse (9.38) WLqqe (9.39)二、实例分析二、实例分析 机器维修服务机器维修服务 （一）问题提出（一）问题提出机器发生故障后排队等待修理，队伍越长因停产造成机器发生故障后排队等待修理，队伍越长因停产造成的损失越大。提高维修工人和设备的服务速度或增加的损失越大。提高维修工人和设备的服务速度或增加其数量可以减少队长，但将使修理费用上升选择怎样其数量可以减少队长，但将使修理费用上升选择怎样的服务速度，或者确定几个维修工人和设备使损失和的服务速度，或者确定几个维修工人和设备使损失和修理的总费用最小。修理的总费用最小。 （二）建模与分析（二）建模与分析模型模型最优服务率最优服务率 假设假设: (1)发生故障机器维修服务服从发生故障机器维修服务服从M/M/1，平均到达，平均到达率率(单位时间发生故障的机器数单位时间发生故障的机器数)为为 ，平均服务率，平均服务率(单位单位时间平均修理数时间平均修理数)为为，且，且 。C1C