管理运筹学第12章排序与统筹方法课件.ppt

第十二章排序与统筹方法 1车间作业计划模型 2统筹方法 在本章中 我们将介绍车间作业计划模型和统筹方法 这两个问题尽管处理的方法有所不同 但当我们面临必须完成若干项不能同时进行的工作时 它们都将帮助我们应该按照怎样的次序 怎样的时间表来做这些工作 使得效果最佳 例如完成全部工作所用时间最短或费用最少等等 1 PPT学习交流 1车间作业计划模型 车间作业计划是指一个工厂生产工序的计划和安排 一 一台机器 n个零件的排序问题二 两台机器 n个零件的排序问题 2 PPT学习交流 1车间作业计划模型 一 一台机器 n个零件的排序问题例1 某车间只有一台高精度的磨床 常常出现很多零件同时要求这台磨床加工的情况 现有六个零件同时要求加工 这六个零件加工所需时间如下表所示 应该按照什么样的加工顺序来加工这六个零件 才能使得这六个零件在车间里停留的平均时间为最少 3 PPT学习交流 1车间作业计划模型 解 如果我们用Pi表示安排在第i位加工的零件所需的时间 用Tj表示安排在第j位加工的零件在车间里总的停留时间 则有不同的加工顺序得到不同的各零件的平均停留时间 如何得到一个使得各零件的平均停留时间最少的排序呢 这就是我们最后要解决的优化问题 而且我们要设法找到一种简便的算法 对于某种加工顺序 我们知道安排在第j位加工的零件在车间里总的停留时间 可知这六个零件的停留时间为 那么各个零件平均停留时间为从上式可知 对于一台机器n个零件的排序问题 只要系数越大 配上加工时间越少的 即按照加工时间排出加工顺序 加工时间越少的零件排在越前面 加工时间越多的零件排在越后面 可使各个零件的平均停留时间为最少 也就是按照3 4 5 6 1 2的顺序来加工零件 可使各个零件的平均停留时间为最少 4 PPT学习交流 1车间作业计划模型 按照3 4 5 6 1 2的顺序来加工零件 各个零件的停留时间如表12 4所示 各个零件的平均停留时间为这与用 先到先加工 顺序所需平均停留时间4 93相比较 有很大的进步 对于一台机器n个零件的排序问题 我们按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少 表12 4 5 PPT学习交流 1车间作业计划模型 二 两台机器 n个零件例2 某工厂根据合同定做一些零件 这些零件要求先在车床上车削 然后再在磨床上加工 每台机器上各零件加工时间如表12 5所示 表12 5应该如何安排这五个零件的先后顺序才能使完成这五个零件的总的加工时间为最少 解 由于每个零件必须先进行车床加工 再进行磨床加工 所以在车床上加工零件的顺序与在磨床上加工零件的顺序是一样的 如果这些零件在车床上和磨床上加工顺序都为1 2 3 4 5 我们用图12 1中的线条图来表示各零件加工的开始时间与完成时间 这种图是由一根时间轴和车床 磨床在每个时间段的状况的图形所构成 6 PPT学习交流 1车间作业计划模型 图12 1从上图中我们可以看出 加工时间的延长主要是由于磨床的停工待料造成的 只要减少磨床的停工待料的时间就能减少整个加工任务的总时间 为了减少磨床的停工待料 我们应该一方面把在车床上加工时间越短的零件越早加工 减少磨床等待的时间 另一方面把在磨床上加工时间越短的零件越晚加工 以便充分利用前面的时间 这样我们就得到了使完成全部零件加工任务所需总时间最少的零件排序方法 7 PPT学习交流 1车间作业计划模型 寻找例2的最优解 我们在表12 5中找到所列出的最短加工时间是0 25 它是第二道工序磨床加工零件2的所需时间 由于这个时间与磨床有关 故我们把零件2放在加工顺序的末尾 即第五位 并在表中划去零件2所在行 如表12 6中红色线条所示 接着 我们又找到最短加工时间为0 5 这一时间与磨床 第二工序 有关 我们把磨床加工时间为0 5的零件1放到除第五外的加工顺序的末尾 即第四位加工 同时把表中的零件1所在的行划去 如表12 6中黄色线条所示 下一个最短加工时间为0 75 这个加工时间是车床 第一工序 加工零件5的所需时间 故把零件5排在加工顺序的第一位上 同时把表中的零件5所在的行划去 如表12 6中蓝色线条所示 表12 6 8 PPT学习交流 同样 下一个最短加工时间为1 这是车床加工零件3的所需时间 故把零件3排在第二位上 同时把零件3所在的行划去 如表12 6中黑色线条所示 这样就得到了最优加工顺序 5 3 4 1 2 一共只需7个小时就能完成全部加工 从例2中我们可以归纳出关于两台机器n个零件的排序问题 使得全部任务总的时间最短的排序算法 在加工所需时间表上选出最短加工时间tij 这是第i工序加工j零件所需时间 当i 1时 将零件j的顺序尽量靠前 若i 2时 将零件j的顺序尽量靠后 在表上划去零件j的所在行 回到步骤1 1车间作业计划模型 9 PPT学习交流 2统筹方法 统筹方法包括绘制计划网络图 进度安排 网络优化等环节 下面进行分别讨论 一 计划网络图统筹方法的第一步工作就是绘制计划网络图 也就是将工序 或称为活动 进度表转换为统筹方法的网络图 例3 某公司研制新产品的部分工序与所需时间以及它们之间的相互关系都显示在其工序进度表如表12 8所示 请画出其统筹方法网络图 表12 8 10 PPT学习交流 2统筹方法 解 用网络图表示上述的工序进度表网络图中的点表示一个事件 是一个或若干个工序的开始或结束 是相邻工序在时间上的分界点 点用圆圈表示 圆圈里的数字表示点的编号 弧表示一个工序 或活动 弧的方向是从工序开始指向工序的结束 弧上是各工序的代号 下面标以完成此工序所需的时间 或资源 等数据 即对此弧所赋的权数 a b c d e 60 13 8 38 15 图12 4 11 PPT学习交流 2统筹方法 例 把例 的工序进度表做一些扩充 如表12 9 请画出其统筹方法的网络图 表12 9 12 PPT学习交流 2统筹方法 解 我们把工序 扩充到图12 4发生了问题 由于 是 的紧前工序 故 的结束应该是 的开始 所以代表 的弧的起点应该是 由于工序 的结束也是 所以工序 也成了工序 的紧前工序 与题意不符 为此我们设立虚工序 虚工序是实际上并不存在而虚设的工序 用来表示相邻工序的衔接关系 不需要人力 物力等资源与时间 1 5 2 6 4 3 a 60 b 15 8 e 10 13 d c 38 f 图12 5 13 PPT学习交流 2统筹方法 在网络图上添加 工序得网络图12 6 在统筹方法的网络图中不允许两个点之间多于一条弧 因此增加了一个点和虚工序如图12 7 1 2 5 6 7 3 4 a 60 15 b e c 13 d 38 8 h 5 10 f g 16 图12 6 14 PPT学习交流 2统筹方法 在绘制统筹方法的网络图时 要注意图中不能有缺口和回路 1 2 5 7 8 3 4 a 60 15 b e c 13 d 38 8 h 5 10 f 6 16 g 图12 7 0 0 15 PPT学习交流 2统筹方法 二 网络时间与关键路线在绘制出网络图之后 我们可以由网络图求出 1 完成此工程项目所需的最少时间 2 每个工序的开始时间与结束时间 3 关键路线及其相应的关键工序 4 非关键工序在不影响工程的完成时间的前提下 其开始时间与结束时间可以推迟多久 例5 某公司装配一条新的生产线 具体过程如表12 10 求 完成此工程的最少时间 关键路线及相应的关键工序 各工序的最早开始时间及结束时间和非关键工序在不影响工程完成时间的前提下 其开始时间与结束时间可以推迟多久 16 PPT学习交流 2统筹方法 表12 10 17 PPT学习交流 2统筹方法 解 据表12 10 绘制网络图如图12 8 图12 8如图12 8 就是一条关键路线 我们要干完所有的工序就必须走完所有这样的路线 由于很多工序可以同时进行 所以网络中最长的路线就决定了完成整个工程所需的最少时间 这条路线称为关键路线 1 2 3 4 6 7 8 5 a 60 b 45 e c h j 35 i g 10 30 d 20 40 25 f 18 15 18 PPT学习交流 2统筹方法 下面我们给出找关键路线的办法首先 从网络的发点开始 按顺序计算出每个工序的最早开始时间 ES 和最早结束时间 EF 设一个工序所需的时间为t 这对于同一个工序来说 有EF ES t 工序a的最早开始时间 工序a的最早完成时间 1 2 a 0 60 60 图12 9 19 PPT学习交流 2统筹方法 图12 10其次 从网络的收点开始计算出在不影响整个工程最早结束时间的情况下各个工序的最晚开始时间 缩写为LS 和最晚结束时间 缩写为LF 显然对同一工序LS LF t 1 2 3 6 7 8 5 a 0 60 60 b 60 105 45 e 60 100 c 60 70 h 100 115 j 135 170 35 i 110 135 g 80 110 30 d 60 80 20 40 25 f 70 88 18 4 10 15 20 PPT学习交流 2统筹方法 运用此法则 可以从首点开始计算出每个工序的LF与LS 如图12 11所示 图12 11接着 可以计算出每一个工序的时差 把在不影响工程最早结束时间的条件下 工序最早开始 或结束 的时间可以推迟的时间 称为该工序的时差 对每个工序来说其时差记为Ts有Ts LS ES LF EF 1 2 3 6 7 8 5 a 0 60 60 0 60 b 60 105 45 90 135 e 60 100 c 60 70 h 100 115 j 135 170 35 135 170 i 110 135 g 80 110 30 80 110 d 60 80 20 60 80 40 80 120 25 110 135 f 70 88 18 117 135 4 10 107 117 15 120 135 21 PPT学习交流 2统筹方法 最后将各工序的时差 以及其他信息构成工序时间表如表12 11所示 表12 11这样就找到了一条由关键工序a d g i和j依次连成的从发点到收点的关键路线 22 PPT学习交流 三 完成工序所需时间不确定时的网络时间和关键路线当完成工序所需时间不确定的情况下怎样求网络时间和关键路线呢 下面我们结合案例介绍求解办法 例6 长征研究院培训中心负责明年春天的各干部的工商管理培训 培训中心列出有关培训组织的各项活动的信息如表12 12所示 要求绘制出统筹方法的网络图 设法求出网络时间和关键路线 并确定开始这个组织工作的时间以保证培训工作如期举行 解 由表12 12 绘出统筹方法的网络图如图12 12所示 图12 12 2统筹方法 23 PPT学习交流 2统筹方法 表12 12 24 PPT学习交流 2统筹方法 由于是第一次搞培训 缺乏经验和有关统计资料来确定完成每个活动所需时间 但对所需时间做了三种估计 1 乐观时间 指在顺利情况下 完成活动所需最少时间 用a表示 2 最可能时间 指在正常情况下 完成活动所需时间 用m表示 3 悲观时间 指不顺利情况下 完成活动所需最多时间 用b表示 如表12 13所示 25 PPT学习交流 表12 13单位 周 26 PPT学习交流 2统筹方法 显然这三种完成活动所需时间都具有一定概率 由经验 我们可以可以假定这些时间的概率分布近似服从分布 我们可以用如下公式计算出完成活动所需的平均时间 以及方差例如 完成活动g所需平均时间 同时求出方差为 27 PPT学习交流 2统筹方法 同样可以求出每个活动的完成所需平均时间及方差 如表12 14 表12 14 28 PPT学习交流 2统筹方法 下面就用平均时间代替完成活动所需时间 并在网络图上标上每个活动最早开始时间和最早结束时间 如图12 14所示 1 2 3 4 5 8 7 6 a 0 2 g 5 9 b 2 5 e 5 6 d 2 4 f 6 8 c 0 2 i 13 15 h 9 13 3 2 2 2 1 4 2 4 2 图12 14 29 PPT学习交流 同样也可以标上最晚开始时间和最晚完成时间等 1 2 3 4 5 8 7 6 a 0 2 g 5 9 b 2 5 e 5 6 d 2 4 f 6 8 c 0 2 i 13 15 h 9 13 2 1 3 1 10 11 4 5 9 4 9 13 2 3 5 2 0 2 3 2 5 2 13 15 2 11 13 图12 15 30 PPT学习交流 表12 15 31 PPT学习交流 2统筹方法 从表12 15上我们找到了一条从发点到收点由关键工序a b g h i组成的关键路线 用双线标出来 则完成培训工作所需的平均时间为各关键路线的时间之和 2 3 4 4 2 15 周 同时完成时间近似服从一定的概率分布正态分布 则均值为关键路线上各关键活动之均值之和15 方差也为关键路线上各关键活动方差之和1 05 由此我们可以计算出此项培训组织工作不同完工时间的概率 如16周内完工的概率 为求此概率 可以先求值 式中的T为预定完工时间16 E T 15 算得 0 976 查正态分布函数表可知概率为 即在16周内完工的概率为83 55 32 PPT学习交流 2统筹方法 其正态分布图如图12 16所示 如果我们要求以99 的概率来保证培训组织工作如期做完 使培训工作如期举行 也就是说 概率为99 的完工时间应为多少周 在标准正态分布函数表中可查出的值为2 33 从公式得T 17 39 周 也就是说只要在培训工作前17 39周开始做培训组织工作就能保证培训工作如期举行 16 图12 16 15 33 PPT学习交流 2统筹方法 四 网络优化得到初始的计划方案 但通常要对初始方案进行调整与完善 根据计划目标 综合考虑进度 资源和降低成本等目标 进行网络优化 确定最优的计划方案 1 时间 资源优化做法 1 优先安排关键工序所需的资源 2 利用非关键工序的时差 错开各工序的开始时间 拉平资源需要量的高峰 3 统筹兼顾工程进度的要求和现有资源的限制 往往要经过多次综合平衡 才能得到比较合理的计划方案 下面列举一个拉平资源需要量最高峰的实例 在例5中 若机械加工工人人数为65人 并假定这些工人可完成这5个工序任一个 下面来寻求一个时间 资源最优方案 如表12 16所示 34 PPT学习交流 2统筹方法 表12 16 若上述工序都按最早开始时间安排 那么从第60天至第135天的75天里 所需的机械加工工人人数如图12 17所示 35 PPT学习交流 2统筹方法 在图的上半部中 工序代号后的数字是所需机械加工工人数 点划线下面的数字是非关键工序时差长度 图的下半部表示从第60天至135天内的75天里 所需机械加工工人数 这样的图称为资源负荷图 2 7 4 6 3 5 f 22人 18 h 39人 15 58人 64人 80人 81人 42人 65人 60708090100110120130 d 58人 i 26人 g 42人 30 20 25 图12 17 26人 65人 工人数 时间 天 36 PPT学习交流 2统筹方法 同时我们应优先安排关键工序所需的工人 再利用非关键工序的时差 错开各工序的开始时间 从而拉平工人需要量的高峰 经过调整 我们让非关键工序f从第80天开始 工序h从第110天开始 找到了时间 资源优化的方案 如图12 18所示 在不增加工人的情况下保证了工程按期完成 2 4 6 7 5 3 f 22人 h 39人 d 58人 i 26人 g 42人 工人数 65人 60708090100110120130 58人 42人 64人 26人 65人 图12 18 时间 天 37 PPT学习交流 2统筹方法 2 时间 费用优化需要考虑时间与费用的问题 在既定的时间前工程完工的前提下 使得所需的费用最少 或者在不超工程预算的条件下使工程最早完工 这些是时间 费用优化要研究和解决的问题 直接费用 为了加快工程进度 需要增加人力 设备和工作班次 这需要增加一笔费用 成为直接费用 间接费用 由于工程早日完工 减少了管理人员的工资办公费等费用称为间接费用 一般说工序作业时间越短 直接费用越多 间接费用越少 38 PPT学习交流 2统筹方法 缩短工序的作业时间有一定的限度 这个限度称为工序的最快完成时间 我们设完成工序j的正常所需时间为Tj 直接费用为cj 完成工序j的最快完成时间为T j 直接费用为c j 这样我们可以计算出缩短工序j的一天工期所增加的直接费用 用kj表示 称为直接费用变动率 有时间 费用优化问题可建立两个线性规划模型 模型一 在既定的时间T完工的前提下 问各工序的完成时间为多少才使因缩短工期而增加的直接费用最少 设工序 i j 的提前完工时间为yij 我们用Tij T ij分别表示正常完工时间与最快完工的时间 则有工序 i j 的实际完工时间为 Tij yij 我们用cij c ij表示用正常完工时间和最快完成时间完成工序所需要的费用 kij为工序 i j 的直接费用变动率 得到这个问题的线性规划模型如下 minf kij yij i j s t xj xi Tij yij 对一切弧 i j yij Tij T ij 对一切弧 i j xn x1 T xi 0 yij 0 39 PPT学习交流 2统筹方法 例7 例5所提供的信息都作为本例的信息 另外还给出了在装配过程中各道工序所需正常完工时间与最快完工时间 以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用 如表12 17所示 40 PPT学习交流 表12 17 缩短一天工期增加的直接费用 费用变动率元 天 41 PPT学习交流 2统筹方法 该工程要求在150天内完工 问每个工序应比正常完工时间提前多少天完成 才能使整个工程因缩短工期而增加的直接费用为最少 如果工期要求在140天完工呢 1 2 3 4 5 6 7 8 a b f e c h g i j d 图12 19 42 PPT学习交流 2统筹方法 解 网络图如图12 19所示 根据此网络图建立数学模型 设此网络图上第i点发生的时间为xi 工序提前完工的时间为yij 目标函数minf 120y27 300y23 400y24 500y25 230y37 350y46 400y57 290y67 s t x2 x1 60 y12x7 x2 45 y27x3 x2 10 y23x4 x2 20 y24x5 x2 40 y25x7 x3 18 y37x6 x4 30 y46x5 x4 0 虚拟弧 4 5 x7 x5 15 y57x7 x6 25 y67x8 x7 35 y78 43 PPT学习交流 2统筹方法 x1 0 y12 0 y27 15 y23 5y24 10y25 5y37 8y46 10y57 5y67 10y78 0 x8 150 xi 0 yij 0 对一切可能的ij 44 PPT学习交流 用 管理运筹学 软件进行计算 很快得到以下结果 也就是说我们缩短工序g和工序i的10天工期 我们可以付出最少的直接费用6400元 提前20天即在150天里完成整个工程 45 PPT学习交流 如果工期要求在140天里完成 那么我们只要在上述的线性规划的模型里把约束条件中的最后一个 x8 150 改为x8 140 其余一切不变 用 管理运筹学软件 运算 得到如下结果 为了使工程在140天里完成 我们至少要付出14900元的直接费用 各工序的开始时间和缩短的工期如解所示 46 PPT学习交流 对于例7这样的问题我们也可以用统筹法予以解决 若要求我们在150天里完成工程 缩短了正常工期的20天 我们在关键路线上 找出直接费用变动率最低的关键工序 最大限度的缩短其完成的时间 从表12 17上可知关键工序a d g i j中 工序i的直接费用变动率最低 其次是工序g 已知这两个工序都至多只能缩短10天 这样我们就缩短工序i和g各10天时间 而不需要缩短其他工序就能保证150天里完成工程 为缩短这20天工期的付出的最少的直接费用为6400