软件外包中分包商选择的优化模型及算法

曹 萍，陈福集

(福州大学公共管理学院，福建福州350108)

软件外包得到越来越多企业的青睐，成为当今外包发展最为迅速的领域之一［1］，而其高失败率也使软件外包风险的研究逐渐成为受关注的热点之一。导致软件外包失败的原因来自多方面，其中最主要的是外包决策失误带来的风险［2］。软件外包决策包括软件外包项目的选择、承包商的选择、合同的协商与签订等，其中最大的风险来自对承包商的选择。

在外包中承包商的选择是一个非常重要的决策问题。HANDFIELD等将AHP法用于承包商选择［3］;MURTHY等以总成本最小化为目标建立了承包商选择的线性规划模型［4］;SNIR等从博弈论的角度提出了两阶段合同结构的承包商选择问题，并进行了分析;TALLURI和BAKER提出了利用数据包络分析(DEA)和0－1整数规划的两阶段伙伴选择模型，选择出符合要求的承包商［5］。承包商的选择本质上是一个多准则决策问题［6］，但多准则决策方法在承包商选择方面并未得到充分的应用，现有的研究大多将一些目标函数作为约束条件，进而将问题转化为单目标优化问题。而应用多准则方法进行承包商选择的文献较少，其中最常用的方法是AHP和目标规划［7］。此外，WEBER等通过系统地分析相冲突的准则之间的平衡，整合考虑了价格、质量和延迟作为目标，建立了多目标线性规划进行承包商选择［8］。KUMAR等针对现实中某些参数具有模糊性的情况提出了承包商选择的模糊混合整数规划［9］。KARPAK和KASUGANTI使用可视化的交互目标规划解决承包商选择过程，以成本最小化和质量及可靠性最大化为目标，采用定量方法识别和分配承包商之间的优先顺序［10］。

分包商的选择属于承包商选择问题中的一类，但与一般意义上的承包商选择有所不同，分包商选择中发包方与分包商之间类似于供应链中上下游企业之间的关系，发包方对各分包商的情况较为熟悉。笔者针对软件企业外包风险控制中分包商选择问题(multi－subcontractor selection problem，MSSP)进行研究，首先给出研究的假设条件并对问题进行界定;然后构建MSSP多目标优化模型，针对模型的特点，设计启发式算法对模型进行求解;最后用算例对笔者的研究成果进行说明。

1 问题界定及优化模型构建

按照构件化技术的思路，软件通常都按照模块产品分组，形成模块组，实行模块组内的总并发控制方式进行设计。企业在做出软件分包的决定之后，分包商的选择便成为企业进行风险规避的关键决策。笔者提出了外包风险管理中分包商选择的多目标规划(multi－objective programming，MOP)模型，该模型在综合考虑风险［11］、费用和时间3个因素基础上，以成本最小和风险最小为目标，建立多目标规划模型在候选的软件分包商中选择合适的分包方，以实现软件发包方总费用最小且开发失败风险最小。其研究的假设条件如下:

(1)待外包的软件已按功能分解成多个模块，每个模块可以由不同的分包商开发;

(2)发包方是作为总承包商的软件企业，将项目分包给若干分包商去开发;

(3)发包方与多个分包商之间有稳定的业务往来，对各分包商的情况及以往项目的开发成功率较为了解;

(4)为了分散系统开发风险和节约时间，每个分包商开发的模块数不超过1个;

(5)作为发包方的软件企业对完成时间有一个目标工期。

模型符号定义如下:m为信息系统中待外包开发的功能模块总数;i为模块的下标，为候选软件分包商的数目;j为候选分包商的下标cij为第j个分包商对模块i的竞标费用。

由于作为发包方的软件企业与多个承包商有稳定的业务关系，他们之间类似于供应链中上下游企业间的合作伙伴关系，因此发包方对各分包商的技术能力、开发经验等有一定程度的了解。发包企业可通过以往采集的数据，采用相应的定量分析方法对各分包商进行评估，获得各候选分包商开发不同模块的失败概率，符号定义如下:

rij为模块i由第j个候选分包商开发的失败概率，0≤rij≤1;D为发包方预期的功能模块开发完成的目标时间;dij为候选分包商j对模块i的竞标时间;

考虑到该软件成功的充要条件是所有功能模块都能开发成功，问题可以用下面的模型来描述:

其中:［x］+=max{0，x};目标 z1(x)为软件项目开发失败的概率;目标z2(x)为外包的总费用，由模块开发费用和延迟费用所组成;β为惩罚系数。式(3)表示一个功能模块只选择一个候选承包商，式(4)表示委托一个候选承包商开发的软件模块不超过一个。

2 模型算法

