在IT外包项目管理中, 能否按时完工一直是委托方和承包商的关注重点, 工期控制的成功与否在一定程度上决定着项目的成败^[1-2].在项目进度控制方面, 项目管理者常用的方法和技术包括Gantt图、关键路径法、基于挣值(earned value)的技术、基于里程碑的方法^[3-5]等.在风险分析方面, 有等风险图法、模糊分析法、风险报酬法和蒙特卡罗模拟法等多种方法^[6-7].本文采用的IT外包进度风险控制的结构化分布式决策模型^[1], 不仅着眼于项目本身作业过程的进度风险的评估和控制, 还考虑了IT外包项目在执行过程中所涉及到的多方交互合作的实际情况.

用遗传算法求解项目进度相关的例子有很多.周方明等将主成分分析(PCA)、遗传算法(GA)与BP神经网络相结合, 提出基于PCA-GA-BP的工程项目工期风险预测模型, 并证明其对实际工程具有指导意义^[6]; Dao等曾在项目日程安排的优化上使用遗传算法, 为该类问题提供了一种新的思路^[7].

IT外包项目中进度风险控制是一个分布式优化问题, 具有两层复杂结构, 且决策变量存在离散和连续的混合情况，因此，该优化问题的求解难度较高.本文根据问题特点对传统遗传算法(traditional genetic algorithm, TGA)进行改进.首先, 设计两层遗传算法以分解问题的解空间, 降低求解难度；然后, 为了避免TGA易于早熟和局部搜索能力不强的问题, 引入模拟退火和自适应机制, 设计了TLHGA(two-level hybrid genetic algorithm), 以期为本优化问题提供一种有效的求解手段.

1 IT外包项目进度风险控制问题

一个委托方按照开发流程将项目进行分解, 委托给多个承包商并使其完成相应的目标^[1].模型分为上、下两层, 上层的决策者为委托方, 由委托方将风险控制的预算资金分配给各承包商; 下层的决策者为承包商, 有M个承包商接受资金分配并对所承包的子项目中的N个活动选择相应的进度风险控制措施.以承包商i为例, 将其得到的风险控制投入资金x_i分配到其负责子项目的关键路径上的N个活动中.

问题定义:子项目i的进度风险由风险暴露(risk exposure)来定义, 即子项目出现拖期的概率乘以损失的程度(拖期的时间):

(1)

模型假设:

1) 委托方在与各承包商签订的合同中规定各合同总价款均为U_i, 若各子项目发生延期, 则需赔款V_i, i=1, 2, …, M, M为承包商数量; x_i为承包商i的预算资金; B_max为总的预算资金的最大上限值; R_max是各承包商负责的子项目的进度风险水平的最大上限值; Benifit_i表示承包商i所获得的收益; P(A_i)表示承包商i项目的完成概率, P(A_i )表示承包商i的拖期概率.

2) 子项目i关键路径上的每一个活动j的直接费用为c_ij(j=1, …, N_i), 子项目计划工期为T_i⁰, 子项目实际工期为T_i.子项目i间接费用一般随着总工期的增加而增长, 假设单位时间的间接费用为C_i, t_ij(y_ij)是子项目i每个活动j的拖期时间, cost_ij(y_ij)表示每个活动j上所投入的资金.

3) 承包商i的进度风险水平是Risk_i(x_i).

4) 子项目之间在工序上是串行的.

上层模型:

(2)

(3)

(4)

(5)

上层模型以项目整体的进度风险为目标函数, 即式(2).式(3)表示对总预算资金投入的限制, 式(4)指各承包商负责的子项目的进度风险不能超过给定的水平R_max.上层模型的最优解为(x₁^*, x₂^*, …, x_M^*).

下层模型:

(6)

(7)

(8)

(9)

(10)

