网络计划(运筹学)9.ppt

* 下面列举一个拉平资源需要量高峰的实例．在前例中，若完成工序d，f，g，h，i的机械加工工人人数为65人，并假定这些工人可以完成这五个工序中的任一个工序，下面我们来寻求一个时间－资源优化方案． 有关d，f，g，h，i工序所需的工人人数及上述工序开始时间，所需时间及时差如下表所示． * 若上述各工序都按最早开始时间安排，那么从第60天至第135天的75天里，所需的机械加工工人的人数如下图所示． 从图可见，在第70－80天和第100－110天这两段时间，需要工人数达到80与81人，远超过了现有工人人数。 另一方面在第90－100天和第115－135天所需工人数仅有42人和26人，远远少于现有工人数 这种安排的资源负荷是不均匀的，不妥当的。 * 我们应该优先安排关键工序所需的工人，再利用非关键工序的时差，错开各工序的开始时间，从而拉平工人需要量的高峰． 经过调整，我们让非关键工序f从第80天开始，工序h从第110天开始．找到了时间-资源优化的方案. 如下图所示，在不增加工人的情况下保证了工程按期完成． 开始时间 70?80 开始时间 100?100 * 2，时间－费用优化问题 在编制网络计划时，我们要考虑这样一些时间与费用的问题：在既定的时间前工程完工的前提下，使得所需要的费用最少，或者在不超过工程预算的条件下，使得工程最早完工．这些就是时间—费用优化要研究和解决的问题． 加快工程进度的一个关键概念是应急处理。应急完成工序是指通过某些高费用的途径（如加班，雇佣临时工，使用特殊设备或材料等），把工序的完成时间减少到正常水平之下。 应急 正常 * 时间－费用的优化问题可以化为线性模型来求解 规划问题：若考虑工程项目的成本，包括应急费用，那么问题是在项目工期小于或等于项目管理者期望水平的限制条件下，使得总成本最小化。 决策： （1）每项工序的开始时间 （2） 进行应急处理后每项工序的工期减少量 （3）项目的期望完成时间。 * 设xi为工序i的最早完成时间，yi为工序i的应急时间。假定工程开始时间为0，则对于工序1，有x1?t1-y1，即x1+y1?t1，其中t1为工序1的正常完成时间。 对其他紧相邻工序i和j，有xj-xi ?tj-yj，即xj+yj-xi ?tj。其中tj为工序j的正常完成时间 则线性规划模型为 其中si为工序i的成本斜率，Ci为工序i说允许的最大应急时间，T为工程要求的完成时间。 * 举例： 继续前面的例子，下表给出了在装配过程中各道工序所需正常完工时间与最快完工时间，以及对应正常完工时间与最快完工时间的所需的直接费用和每缩短一天工期所需增加的直接费用。 该工程要求在150天内完工，问每个工序应比正常完工时间提前多少天完成，才能使整个工程因缩短工期而增加的直接费用为最少。 * * 设此网络图上第i点发生的时间为xi，工序(i，j)提前完工的时间为yij，则 * * 结果： 我们缩短工序g的10天工期，缩短工序i的10天工期，这样我们可以多付出最少的直接费用6400元，提前20天即在150天里完成整个工程 * 对于该问题我们也可以用PERT图求解。在绘制了计划网络图、计算了工序的时间、找出关键路线之后，由于要求我们在150天里完成工程，缩短了正常工期的20天时间。我们在关键路线上，找出直接费用变动率最低的关键工序，最大限度的缩短其完成时间．从前表上可知其关键工序a,d,g,i,j中，工序i的直接费用变动率最低，其次是工序g。已知这两个工序都至多只能缩短10天，这样我们就缩短工序i和g各10天时间，而不需经缩短其他的关键工序和非关键工序就能保证在150天完成整个工程。为缩短这20天的工期付出的最少的直接费用为290x10＋350x10＝6400。这个答案是和线性规划的答案一样的。 * * 工序延续时间估计 经验法与专家法（平均值）：适用于重复性工作，不确定性因素少 三点估计法（又称六分法） 其中a—对工序e延续时间的最乐观时间（在顺利情况下工序e完成的最短可能时间） b—对工序e延续时间的最悲观时间（最不顺利下工序e完成的最长可能时间） M—对工序e延续时间的最可能时间（在正常情况下工序e完成耗费的时间） * * 三点估计法 这是由于通常认为工序延续时间 * * 随机性网络时间参数与关键路线 问题与求解 例 (培训计划制订) 序号 工序 紧前工序 乐观时间ai 最可能时间mi 悲观时间bi 1 a -- 1.5 2.0 2.5 2 0.028 2 b a 2.0 2.5 6.0 3 0.445 3 c -- 1.0 2.0 3.0 2 0.111 4 d c 1.5 2.0 2.5 2 0.028 5 e b, d