运筹学课件 第十章 排队论.ppt
《运筹学课件 第十章 排队论.ppt》由会员分享,可在线阅读,更多相关《运筹学课件 第十章 排队论.ppt(65页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、运筹学教程第十章第十章 排队论排队论第一节第一节 引言引言一、排队系统的特征及排队论一、排队系统的特征及排队论排队论研究排队系统的数学理论和方法,排队论研究排队系统的数学理论和方法,是运筹学的一个重要分支。是运筹学的一个重要分支。排队问题表现:排队问题表现:运筹学教程到达的顾客要求的服务服务机构1、不能运转机器2、病人3、打电话4、等待降落飞机5、河水进入水库修理就诊通话降落放水,调整水位修理工人医生交换台跑道指挥机构水闸管理员排队可以是人,也可以是物。排队可以是人,也可以是物。排队可以是人,也可以是物。排队可以是人,也可以是物。为了一致:将要求得到服务的对象统称为为了一致:将要求得到服务的对
2、象统称为为了一致:将要求得到服务的对象统称为为了一致:将要求得到服务的对象统称为“顾客顾客顾客顾客”,将提,将提,将提,将提供服务的服务者称为供服务的服务者称为供服务的服务者称为供服务的服务者称为“服务员服务员服务员服务员”或或或或“服务机构服务机构服务机构服务机构”。运筹学教程排队系统的一般描述排队系统的一般描述排队系统的一般描述排队系统的一般描述;顾客为了得到服务而到达系统,如果不能顾客为了得到服务而到达系统,如果不能顾客为了得到服务而到达系统,如果不能顾客为了得到服务而到达系统,如果不能立刻得到服务而又允许排队等待,则加入立刻得到服务而又允许排队等待,则加入立刻得到服务而又允许排队等待,
3、则加入立刻得到服务而又允许排队等待,则加入等待队伍,待获得服务后离开系统。等待队伍,待获得服务后离开系统。等待队伍,待获得服务后离开系统。等待队伍,待获得服务后离开系统。服务台顾客到达服务完后离开单服务台服务系统单服务台服务系统单服务台服务系统单服务台服务系统队列运筹学教程服务台1顾客到达服务完后离开服务台2服务台s队列S S个服务台,一个队列服务系统个服务台,一个队列服务系统个服务台,一个队列服务系统个服务台,一个队列服务系统服务台1顾客到达服务完后离开服务台2服务台s队列1S S个服务台,个服务台,个服务台,个服务台,s s个队列服务系统个队列服务系统个队列服务系统个队列服务系统队列s队列
4、2服务完后离开服务完后离开运筹学教程服务台顾客到达服务完后离开队列服务台队列多个服务台的串联服务系统多个服务台的串联服务系统多个服务台的串联服务系统多个服务台的串联服务系统服务机构聚(输入)散(输出)随机随机随机随机 服务系统服务系统服务系统服务系统运筹学教程二、排队系统的描述二、排队系统的描述二、排队系统的描述二、排队系统的描述1 1 1 1、输入过程:说明顾客按照怎样的规律到达系统。、输入过程:说明顾客按照怎样的规律到达系统。、输入过程:说明顾客按照怎样的规律到达系统。、输入过程:说明顾客按照怎样的规律到达系统。(1)(1)(1)(1)顾客总体数:按顾客源顾客的数量,可分为有限顾客源和顾客
5、总体数:按顾客源顾客的数量,可分为有限顾客源和顾客总体数:按顾客源顾客的数量,可分为有限顾客源和顾客总体数:按顾客源顾客的数量,可分为有限顾客源和无限顾客源;无限顾客源;无限顾客源;无限顾客源;(2)(2)(2)(2)按顾客到达的形式,分为单个到达和成批到达;按顾客到达的形式,分为单个到达和成批到达;按顾客到达的形式,分为单个到达和成批到达;按顾客到达的形式,分为单个到达和成批到达;(3)(3)(3)(3)按顾客相继到达的时间间隔分布,可分为按顾客相继到达的时间间隔分布,可分为按顾客相继到达的时间间隔分布,可分为按顾客相继到达的时间间隔分布,可分为a.a.a.a.定长分布定长分布定长分布定长分
6、布 DDDD:顾客相继到达的时间间隔为确定性的常数。顾客相继到达的时间间隔为确定性的常数。顾客相继到达的时间间隔为确定性的常数。顾客相继到达的时间间隔为确定性的常数。b.b.b.b.最简流(最简流(最简流(最简流(poissonpoissonpoissonpoisson流)流)流)流)MMMM:顾客相继到达的时间间隔顾客相继到达的时间间隔顾客相继到达的时间间隔顾客相继到达的时间间隔 X(n)X(n)X(n)X(n)独立的,同负指数分布独立的,同负指数分布独立的,同负指数分布独立的,同负指数分布:运筹学教程补充:泊松分布:补充:泊松分布:补充:泊松分布:补充:泊松分布:设随机变量设随机变量设随机
7、变量设随机变量X X所有可能的取值为所有可能的取值为所有可能的取值为所有可能的取值为0 0,1 1,2 2,而各,而各,而各,而各个取值的概率为个取值的概率为个取值的概率为个取值的概率为称称称称x x服从参数为服从参数为服从参数为服从参数为 的泊松分布的泊松分布的泊松分布的泊松分布运筹学教程2 2 2 2、排队及其规则、排队及其规则、排队及其规则、排队及其规则(1 1 1 1)排队)排队)排队)排队分为有限排队和无限排队。分为有限排队和无限排队。分为有限排队和无限排队。分为有限排队和无限排队。无限排队:系统空间无限;又称为等待制排队系统。无限排队:系统空间无限;又称为等待制排队系统。无限排队:
8、系统空间无限;又称为等待制排队系统。无限排队:系统空间无限;又称为等待制排队系统。有限排队:系统空间有限;又分为:有限排队:系统空间有限;又分为:有限排队:系统空间有限;又分为:有限排队:系统空间有限;又分为:a.a.a.a.损失制:排队空间为零的系统,不允许排队;到达的损失制:排队空间为零的系统,不允许排队;到达的损失制:排队空间为零的系统,不允许排队;到达的损失制:排队空间为零的系统,不允许排队;到达的顾客有一部分未接受服务就离去;顾客有一部分未接受服务就离去;顾客有一部分未接受服务就离去;顾客有一部分未接受服务就离去;b.b.b.b.混合制:损失制和等待制系统的结合;顾客到达后,混合制:
9、损失制和等待制系统的结合;顾客到达后,混合制:损失制和等待制系统的结合;顾客到达后,混合制:损失制和等待制系统的结合;顾客到达后,一直等到服务完毕以后才离去;不允许队列无限等待。一直等到服务完毕以后才离去;不允许队列无限等待。一直等到服务完毕以后才离去;不允许队列无限等待。一直等到服务完毕以后才离去;不允许队列无限等待。又分为又分为又分为又分为:运筹学教程(i)i)队长有限:系统等待空间有限。队长有限:系统等待空间有限。队长有限:系统等待空间有限。队长有限:系统等待空间有限。有有有有限限限限系系系系统统统统的的的的空空空空间间间间为为为为K,K,顾顾顾顾客客客客到到到到达达达达时时时时的的的的
10、队队队队长长长长为为为为L L。若若若若LKLK,则则则则顾顾顾顾客客客客进进进进入入入入队队队队列列列列等等等等待待待待服服服服务务务务,若若若若L=KL=K,则则则则顾客离去。顾客离去。顾客离去。顾客离去。(ii)ii)等等等等待待待待时时时时间间间间有有有有限限限限:顾顾顾顾客客客客对对对对等等等等待待待待时时时时间间间间具具具具有有有有不不不不耐耐耐耐烦烦烦烦性性性性的的的的系系系系统统统统。设设设设最最最最长长长长等等等等待待待待时时时时间间间间是是是是T T0 0,某某某某个个个个顾顾顾顾客客客客从从从从进进进进入入入入队队队队列列列列后后后后的的的的等等等等待待待待时时时时间间间
11、间为为为为T T。若若若若TTTT0 0,顾顾顾顾客客客客继继继继续等待;若续等待;若续等待;若续等待;若T=TT=T0 0,则顾客脱离队列而离去。则顾客脱离队列而离去。则顾客脱离队列而离去。则顾客脱离队列而离去。(iii)iii)逗留时间有限:等待时间与服务时间之和。逗留时间有限:等待时间与服务时间之和。逗留时间有限:等待时间与服务时间之和。逗留时间有限:等待时间与服务时间之和。运筹学教程(2 2)排队规则)排队规则)排队规则)排队规则(i)(i)先到先服务(先到先服务(先到先服务(先到先服务(FCFSFCFS,First Come First ServeFirst Come First S
12、erve););););(ii)(ii)后后后后 到到到到 先先先先 服服服服 务务务务(LCFSLCFS,Last Last Come Come First First ServeServe););););(iii)(iii)有优先权的服务(有优先权的服务(有优先权的服务(有优先权的服务(PSPS,Priority Serve Priority Serve)(iiiiiiii)随随随随 机机机机 服服服服 务务务务(SIROSIRO,Service Service in in Random Random OrderOrder)运筹学教程3 3、服务机制、服务机制、服务机制、服务机制排队系统的
13、服务机制主要包括:排队系统的服务机制主要包括:排队系统的服务机制主要包括:排队系统的服务机制主要包括:服务员的数量、连接形式(串联或并联);服务员的数量、连接形式(串联或并联);服务员的数量、连接形式(串联或并联);服务员的数量、连接形式(串联或并联);顾客单个或成批接受服务;顾客单个或成批接受服务;顾客单个或成批接受服务;顾客单个或成批接受服务;服务时间的分布;服务时间的分布;服务时间的分布;服务时间的分布;服务时间为服务时间为服务时间为服务时间为V V,分布函数为分布函数为分布函数为分布函数为B(t)B(t),密度函数为密度函数为密度函数为密度函数为b(t)b(t):(1 1)定长分布(定
14、长分布(定长分布(定长分布(D):D):每个顾客接受服务时间是一个常数。每个顾客接受服务时间是一个常数。每个顾客接受服务时间是一个常数。每个顾客接受服务时间是一个常数。(2 2)负指数分布()负指数分布()负指数分布()负指数分布(MM):):):):每个顾客接受服务时间相互独立,每个顾客接受服务时间相互独立,每个顾客接受服务时间相互独立,每个顾客接受服务时间相互独立,具有相同的负指数分布:具有相同的负指数分布:具有相同的负指数分布:具有相同的负指数分布:运筹学教程(3 3)k k阶爱尔郎分布(阶爱尔郎分布(阶爱尔郎分布(阶爱尔郎分布(E Ek k):):):):每个顾客接受服务时间服每个顾客
15、接受服务时间服每个顾客接受服务时间服每个顾客接受服务时间服从从从从k k阶爱尔郎分布,具有密度函数:阶爱尔郎分布,具有密度函数:阶爱尔郎分布,具有密度函数:阶爱尔郎分布,具有密度函数:运筹学教程三、排队系统的符号表示三、排队系统的符号表示三、排队系统的符号表示三、排队系统的符号表示一个排队系统的特征可以用六个参数表示,形式为:一个排队系统的特征可以用六个参数表示,形式为:一个排队系统的特征可以用六个参数表示,形式为:一个排队系统的特征可以用六个参数表示,形式为:X XY YZ Z A AB BC C其中其中其中其中X X 顾客到达的概率分布,可取顾客到达的概率分布,可取顾客到达的概率分布,可取
16、顾客到达的概率分布,可取MM、D D、E Ek k等;等;等;等;Y Y 服务时间的概率分布,可取服务时间的概率分布,可取服务时间的概率分布,可取服务时间的概率分布,可取MM、D D、E Ek k等;等;等;等;Z Z 服务台个数,取正整数;服务台个数,取正整数;服务台个数,取正整数;服务台个数,取正整数;A A 排队系统的最大容量,可取正整数或排队系统的最大容量,可取正整数或排队系统的最大容量,可取正整数或排队系统的最大容量,可取正整数或 ;B B 顾客源的最大容量,可取正整数或顾客源的最大容量,可取正整数或顾客源的最大容量,可取正整数或顾客源的最大容量,可取正整数或 ;C C 排队规则,可
17、取排队规则,可取排队规则,可取排队规则,可取FCFSFCFS、LCFSLCFS等。等。等。等。运筹学教程例如例如例如例如M/M/1/M/M/1/FCFS/FCFS表示顾客到达的时间间隔是负指数分布,服务时间是负表示顾客到达的时间间隔是负指数分布,服务时间是负表示顾客到达的时间间隔是负指数分布,服务时间是负表示顾客到达的时间间隔是负指数分布,服务时间是负指数分布,一个服务台,排队系统和顾客源的容量都是指数分布,一个服务台,排队系统和顾客源的容量都是指数分布,一个服务台,排队系统和顾客源的容量都是指数分布,一个服务台,排队系统和顾客源的容量都是无限,实行先到先服务的一个服务系统。无限,实行先到先服
18、务的一个服务系统。无限,实行先到先服务的一个服务系统。无限,实行先到先服务的一个服务系统。可以缩写为可以缩写为可以缩写为可以缩写为M/M/1M/M/1。M/M/S/K:M/M/S/K:表示顾客到达的时间间隔是负指数分布,服务时间是负表示顾客到达的时间间隔是负指数分布,服务时间是负表示顾客到达的时间间隔是负指数分布,服务时间是负表示顾客到达的时间间隔是负指数分布,服务时间是负指数分布,指数分布,指数分布,指数分布,S S S S个服务台,排队系统容量个服务台,排队系统容量个服务台,排队系统容量个服务台,排队系统容量K K K K和顾客源的容量和顾客源的容量和顾客源的容量和顾客源的容量都是无限,实
19、行先到先服务的一个服务系统都是无限,实行先到先服务的一个服务系统都是无限,实行先到先服务的一个服务系统都是无限,实行先到先服务的一个服务系统。运筹学教程四、排队系统的主要数量指标和记号四、排队系统的主要数量指标和记号四、排队系统的主要数量指标和记号四、排队系统的主要数量指标和记号描述一个排队系统运行状况的主要指标:描述一个排队系统运行状况的主要指标:描述一个排队系统运行状况的主要指标:描述一个排队系统运行状况的主要指标:1 1、队长、排队长、队长、排队长、队长、排队长、队长、排队长队长:系统中的顾客数量(排队顾客队长:系统中的顾客数量(排队顾客队长:系统中的顾客数量(排队顾客队长:系统中的顾客
20、数量(排队顾客+接受服务顾客)。接受服务顾客)。接受服务顾客)。接受服务顾客)。排队长:系统中的正在排队等待服务的顾客数量。排队长:系统中的正在排队等待服务的顾客数量。排队长:系统中的正在排队等待服务的顾客数量。排队长:系统中的正在排队等待服务的顾客数量。2 2、等待时间和逗留时间、等待时间和逗留时间、等待时间和逗留时间、等待时间和逗留时间等待时间:从顾客到达时刻起到他开始接受服务止这段时间等待时间:从顾客到达时刻起到他开始接受服务止这段时间等待时间:从顾客到达时刻起到他开始接受服务止这段时间等待时间:从顾客到达时刻起到他开始接受服务止这段时间为等待时间。为等待时间。为等待时间。为等待时间。逗
21、留时间:从顾客到达时刻起到他接受服务完成这段时间为逗留时间:从顾客到达时刻起到他接受服务完成这段时间为逗留时间:从顾客到达时刻起到他接受服务完成这段时间为逗留时间:从顾客到达时刻起到他接受服务完成这段时间为逗留时间。逗留时间。逗留时间。逗留时间。运筹学教程3 3、忙期和闲期、忙期和闲期、忙期和闲期、忙期和闲期忙期:顾客到达空闲的服务机构起,到服务机构再次成为忙期:顾客到达空闲的服务机构起,到服务机构再次成为忙期:顾客到达空闲的服务机构起,到服务机构再次成为忙期:顾客到达空闲的服务机构起,到服务机构再次成为空闲止的这段时间。空闲止的这段时间。空闲止的这段时间。空闲止的这段时间。闲期:服务机构连续
22、保持空闲的时间。闲期:服务机构连续保持空闲的时间。闲期:服务机构连续保持空闲的时间。闲期:服务机构连续保持空闲的时间。运筹学教程主要数量指标的常用记号:主要数量指标的常用记号:主要数量指标的常用记号:主要数量指标的常用记号:N(t)N(t):时刻时刻时刻时刻t t系统中顾客数量(系统的状态),队长;系统中顾客数量(系统的状态),队长;系统中顾客数量(系统的状态),队长;系统中顾客数量(系统的状态),队长;Nq(tNq(t):时刻时刻时刻时刻t t系统中排队顾客数量,排队长;系统中排队顾客数量,排队长;系统中排队顾客数量,排队长;系统中排队顾客数量,排队长;T(t)T(t):时刻时刻时刻时刻t
23、t到达系统的顾客在系统中的逗留时间;到达系统的顾客在系统中的逗留时间;到达系统的顾客在系统中的逗留时间;到达系统的顾客在系统中的逗留时间;Tq(tTq(t):时刻时刻时刻时刻t t到达系统的顾客在系统中的等待时间;到达系统的顾客在系统中的等待时间;到达系统的顾客在系统中的等待时间;到达系统的顾客在系统中的等待时间;P Pn n(t(t)时刻时刻时刻时刻t t系统中有系统中有系统中有系统中有n n个顾客的概率,系统的瞬时状个顾客的概率,系统的瞬时状个顾客的概率,系统的瞬时状个顾客的概率,系统的瞬时状态;态;态;态;P Pn n 系统达到统计平衡时处于状态系统达到统计平衡时处于状态系统达到统计平衡
24、时处于状态系统达到统计平衡时处于状态n n n n的概率;的概率;的概率;的概率;运筹学教程统计平衡:统计平衡:统计平衡:统计平衡:N-N-N-N-系统处于平衡状态时的队长,均值为系统处于平衡状态时的队长,均值为系统处于平衡状态时的队长,均值为系统处于平衡状态时的队长,均值为L,L,L,L,称为平均队长。称为平均队长。称为平均队长。称为平均队长。N N N Nq q q q-系统处于平衡状态时的排队长,均值为系统处于平衡状态时的排队长,均值为系统处于平衡状态时的排队长,均值为系统处于平衡状态时的排队长,均值为LqLqLqLq,称为平均排队长。称为平均排队长。称为平均排队长。称为平均排队长。T-
25、T-T-T-系系系系统统统统处处处处于于于于平平平平衡衡衡衡状状状状态态态态时时时时的的的的顾顾顾顾客客客客的的的的逗逗逗逗留留留留时时时时间间间间,均均均均值值值值为为为为W,W,W,W,称称称称为为为为平平平平均均均均逗留时间。逗留时间。逗留时间。逗留时间。T T T Tq q q q-系系系系统统统统处处处处于于于于平平平平衡衡衡衡状状状状态态态态时时时时的的的的顾顾顾顾客客客客的的的的等等等等待待待待时时时时间间间间,均均均均值值值值为为为为W,W,W,W,称称称称为为为为平平平平均等待时间。均等待时间。均等待时间。均等待时间。n n n n 系系系系统统统统处处处处于于于于平平平平衡
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运筹学课件 第十章 排队论 运筹学 课件 第十 排队
限制150内