2.1 模型处理

上述模型的目标函数为非线性多目标函数，本质上是非线性0－1整数规划问题，笔者设计了混合粒子群优化算法(GA－PSO)对模型进行求解。PSO(particle swarm optimized)算法最早用来求解无约束单目标的优化问题，该模型存在多目标和严格不等式约束，对于严格不等式约束采用在可行域内初始化的方法;对多目标模型采用理想点法进行处理，将其转化为单目标模型。转化后的模型为:

将目标函数进一步处理，可得:

该目标函数中的常数不会影响到目标函数的值，故可以省掉。上述问题最终可表示为:

2.2 混合粒子群算法的总体思路

粒子群优化的基本思想是将每一个可能产生的解表述为群中的一个微粒，每个微粒都具有自己的位置向量和速度向量，以及一个由目标函数决定的适应度。所有微粒在搜索空间中以一定的速度飞行，通过追随当前搜索到的最优值来寻找全局最优。其中，位置代表参数取值，速度表示各参数改进的方向和步长。算法首先通过随机初始化产生一群粒子，然后进行迭代寻优。在每一次为演化迭代中，粒子通过跟踪两个极值来不断更新自己:一个为粒子本身所找到的最优解，称为个体极值pbest，另一个为整个种群目前为止所找到的最优解，称为全局极值gbest。然后根据式(8)和式(9)不断更新速度与位置:

式中:vk为粒子的速度向量;xk为当前粒子的位置;pbestk为粒子本身所找到的最优解位置;gbestk为整个种群目前找到的最优解位置;co、c1、c2为系数。

由于PSO算法最初是处理连续优化问题的，对于整数规划问题，若按基本粒子群算法，其速度难以表达。借鉴遗传算法的交叉和变异操作，将其引入粒子群算法，即基于遗传算法的混合粒子群(PSO based on genetic algorithm)来求解该模型。在求解过程中将当前解与个体极值和全局极值分别进行交叉操作，产生新的解。

2.3 求解MSSP问题的混合粒子群算法设计

(1)初始化。设定粒子数为M，要外包的功能模块数为 num，解可以表示为 X0=(X1j，X2j，…，XMj)T(j=1，2，…，num)，包含 M个解向量;第t(t=1，2，…，M)个解向量表示为 Xtj=(xt1，xt2，…，xtnum)，含义是选择第xti个供应商开发第i(i=1，2，…，num)个功能模块。依据此编码方案，随机产生M个初始解，规定迭代次数为N次;

(2)根据式(1)和式(2)计算单目标极值z*1和z*2;

(3)根据式(7)的目标函数F计算适应值f(i)(i=1，2，…，M)，得到 M个初始值;

(4)设个体极值为plbest，个体极值位置为pcbest，对它们进行初始化 plbest(i)=f(i)，(i=1，2，…，M)，pcbest=(1，2，…，M)T;找出全局极值glbest=max f(i)，并找出相应的全局极值位置gcbest=Xij;

(5)外层循环当前迭代次数设定为K=1;

(6)内层循环当前迭代粒子数设定为par1=1;

(7)当前粒子数par1的位置为X0(par1);

(8)X0(par1)与全局极值glbest的位置gcbest交叉得到X'1(par1);X'1(par1)再与个体极值plbest的位置pcbest交叉得到X1(par1);对X1(par1)进行变异操作;根据当前位置计算适应值f(i)(i=1，2，…，M);

(9)如果 f(i)≤plbest，则 plbest=f(i)，并相应地更改pcbest的值;par1=par1+1，如果par1≤M，转步骤(7)，否则，进入下一步;

(10)将plbest中最大的值作为全局极值，glbest=max［plbest(i)］(i=1，2，…，M)，并将相对应的解赋给全局极值gcbest;

(11)K=K+1;如果K≤N，转步骤(6);否则结束运算。

其中步骤(8)中的交叉和变异可采用以下策略:

2) POD数据处理核心模块的主要功能是对数据进行POD分析，包括POD分解(进行POD分解计算，分别计算特征值、特征模态和模态系数)、POD重构(基于POD分解得到的特征值、模态和模态系数对流场进行重构)和相位平均(基于重构的流场进行相位平均，同时计算流场瞬态相位角和相位流场信息等)等3个子模块[4, 8, 10-11] 。

(1)交叉策略:①设两个串old1和old2;②在old2中随机选择一个交叉区域;③将交叉区域加到old1前面，删除old1中已在交叉区域中出现过的数字。

(2)变异策略:①在解空间x=(x1，x2，…，xn)T中随机选择一个 j，j=1，2，…，n;②产生一个一定范围内的随机整数 t，t∈{1，2，…，n};③判断 t是否与解空间中的数相同，如果t=xj(j=1，2，…，n)，则返回②，否则继续执行下一步;④xj←t。

