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

* 运筹学 熊中楷教授 * 运筹学 熊中楷教授 排 队 论 第 十一 章：排队论应用 老板开一个香辣螃蟹连锁店，要多少服务员？ 排队论帮助公司进行决策: 第 十 一章：排队论应用 排队过程 服务过程 离开过程 进入的速度和离开的速度决定系统拥挤的程度 而进入的速度取决于服务的速度和服务员人数 服务系统忙闲程度 顾客进入系统的速度 顾客离开系统的速度 到达的顾客 要求服务的内容 服务的机构 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 /FCFS M/M/C/ M/G/1 M：负指数分布 D: 确定型 G：一般服务时间分布 FCFS: 先到先服务 系统容量限制 顾客源数目 服务规则 如先到先服务 ti ti+1 到达间隔时间 第i人服务时间S i 第i人等待时间 Wi 第(i+1)人等待时间Wi+1 等待时间Wi+1 ＝ Max { 0, Wi ＋Si －ti } 第 十一章：排队论应用 第i-1 人服务结束时间 第i-1 人到达时间ti 第i人服务结束时间 1.000 365 合计 0.003 1 10以上 0.005 2 9 0.011 4 8 0.052 19 7 0.071 26 6 0.134 49 5 0.195 71 4 0.203 74 3 0.175 64 2 0.118 43 1 12/365=0.033 12 0 频率 频数（天） 一天中船到达数n 第 十一章：排队论应用 平均到达率＝（全年到达总数）/（365）＝3.48/天 第 十一章：排队论应用 等待时间 顾客编号 到达时间 服务时间 间隔时间 13 3 2 4 47 12 0 2 5 45 11 0 7 2 38 10 0 2 1 36 9 5 10 3 26 8 6 4 3 22 7 5 3 4 19 6 18 10 7 2 12 5 17 2 1 9 11 4 16 6 5 1 6 3 15 3 4 7 2 2 14 0 7 5 0 1 等待时间 间隔时间 服务时间 到达时间 顾客编号 等待时间 间隔时间 服务时间 到达时间 顾客编号 第 十一章：排队论应用