1、1第七章第七章 随机服务理论概述随机服务理论概述确定型只是随机现象的特例确定型只是随机现象的特例27.1 随机服务系统随机服务系统 系统的输入与输出是随机变量系统的输入与输出是随机变量 A.k.Erlang 于于19091920年发表了一系列根据话务量计年发表了一系列根据话务量计算电话机键配置的方法，为随机服务理论奠定了基础算电话机键配置的方法，为随机服务理论奠定了基础 又称为又称为排队论排队论(Queuing Theory)或或拥塞理论拥塞理论(Congestion Theory)顾顾客客源源三个服务台三个服务台离离去去的的顾顾客客随机服务系统随机服务系统排队等待顾客排队等待顾客.3 与服务
2、系统性能相关的特性与服务系统性能相关的特性 服务系统存在来自两个矛盾方面的要求服务系统存在来自两个矛盾方面的要求 顾客希望服务质量好，如排队等待时间短，损失率低顾客希望服务质量好，如排队等待时间短，损失率低 系统运营方希望设备利用率高系统运营方希望设备利用率高 给用户一个经济上能够承受的满意的质量给用户一个经济上能够承受的满意的质量 哪些系统特性会影响系统的性能？哪些系统特性会影响系统的性能？服务机构的组织方式与服务方式服务机构的组织方式与服务方式 顾客的输入过程和服务时间分布顾客的输入过程和服务时间分布 系统采用的服务规则系统采用的服务规则 7.1.1 服务机构的组织方式与服务方式服务机构的
3、组织方式与服务方式 单台制和多台制单台制和多台制 并联服务并联服务 串联服务串联服务 串并联服务、网络服务串并联服务、网络服务 全利用度、部分利用度全利用度、部分利用度4 与服务系统性能相关的特性与服务系统性能相关的特性 7.1.2 输入过程和服务时间输入过程和服务时间 顾客单个到达或成批到达顾客单个到达或成批到达 顾客到达时间间隔的分布和服务时间的分布顾客到达时间间隔的分布和服务时间的分布 顾客源是有限的还是无限的顾客源是有限的还是无限的 7.1.3 服务规则服务规则 损失制损失制 等待制等待制：先到先服务先到先服务(FIFO)，后到先服务，随机服务，优，后到先服务，随机服务，优先权服务先权
4、服务 混合制混合制 逐个到达，成批服务；成批到达，逐个服务逐个到达，成批服务；成批到达，逐个服务57.2 随机服务过程随机服务过程 单台服务系统、等待制、先到先服务单台服务系统、等待制、先到先服务 顾客在系统中的总时长：逗留时间顾客在系统中的总时长：逗留时间=等待时长等待时长+服务时长服务时长 等待时长与顾客到达率和服务时长有关等待时长与顾客到达率和服务时长有关顾客顾客到达时刻到达时刻开始开始服务时刻服务时刻服务服务终结时刻终结时刻t1 234 1 2 3 4w2w3h1h2h3h4空空12 346 当服务台连续不断服务时，有如下关系：当服务台连续不断服务时，有如下关系：wi+1+i+1=wi
5、+hi wi+hi 表示了累计的未完成的服务时长，一般地有表示了累计的未完成的服务时长，一般地有 0 if00 if1111iiiiiiiiiihwhwhww 忙期和忙时忙期和忙时 系统系统连续不断服务的时期称为忙期。而系连续不断服务的时期称为忙期。而系统最繁忙的一个小时称为忙时。统最繁忙的一个小时称为忙时。排队系统的指标及其关系排队系统的指标及其关系 1）Wq、Wd 分别是顾客的分别是顾客的平均排队等待时间和平均逗留时间平均排队等待时间和平均逗留时间2）Lq、Ld分别是分别是系统平均排队的顾客数和系统的平均顾客数系统平均排队的顾客数和系统的平均顾客数3）h 是顾客的是顾客的平均服务时长，平均
6、服务时长，是顾客的是顾客的平均到达率。平均到达率。4）Ln 是同时接受服务的平均顾客数是同时接受服务的平均顾客数(即即平均服务台占用数平均服务台占用数)5）Ld=Wd=(Wq+h)=Lq+Ln ，Lq=Wq，Ln=h77.3 服务时间与间隔时间服务时间与间隔时间 7.3.1 概述概述顾客的服务时间由于多种原因具有不确定性，最好的描述顾客的服务时间由于多种原因具有不确定性，最好的描述方法就是概率分布；同样顾客到达的间隔时间也具有一定方法就是概率分布；同样顾客到达的间隔时间也具有一定的概率分布的概率分布服务时间和到达间隔时间服从什么分布？可以先通过统计服务时间和到达间隔时间服从什么分布？可以先通过
7、统计得到经验分布，然后再做理论假设和检验得到经验分布，然后再做理论假设和检验经验分布一般采用直方图来表示，如下图经验分布一般采用直方图来表示，如下图频率频率%3020102468通话分钟通话分钟8若统计区间分得越细，样本越多，则经验分布的轮廓越接若统计区间分得越细，样本越多，则经验分布的轮廓越接近曲线近曲线一般服务时间和间隔时间都是非负的连续实变量，令一般服务时间和间隔时间都是非负的连续实变量，令 h 代代表服务时间，表服务时间，代表间隔时间，代表间隔时间，t 为给定的时间，则它们的为给定的时间，则它们的概率分布函数分别表示为概率分布函数分别表示为F(t)=Ph t F(t)=P t它们的概率
8、密度函数为它们的概率密度函数为f(t)=F(t)，具有性质：，具有性质：f(t)0，f(t)dt=1服务时间落在区间服务时间落在区间(a,c)的概率为的概率为 )()()(aFcFdttfchaPca 服务时间落在区间服务时间落在区间(t,t+t)的概率为的概率为 Pt 1 个服务台终结的概率为个服务台终结的概率为 o(t)，称为，称为普通性普通性)()(1()(totottotCknkkn 137.4 输入过程输入过程即顾客到达的分布，可用相继到达顾客的间隔时间描述，即顾客到达的分布，可用相继到达顾客的间隔时间描述，也可以用单位时间内到达的顾客数描述也可以用单位时间内到达的顾客数描述 间隔时
9、间服从定长分布间隔时间服从定长分布 单位时间内到达的顾客数服从单位时间内到达的顾客数服从波松分布波松分布(法国数学家法国数学家Poisson,1837)间隔时间服从爱尔兰分布间隔时间服从爱尔兰分布 一般独立同分布一般独立同分布 7.4.1 波松输入过程及其特点波松输入过程及其特点(0,t)时间内到达时间内到达 k 个顾客的个数服从波松分布，若个顾客的个数服从波松分布，若tkkekttP!)()(为为到达率到达率电话呼叫的到达，商店的顾客到达，十字路口的汽车流，电话呼叫的到达，商店的顾客到达，十字路口的汽车流，港口到达的船只，机场到达的飞机等港口到达的船只，机场到达的飞机等14 7.4.1 波松
10、输入过程及其特点波松输入过程及其特点(1)平稳性平稳性：顾客到达数只与时间区间长度有关：顾客到达数只与时间区间长度有关(2)无后效性无后效性：不相交的时间区间内所到达的顾客数是独立的：不相交的时间区间内所到达的顾客数是独立的(3)普通性普通性：在：在 t 时间内到达一个顾客的概率为时间内到达一个顾客的概率为 t+o(t)，到，到达两个或两个以上顾客的概率为达两个或两个以上顾客的概率为 o(t)；即两个顾客不可能同；即两个顾客不可能同时到达时到达(4)有限性：在有限的时间区间内，到达的顾客数是有限的。有限性：在有限的时间区间内，到达的顾客数是有限的。波松过程具有波松过程具有可迭加性可迭加性 即独
11、立的波松分布变量的和仍为波松分布即独立的波松分布变量的和仍为波松分布 tnntjnjtjjtjjtiientejntejtjnxPjxPnxxPntjinejttPeittP)(21 20 120121 2 1212121!)()!()(!)(),0(,!)()(,!)()(:个顾客的概率为个顾客的概率为内来到内来到在在令令设两个波松分布为设两个波松分布为15 7.4.1 波松输入过程及其特点波松输入过程及其特点波松过程的到达间隔时间为负指数分布波松过程的到达间隔时间为负指数分布 令令 代表间隔时间，则概率代表间隔时间，则概率 P t代表时间区间代表时间区间(0,t)内内没有顾客来的概率；由波
12、松分布可知没有顾客来的概率；由波松分布可知P0(t)=P t=et 故间隔时间故间隔时间 的分布为的分布为 P t=1 et7.4.2 马尔科夫链马尔科夫链马尔科夫链马尔科夫链(Markov Chain)又简称又简称马氏链马氏链，是一种，是一种离散事件离散事件随机过程。用数学式表达为随机过程。用数学式表达为PXn+1=xn+1|X1=x1,X2=x2,.,Xn=xn=PXn+1=xn+1|Xn=xn Xn+1的状态只与的状态只与 Xn的状态有关，与的状态有关，与 Xn 前的状态无关，前的状态无关，具有具有无记忆性无记忆性，或，或无后效性无后效性，又称，又称马氏性马氏性 状态转移是一步一步发生的
13、，一步状态转移概率状态转移是一步一步发生的，一步状态转移概率Pij(t)=PXn+1=j|Xn=i16 例例 7.4.2 一售货员出售两种商品一售货员出售两种商品A和和B，每日工作，每日工作 8 小时。购买每种小时。购买每种商品的顾客到达过程为波松分布，到达率分别为商品的顾客到达过程为波松分布，到达率分别为 A=8人人/日，日，B=16人人/日，试求：日，试求：(1)1小时内来到顾客总数为小时内来到顾客总数为 3 人的概率；人的概率；(2)三个顾客全是购买三个顾客全是购买B类商品的概率。类商品的概率。解解：(1)总到达率为总到达率为 A+B=24人人/日，日，1 小时小时=1/8 日，故日，故
14、(2)3 个顾客全是购买个顾客全是购买 B 类商品的概率为类商品的概率为224.0!3)8/124()8/1(8/12433 eP0664.0!3)8/116()8/1()8/1(8/188/116303 eePPAB177.5 生灭过程生灭过程一种描述自然界生灭现象的数学方法，如细菌的繁殖和灭一种描述自然界生灭现象的数学方法，如细菌的繁殖和灭亡，人口的增减，生物种群的灭种现象等亡，人口的增减，生物种群的灭种现象等采用马氏链采用马氏链 令令 N(t)代表系统在时刻代表系统在时刻 t 的状态，下一瞬间的状态，下一瞬间 t+t 系统的系统的状态只能转移到相邻状态，或维持不变，如图所示状态只能转移到
15、相邻状态，或维持不变，如图所示 三种转移是不相容的，三者必居其一三种转移是不相容的，三者必居其一 只有具有无记忆性和普通性的过程只有具有无记忆性和普通性的过程(分布分布)才适用马氏链才适用马氏链 令令 Pj(t)=PN(t)=j代表系统在时刻代表系统在时刻 t 处于状态处于状态 j 的概率的概率jjj+1j 1tt+t j t j+j)t j t18 生灭过程的马氏链生灭过程的马氏链01j+1njj 1.0 t j t j t 1 t j t j t 1 t j t n t n t 1+1)t j-1+j-1)t j+j)t j+1+j+1)t根据马氏链，应用全概率公式，有状态转移概率方程根据
16、马氏链，应用全概率公式，有状态转移概率方程1,2,1)()1)()()()(1111 njtotttpttpttpttpjjjjjjjj 另有两个边界方程另有两个边界方程)()1)()()(00110tottpttpttp )()1)()()(11tottpttpttpnnnnn 19 生灭方程的推导过程生灭方程的推导过程将上述三个差分方程化为微分方程将上述三个差分方程化为微分方程)()()()()(1,2,1)()()()()()(lim111111110tptptptpnjtptptpttpttpjjjjjjjjjjjjjjjjjt 即即上述三个方程是动态方程，当系统处于稳态时，系统处于上
17、述三个方程是动态方程，当系统处于稳态时，系统处于统计平衡状态，即状态概率不随时间变化，从而状态概率统计平衡状态，即状态概率不随时间变化，从而状态概率导数为导数为 0；令上三个方程左侧为；令上三个方程左侧为 0，得稳态方程组，得稳态方程组)()()()()()(1100110tptptptptptpnnnnn 同理有同理有)3(0)2(10)()1(001111110011njppnjpppjppnnnnjjjjjjj 20 生灭过程稳态解生灭过程稳态解01j+1njj 1.0 j j 1 j j 1 j n n方程方程(1),(2),(3)与稳态状态转移图一一对应；递归解如下：与稳态状态转移图
18、一一对应；递归解如下：)3(0)2(10)()1(001111110011njppnjpppjppnnnnjjjjjjj 11211100002111011021102101011 ,1)(,:)2(,1 njjjnjjjjjjjppppppppjpp 得得由由归纳法归纳法得得依次递推依次递推式得式得代入代入将将令令21 满足生灭过程的条件满足生灭过程的条件系统的输入过程和服务过程具有平稳、无记忆性和普通性系统的输入过程和服务过程具有平稳、无记忆性和普通性服务台是独立的、相同的、并联的服务台是独立的、相同的、并联的波松输入过程和负指数服务时长就具有这些性质波松输入过程和负指数服务时长就具有这些
19、性质 可以用马氏链来描述系统的状态转移可以用马氏链来描述系统的状态转移 这种系统称为这种系统称为生灭服务系统生灭服务系统，一般用，一般用 M/M/n 表示，又表示，又称为称为标准服务系统标准服务系统；标准服务系统的形式很多，但都是基于生灭方程，关键标准服务系统的形式很多，但都是基于生灭方程，关键是找出是找出 j,j 的不同表达式，将它们代入的不同表达式，将它们代入生灭方程生灭方程标准服务系统的表示法：标准服务系统的表示法：(X/Y/Z:A/B/C)，X 表示输入过程，表示输入过程，Y 表示服务过程，表示服务过程，Z 表示并联服务台的个数，表示并联服务台的个数，A 表示顾客表示顾客源，源，B 表示系统容量，表示系统容量，C 表示服务规则表示服务规则(M/M/n:/m/FIFO)表示波松输入，负指数服务时长，表示波松输入，负指数服务时长，n 个并联服务台，顾客源无穷，系统容量为个并联服务台，顾客源无穷，系统容量为 m,m n，先，先到先服务到先服务 D 定长分布；定长分布；Ek k阶爱尔兰分布；阶爱尔兰分布；G 一般独立分布一般独立分布23
