运筹说 第89期｜网络计划-网络计划的优化

通过画网络图并计算时间参数，我们已得到了一个初步的网络计划，而网络计划技术的核心却在于从工期、成本、资源等方面对这个初步方案做进一步的改善和调整，以求得最佳效果，这一过程，就是网络计划的优化。接下来让我们跟随小编的脚步，学习网络计划优化的相关知识吧。

一、引言

衡量一个计划的优劣，本应从工期、成本、资源消耗等方面综合评价，但是目前还没有一个能全面反映这些指标的综合数学模型，一般只是按照某一个或两个指标来衡量计划的优劣，不问的优化目标有不问的优化方法，接下来小编将举例说介绍几种优化的方法

二、改变串联工作

让我们首先学习第一种网络计划优化的方法，把串联工作改为平行工作或交叉工作。

1、方法论

为了缩短整个任务的完工期，达到时间优化的目标，可以研究关键路线上串联的每一项工作有无可能改为平行工作或交叉进行的工作，以缩短工期。

2、例题展示

例题1：

如下图所示，原计划市场调研需12天（图a），如增加人力改为三组同时进行，则只需4天即可（图b）。

例题2：

又如下图所示之例，挖沟工作A需9天，埋管子工作B需6天，串联工作需时15天，而变为三段交叉工作，只需11天。这种方法虽然简单，但是行之有效。

三、利用时差

第二种优化方法是利用时差来优化工作时长。由于网络图中的非关键路工作都有时差，所以这些工作在开工时间上，具体工时上都具有一定的弹性。为了缩短任务的总工期，可以考虑放慢非关键工作的进度，减少这些工作的人力、资源，转去支援关键工作，以使关键工作的工时缩短来达到目的。

四、有限资源的合理分配

第三种优化方法为通过有限资源的合理分配来调整工期，使得工期最短。

1、方法论

一项任务的可用资源，一般情况下总是有限的，因此时间计划必须考虑资源问题，考虑如何在有限资源情况下使工期最短。

调整的基本原则是：

（1）尽量保证关键工作的日资源需求量。

（2）利用非关键工作的时差错开各工作的使用资源时间。

（3）在技术章程允许条件下，可适当延长时差大的工作的工时，或切断某些非关键工作，以减少日总需求量。

具体方法是按资源的日需求量所划分的时间段逐步从始点向终点进行调整。

2、例题展示

以人力资源为例，下图所示的网络图，已计算出关键路线为：①→②→③→⑤→⑥，总工期为11天。箭杆上△中标注数字为工作每天所需人力数（假设所有工作都需要同一种专业工人）。

画出带日程的网络图及资源动态曲线，如下图（图中虚线为非关键工作的总时差）。

由图可见，若按每道工作的最早开工时间安排，人力需求很不均匀，最多者为20人/日，最少为1人/日，这种安排即使在人力资源充足条件下也是很不经济的。现假设资源有限，每日可用人力为10人。下面进行计划调整，希望能不延迟总工期或尽量少延迟。

本例中，第一个时间段为[0，2]，需求量为18人/日，在调整时要对本时间段内各工作按总时差的递增顺序排队编号，如：

工作（1，2），总时差0，编为1#

工作（1，4），总时差1，编为2#

工作（1，6），总时差7，编为3#

对编号小的优先满足资源需求量，当累计和超过10人时，未得到人力安排的工作应移入下一时间段，本例中工作（1，2）与（1，4）人力日需求量为9，而工作（1，6）需9人/日，所以应把（1，6）移出[0，2]间段后开工，见下图。

接着调整[2，3]间段。在编号时要注意，如果已进行的非关键工作不允许中断，则编号要优先考虑，把它们按照新的总时差与最早开始时间之和的递增顺序排列，否则同第一段的编号规则。

本例中（1，4）为已进行中工作，假设不允许中断。而（2，3）为关键工作，（1，6）还有时差5天，则编号顺序为：

工作（1，4），总时差1，编为1#

工作（2，3），总时差0，编为2#

工作（1，6），总时差5，编为3#

累加所需人力资源数，工作（1，4）与（2，3）共需10人/日，所以工作（1，6）要移出[2，3]时间段，调整结果见下图。

以后各时间段类似处理，经过几次调整，可得下图。此时人力日需求量已满足不超过10人的限制，总工期未受影响，必要时总工期可能会延迟。这种方法也可用于多种资源分配问题。

需要说明的是，由于编号及调整规则只是一种原则，所以调整结果常常是较好方案，不一定是工期最短方案。由于求精确解有时很繁难，网络优化中多采用这类近似算法。

五、最低成本日程

1、方法论

项目或任务的成本一般包括直接费用和间接费用两部分。

直接费用是完成各项工作直接所需人力、资源、设备等费用，为缩短工作的作业时间，需采用一些技术组织措施，相应会增加一些费用，在一定范围内，工作的作业时间越短，直接费用越大。

间接费用则包括管理费、办公费等，常按任务期长短分摊，在一定条件下，工期越长，间接费用越大。它们与工期的关系如下图所示。

工期缩短时直接费用要增加而间接费用减少，总成本是由直接费用与间接费用相加而得。通过计算网络计划的不同完工期相应的总费用，以求得成本最低的日程安排就是“最低成本日程”，又称“工期一成本”优化。