下层模型以承包商i总收益最大化为目标函数, 即式(6).式(7)表示承包商的净收益不小于其可接受的最低收益水平；式(8)指项目进度风险不大于预期的风险水平；约束(9)表示风险控制费用在委托方风险投入的可承受范围内；式(10)表示备选的风险控制措施, 其中表示子项目i中活动j备选的风险控制措施的数量, 若y_ij=0, 则表示不对活动j采取任何风险控制措施,Q为最大可选择的风险控制措施.第i个下层模型的最优解为(y_i1^*, y_i2^*, …, y_iNi^*).

2 两层混合遗传算法设计

IT外包项目进度风险控制问题是一个两层的、混合数学规划问题.当子项目和措施的数量较多时, 该问题的解空间将迅速增大, 导致其是一个NP难问题，因此, 选择GA作为本问题的求解方法.本文根据问题特点对TGA进行了改进.首先, 设计两层GA使问题的解空间得以分解, 降低求解难度.然后, 为了避免TGA易于早熟和局部搜索能力不强的问题^[5-7], 引入模拟退火和自适应机制, 对上层模型采用模拟退火算法, 对下层模型采用自适应遗传算法, 设计了TLHGA, 以期为本优化问题提供一种有效的求解手段.

2.1 模拟退火机制

对于上层种群中的最优个体, 实施模拟退火机制.模拟退火具有较强的局部搜索能力, 易于跳出局部最优解, 能弥补TGA易于早熟的缺陷.由于本文上层的自变量是具体的资金额, 且有一定的限制.因此, 模拟退火算法中产生函数的机制为:随机产生a, 将其与自变量相加或相减, 使最终结果符合限制条件.模拟退火机制的具体操作过程为:①利用产生函数, 产生新个体; ②判断新个体的适应值是否减小(求最小值), 若适应值减小, 则用新个体取代原个体, 否则按照接受准则判断是否接受新个体; ③在降温机制和每个温度条件一定的交换次数限制下, 重复步骤①和步骤②.接受准则采用Boltzmann概率分布^[7], 公式为

(11)

式中:E为温度T时的风险水平, ΔE为其增量.降温机制是指温度按T=T · T_R变化, T为初始温度, T_R为温度变化率.

2.2 自适应机制

遗传算法的核心部分在于选择、交叉和变异, 而算法中的交叉和变异过程受到交叉概率P_c与变异概率P_m影响, 所以实际上, P_c与 P_m的选择是影响遗传算法性能的关键^[7].自适应机制使得P_c与 P_m的值在程序运行过程中能够随着当代种群适应值的改变而改变.

1) 将单点交叉与自适应交叉相结合.自适应交叉率的公式为

(12)

2) 将基本位变异与自适应变异相结合.自适应变异率的公式为

(13)

在式(12)和式(13)中, P_c1和 P_m1表示种群取平均适应值时的交叉率和变异率, P_c2和 P_m2表示种群取最大适应值时的交叉率和变异率.f_m表示当次迭代时种群的最大适应值, f_avg表示当次迭代时种群的平均适应值, f ′表示要交叉的两个个体中较大的适应值, f表示要变异个体的适应值.

2.3 TLHGA流程图

TLHGA算法流程图如图 1所示, 其中图 1b是图 1a中的虚线部分, 代表下层结构.在算法中, 上层搜索的终止由初始温度和每个温度下的迭代次数确定, 下层的终止由迭代次数确定.

3 算例及分析

本节以国内某IT外包服务公司为背景, 设计仿真实例来验证算法的有效性.算例考虑有1个委托方和M个承包商的情况, M=1, 2, …, 5；这5种情况总的预算资金上限分别为B_max=900, 1 800, 2 700, 3 600, 4 500, 进度风险水平约束为R_max=0.05.各承包商与委托方通过签订合同开展合作, 合同中的总价款U_i=10 000, 项目延期的赔偿款V_i=3 000, i=1, 2, …, 5.承包商的利润率r=0.2.假定每个项目由10个活动组成(N_i=10), 且活动在工序上是串行的.各活动的费用c_ij=650, i=1, 2, …, 5, j=1, 2, …, 10.各活动的进度风险发生概率p_ij={0.93, 0.87, 0.79, 0.79, 0.75, 0.73, 0.71, 0.67, 0.65}.为了防止进度风险发生致使项目失败, 对于每个活动, 可以从4个(Q=4)风险控制措施中选择一个用于风险防范.在风险措施的控制下, 项目在执行过程中的工期会有相应的缩减, 由t_ij 变为t_ij(y_ij).在本算例中风险控制措施编号越大, 则活动工期缩减得越多.其中项目i的计划工期T_i⁰=1 000, 实际工期由式(14)表示：

