十一章 排序与统筹.ppt

十一章排序与统筹 p234 1 车间作业计划模型一 一台机器 几个零件的排序问题例1应该按照什么样的加工顺序来加工零件 使所有零件在车间停留的平均时间最少 设第j次加工零件在车间停留的时间为Tj 第i次加工零件的加工时间Pi 择有Tj P1 P2 Pj 1 Pj所有零件在车间停留的平均时间为T1 T2 T3 T4 T5 T6 P1 P1 P2 P1 P2 P3 P1 P2 P3 P4 P1 P2 P3 P4 P5 P1 P2 P3 P4 P5 P6 6P1 5P2 4P3 3P4 2P5 P6 两台机器 n个零件例2 2 统筹方法一计划网络图 p241 例3 1 2 3 4 5 a b c d e 60 15 13 38 8 例4 p242 1 2 3 5 6 a b c d e 60 15 13 38 8 4 10 f 习题4 1 3 4 6 7 a c d e b 5 g f 2 二 网络时间与关键路线在绘制出网络图后 我们可以根据网络图求出 1 完成此工程项目所需的最少时间 2 每个工序的开始时间与结束时间 3 关键路线及其相应的关键工序 4 非关键工序在不影响工程进度的前提下 其开始时间与机务时间可以推迟多久 例5 1 2 8 4 6 a c d e b 5 g f 7 3 45 18 10 60 20 40 h i j 30 25 35 15 路线 在网络图上从出发点开始 沿着弧的方向连续地到达收点的一条路 关键路线 网络图中最长的路线 1 2 7 8 1 2 3 7 8 1 2 5 7 8 1 2 4 6 7 8 长度 140 长度 123 长度 150 长度 170 寻找关键路线的方法用ES表示一个工序最早开工时间 用EF表示一个工序最早完工时间 用t表示一个工序所需时间 我们有EF ES t用 ES EF 放在工序的上面来记录一个工序的最早开工时间和最早完工时间 1 2 8 4 6 a c d e b 5 g f 7 3 45 18 10 60 20 40 h i j 30 25 35 15 0 60 60 105 135 170 110 135 80 110 60 80 70 88 60 100 60 70 100 115 用LS表示一个工序最晚开工时间 用LF表示一个工序最晚完工时间 用 LS LF 放在工序的下面来记录一个工序的最晚开工时间和最晚完工时间 1 2 8 4 6 a c d e b 5 g f 7 3 45 18 10 60 20 40 h i j 30 25 35 15 0 60 60 105 135 170 110 135 80 110 60 80 70 88 60 100 60 70 100 115 107 117 90 135 117 135 135 170 110 135 80 110 60 80 0 60 80 120 120 135 用Ts表示工序的时差Ts LS ES LF EF如 对于B工序 Ts 90 60 30对关键路线上的所有工序 其时差都为零 例5 1 3 2 5 6 a c d e b 4 g f 2 5 2 4 4 3 4 关键路线最早完工时间12天最晚开工时间和完工时间 1 3 2 5 6 a c d e b 4 g f 2 5 2 4 4 3 4 0 2 4 9 0 4 4 7 4 8 8 12 9 11 1 2 3 4 6 1 3 2 5 6 a c d e b 4 g f 2 5 2 4 3 4 0 2 4 9 0 4 4 7 4 8 8 12 9 11 8 12 4 8 10 12 5 10 2 4 5 8 0 4 4 网络优化1 时间 资源优化为了使工程进度与资源利用都得到比较合理安排 可采取以下的做法 1 优先安排关键工序所需要的资源 2 利用非关键工序曲时差 错开各工序的开始时间 拉平资源需要量的高峰 3 要统筹兼顾工程进度的要求和现有资源的限制 往往要经过多次综合平衡 才能得到比较合理的计划方案 工人人数65 3 4 7 f g d 6 i 2 18 20 30 25 58人 22人 42人 26人 39人 15 5 h 2 时间 费用优化在既定时间完成工程的前提下 使得费用最少 或者在不超过工程预算的条件下 使得工程最早完工 缩短工序的作业时间的限度称为工序的最快完成时间 设完成工序j的正常所需时间为Tj 直接费用为cj 最快完成时间为 直接费用为 缩短工序一天工期所减少的直接费用 我们用kj表示 有kj 模型一设网络图上点i发生的时间为xi T表示既定的时间 对一个工序 我们既可以用工序的代号来表示 也可以用表示这个工序的弧 i j 来表示 设工序 i j