基于进化计算的项目工期与资源优化研究

段灵婧

贵州商学院 贵州贵阳 550014

据调查，大部分项目管理者在管理过程中，往往通过传统的“经验”预测完成一项项目所需的工期以及资源，由于每个项目具有其唯一性，这就导致在项目实施过程中会出现大量的变化，使得在管理过程中产生更多的不确定性，造成资源浪费或延长工期。项目资源管理是在保证满足工程质量、工期等合同要求的前提下，通过计划、组织、控制和协调等活动对项目实施过程中所使用的资源进行统筹安排，以实现预定的工期和成本目标，并尽可能降低成本的一种科学的管理活动[1]。所以，首先应该仔细研究工程项目的工期，科学合理地制订出建设工期和进度计划；其次要对项目中所需的各种资源进行统筹的安排，以做好资源的优化配置工作。本文利用进化算法对在资源有限的条件下，寻求最短工期和工期固定的情况下，如何使资源达到均衡消耗的目的予以研究。

一、NSGA-II

NSGA-II是对NSGA算法的改进，其引入了拥挤度和精英选择策略，使得优化过程更加具有泛化性，以及具有更优的遗传性，在解决多目标优化问题时被广泛应用，其能够实现项目工程在资源(人力、工期等)受限的条件下，进行全局搜索，实现资源均衡，最后得到最优方案。该算法一共包括了下面这些重要算子：快速非支配排序(FNDS)、拥挤度(CCM)、适应度(Fitness)、锦标赛选择(TSM)、模拟二进制交叉(SBX)、多项式变异(PM)、精英选择策略(ESS)等。由于在多目标优化时经常相互冲突，在进化过程中很难选择更好的解决方案进入下一代，NSGA-II使用快速非支配排序方法(FNDS)和拥挤比较方法(CCM)为下一代选择合适的个体。在产生新种群的交叉、变异和适应度进化操作之后，NSGA-II将原始种群和新产生的种群结合在一起。然后根据FNDS将组合的个体(解)划分为一组非支配等级。假设种群规模按等级划分，排名较低(较好)的个体将首先被选中进入下一代种群。即第一等级的个体直接进入下一代种群，然后第二等级的个体进入下一代种群，然后第三等级，依此类推，直到选择N个个体。本文中，Fitness设置函数如下：

f1(Xi)=T

(1)

(2)

其中，f2(Xi)代表资源闲置量，总工期用T表示，rt表示第t天需要的资源。

二、R&C-NSGA-II

(一)R&C

CCM的过程可能会消耗大量的计算负担，当M远小于当前秩的个体数时，随机选择M个个体即可，这不仅可以避免CCM的计算负担，而且还能实现种群多样性。因此，本文采用了一种结合RSM和CCM的自适应选择方法R&C，根据M与当前秩的个体数(|Fi|)的关系。如果M远小于|Fi|，即M<λ·|Fi|，其中λ是控制选择策略的参数，则R&C采用随机方式从当前的前沿Fi中随机选择M个个体。否则，由CCM选择M个个体。详细过程如下算法3所示。

Algorithm 3 R&CInput:Fi,M,Pt+1Begin1.If M<λ·|Fi|2.从Fi中随机选择M个,置入Pt+1;3.Else4.从Fi中采用CCM的方法,选择M个,置入Pt+1;5.End IfEnd

(二)R&C-NSGA-II

R&C-NSGA-II如下算法4所示。R&C有助于提高NSGA-II在解决MOPs方面的性能。

算法4中，t表示当前进化代，tmax表示最大进化代。Pt是第t代的父代种群，Qt是第t代的后代种群。F存储由FNDS形成的所有不同等级，其中Fi表示第i个等级。在初始化中，随机生成大小为N的父种群Pt，t初始设置为0。R&C-NSGA-II停止，直到达到tmax。其现代码如下所示：

三、工期与资源的优化方式

(一)资源有限、工期最短

根据工期目标对工程项目进行任务分解，确定各工作之间的逻辑关系，编制网络计划及相应的资源计划[2]。由于在实际情况下资源的供应受到条件的限制，导致某些工作不能在同一时段内同时进行，所以需要尽可能地调整进度计划的计算工期，一般通过调整关键路径上关键工作的持续时间，使其在满足要求工期的前提下，达到工期最合理的目的[3]。

(二)工期固定、资源均衡

工期固定、资源均衡的优化过程就是调整计划安排，在工期保持不变的条件下，使资源需用量尽可能均衡的过程。即尽可能在整个计划实施中不出现短时期的高峰和低谷，通过调整这两个时间段的资源用量，使每天的资源需用量接近于平均值，从而使得资源更加均衡的配置[4]。

四、实例验证

已知某工程项目由7项工作构成，其各项数据如表1所示，该项目的双代号网络图如图1所示。

图1 某工程项目的双代号网络图

根据该工程项目的双代号网络图，计算出总工期T为11周，其关键线路为①—②—④—⑤—⑥，关键工作为A—D—E—G。

表1 某工程项目的工期与资源用量

根据各项工作所需的资源绘制出初始资源用量图，如图2。

图2 初始资源用量图

设rt—在第t周的资源需用量；

rm—资源每周平均需用量。

rm=∑rt/T=(r1+r2+r3+…+rt)/T

由上可知，资源每周平均需用量rm=∑rt/T=(r1+r2+r3+…+r11)/T=1320/11=120，所以，假设经过优化后每周的资源用量控制在120以内，可以避免资源的浪费或因资源不足而造成工期的延长。

根据R&C-NSGA-Ⅱ优化方案，本文设置参数如下表2所示：

表2 R&C-NSGA-Ⅱ参数设置一览表

通过R&C-NSGA-Ⅱ，可获得pareto解8组，根据其解，取其中2组结果进行项目优化方案与初始方案比较，如图3所示。

由图3可知，第一种优化方案使资源高峰值150降低到了120，达到了工期和资源的均衡，使资源用量维持在120以内。

结论

在现代的项目管理中都会涉及项目管理活动和资源配置问题，任何的项目管理活动中都有两个重要的绩效管理目标，即项目的最短化和资源配置均衡化[5]。通常情况下，如果可以在资源短缺限制条件下得到合理的分配，所产生的经济效益就会显著增加，而资源的优化配置就是为了让资源获得更好利用，最终实现企业效益最大化[6]。