3 算法测试及分析

表1 候选分包商对各个模块的报价 元

通过事先评估，获得候选分包商开发不同模块的失败概率rij如表2所示。

表2 候选分包商开发不同模块的失败概率

候选分包商的竞标完成时间如表3所示。算法基本参数设置如下:初始化粒子数n=

某软件企业为分散风险，将软件项目的某些部分外包给其他企业，与多方合作共同承担软件项目的开发，实现彼此之间优势互补。将软件项目进行分解后，其中5个模块打算通过外包的方式开发，为期6个月，β=0.5(万元)。其中8个合作伙伴作为候选分包商，每个分包商对各个模块的报价如表1所示，表1中各分包商用企业表示。5，向量的维数m=5，即随机产生5个数值在［1，8］之间的整数解。r1，r2的取值可根据企业对成本和风险的偏好来选取不同值。如取r1=0.4，r2=0.6进行测试，该算法使用Matlab 7.0编程实现。首先计算出理想点(z*1，z*2)，迭代100次得到(z*1，z*2)=(0.127 1，56 300)。然后再对式(7)进行计算，在不同迭代次数条件下，分别测试该算法20次，其计算结果如表4所示。

表3 候选分包商的竞标完成时间 天

表4 计算结果

图1 测试结果

获得全局极值glbest和位置gcbest，最优解为X*=(7，1，5，8，6)，最优值F*=1.368 7，该最优解综合考虑了成本和开发失败的风险以及延迟惩罚。

从表4可知，随着迭代次数的增加，结果越来越接近最优解。图1的测试结果显示了在不同的迭代次数下的计算过程，在迭代次数大于50次时已能较好地收敛，可见该算法具有较好的收敛性。仿真结果表明，该算法可以有效地解决非线性多目标0－1规划问题。

4 结论

笔者建立了软件外包中的分包商选择模型，该模型属于NP－hard问题，目前还没有有效的算法求解该问题。笔者针对该模型是0－1规划的问题，在粒子群算法中引入遗传算法的思想，设计了遗传算法和粒子群算法的混合算法(GAPSO)对模型进行求解。算法有效地结合了智能算法和群智能算法，在运算中，既表现出了智能算法的个体智能(交叉、变异和选择)，也充分利用了群智能的信息(个体最优和群体最优)，经过仿真计算，证明了算法可有效地用于解决分包商选择非线性整数规划模型。为软件企业选择分包商合作开发软件项目提供了决策模型支持，具有一定的现实意义。

［1］CHATTERJID.Accessing external sources of technology［J］.IEEE Engineering Management Review，1997，25(2):80－89.

［2］GOPAL A，MUKHOPADHYAY T，KRISHNAN MS.The role of software processes and communication in offshore software development［J］.Communications of the ACM，2002，45(4):193 －201.

［3］HANDFIELD R B，RAGATZG L，PETERSEN K J，et al.Involving suppliers in new product development［J］.California Management Review，1999，42(1):59 －72.

［4］MURTHY N N，SONI S，GHOSH S.A framework for facilitating sourcing and allocation decisions for make－ to － order items［J］.Decision Sciences，2004，35(4):609－637.

［5］TALLURI S，BAKER R C.A quantitative framework for designing efficient business process alliance［C］//Engineering and Management.Vancouver:IEEE，1996:656－661.

［6］CAO Q，WANG Q.Optimizing vendor selection in a two－stage outsourcing process［J］.Computers ＆ Operations Research，2007，34(3):3757 －3768.

［7］GHODSYPOUR SH，O'BRIEN C.The total cost of logistics in supplier selection，under conditions ofmultiple sourcing，multiple criteria and capacity constraint［J］.International Journal of Production Economics，2001，73(1):15－27.

［8］WEBER C A，CURRENT JR.A multi objective approach to supplier selection［J］.European Journal of Operational Research，1993(68):173 －184.

［9］KUMAR M，VRAT P，SHANKAR R.A multi－ objective interval programming approach for supplier selection problem in a supply chain［C］//Proceedings of the 2002 International Conference on E－Manufacturing:an Emerging Need for 21st Century World Class Enterprises.Bhopal:IEI，2002:15 －19.

［10］KARPAK K，KASUGANTIR R.An application of visual interactive goal programming:a case in supplier selection decisions［J］.Journal of Multi－ criterion Decision Making，1999(8):93 －105.

［11］黄宜，王长伟，王艳伟.内部信息不对称下IT项目外包决策风险测度［J］.武汉理工大学学报:信息与管理工程版，2010，32(1):125 －128.