运筹学8、排队论.ppt

运筹学运运运运 筹筹筹筹 学学学学OperationsResearchOperationsResearchQueuing theory第第7章章 排队论排队论7.1 排队论的基本概念排队论的基本概念7.2 排队系统常用分布排队系统常用分布 7.3 单服务台模型单服务台模型M/M/17.4 多服务台模型多服务台模型M/M/s7.5 其它服务时间分布模型其它服务时间分布模型7.6 排队系统的优化排队系统的优化 Where the Time Goes美国人一生中平均要花费美国人一生中平均要花费-6年年 吃吃5年年 排队等待排队等待4年年 做家务做家务2年年 回电话不成功回电话不成功 1年年 寻找放置不当的物品寻找放置不当的物品8个月个月 打开邮寄广告打开邮寄广告6个月个月 停在红灯前停在红灯前排队系统的基本特征排队系统的基本特征离开排队规则到达过程排队结构服务过程退出离开需求群体商业服务系统商业服务系统系统类型系统类型顾客顾客服务台服务台理发店人理发师银行出纳服务人出纳ATM机服务人ATM机商店收银台人收银员管道服务阻塞的管道管道工电影院售票窗口人售票员机场检票处人航空公司代理人经纪人服务人股票经纪人内部服务系统内部服务系统系统类型系统类型顾客顾客服务台服务台秘书服务雇员秘书复印服务雇员复印机计算机编程服务雇员程序员大型计算机雇员计算机急救中心雇员护士传真服务雇员传真机物料处理系统货物物料处理单元维护系统设备维修工人质检站物件质检员运输服务系统运输服务系统系统类型系统类型顾客顾客服务台服务台公路收费站汽车收费员卡车装货地卡车装货工人港口卸货区轮船卸货工人等待起飞的飞机飞机跑道航班服务人飞机出租车服务人出租车电梯服务人电梯消防部门火灾消防车停车场汽车停车空间急救车服务人急救车到达过程到达过程静态动态预约定价接受/拒绝不加入排队退出排队恒定到达率的随机到达变动到达率的随机到达由设施控制顾客控制到达过程到达过程的内容到达过程的内容顾客总体数或顾客源数顾客总体数或顾客源数有限或无限有限或无限顾客的到达类型顾客的到达类型单个或成批单个或成批顾客的到达间隔时间顾客的到达间隔时间间隔时间分布间隔时间分布排队结构排队结构领号多条队列有限队长有限队长有限或无限队长快速通道排队结构单一队列允许或不允许移动排队结构排队结构-例例多队多服务台多队多服务台领号领号 34826101211579单队多服务台单队多服务台入口入口 排队规则排队规则排队规则静态(FCFS规则)(LCFS规则).动态基于排队状况选择即与特定顾客特征选择等待的顾客数协商优先级强占顾客服务时间(SPT规则)排队规则的内容排队规则的内容损失制系统损失制系统服务台被占用时新到的顾客将离开服务台被占用时新到的顾客将离开等待制系统等待制系统FCFSLCFSRSPR混合制系统混合制系统损失制与等待制的混合损失制与等待制的混合服务过程服务过程服务过程静态服务过程动态服务过程自我服务机械速度不同的服务率开关服务通道服务过程的内容服务过程的内容服务台数量服务台数量单个或多个单个或多个每次服务顾客的数量每次服务顾客的数量单个或成批单个或成批服务顾客的时间分布服务顾客的时间分布时间分布时间分布常用的记号常用的记号n 系统中的顾客数系统中的顾客数 平均到达率，即单位时间内平均到达的顾客数平均到达率，即单位时间内平均到达的顾客数 平均服务率，即单位时间内服务完毕的顾客数平均服务率，即单位时间内服务完毕的顾客数Sn(t)时刻时刻t系统中有系统中有n个顾客个顾客Pn(t)时刻时刻t系统状态系统状态Sn(t)的概率的概率C 服务台的个数服务台的个数M 顾客相继到达的时间间隔服从负指数分布顾客相继到达的时间间隔服从负指数分布D 顾客相继到达的时间间隔服从定长分布顾客相继到达的时间间隔服从定长分布Ek 顾客相继到达的时间间隔服从顾客相继到达的时间间隔服从k阶阶Erlang分布分布排队系统的符号表示排队系统的符号表示 一一个个排排队队系系统统的的特特征征可可以以用用六六个个参参数数表表示示，形式为：形式为：ABC：def其中其中A 顾客到达的概率分布，可取顾客到达的概率分布，可取M、D、Ek等；等；B 服务时间的概率分布，可取服务时间的概率分布，可取M、D、Ek等；等；C 服务台个数，取正整数；服务台个数，取正整数；d 排队系统的最大容量，可取正整数或排队系统的最大容量，可取正整数或；e 顾客源的最大容量，可取正整数或顾客源的最大容量，可取正整数或；f 排队规则，可取排队规则，可取FCFS、LCFS等。等。M/M/1：/FCFS表示：表示：顾客到达的时间间隔是负指数分布顾客到达的时间间隔是负指数分布服务时间是负指数分布服务时间是负指数分布一个服务台一个服务台排队系统和顾客源的容量都是无限排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统实行先到先服务的一个服务系统 Poisson流（流（Poisson过程）过程）定义定义 满足以下四个条件的输入流称为满足以下四个条件的输入流称为Poisson流（流（Poisson过程）过程）1、平平稳稳性性：在在时时间间区区间间t,t+t)内内到到达达k个个顾顾客客的的概概率率与与t无无关关，只只与与 t有关。记为有关。记为pk(t）。）。2、无后效性：、无后效性：不相交的时间区间内到达的顾客数互相独立。不相交的时间区间内到达的顾客数互相独立。3、普通性：、普通性：设在设在t,t+t）内到达多于一个顾客的概率为）内到达多于一个顾客的概率为q(t），则），则q(t)=o(t)即即4、有限性：、有限性：任意有限个区间内到达有限个顾客的概率等于一。即任意有限个区间内到达有限个顾客的概率等于一。即Poisson流与流与Poisson分布分布定定理理 对对于于一一个个参参数数为为 的的Poisson流流，在在0，t)内内到达到达k个顾客的概率为个顾客的概率为 即服从以即服从以 为参数的为参数的Poisson分布。分布。=1=3=7Pkk.4.3.2.1 0数学家泊松（Poisson）（17811840）v“泊松是第一个沿着复平面上的路径实行积分的人.”克兰“我建立了描述随机现象的一种概率分布.”泊松泊松是法国数学家、物理学家和泊松是法国数学家、物理学家和力学家力学家Poisson流与负指数分布之间的关系流与负指数分布之间的关系 定理定理 在排队系统中，如果单位时间内顾客到达在排队系统中，如果单位时间内顾客到达数服从以数服从以 为参数的为参数的Poisson分布，则顾客相继分布，则顾客相继到达的时间间隔服从以到达的时间间隔服从以 为参数的负指数分布。为参数的负指数分布。=0.41/为平均到达间隔时间Excel中的泊松分布vPOISSONv用途：用途：返回泊松分布。泊松分布通常用于预测一段时间内事件发生的次数，比如一分钟内通过收费站的轿车的数量。v语法：语法：POISSON(x，mean，cumulative)v参数：参数：X是某一事件出现的次数，Mean是期望值，Cumulative为确定返回的概率分布形式的逻辑值。Cumulative为一逻辑值，确定所返回的概率分布形式。如果cumulative为TRUE，函数POISSON返回泊松累积分布概率，即，随机事件发生的次数在0到x之间（包含0和1）；如果为FALSE，则返回泊松概率密度函数，即，随机事件发生的次数恰好为x。v实例：实例：公式“=POISSON(5，10，TRUE)”返回0.067085963，=POISSON(3，12，FALSE)返回0.001769533。k阶阶Erlang分布分布 定定理理 设设v1，v2，vk是是k个个互互相相独独立立的的，具具有有相同参数相同参数 的负指数分布随机变量，则随机变量的负指数分布随机变量，则随机变量S=v1+v2+vk服从服从k阶阶Erlang分布，分布，S的密度函数为的密度函数为m=1k=1k=2k=4k=8系统绩效度量系统绩效度量 系统总的平均顾客数系统总的平均顾客数L 平均等待顾客个数平均等待顾客个数Lq 包括服务的平均等待时间包括服务的平均等待时间W 平均顾客等待时间平均顾客等待时间Wq基本排队模型基本排队模型 M/M/1:/FCFS 顾客到达的时间间隔是负指数分布顾客到达的时间间隔是负指数分布服务时间是负指数分布服务时间是负指数分布一个服务台一个服务台排队系统和顾客源的容量都是无限排队系统和顾客源的容量都是无限实行先到先服务的一个服务系统实行先到先服务的一个服务系统M/M/1:/FCFS的分析的分析 假设假设在在t+t时刻系统中顾客数为时刻系统中顾客数为n的概率的概率Pn(t+t)SnSnSn+1Sn-1SnPn(t)Pn-1(t)Pn+1(t)Pn(t)t时刻时刻t+t时刻时刻无到达，无离开无到达，无离开无到达，离开一个无到达，离开一个到达一个，无离开到达一个，无离开到达一个，离开一个到达一个，离开一个系统的过渡状态与稳定状态系统的过渡状态与稳定状态过渡过渡稳定稳定稳定状态下的状态概率稳定状态下的状态概率得到得到 令令 称称 为服务强度，则为服务强度，则得得M/M/1:/FCFS的状态转移分析的状态转移分析012n-1nn+1例例高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为100辆辆小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒秒辆。求辆。求1、收费处空闲的概率；、收费处空闲的概率；2、收费处忙的概率；、收费处忙的概率；3、系统中分别有、系统中分别有1，2，3辆车的概率。辆车的概率。解解根据题意根据题意,=100辆辆/小时小时,1/=15秒秒=1/240（小时（小时/辆）辆）,即即 240（辆（辆/小时）。小时）。因此，因此，=/=100/240=5/12。系统空闲的概率为：系统空闲的概率为：P0=1-=1-(5/12)=7/12=0.583系统忙的概率为：系统忙的概率为：1-P0=1-(1-)=5/12=0.417系统中有系统中有1辆车的概率为：辆车的概率为：P1=(1-)=0.4170.583=0.243系统中有系统中有2辆车的概率为：辆车的概率为：P2=2(1-)=0.417 20.583=0.101系统中有系统中有3辆车的概率为：辆车的概率为：P3=3(1-)=0.417 30.583=0.0421Little公式公式 M/M/1:/FCFS的系统指标的系统指标系统中的平均顾客数系统中的平均顾客数L 队列中的平均顾客数队列中的平均顾客数Lq 顾客在系统中的平均逗留时间顾客在系统中的平均逗留时间W 顾客在队列中的平均逗留时间顾客在队列中的平均逗留时间Wq 例例 高高速速公公路路入入口口收收费费处处设设有有一一个个收收费费通通道道，汽汽车车到到达达服服从从Poisson分分布布，平平均均到到达达速速率率为为200辆辆/小小时时，收收费费时时间间服服从从负负指指数数分分布布，平平均均收收费费时时间间为为15秒秒/辆。求辆。求L、Lq、W和和Wq。解解根据题意，根据题意，=200辆辆/小时，小时，=240辆辆/小时，小时，=/=5/6。有限队列模型有限队列模型 M/M/1:N/FCFS 当队列的容量从无限值变为有限值当队列的容量从无限值变为有限值N时，时，M/M/1:/FCFS就转化成为就转化成为M/M/1:N/FCFS 系统的状态转移图系统的状态转移图012n-1n系统的状态概率平衡方程系统的状态概率平衡方程对于状态对于状态0：P0=P1对于状态对于状态k：Pk-1+Pk+1=(+)Pk 0kN对于状态对于状态N：PN-1=PN系统的状态概率系统的状态概率由由得到得到 系统的运行指标系统的运行指标 对于对于1有有有效到达率有效到达率 Little公式公式例例一一个个单单人人理理发发店店，除除理理发发椅椅外外，还还有有4把把椅椅子子可可供供顾顾客客等等候候。顾顾客客到到达达发发现现没没有有座座位位空空闲闲，就就不不再再等等待待而而离离去去。顾顾客客到到达达的的平平均均速速率率为为4人人/小小时时，理理发发的的平平均均时时间间为为10分分钟钟/人人。顾顾客客到达服从到达服从Poisson流，理发时间服从负指数分布。求：流，理发时间服从负指数分布。求：1、顾客到达不用等待就可理发的概率；、顾客到达不用等待就可理发的概率；2、理发店里的平均顾客数以及等待理发的平均顾客数；、理发店里的平均顾客数以及等待理发的平均顾客数；3、顾客来店理发一次平均花费的时间及平均等待的时间；、顾客来店理发一次平均花费的时间及平均等待的时间；4、顾客到达后因客满而离去的概率；、顾客到达后因客满而离去的概率；5、增加一张椅子可以减少的顾客损失率。、增加一张椅子可以减少的顾客损失率。解解这是一个这是一个M/M/1:N/FCFS系统，其中系统，其中N=4+1=5，=4人人/小时，小时，=6人人/小时，小时，=2/3。因客满而离去的概率为因客满而离去的概率为0.048 当当N=6时时 P5-P6=0.0480-0.0311=0.0169=1.69%即增加一张椅子可以减少顾客损失率即增加一张椅子可以减少顾客损失率1.69%M/M/1:/m/FCFS模型模型设顾客总数为设顾客总数为m。当顾客需要服务时，就进入队列等。当顾客需要服务时，就进入队列等待；服务完毕后，重新回到顾客源中。如此循环往复待；服务完毕后，重新回到顾客源中。如此循环往复。服务台.顾客源需要服务服务完毕队列分析分析假定每一个顾客在单位时间内需要接受服务的平均假定每一个顾客在单位时间内需要接受服务的平均次数是相同的，设为次数是相同的，设为。当。当正在等待及正在接受服正在等待及正在接受服务的顾客数为务的顾客数为n时时，则在单位时间内要求接受服务，则在单位时间内要求接受服务的平均顾客数为的平均顾客数为：n=(m-n)01nm状态转移方程状态转移方程0P0=P1 n+Pn=Pn+1+n-1Pn-1(n=1，2，m-1)Pm=m-1Pm-1(n=1，2，m)运行指标运行指标 例例某某车车间间有有5台台机机器器，每每台台机机器器的的连连续续运运转转时时间间服服从从负负指指数数分分布布，平平均均连连续续运运行行时时间间15分分钟钟。有有一一个个修修理理工工，每每次次修修理时间服从负指数分布，平均每次理时间服从负指数分布，平均每次12分钟。求分钟。求:(1)修理工空闲的概率；修理工空闲的概率；(2)五台机器都出故障的概率；五台机器都出故障的概率；(3)出故障的平均台数；出故障的平均台数；(4)平均停工时间；平均停工时间；(5)平均等待修理时间；平均等待修理时间；(6)评价这个系统的运行情况。评价这个系统的运行情况。解解根据题意，根据题意，m=5，=1/15，=1/12，=/=0.8 多服务台模型多服务台模型M/M/c 标准的标准的M/M/c:/FCFS模型模型系统容量有限的系统容量有限的M/M/c:N/FCFS模型模型有限顾客源的有限顾客源的M/M/c:/m/FCFS模型模型 M/M/c:/FCFS模型模型 服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列顾客到达后，进入队列尾端；当某一个服务台空闲顾客到达后，进入队列尾端；当某一个服务台空闲时，队列中的第一个顾客即到该服务台接收服务；时，队列中的第一个顾客即到该服务台接收服务；服务完毕后随即离去。各服务台互相独立且服务速服务完毕后随即离去。各服务台互相独立且服务速率相同，即率相同，即1=2=c 分析分析系统的服务速率与系统中的顾客数有关。当系统中系统的服务速率与系统中的顾客数有关。当系统中的顾客数的顾客数k不大于服务台个数，即不大于服务台个数，即1kc时，系统中时，系统中的顾客全部在服务台中，这时系统的服务速率为的顾客全部在服务台中，这时系统的服务速率为k；当系统中的顾客数；当系统中的顾客数kc时，服务台中正在接受服时，服务台中正在接受服务的顾客数仍为务的顾客数仍为c个，其余顾客在队列中等待服务，个，其余顾客在队列中等待服务，这时系统的服务速率为这时系统的服务速率为c。则当则当1时系统才不会排成无限长的队列时系统才不会排成无限长的队列 状态转移图与状态转移方程状态转移图与状态转移方程对状态对状态0:P0=P1对状态对状态 1:P0+2P2=(+)P1对状态对状态 c：Pc-1+cPc+1=(+c)Pc对状态对状态n Pn-1+cPn+1=(+c)Pn01cn状态概率状态概率运行指标运行指标 例例某某售售票票处处有有三三个个窗窗口口，顾顾客客到到达达服服从从Poisson流流，到到达达速速率率为为0.9人人分分，售售票票时时间间服服从从负负指指数数分分布布，每每个个窗窗口口的的平平均均售售票票速速率率为为0.4人人分分。顾顾客客到到达达后后排排成一队，依次到空闲窗口购票。求：成一队，依次到空闲窗口购票。求：(1)所有窗口都空闲的概率；所有窗口都空闲的概率；(2)平均队长；平均队长；(3)平均等待时间及逗留时间；平均等待时间及逗留时间；(4)顾客到达后必须等待的概率。顾客到达后必须等待的概率。解解/=2.25，=/c=0.75(1)所有窗口都空闲的概率，即求所有窗口都空闲的概率，即求P0的值的值(2)平均队长，即求平均队长，即求L的值，必须先求的值，必须先求Lq(3)平均等待时间和平均逗留时间，即求平均等待时间和平均逗留时间，即求Wq和和W和的值和的值(4)顾客到达后必须等待，即顾客到达后必须等待，即n3 M/M/c:N/FCFS模型模型 离开离开服务台服务台服务台顾客到达顾客离去顾客离去顾客离去队列分析分析设系统容量为设系统容量为N(Nc)，当系统中的顾数，当系统中的顾数nN时，到时，到达的顾客就进入系统；当达的顾客就进入系统；当n=N时，到达的顾客就被时，到达的顾客就被拒绝。设顾客到达的速率为拒绝。设顾客到达的速率为，m每个服务台服务每个服务台服务的速率为的速率为，=/c。由于系统不会无限止地接。由于系统不会无限止地接纳顾客，对纳顾客，对不必加以限制。不必加以限制。状态转移图与状态转移方程状态转移图与状态转移方程对状态对状态0:P0=P1对状态对状态 1:P0+2P2=(+)P1对状态对状态 c：Pc-1+cPc+1=(+c)Pc对状态对状态N PN-1=cPN 01cN状态概率状态概率运行指标运行指标 例例某某旅旅馆馆有有8个个单单人人房房间间，旅旅客客到到达达服服从从Poisson流流，平平均均速速率率为为6人人天天，旅旅客客平平均均逗逗留留时时间间为为2天，求：天，求：(1)每天客房平均占用数；每天客房平均占用数；(2)旅馆客满的概率。旅馆客满的概率。解解旅馆旅馆8个房间全满的概率为个房间全满的概率为0.423 平均占用客房数为平均占用客房数为6.9间。客房占用率为间。客房占用率为86.6%M/M/c:/m/FCFS模型模型 顾客到达修理速率发生故障等待修理的机器修理速率修理速率正在修理的机器到达速率(m-n)修理速率c运行的机器数 m-n状态概率状态概率 其中其中 运行指标运行指标效效到到达达速速率率e为为单单位位时时间间内内出出现现故故障障的的机器数，有机器数，有e=(m-L)例例车车间间有有5台台机机器器，每每台台机机器器的的故故障障率率为为1次次小小时时，有有2个个修修理理工工负负责责修修理理这这5台台机机器器，工工作作效效率率相相同同，为为4台小时。求：台小时。求：(1)等待修理的平均机器数；等待修理的平均机器数；(2)等待修理及正在修理的平均机器数；等待修理及正在修理的平均机器数；(3)每小时发生故障的平均机器数；每小时发生故障的平均机器数；(4)平均等待修理的时间；平均等待修理的时间；(5)平均停工时间。平均停工时间。解解 可以计算得到（算式略）：可以计算得到（算式略）：P1=0.394，P2=0.197，P3=0.074，P4=0.018，P5=0.002 由此，计算系统的各项运行指标如下：由此，计算系统的各项运行指标如下：排队系统的优化排队系统的优化一般排队系统的总费用构成：一般排队系统的总费用构成：总费用总费用=服务能力费服务能力费+顾客损失费顾客损失费最佳服务能力最佳服务能力服务能力顾客损失费顾客损失费服务能力费服务能力费总费用总费用费用M/M/1:/FCFS模型的模型的单位时间总费用单位时间总费用单位时间单位时间服务成本服务成本单位顾客停单位顾客停留单位时间留单位时间损失成本损失成本M/M/c:/FCFS模型的模型的c