1、12/26/2022 第1页共31页6 排队与服务系统排队与服务系统一、生灭过程一、生灭过程二、排队与服务系统二、排队与服务系统三、排队系统三、排队系统12/26/2022 第2页共31页一、生灭过程一、生灭过程1、定义：、定义：为生灭过程。为生灭过程。则称该马尔科夫链则称该马尔科夫链）（满足：满足：如果它的转移概率如果它的转移概率间间马氏过程，其状态空马氏过程，其状态空是参数连续状态离散的是参数连续状态离散的设设0,2),()()4()()(1)()3(;0,0),()()2(;0),()(1,0),(,2,1,00,011 tXjihohphohhphohhphohhpSjittpStXt
2、ijiiiiiiiiiiiiijt 由定义可知，生灭过程的各个状态是相通的由定义可知，生灭过程的各个状态是相通的.设设X所描述的所描述的是某群体含有个体的个数随时间变化的过程是某群体含有个体的个数随时间变化的过程,在时间间隔为在时间间隔为h的的一小段时间内一小段时间内,忽略高阶无穷小后忽略高阶无穷小后,只有三种可能：只有三种可能：12/26/2022 第3页共31页。状状态态不不变变，其其概概率率为为率率为为即即死死去去一一个个个个体体）的的概概变变到到由由状状态态为为即即生生一一个个个个体体）的的概概率率变变到到状状态态由由hhiihiiiiii)(1)3(;(1)2(;(1)1(22221
3、11100)()(Q矩阵为矩阵为显然，生灭过程的密度显然，生灭过程的密度2、柯氏方程、柯氏方程。后后退退方方程程 ,3,2,1),()()()()()()()1(,1,1itptptptptQPtPjiijiiijiiij一、生灭过程一、生灭过程12/26/2022 第4页共31页。前进方程前进方程 ,3,2,1,)()()()()()()()2(11,11,jtptptptpQtPtPjjijiiijiiij。得得由由设设所所满满足足的的微微分分方方程程、,3,2,1),()()()()()()()()()(),),(),()()()(311111100010jtptptptptptptpQ
4、tttptptjtXPtpjjjjjjjjj 0)(0()()(,),()0(11111100210jjjjjjjjjppppppjtXPtpppp常常数数），上上述述方方程程成成为为定定义义由由平平稳稳分分布布的的且且系系统统达达到到统统计计平平衡衡，又又设设一、生灭过程一、生灭过程12/26/2022 第5页共31页0020121110211010,ppppppjjj 递递推推解解得得 02101,jjpppp构构成成一一分分布布，必必有有欲欲使使,121110 jjj时时当当级级数数,111211100 jjjp得得 平稳分布存在，上述即为所求，否则平稳分布不存在。平稳分布存在，上述即为
5、所求，否则平稳分布不存在。一、生灭过程一、生灭过程12/26/2022 第6页共31页例例1、一个服务机构，其顾客按比率为、一个服务机构，其顾客按比率为一个服务员一个服务员,并且服务时间是一个均值为并且服务时间是一个均值为 指数分布的随机变量指数分布的随机变量.如果服务机构没有顾客如果服务机构没有顾客,则顾客一到就服务则顾客一到就服务,否则就排队否则就排队.然而然而,如如果机构内有两人在排果机构内有两人在排1泊松过程到达泊松过程到达,只有只有的人数。的人数。（1）写出状态空间；）写出状态空间；（2）求出）求出Q矩阵；矩阵；（3）求平稳分布。）求平稳分布。队就离开而不返回队就离开而不返回.令令X
6、(t)表示服务机构中表示服务机构中一、生灭过程一、生灭过程12/26/2022 第7页共31页解解:(1）S=0,1,2,3;(2)设设X(t)=0,如果有一个顾客，则转移到状态如果有一个顾客，则转移到状态1，顾客在，顾客在(t,t+h)内到达的概率为内到达的概率为)(!1hohehh这样这样,01q 由于两个及两个以上顾客不能同时到达故由于两个及两个以上顾客不能同时到达故,00302qq 于是于是,Q矩阵的第一行为矩阵的第一行为)0,0,(如果一个顾客在服务机构中如果一个顾客在服务机构中,假定假定t以前没有完成以前没有完成,在在(t,t+h)对其的服务将完成的概率为对其的服务将完成的概率为一
7、、生灭过程一、生灭过程12/26/2022 第8页共31页txhttxdxedxetxhttxdxedxe)(1hoheh 所以，若所以，若X(t)=1,则在则在(t,t+h)内变到内变到0的概率为的概率为),(hoh 因此因此,10q 另一种情况为一个顾客到过程转到状态另一种情况为一个顾客到过程转到状态2，,0,1312qq于是于是Q矩阵的第二行为矩阵的第二行为)0,),(,(一、生灭过程一、生灭过程12/26/2022 第9页共31页当当X(t)=2时，时，Q的第三行为的第三行为),(,0(当当X(t)=3时，时，Q的第四行为的第四行为),0,0(所以所以00)(00)(00Q （3）由生
8、灭过程的结论知平稳分布为,)(00pppkkk一、生灭过程一、生灭过程12/26/2022 第10页共31页。其其中中,3,2,1,0,)1()(03013210kpppkkii 将本例所描述的问题及所解决的方法一般化就是排队与服将本例所描述的问题及所解决的方法一般化就是排队与服务系统。务系统。一、生灭过程一、生灭过程12/26/2022 第11页共31页二、排队与服务系统二、排队与服务系统 1、排队问题与服务系统的分类、排队问题与服务系统的分类（1）消失制系统）消失制系统（2）等待制系统）等待制系统（3）混合制系统）混合制系统 等待与混合制系统中，还有服务原则问题等待与混合制系统中，还有服务
9、原则问题：（1）先到先服务；）先到先服务；（2）随机服务；）随机服务；（3）优先服务。）优先服务。12/26/2022 第12页共31页2、排队模型的表示与研究问题、排队模型的表示与研究问题(1)排队模型可表示为排队模型可表示为。mnGG21其中其中或或系系统统内内顾顾客客的的容容量量。表表示示顾顾客客排排队队允允许许队队长长员员的的数数目目表表示示服服务务分分布布；表表示示服服务务服服从从分分布布；表表示示顾顾客客流流服服从从mnGGGG;2211(2)研究以下问题研究以下问题 1)系统绝对通过能力系统绝对通过能力A,即单位时间内被服务顾客的人数即单位时间内被服务顾客的人数;2)系统相对通过
10、能力系统相对通过能力Q,即被服务顾客数与请求服务的顾即被服务顾客数与请求服务的顾客数的比值客数的比值;3)系统消失概率系统消失概率消P ,服务系统满员的概率或服务员都在服务系统满员的概率或服务员都在忙着忙着,排队位置满座的概率排队位置满座的概率;二、排队与服务系统二、排队与服务系统12/26/2022 第13页共31页 4)系统内顾客的平均数系统内顾客的平均数L;5)系统内排队等候顾客系统内排队等候顾客 ;QL（3）Little公式公式 当系统达到统计平稳状态后，系统内顾客的平均数当系统达到统计平稳状态后，系统内顾客的平均数L和系和系统内顾客所化时间的平均数统内顾客所化时间的平均数W有着重要关
11、系。有着重要关系。强强度度。表表示示顾顾客客流流进进入入系系统统的的其其中中eeLW,6)系统内顾客所花时间的平均值系统内顾客所花时间的平均值W;7)系统内顾客花在排队等候时间的平均值系统内顾客花在排队等候时间的平均值 类似地，系统内顾客在排队等候时间的平均值类似地，系统内顾客在排队等候时间的平均值QW排队等候顾客的平均数排队等候顾客的平均数QL满足：满足：。eQQLW与系统内与系统内二、排队与服务系统二、排队与服务系统12/26/2022 第14页共31页（3）Little公式公式 当系统达到统计平稳状态后，系统内顾客的平均数当系统达到统计平稳状态后，系统内顾客的平均数L和系和系统内顾客所化
12、时间的平均数统内顾客所化时间的平均数W有着重要关系。有着重要关系。强强度度。表表示示顾顾客客流流进进入入系系统统的的其其中中eeLW,6)系统内顾客所花时间的平均值系统内顾客所花时间的平均值W;7)系统内顾客花在排队等候时间的平均值系统内顾客花在排队等候时间的平均值 类似地，系统内顾客在排队等候时间的平均值类似地，系统内顾客在排队等候时间的平均值QW排队等候顾客的平均数排队等候顾客的平均数QL满足：满足：。eQQLW与系统内与系统内二、排队与服务系统二、排队与服务系统12/26/2022 第15页共31页三、排队系统三、排队系统1、系系统统01MM 设系统内仅有一个服务员，顾客按强度设系统内仅
13、有一个服务员，顾客按强度顾客到达时服务员不闲时立即离去，服务时间顾客到达时服务员不闲时立即离去，服务时间T服从参数为服从参数为的指数分布。的指数分布。求：求：（1）系统的绝对通过能力；）系统的绝对通过能力；（2）系统的相对通过能力。）系统的相对通过能力。泊松过程到达，泊松过程到达，12/26/2022 第16页共31页 设设X(t)=0表示系统闲表示系统闲,X(t)=1系统忙系统忙,则对于任意时间则对于任意时间t,系统系统状态概率状态概率)(),(10tptp满足满足1)()(10tptp由例由例1可知：可知：0)0(,1)0(,)()()()()(10011100pptptpptptptp解
14、之得解之得tetp)(0)(tetp)(1)(三、排队系统三、排队系统12/26/2022 第17页共31页系统的相对通过能力系统的相对通过能力)(0tpQ 当系统达到平稳状态时当系统达到平稳状态时Q系统的绝对通过能力系统的绝对通过能力 QA系统的消失概率为系统的消失概率为11 QP消消三、排队系统三、排队系统12/26/2022 第18页共31页系系统统0nMM2、系统的状态空间为系统的状态空间为 nS,2,1,0 设系统内仅有设系统内仅有n个服务员，顾客按强度个服务员，顾客按强度 顾客到达时，服务员不闲时立即离去，服务时间顾客到达时，服务员不闲时立即离去，服务时间T服从服从参数为参数为的指
15、数分布。的指数分布。求：求：（1）系统的绝对通过能力；）系统的绝对通过能力；（2）系统的相对通过能力。）系统的相对通过能力。泊松过程到达，泊松过程到达，三、排队系统三、排队系统12/26/2022 第19页共31页 )()()()()1()()()()()(2)()()()()()()(120111001tptpntptpktptpktptptptptptptptpnnnkkkk初始条件为初始条件为0)0()0()0(,1)0(210 npppp解上述方程组，得状态概率：解上述方程组，得状态概率：)(,),(),(),(210tptptptpn 三、排队系统三、排队系统12/26/2022 第
16、20页共31页 由于系统的状态互通且状态数有限，所以极限概率存在：由于系统的状态互通且状态数有限，所以极限概率存在：npppp,210 由状态概率图可以求得：由状态概率图可以求得：。nkpkpkk,2,1,!0 其中：其中：。nkkkp0!01,所以所以。，消消消消QApQnpPnn1,!三、排队系统三、排队系统12/26/2022 第21页共31页3、系系统统1MM 易知，系统是生灭过程，状态空间为易知，系统是生灭过程，状态空间为,2,1,0 S利用生灭过程的结论得利用生灭过程的结论得 ,2,1,0kppkk 设系统内仅有设系统内仅有1个服务员，顾客按强度个服务员，顾客按强度 顾客到达时，服
17、务员不闲，顾客排队，等候服务，服务时间顾客到达时，服务员不闲，顾客排队，等候服务，服务时间T服从参数为服从参数为的指数分布。的指数分布。泊松过程到达，泊松过程到达，.1),1(,1100000ppppkkkk三、排队系统三、排队系统12/26/2022 第22页共31页 系统内顾客的平均数为系统内顾客的平均数为0001)1()1(kkkkkkkkkpL排队顾客的平均数为排队顾客的平均数为)1()1(0111ppkppkLkkkkkkQ1)(2 在系统内顾客所化时间的平均值为在系统内顾客所化时间的平均值为三、排队系统三、排队系统12/26/2022 第23页共31页111111000kkkkkk
18、pkppkW顾客排队时间的平均值为顾客排队时间的平均值为001()QkkkkkWpkp 4、系系统统mMM1三、排队系统三、排队系统12/26/2022 第24页共31页系统的状态空间为系统的状态空间为1,2,1,0 mS由状态转移概率图可以求得由状态转移概率图可以求得。1,2,1,0,1)1(2 mkpmkk 设系统内仅有一个服务员，顾客按强度设系统内仅有一个服务员，顾客按强度 顾客到达时，服务员不闲时如顾客到达时，服务员不闲时如m个坐位不满，顾客参加排个坐位不满，顾客参加排队，等待服务。否则，立即离去，服务务时间队，等待服务。否则，立即离去，服务务时间T服从参数为服从参数为指数分布。指数分
19、布。泊松过程到达，泊松过程到达，4、系系统统mMM1三、排队系统三、排队系统12/26/2022 第25页共31页系统的消失概率为系统的消失概率为,1)1(211mmmpP消消系统相对通过能力系统相对通过能力,1)1(1121mmPQ消消系统的绝对通过能力系统的绝对通过能力,1)1(121mmQA系统内顾客的平均数系统内顾客的平均数1010211mkkmkmkkkpL三、排队系统三、排队系统12/26/2022 第26页共31页 排队等候的顾客平均数排队等候的顾客平均数111111)1(mkmkkkmkkQpkppkL1000)1()1(mkkpLpkp2121)1(11mmmmm)1(321
20、(1)1(22mmm 2122)1()2()1(11)1(mmmmm三、排队系统三、排队系统12/26/2022 第27页共31页系统内所化时间的平均值为系统内所化时间的平均值为2121)2()1(1)1(mmmmmLW2121)2()1(1)1(1mmmmm系统内顾客排队所化时间的平均值为系统内顾客排队所化时间的平均值为2121)1(1)1(mmmQQmmLW211)1(1)1(mmmmm三、排队系统三、排队系统12/26/2022 第28页共31页5、系系统统nMM显然系统的状态空间为显然系统的状态空间为,2,1,0 S 由系统的状态转移概率图可知，本系统为生灭过程，于由系统的状态转移概率
21、图可知，本系统为生灭过程，于 是是 设系统内有设系统内有n个服务员，顾客按强度个服务员，顾客按强度顾客到达时所有服务员不闲时，顾客参加排队，直到服务顾客到达时所有服务员不闲时，顾客参加排队，直到服务员为其服务为止。所有服务员服务务时间员为其服务为止。所有服务员服务务时间T服从参数为服从参数为指数分布。指数分布。泊松过程到达，泊松过程到达，,!,2,1,!00pnnnkpkpnkkkk三、排队系统三、排队系统12/26/2022 第29页共31页01000!1pnnpkpnknkkknkkk 1,)(!21120nnnnpnn1120)(!21 nnnpnn rnnnnnnnp1!21120 系
22、统内顾客的平均数系统内顾客的平均数三、排队系统三、排队系统12/26/2022 第30页共31页01000!pnnkpkkkpLnkknknkkkk201)1(!nnnnp系统内排队等候顾客的平均数系统内排队等候顾客的平均数20111!nnnpkpLnkknQ系统内顾客所化时间的平均值系统内顾客所化时间的平均值201!1nnnpLWn三、排队系统三、排队系统12/26/2022 第31页共31页 系统内顾客排队等候所化时间的平均值系统内顾客排队等候所化时间的平均值201!nnnpLWnQQ6、系系统统mnMM7、成成批批到到达达系系统统1MM8、服务时间服从、服务时间服从Gamma分布系统分布系统 作业作业:P224 习题六习题六 2、4、6、8、11三、排队系统三、排队系统