(14)

参数μ_ij={0.02, 0.025, 0.03, 0.035, 0.04, 0.045, 0.05, 0.055, 0.06, 0.065}, 不同取值表示相同风险控制措施对不同活动工期缩减作用的不同效果.从式(14)可以看出, 各活动未进行风险控制的实际工期为120.执行风险控制措施需要一定的费用, 费用的函数由式(15)表示：

(15)

其中, ω_ij={0.55, 0.6, 0.65, 0.7, 0.75, 0.8, 0.85, 0.9, 0.95, 1}.

3.1 算法参数设置

算法上层需要确定的参数是模拟退火的初始温度T和温度变化率T_R.以M=1为例，对T=60, 65, 70, 75, 80, 85和T_R=0.4, 0.5, 0.6的情况进行组合，分别设计18组算例, 每组运行30次.以项目进度风险水平的最小值和平均值为评判指标，通过实验得到参数T=60和T_R=0.6.其他参数包括:种群规模取10, 温度的下限T_min取4.算法下层自适应遗传算法中P_c1=0.9, P_c2=0.6, P_m1=0.1, P_m2=0.01.种群规模取30, 迭代次数为60.

3.2 仿真结果及其分析

使用TLHGA对模型进行求解, 得到的最优仿真结果见表 1, 其中pr是上层最优适应值, x是委托方为承包商分配的资金, prisks是承包商的进度风险值, p为所选的进度风险措施编号, Benefit是承包商的收益, tsum项目工期缩短量.

以M=2的结果为例来说明仿真结果的含义.委托方将项目委托给2个承包商, 委托方分配给承包商1和2的资金分别为849和884.在风险控制措施的作用下, 整个项目的进度风险水平为80.63, 其中承包商1和承包商2的进度风险水平分别控制在40.74和39.89.在进行风险控制前各子项目的实际工期均为1 200, 采取相应的风险措施后, 承包商1和承包商2的子项目的工期分别缩短为35.42和27.73.与此同时, 承包商1和承包商2分别获得风险控制收益为2 450.31和2 485.72.

为了验证算法的有效性, 将TLHGA的仿真结果与TLPSO^[1]和TGA的结果进行比较, 结果见图 2, 其中prBest是最优值、prAVG是最优值的平均值、prVAR是最优值的方差、CPUTimeAVG是平均CPU时间.由图 2a可以看出, 随着问题规模的增加, TGA的整体图线在TLPSO的下方, TLHGA的整体图线在TGA的下方, 显然, TGA比文献[1]中使用的TLPSO算法从结果上看更适合该问题, 而TLHGA得到了比TGA更好的最优解.图 2b描述的是仿真结果得到的目标值的平均值, 可以看出与图 2a中有相似的结论.由图 2c可以看出, TGA和TLHGA表现出来的稳定性不及TLPSO.在图 2d中, 随着问题规模的不断增加, TLPSO和TGA的平均CPU时间都有明显的增大, 但TLHGA的CPU时间并没有随着问题规模的增加而明显增大, 表明该算法的寻优效率较高.

4 结语

本文针对IT外包项目进度风险控制的两层分布式决策问题, 分别引入了模拟退火和自适应机制, 设计了两层混合遗传算法(TLHGA).在仿真实验中, 设计了五个数值算例, 分别采用TGA和TLHGA进行求解, 并将仿真结果与文献[1]中TLPSO的结果进行了对比.结果表明, 在最优适应值、平均适应值、方差和CPU时间等诸多方面, TLHGA都表现不错, 尤其是在时间效率方面表现尤为突出.