《管理运筹学第十章排队论课件》由会员分享，可在线阅读，更多相关《管理运筹学第十章排队论课件（53页珍藏版）》请在金锄头文库上搜索。
1、上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院运筹学上海应用技术学院经管学院上海应用技术学院经管学院龚有容龚有容Email：电电 话：话：62088001上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院 第十章第十章 排队论排队论上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论10.1概述概述排队论（排队论（Queing Theory）也称随机服务）也称随机服务系统。任何一个服务系统均由客体和主系统。任何一个服务系统均由客体和主体组成。前者是要求服务的对象，我们体组成。前者是要求服务的对象，我们一律称之为一律称之为“顾客顾客”；后
2、者是提供服务；后者是提供服务的的机构或人员，一律称之为机构或人员，一律称之为“服务员服务员”。顾顾客可泛指机器、病人、飞机、轮船等，客可泛指机器、病人、飞机、轮船等，服务员可泛指机修工、医生、码头等。服务员可泛指机修工、医生、码头等。上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论.服服务务系系统统顾客顾客:机器、飞机、轮船、病人机器、飞机、轮船、病人顾客到达顾客到达等待服务等待服务接受服务接受服务顾客离去顾客离去服务员：机修工、码头设备、医生服务员：机修工、码头设备、医生到达时间到达时间服务时间服务时间 系统空闲系统空闲到达时间到达时间=服务时间服务时间
3、 充分利用充分利用,无排队无排队到达时间到达时间服务时间服务时间 排队越来越长排队越来越长上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论问题是问题是: 到到达达间间隔隔、服服务务时时间间均均为为随随机机变变量量，这这也也是是随随机机服服务务系系统统的的基基本本特特征征。所所以以难难以以确确定定系系统统状状态态，只只能能求求期期望望值值。我我们们希希望望借借助助随随机机服服务务系系统统理理论论来来揭示这些规律。揭示这些规律。上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论 例：某港口装卸台负责货轮装卸工作，货轮即顾客以
4、例：某港口装卸台负责货轮装卸工作，货轮即顾客以某固定周期间隔到达港口，比如每隔某固定周期间隔到达港口，比如每隔a=6a=6小时到达一艘，小时到达一艘，而装卸台卸货需要一段时间，假定它对每艘货轮的服而装卸台卸货需要一段时间，假定它对每艘货轮的服务时间也是定长的，比如每艘需卸时间为务时间也是定长的，比如每艘需卸时间为s=4s=4小时。这小时。这一服务系统的特征是到达和服务时间均是确定不变的一服务系统的特征是到达和服务时间均是确定不变的定长。定长。结论：结论：如果如果sa,sa，则形成等待卸货队伍，且队长不断增加。，则形成等待卸货队伍，且队长不断增加。上海应用技术学院经济与管理学院上海应用技术学院经
5、济与管理学院第十章第十章 排队论排队论.如果货轮到达时间间隔是随机变量如果货轮到达时间间隔是随机变量,码头卸货时间也为随码头卸货时间也为随机变量机变量,则构成一个随机服务系统。即便货轮到达时间间则构成一个随机服务系统。即便货轮到达时间间隔的平均时间还为隔的平均时间还为6小时，但每一个间隔时间小时，但每一个间隔时间Xi（i=1、2）并不都是）并不都是6小时，只是指：小时，只是指：同理，平均服务时间为同理，平均服务时间为4小时，从而会产生排队或服务空小时，从而会产生排队或服务空闲时间。但事先无法确定。闲时间。但事先无法确定。上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章
6、排队论排队论对于随机服务系统希望知道：对于随机服务系统希望知道：1、在系统中平均队长、在系统中平均队长L从长远来看，平均等待服从长远来看，平均等待服务加上正接受服务的货轮期望数；务加上正接受服务的货轮期望数；2、在队中平均队长、在队中平均队长Lq从长远来看，平均等待服务从长远来看，平均等待服务的货轮期望数；的货轮期望数；3、系统中平均逗留时间、系统中平均逗留时间 从长远看，任一进从长远看，任一进入系统货轮用于等待服务加上接受服务的期望时间；入系统货轮用于等待服务加上接受服务的期望时间；4、在队中平均等待时间、在队中平均等待时间 从长远看，任一进从长远看，任一进入系统货轮用于等待服务的期望时间。
7、入系统货轮用于等待服务的期望时间。上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论一、服务系统的结构一、服务系统的结构假如将要求服务的对象统称为假如将要求服务的对象统称为“顾客顾客”，进行服务的统称为进行服务的统称为“服务机构服务机构”或或“服务员服务员”，一，一个排队系统就能抽象地描述为：个排队系统就能抽象地描述为：为了获得某种服务而到达的顾客，若不能立即为了获得某种服务而到达的顾客，若不能立即获得服务，而又允许排队等待，则加入等待队获得服务，而又允许排队等待，则加入等待队伍，获得服务之后离开系统。伍，获得服务之后离开系统。作为服务系统基本上由三个部分组
8、成：作为服务系统基本上由三个部分组成：上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论1、输入过程、输入过程 刻划顾客按怎样的规律到达服务系刻划顾客按怎样的规律到达服务系统，主要有以下几方面：统，主要有以下几方面：1）顾客总体（顾客源）数可能是有限的（例厂内故）顾客总体（顾客源）数可能是有限的（例厂内故障设备数）也可能是无限的（到达售票窗口前的顾障设备数）也可能是无限的（到达售票窗口前的顾客总体）；客总体）；2）顾客可能是单个到达，也可能是成批到达；）顾客可能是单个到达，也可能是成批到达；3）顾客相继到达的间隔时间分布可以是确定型，也）顾客相继到达的间隔时
9、间分布可以是确定型，也可以是随机型；可以是随机型；4）顾客的到达可以是相互独立的，即以前的到达情）顾客的到达可以是相互独立的，即以前的到达情况对以后顾客的到来没有影响；况对以后顾客的到来没有影响；上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论5）输入过程可以是）输入过程可以是平稳平稳的（指描述相继到达的的（指描述相继到达的间隔时间分布和所含参数（如间隔时间分布和所含参数（如 ）都与时间都与时间无关无关，否则称为非平稳的；，否则称为非平稳的；6）具有不耐烦顾客的输入）具有不耐烦顾客的输入a）弃长队而去）弃长队而去b）排队太久而去）排队太久而去c）转队）转队
10、上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论2、排队规则（到达的顾客按什么样的规则接受服务）、排队规则（到达的顾客按什么样的规则接受服务）1）损失制）损失制 即服务台一旦占用，顾客随即离去；即服务台一旦占用，顾客随即离去；2）等待制）等待制 顾客到达后须等待服务，服务次序为：顾客到达后须等待服务，服务次序为：a）先到先服务）先到先服务b）后到先服务）后到先服务c）随机服务）随机服务d）有优先权的服务）有优先权的服务3）混合制（损失制与等待制的混合）混合制（损失制与等待制的混合）a）队长有限制的情形）队长有限制的情形队长队长k，离去，离去上海应用技术学院
11、经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论b）等待（或逗留）时间有限制的情形）等待（或逗留）时间有限制的情形排队时间排队时间t0,离去离去;反之排下去反之排下去4)从队伍的数目看从队伍的数目看,可以是单列可以是单列,也可以是多列也可以是多列a)顾客可转移顾客可转移;b)顾客不可转移顾客不可转移;上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论3、服务机构、服务机构1）服务员的数目）服务员的数目串列、并列、串并混合串列、并列、串并混合2）服务方式）服务方式对单个顾客服务或对成批顾客服务对单个顾客服务或对成批顾客服务3）服务时间）服
12、务时间分确定型和随机型服务时间分确定型和随机型服务时间上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论二、表示排队模型的符号二、表示排队模型的符号D.G.Kendall 于于1953 年提出排队符号年提出排队符号: (i/j/c)i:到达过程的分布到达过程的分布;j:服务过程分布服务过程分布;c:服务员数服务员数到了到了1971年进一步定为：年进一步定为：(到达分布到达分布/服务分布服务分布/服务员数服务员数/系统容量系统容量/顾客源顾客源/排队规则排队规则)(M/M/1/FCFS)常规表示法为常规表示法为(M/M/1)上海应用技术学院经济与管理学院上海应
13、用技术学院经济与管理学院第十章第十章 排队论排队论三、排队模型中常用参数三、排队模型中常用参数 ：到达速度（单位时间到达顾客数）；：到达速度（单位时间到达顾客数）； ：服务速度（单位时间服务完成数）；：服务速度（单位时间服务完成数）；1/ ：相继顾客到达的平均间隔时间；：相继顾客到达的平均间隔时间；1/ ：一个顾客的平均服务时间；：一个顾客的平均服务时间； =（1/ ：1/ ）= / 称为称为服务强度服务强度，指相同时，指相同时间区间内顾客到达的平均数与能被服务完的平均顾间区间内顾客到达的平均数与能被服务完的平均顾客数之比；客数之比；上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院
14、第十章第十章 排队论排队论四、系统的稳态性态四、系统的稳态性态1、 j稳态概率稳态概率 j定义为稳态系统中有定义为稳态系统中有j个顾客（包括正在服务的）个顾客（包括正在服务的）的概率。的概率。 0=1- 称为系统空闲的概率称为系统空闲的概率上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论2、3、4、5、上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论6、7、进入系统的顾客逗留时间超过进入系统的顾客逗留时间超过t的概率。的概率。进入系统的顾客等待时间超过进入系统的顾客等待时间超过t的概率。的概率。上海应用技术学院经济与管
15、理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论五、稳态性态中各量值的分析五、稳态性态中各量值的分析1、 = / 的意义的意义1）平均到达速度与平均服务速度之比；）平均到达速度与平均服务速度之比；2）服务员利用率）服务员利用率 =1- 03）一个平均服务时间）一个平均服务时间 内到达的顾客平均数内到达的顾客平均数上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论4）正在接受服务的顾客平均数）正在接受服务的顾客平均数 =0 0+1（1- 0）2、L与与Lq的关系的关系表示系统中平均人数等于队中平均人数加上正在接表示系统中平均人数等于队中平均人数加
16、上正在接受服务顾客平均人数。受服务顾客平均人数。上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论3、系统逗留时间减排队时间恰为服务时间的期望值。系统逗留时间减排队时间恰为服务时间的期望值。上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论4、上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论5、上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论10.2 M/M/1模型实例模型实例例例1、某厂有几千名工人，医务室平均每小时约有、某厂有几千名工人，医务室
17、平均每小时约有4位工人来看病，医生每小时平均诊断约位工人来看病，医生每小时平均诊断约5个病人，若个病人，若到达时间间隔服从普阿松（到达时间间隔服从普阿松（Pisson）分布，服务时间）分布，服务时间服从负指数分布，试分析该系统。服从负指数分布，试分析该系统。解：本例属标准解：本例属标准(M/M/1/FCFS)问题，问题，已知已知 =4人人/小时；小时； =5 人人/小时，小时， = / =4/5=0.8系统队长系统队长L= /(1- )=0.8/(1-0.8)=4人人; 平均平均4人排队和人排队和看病看病队长队长Lq= 2/(1- )=0.82/(1-0.8)=3.2人人;平均有平均有3.2人
18、在排人在排队队或或 Lq= L- =4-0.8=3.2人人上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论工人在医务室平均逗留时间：工人在医务室平均逗留时间：病人平均在医务室内排队和看病时间约为病人平均在医务室内排队和看病时间约为1小时。小时。工人在医务室平均排队时间：工人在医务室平均排队时间：病人平均在医务室内排队时间约为病人平均在医务室内排队时间约为0.8小时。小时。上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论系统空闲概率系统空闲概率 0=1- =1-0.8=0.2系统忙的概率系统忙的概率1- 0= =0.8以
19、该厂每天工作以该厂每天工作8小时计小时计,则每天平均来看病的人数为则每天平均来看病的人数为:L总总=8 =84=32人人/天天;全体病人每天平均等待看病所化时间为全体病人每天平均等待看病所化时间为:W总总=病人逗留时间和排队超过病人逗留时间和排队超过1小时的概率分别为：小时的概率分别为：上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论若要计算系统中大于若要计算系统中大于10个病人的概率个病人的概率,则则: n10= 11=0.811=0.086即医务室中大于即医务室中大于10个病人的概率仅为个病人的概率仅为8.6%医务室中病员大于医务室中病员大于K的概率的
20、概率上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论例例2、某电机修理车间，每天平均有、某电机修理车间，每天平均有2台电机到达修理。台电机到达修理。负责修理的是负责修理的是1名修理工，平均每名修理工，平均每3小时修完小时修完1台。若到台。若到达为泊松分布，修理时间为负指数分布，求达为泊松分布，修理时间为负指数分布，求1台电机从台电机从到达到修理完毕的平均时间及修理工人每天的平均空到达到修理完毕的平均时间及修理工人每天的平均空闲时间（每天以闲时间（每天以8小时计）小时计）解：本问题属解：本问题属(M/M/1/FCFS)模式模式到达速度到达速度 =2台台/8小
21、时小时=1/4 台台/小时小时服务速度服务速度 =1台台/3小时小时=1/3 台台/小时小时 = / =1/4/1/3=3/40.5=e- (1- )t=e-4(1-0.5)0.5=0.3678上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论若是租赁场地，则新系统变为：若是租赁场地，则新系统变为：M/M/1/3/M/M/1/3/FCFS/FCFS模型模型此时顾客流失率为：此时顾客流失率为：加油站每周将增加服务车辆数为：加油站每周将增加服务车辆数为：上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院第十章第十章 排队论排队论每周将增加收入为：每周将增加收入为：5050元元/ /辆辆18.3818.38辆辆/ /周周=919=919元元10001000元元/ /周周由于增加的收入不足以支付每周的场地由于增加的收入不足以支付每周的场地租赁费租赁费, ,所以租赁空地不经济。所以租赁空地不经济。上海应用技术学院经济与管理学院上海应用技术学院经济与管理学院
