第十一章排队论(运筹学-重庆大学,熊中楷)

运筹学排队论第十一章：排队论应用

老板开一个香辣螃蟹连锁店，要多少服务员？排队论帮助公司进行决策:第十一章：排队论应用

排队过程服务过程离开过程进入的速度和离开的速度决定系统拥挤的程度而进入的速度取决于服务的速度和服务员人数服务系统忙闲程度顾客进入系统的速度顾客离开系统的速度到达的顾客要求服务的内容服务的机构1不能运转的机器修理修理技工2修理工领取修配零件分发修配零件的管理员3病人诊断或者手术医生4电话呼唤通话交换台5文件稿打印打字员6提货单提货仓库保管员7到达机场上空的飞机降落跑道8进入港口的货船装货码头9进入我方阵地的敌机被打我方高炮10

应用范围

第十一章：排队论应用

决策目标：分析系统，系统不能太忙，也不能太空闲决策变量：系统服务员的个数如果系统太忙，则有的顾客将不愿意等待而离开，失去商机如果系统太闲，也不经济引例：服务系统忙闲程度顾客进入系统的速度顾客离开系统的速度第十一章：排队论应用

已知随机服务系统，有三个服务员，平均每分钟到达顾客数约为0.9人，每位顾客的平均服务时间约为2.5分钟。问服务员有多忙？（复旦大学研究生考题）第十一章：排队论应用

第十一章：排队论应用

（复旦大学研究生考题）分析：有三个服务员，平均每分钟到达顾客数约为0.9人，相对于一个服务员来说，平均每分钟到达顾客数约为0.3人每位顾客的平均服务时间约为2.5分钟，每分钟服务顾客人数（1/2.5）即每分钟有（1/2.5）＝0.4人离开系统即每10分钟有3人进来，可以服务4人，因此三名服务员平均75％时间用于为顾客服务，有25％时间空闲服务系统忙闲程度顾客进入系统的速度顾客离开系统的速度1输入过程(1)顾客的数目有限或者无限（2）顾客到达的方式可能是单个的，也可能是成批的这里不考虑成批的情况（3）顾客到达的过程随机的第十一章：排队论应用

2排队过程:（1）顾客有的有耐心，有的没有耐心（2）先到先服务（3）后到先服务（4）随机服务（5）有优先权的服务3服务机构：（1）服务员可能为0，1，2……（2）服务时间随机（3）服务方式可能是单个的，也可能是成批的

排队系统的组成：第十一章：排队论应用

X/Y/Z/A/B/C排队模型的分类:顾客到达间隔时间分布不可控服务时间分布服务台个数决策变量例：M/M/1//m/FCFSM/M/C/M/G/1M：负指数分布D:确定型G：一般服务时间分布FCFS:先到先服务系统容量限制顾客源数目服务规则如先到先服务titi+1到达间隔时间第i人服务时间Si第i人等待时间Wi第(i+1)人等待时间Wi+1等待时间Wi+1＝Max{0,Wi＋Si－ti}第十一章：排队论应用

第i-1人服务结束时间第i-1人到达时间ti第i人服务结束时间一天中船到达数n频数（天）频率01212/365=0.0331430.1182640.1753740.2034710.1955490.1346260.0717190.052840.011920.00510以上10.003合计3651.000第十一章：排队论应用

平均到达率＝（全年到达总数）/（365）＝3.48/天第十一章：排队论应用

顾客编号到达时间服务时间间隔时间等待时间顾客编号到达时间服务时间间隔时间等待时间顾客编号到达时间服务时间间隔时间等待时间10570142274315361561641191217512271018619435722346826310593612010382701145520124742313第十一章：排队论应用

到达间隔次数162103846536272819110以上1合计40服务时间次数1102103745546271819以上1合计41到达时间间隔分布表服务时间分布表P318平均间隔时间＝（最后一个到达时间142）/最人数40＝355分钟/人平均到达率＝41/142＝0.28人/分钟平均服务时间＝127/41＝3.12分钟/人平均服务率＝41/127＝0.32人/分钟服务台平均到达率＝0.28人/分钟平均服务率＝0.32人/分钟服务强度＝0.28/

0.32＝第十一章：排队论应用

标准M/M/1///FCFSp322（1）输入过程：顾客源无限，顾客单个到达，普阿松分布（2）排队规则：单队，队长无限制，先到先服务（3）服务机构：单服务台，服务时间独立，负指数分布服务台平均到达率a平均服务率b服务强度p＝a/

b<1(系统忙的概率)系统空闲概率＝1－服务强度系统状态为n的概率＝（1－服务强度p）（服务强度p）n次方第十一章：排队论应用

一.系统中平均顾客数＝对n求和{（系统中n个顾客）（系统中有n个顾客的概率）}＝（系统忙的概率）/（系统闲的概率）二.系统中等待的平均顾客数＝对n求和{（系统中n－1个顾客）（系统中有n个顾客的概率）}＝（系统忙的概率）的平方/（系统闲的概率）三.系统中顾客逗留时间的期望值＝1/(平均服务率－平均到达率)四系统中顾客等待时间的期望值＝系统中顾客逗留时间的期望值－服务时间＝1/(平均服务率－平均到达率)－1/平均服务率P325排队系统重要参数：第十一章：排队论应用

P326例3第十一章：排队论应用

案例分析：某港口提出四个扩建方案，各个方案装卸能力,各个方案的设备有固定费用C1，（包括工资，设备折旧等）,运行费用C2

（包括燃料，电力等消耗）如下表：M为装卸一艘货船的平均时间

方案A方案B方案C方案D单位装卸一艘货船的平均时间1234小时固定费用C1161051万元/小时运行费用C2114604830万元/小时第十一章：排队论应用

设货船随机达到，平均间隔为6小时，每艘货船在港口停留一小时10万元，求总费用最小的方案解答：总费用=固定费用+运行费用+停留费用时间单位取作小时，则达到率λ＝1/6（单位时间到达船只数）四个方案的服务率分别为µA=1,µB=1/2,µC=1/3,µD=¼（就是单位时间服务船只数，例如B方案每船服务时间2小时，因此B方案单位时间服务船只数1/2）因此服务强度分别为（例如B方案单位时间进1/6,出1/2，忙期：1/3）ρA=1/6ρB=1/3ρC=1/2ρD=2/3根据L=ρ/(1-ρ)港口停留的货轮平均数分别为：LA=1/5LB=1/2LC=1LD=2计算费用如下表：第十一章：排队论应用

方案固定费用C1ρ运行费ρC2L停留费10L总费用A161/61/6×114=191/5237B101/31/3×60=201/2535C51/21/2×48=2411039D12/32/3×30=2022041因此方案B费用最少

第十一章：排队论应用

例：M/M/1排队系统费用分析。某港口提出四个扩建方案，各个方案装卸能力,各个方案的设备有固定费用C1，（包括工资，设备折旧等）,运行费用C2（包括燃料，电力等消耗）如下表：M为装卸一艘货船的平均时间

方案A方案B方案C方案D单位平均时间M1234小时固定费用C1161051万元/小时运行费用C2114604830万元/小时设货船达到服从普阿松分布，平均间隔为6小时，每艘货船在港口停留一小时10万元，求总费用最小的方案第十一章：排队论应用

解:总费用=固定费用+运行费用+停留费用时间单位取作小时，则达到率λ＝1/6四个方案的服务率分别为µA=1,µB=1/2,µC=1/3,µD=1/4因此服务强度分别为ρA=1/6ρB=1/3ρC=1/2ρD=2/3根据L=ρ/(1-ρ)港口停留的货轮平均数分别为：LA