直接费用与工作所需工时关系，常假定为直线关系，如下图所示。工作（i，j）的正常工时为Dij，所需费用Mij，特急工时为dij，所需费用mij，工作（i，j）从正常工时每缩短一个单位时间所需增加的费用称为成本斜率，用cij表示。

 如某工作正常工时为5天，费用600元；按特急工时3天进行所需费用为900元，则

(元/天)，即每缩短一天需增加费用150元。接下来我们通过一个简例说明最低成本日程的计算方法。

2、例题展示

已知网络计划各工作的正常工时、特急工时及相应直接费用如下表，网络图如下图所示。

按正常工时从图中计算出总工期为74天。关键路线为①→③→④→⑥，由上表可计算出正常工时情况下总直接费用为47800元。

设正常工时下，任务总间接费用为18000元，工期每缩短一天，间接费用可节省330元，求最低成本日程。

解：以上图所示的原始网络为基础，计算按下列步骤进行：

（1）从关键工作中选出缩短工时所需直接费用最少的方案，并确定该方案可能缩短的天数。

（2）按照工作的新工时，重新计算网络计划的关键路线及关键工作。

（3）计算由于缩短工时所增加的直接费用。

不断重复上述三个步骤，直到工期不能再缩短为止。

第一次调整：

从上图看出，关键路线上的三道关键工作（1，3），（3，4），（4，6）中，工作（1，3）的成本斜率最小（100），应选择在工作（1，3）上缩短工时，查上表知，最多可缩短12天，即取工作（1，3）新工时为30－12=18（天）。重新计算网络图时间参数结果如下图(a)所示，关键路线为①→②→④→⑥，工期为64天，实际只缩短了10天。这意味着（1，3）工作没有必要减少12天，（1，3）工时应取30-10=20（天）。重新计算，结果如下图(b)，总工期为64天，有两条关键路线：①→②→④→⑥与①→③→④→⑥，此次调整增加直接费用10×100＝1000（元）。

第二次调整：

重复步骤(1)，(2)，(3)，必须注意两条关键路线应同时缩短。有如下几个方案可选择：

（1）在（1，3）与（1，2）上同时缩短一天，需费用100+250＝350（元）；

（2）在（1，3）与（1，2）上同时缩短一天，需费用100+200＝300（元）；

（3）在（3，4）与（1，2）上同时缩短一天，需费用150+250＝400（元）；

（4）在（3，4）与（2，4）上同时缩短一天，需费用150+200=350（元）；

取费用最小方案为方案（2），（1，3）最多可缩短2天，（2，4）可缩短4天，取其中小者，即将（1，3）与（2，4）的工时分别改为20－2＝18（天），22－2＝20（天）。

重新计算网络图时间参数，结果见下图（a）。总工期为62天，这时关键路线仍为2条：①→②→④→⑥与①→③→④→⑥，增加直接费用2×300=600（元）。

第三次调整：

选择费用最小的方案，在工作（2，4）与（3，4）上各缩短2天，即（2，4）与（3，4）的工时分别改为20－2＝18（天），26－2＝24（天），重新计算网络图时间参数，结果见下图（b）。总工期为60天，关键路线为：①→②→④→⑥，①→③→④→⑥和①→③→⑤→⑥，所增加的直接费用为2× 350＝700（元）。

由于一条关键路线①→③→④→⑥上各工作工时已不能缩短，计算结束。

全部计算过程及相应费用变化列成下表。由表中可见，最低成本日程为62天，总成本为63440元。

关于最低成本日程的计算步骤，也可改为计算总费用，并与上一次的总费用进行比较，若费用不能再降低则停止计算。

六、实施计划的管理

网络计划技术是先进的科学方法，但毕竟只是计划，在制订时就包含着许多不确定的因素，所以在计划的实施阶段还必须不断检查，进行分析，及时地采取措施修订计划，才能确保计划的实现。

实施计划的监督与管理的主要内容为：

（1）执行情况的报告。指计划执行单位应定期向主管部门报告计划执行进展情况，包括各工作原计划工时、预定完工期、时差、当前进展情况等。

（2）计划主管部门对报告进行加工分析。主管部门（或计算中心）的调度小组应根据收到的报告资料核对原网络计划作出必要修改。主要修改内容为：将已完成的工作或因某些原因需要取消的工作从网络图中消去；根据实施情况，修改某些未完成工作所需工时或添加某些新的工作。修改后要按新网络图，重新计算有关的时间参数和关键路线、总工期。

（3）网络计划的调整。如果计算出的新工期不符合预定工期就需要进行调整。通过对计划、实际资源、人力的研究，对网络计划的逻辑顺序、工作工时进行修订，使调整后的计划符合预定工期。此外还应进行财务控制，即检查工作是否在预定费用内进行。

完整的网络计划技术是一个管理系统，即最优的计划、精确的情报信息，再加上系统管理，才是网络计划技术的全部精髓。

以上就是关于网络计划优化的全部内容了，经过对这一节知识的学习，大家可以尝试运用上文所介绍的方法对一些实际应用问题进行求解。下一次小编将带大家学习图解评审法，敬请关注！

作者 | 张宇 齐鹏

责编 | 陈梦

审核 | 徐小峰