随机过程与排队论随机过程与排队论上一讲内容回顾上一讲内容回顾连续参数马尔可夫链连续参数马尔可夫链转移概率函数、转移矩阵转移概率函数、转移矩阵连续参数齐次马氏链连续参数齐次马氏链初始分布、绝对分布、遍历初始分布、绝对分布、遍历性、平稳分布性、平稳分布转移概率函数的性质转移概率函数的性质状态转移速度矩阵状态转移速度矩阵生灭过程生灭过程7/28/20247/28/20242 2计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰本讲主要内容本讲主要内容排队论简介排队论简介排队的概念排队的概念排队系统的基本组成排队系统的基本组成经典排队系统的符号表示方法经典排队系统的符号表示方法无限源的简单排队无限源的简单排队问题的引入问题的引入等待时间与逗留时间等待时间与逗留时间忙期忙期基本的排队系统基本的排队系统 系统系统M/M/1/ 队长队长Little公式公式输出过程输出过程7/28/20247/28/20243 3计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰第四章第四章 排队论简介排队论简介v排排队队论论，又又称称为为随随机机服服务务系系统统理理论论，是是研研究究拥拥挤挤现现象象的的一一门门学学科科，它它通通过过研研究究各各种种服服务务系系统统在在排排队队等等待待中中的的概概率率特特性性，来来解解决决系系统统的最优设计和最优控制。的最优设计和最优控制。v排排队队论论起起源源于于20世世纪纪初初丹丹麦麦电电信信工工程程师师A.K. Erlang对对电电信信系系统统的的研研究究，现现已已发发展展成成为为一一门门应应用用广广泛泛的的学学科科，在在电电信信、交交通通运运输输、生生产产与与库库存存管管理理、计计算算机机系系统统设设计计、计计算算机机通通信信网网络络、军军事事作作战战、柔柔性性制制造造系系统统和和系系统统可可靠性等众多领域，有着非常重要的应用。靠性等众多领域，有着非常重要的应用。7/28/20247/28/20244 4计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰排队的概念排队的概念排排队队是是日日常常生生活活和和工工作作中中常常见见的的现现象，由两个方面构成：象，由两个方面构成：1.要求得到服务要求得到服务顾客顾客2.提供服务提供服务服务员或服务台服务员或服务台3.顾顾客客与与服服务务台台(二二者者缺缺一一不不可可)就就构构成成一一个个排排队队系系统统，或或称称为为随随机机服服务务系统系统。7/28/20247/28/20245 5计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰基本的排队系统基本的排队系统1.单服务员单服务员(台台)的排队系统的排队系统2.多服务员多服务员(台台)的排队系统的排队系统顾客到达顾客到达服务完成离去服务完成离去服务员服务员顾客到达顾客到达服务完成离去服务完成离去服务员服务员n服务员服务员2服务员服务员1一个队列一个队列多个队列多个队列顾客到达顾客到达 服务完成离去服务完成离去服务员服务员n服务员服务员2服务员服务员1服务完成离去服务完成离去服务完成离去服务完成离去串联串联顾客到达顾客到达离去离去服务员服务员1服务员服务员27/28/20247/28/20246 6计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰排队系统的基本组成排队系统的基本组成1.输入过程输入过程2.排队规则排队规则3.服务机构服务机构描述顾客来源及顾客描述顾客来源及顾客按怎样的规律抵达。按怎样的规律抵达。服服务务是是否否允允许许排排队队，顾顾客客是是否否愿愿意意排排队队。在在排排队队等等待待的的情情况况下下服务的顺序是什么。服务的顺序是什么。服务台的数目服务台的数目 服务时间分布服务时间分布7/28/20247/28/20247 7计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰输入过程输入过程描述顾客来源及顾客按怎样的规律抵达。描述顾客来源及顾客按怎样的规律抵达。1)顾客总体数顾客总体数顾客的来源可能是有限的，也可能是无限顾客的来源可能是有限的，也可能是无限的的2)到达类型到达类型顾客是单个到达，还是成批到达顾客是单个到达，还是成批到达3)顾客相继到达的间隔时间服从什么概率分布，顾客相继到达的间隔时间服从什么概率分布，分布函数是什么，到达的间隔时间之间是否独分布函数是什么，到达的间隔时间之间是否独立立在排队论中，一般假定顾客到达的间隔时间序列在排队论中，一般假定顾客到达的间隔时间序列 n|n 1相互独立、同分布。相互独立、同分布。7/28/20247/28/20248 8计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰排队规则排队规则服务是否允许排队，顾客是否愿意排队。在排队等待的情服务是否允许排队，顾客是否愿意排队。在排队等待的情况下服务的顺序是什么。况下服务的顺序是什么。1)损失制损失制 顾客到达时，若所有服务台均被占，服务机顾客到达时，若所有服务台均被占，服务机构不允许顾客等待，此时该顾客就自动离去构不允许顾客等待，此时该顾客就自动离去2)等等待待制制 顾顾客客到到达达时时，若若所所有有服服务务台台均均被被占占，他他们们就就排队等待服务排队等待服务a)先到先服务先到先服务b)后到先服务后到先服务c)随机服务随机服务d)有优先权服务：强拆型优先权、非强拆型优先权有优先权服务：强拆型优先权、非强拆型优先权3)混合制混合制 损失制与等待制的混合损失制与等待制的混合a)对长对长(容量容量)有限的混合制有限的混合制b)等待时间有限的混合制等待时间有限的混合制c)逗留时间有限的混合制逗留时间有限的混合制7/28/20247/28/20249 9计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰服务机构服务机构1)服务台的数目服务台的数目 在多个服务台的情况下，是串联或是并联在多个服务台的情况下，是串联或是并联2)顾客所需的服务时间服从什么概率分顾客所需的服务时间服从什么概率分布，每个顾客所需的服务时间是否相布，每个顾客所需的服务时间是否相互独立，是成批服务或是单个服务互独立，是成批服务或是单个服务7/28/20247/28/20241010计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰经典排队系统的符号表示方法经典排队系统的符号表示方法 一个排队系统是由许多条件决定的，一个排队系统是由许多条件决定的，为简明起见，在经典的排队系统中，为简明起见，在经典的排队系统中，常采用常采用35个英文字母个英文字母表示一个排队表示一个排队系统，字母之间用斜线隔开：系统，字母之间用斜线隔开：v第一个字母第一个字母表示表示输入的分布类型输入的分布类型v第二个字母第二个字母表示表示服务时间的分布类型服务时间的分布类型v第三个字母第三个字母表示表示服务台的数目服务台的数目v第四个字母第四个字母表示表示系统的容量系统的容量v第五个字母第五个字母表示表示顾客源中的顾客数目顾客源中的顾客数目。7/28/20247/28/20241111计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰几个经典排队系统的符号表示几个经典排队系统的符号表示vM/M/c/ ：输入过程是泊松流，服务时间服从负指数分布，有输入过程是泊松流，服务时间服从负指数分布，有c个服务台平行服务个服务台平行服务(0c)，容量为无穷的等待制系统容量为无穷的等待制系统vM/G/1/ ：输入过程是泊松流，服务时间独立、服从一般概率输入过程是泊松流，服务时间独立、服从一般概率分布，只有分布，只有1个服务台个服务台，容量为无穷的等待制系统容量为无穷的等待制系统vEk/G/1/K：相继到达的间隔时间独立、服从相继到达的间隔时间独立、服从k阶爱尔朗分布，服阶爱尔朗分布，服务时间独立、服从一般概率分布，只有务时间独立、服从一般概率分布，只有1个服务台个服务台，容量为容量为k(0 k )的混合制系统的混合制系统vD/M/c/K：相继到达的间隔时间独立、服从定长分布，服务时间相继到达的间隔时间独立、服从定长分布，服务时间独立、服从负指数分布，有独立、服从负指数分布，有c个服务台平行服务个服务台平行服务，容量为容量为k(c k0)的的泊泊松松过过程程，即即相相继继到到达达的的间间隔隔时时间间序序列列 n，n 1独独立立、服服从从参参数数为为 ( 0)的负指数分布的负指数分布F(t)1-e- t，t 0；v顾顾客客所所需需的的服服务务时时间间序序列列 n,n 1独独立立、服服从从参参数数为为 ( 0)的的负负指指数数分分布布G(t)1-e- t，t 0；v系统中只有一个服务台；系统中只有一个服务台；v容容量量为为无无穷穷大大，而而且且到到达达过过程程与与服服务务过过程程彼彼此此独立。独立。7/28/20247/28/20241515计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰2.队长队长 假定假定N(t)表示在时刻表示在时刻t系统中的顾客数，包括正在被服系统中的顾客数，包括正在被服务的顾客数，即务的顾客数，即N(t)表示时刻表示时刻t系统的队长，系统的队长，t 0，且令，且令pij( t)PN(t+ t)j|N(t)i，i,j0,1,2,则则1)pi,i+1( t)P在在 t内到达一个而服务未完成内到达一个而服务未完成 在在 t内到达内到达j个而服务完个而服务完j-1个个 P 1t， 1 t 1+ jt 1+ j+1， 1+ j-1t t， 1t 1+ jt 1+ j+1， 1+ j+1t 1+ j+2(1-e-t)e-to( t)to( t)i1,2,3,3)类似分析可得类似分析可得pij( t)o( t)，|i-j| 27/28/20247/28/20241717计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰队长队长(续续2)综合上述综合上述1)2)3)得得N(t)，t 0是可列无限状态是可列无限状态E0,1,2,上的生灭过程，上的生灭过程，其参数为其参数为此生灭过程的绝对分布此生灭过程的绝对分布pj(t)PN(t)=j，j=0,1,2,的福克的福克普朗克方程组为普朗克方程组为7/28/20247/28/20241818计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰队长队长(续续3)令令 ，则称，则称 为系统的为系统的交通强度交通强度(Trafficindensity)。有如下结论：有如下结论： 令令pj ，j=0,1,2,，则，则1)当当1时，时，pj0，j=0,1,2,不构成概率分布；不构成概率分布；2)当当 1时，时，pj，j=0,1,2,存在，与初始条件无存在，与初始条件无关，且关，且pj(1- ) j，j=0,1,2,构成一个几何概率分布。构成一个几何概率分布。7/28/20247/28/20241919计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰结论结论在统计平衡的条件下在统计平衡的条件下( 1)，平均队长平均队长等待队长的分布等待队长的分布平均等待队长平均等待队长7/28/20247/28/20242020计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰结论结论(续续)在等待条件下的等待队长分布在等待条件下的等待队长分布在等待条件下的平均等待队长在等待条件下的平均等待队长根据队长分布意知：根据队长分布意知： p0=1 也是也是系统空闲的概率系统空闲的概率，而，而 正是正是系统系统繁忙的概率繁忙的概率。显然，。显然， 越大，系统就越繁忙越大，系统就越繁忙。7/28/20247/28/20242121计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰3.等待时间与逗留时间等待时间与逗留时间1.假定顾客是先到先服务。假定顾客是先到先服务。 定理定理 在统计平衡在统计平衡( 0时，有时，有Wq(t)PWq=0P0Wq tp0- 00)的随机变量，即参数为的随机变量，即参数为 的泊松流。的泊松流。2.当系统空闲后，从开始空闲时刻起，到下一个顾客服当系统空闲后，从开始空闲时刻起，到下一个顾客服务完毕离去时之间的间隔时间不与服务时间同分布。务完毕离去时之间的间隔时间不与服务时间同分布。 令令Tn+表表 示示 第第n个个 顾顾 客客 服服 务务 完完 毕毕 的的 离离 去去 时时 刻刻 ， 则则Tn+1+-Tn+表示离去的时间间隔，表示离去的时间间隔，n 1，于是，对，于是，对t 0有有 PTn+1+Tn+tPNn+=0PTn+1+Tn+t|Nn+=0 PNn+ 1PTn+1+Tn+t|Nn+ 1PNn+=0P n+1 n+1t PNn+ 1P n+1t其中其中 n+1表示剩余到达间隔时间，与表示剩余到达间隔时间，与 n+1独立，而独立，而Nn+表示表示第第n个离去顾客服务完毕离开系统时的队长。个离去顾客服务完毕离开系统时的队长。7/28/20247/28/20243030计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰输出过程输出过程( (续续) )因此因此由于由于此式表示在统计平衡下，相继输出的间隔时间服从参数为此式表示在统计平衡下，相继输出的间隔时间服从参数为 （ 00）的负指数分布。）的负指数分布。 另外，在统计平衡下，输出的间隔时间相互独立，因另外，在统计平衡下，输出的间隔时间相互独立，因此对此对M/M/1/M/M/1/ 系统，其统计平衡下的输出过程与到达过程系统，其统计平衡下的输出过程与到达过程相同。相同。7/28/20247/28/20243131计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例1 某火车站一个售票窗口，若到达该窗口购票的某火车站一个售票窗口，若到达该窗口购票的顾顾客客按按泊泊松松流流到到达达，平平均均每每分分钟钟到到达达1人人，假假定定售售票票时时间间服服从从负负指指数数分分布布，平平均均每每分分钟钟可可售售2人人，试试研究该售票窗口前的排队情况。研究该售票窗口前的排队情况。解解 由由题题设设知知， 1(人人/分分)， 2(人人/分分)， ，该该系系统统按按M/M/1/ 型型处处理理，于于是是在在统统计计平平衡衡下下，有有平均队长为平均队长为(人人)平均等待队长为平均等待队长为(人人)7/28/20247/28/20243232计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例1(1(续续) )平均等待时间为平均等待时间为(分钟分钟)平均逗留时间为平均逗留时间为(分钟分钟)顾客到达不需要等待的概率为顾客到达不需要等待的概率为等待队长超过等待队长超过5人的概率为人的概率为7/28/20247/28/20243333计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例2 考虑某种产品的库存问题。如果进货过多，则会带来考虑某种产品的库存问题。如果进货过多，则会带来过过多多的的保保管管费费，如如果果存存货货不不足足，则则缺缺货货时时影影响响生生产产，造造成成经经济济损损失失。最最好好的的办办法法是是能能及及时时供供应应，但但由由于于生生产产和和运运输输等等方方面面的的因因素素，一一般般讲讲这这是是难难以以满满足足的的，因因此此希希望望找找到到一一种种合合理理的的库库存存s，使使得得库库存存费费与与缺缺货货损损失失费费的的总总和和达达到到最最小小。假假定定需需求求是是参参数数 的的泊泊松松流流，生生产产是是一一个个一一个个产产品品生生产产的的，每每生生产产一一个个产产品品所所需需时时间间为为参参数数 的的负负指指数数分分布布。库库存存一一个个产产品品的的单单位位时时间间费费用用为为c元元，缺缺一一个个产产品品造造成成的的损损失失费费为为h元元，寻寻找找一一个个最最优优库库存存量量s，使使得得库库存存费费与与损损失失费费之之和和达达到最小（不考虑产品的运输时间）。到最小（不考虑产品的运输时间）。7/28/20247/28/20243434计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例2(续续1)解解 把生产产品的工厂看成是服务机构，需求看作是输入把生产产品的工厂看成是服务机构，需求看作是输入流，于是把问题化成流，于是把问题化成M/M/1/ 系统，需求量表示队长，系统，需求量表示队长，pk表示生产厂有表示生产厂有k个订货未交的概率。设库存量为个订货未交的概率。设库存量为s，则缺货，则缺货时的平均缺货数为时的平均缺货数为平均库存数为平均库存数为7/28/20247/28/20243535计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例2(续续2)单位时间的期望总费用为单位时间的期望总费用为用边际分析法解上式，使上式最小的用边际分析法解上式，使上式最小的s应满足应满足f(s-1) f(s)， f(s+1) f(s)，于是，于是由由f(s+1) f(s)得得，于是，于是由由f(s-1) f(s)得得因此取最佳因此取最佳s*为最靠近为最靠近的正整数即可。的正整数即可。7/28/20247/28/20243636计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例3 设船按泊松流进港口，平均每天到达设船按泊松流进港口，平均每天到达2条，装卸时间条，装卸时间服从负指数分布，平均每天装卸服从负指数分布，平均每天装卸3条船，求：条船，求：1)平均等待对长与平均等待时间；平均等待对长与平均等待时间；2)如果船在港口的停留时间超过一个值如果船在港口的停留时间超过一个值t0就要罚款，求就要罚款，求遭罚款的概率；遭罚款的概率；3)若每超过一天罚款若每超过一天罚款c元，提前一天奖励元，提前一天奖励b元。假定服元。假定服务费与服务率成正比，每天务费与服务率成正比，每天 h元，装卸一条船收入元，装卸一条船收入a元，求使港口每天收入最大的服务率元，求使港口每天收入最大的服务率 *的值。的值。7/28/20247/28/20243737计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例3(续续1)解解 由题设知，由题设知， 2(条条/天天)， 3(条条/天天)， ，该，该系统按系统按M/M/1/ 型处理。型处理。1)平均等待对长为平均等待对长为(条船条船)平均等待时间为平均等待时间为(天天)2)由由于于遭遭到到罚罚款款当当且且仅仅当当船船在在港港口口的的逗逗留留时时间间超超过过t0，所所以遭到罚款的概率为以遭到罚款的概率为3)从从费费用用方方面面考考虑虑，每每天天装装卸卸完完 条条船船收收入入 a元元，每每天天服服务费为务费为h 元。元。7/28/20247/28/20243838计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例3(续续2)平均提前完成时间为平均提前完成时间为平均延后时间为平均延后时间为所以，港口一天的总收入为所以，港口一天的总收入为7/28/20247/28/20243939计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例3(续续3)对对f求导得求导得讨论：讨论：1)bc时，时，2)bc时，由于时，由于 的符号在的符号在 时完全由括号内的两项时完全由括号内的两项决定。令决定。令7/28/20247/28/20244040计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例3(续续4)由上图看出，由上图看出，y1与与y2两曲线有唯一交点，其横坐标为两曲线有唯一交点，其横坐标为 *， b (b-c) *y y2y1且且 *唯一存在、有限，唯一存在、有限，7/28/20247/28/20244141计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例3(续续5) b (b-c) *y y2y13)bc时，时，由下图看出，由下图看出，y1与与y2两曲线仍有唯一交点，两曲线仍有唯一交点，其横坐标为其横坐标为 *，且，且 *唯一存在、有限，唯一存在、有限，7/28/20247/28/20244242计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰例例4 设顾客到达为泊松流，平均每小时到达设顾客到达为泊松流，平均每小时到达 个顾客是已知的。一个个顾客是已知的。一个顾顾客客在在系系统统内内逗逗留留每每小小时时损损失失c1元元，服服务务机机构构的的费费用用正正比比于于服服务务率率 ，每每小小时时每每位位顾顾客客的的费费用用为为c2元元。假假定定服服务务时时间间为为参参数数 的的负负指指数数分分布布，求最佳求最佳服务率服务率 *，使得整个系统总费用最少。，使得整个系统总费用最少。解解 由于平均对长由于平均对长 ，所以每小时顾客的平均损失费为，所以每小时顾客的平均损失费为 元元，每每小小时时服服务务机机构构的的平平均均费费用用为为c2 元元，于于是是单单位位时时间间内内平平均总费用为均总费用为由由得得因为因为，所以最佳服务率为，所以最佳服务率为 *，此时，此时7/28/20247/28/20244343计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰本讲主要内容本讲主要内容排队论简介排队论简介排队的概念排队的概念排队系统的基本组成排队系统的基本组成经典排队系统的符号表示方法经典排队系统的符号表示方法无限源的简单排队无限源的简单排队问题的引入问题的引入等待时间与逗留时间等待时间与逗留时间忙期忙期基本的排队系统基本的排队系统 系统系统M/M/1/ 队长队长Little公式公式输出过程输出过程7/28/20247/28/20244444计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰下一讲内容预告下一讲内容预告无限源的简单排队系统无限源的简单排队系统M/M/1/ 具有可变输入率的具有可变输入率的M/M/1/ 问题的引入问题的引入队长队长等待时间与逗留时间等待时间与逗留时间Little公式公式具有可变服务率的具有可变服务率的M/M/1/ 问题的引入问题的引入队长队长等待时间与逗留时间等待时间与逗留时间7/28/20247/28/20244545计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰 病病人人以以每每小小时时3人人的的泊泊松松流流到到达达医医院院，假假设设该该医医院院只只有有一一个个医医生生服服务务，他他的的服服务务时时间间服服从从负负指指数数分分布布，并并且且平平均均服服务务一一个个顾客时间为顾客时间为15分钟。分钟。a)医生空闲时间的比例？医生空闲时间的比例？b)有多少病人等待看医生？有多少病人等待看医生？c)病人的平均等待时间？病人的平均等待时间？d)一个病人等待超过一个小时的概率一个病人等待超过一个小时的概率？本节习题本节习题7/28/20247/28/20244646计算机科学与工程学院顾小丰计算机科学与工程学院顾小丰