軟件外包中分包商選擇的優(yōu)化模型及算法

曹 萍，陳福集

(福州大學(xué)公共管理學(xué)院，福建福州350108)

軟件外包得到越來越多企業(yè)的青睞，成為當(dāng)今外包發(fā)展最為迅速的領(lǐng)域之一［1］，而其高失敗率也使軟件外包風(fēng)險(xiǎn)的研究逐漸成為受關(guān)注的熱點(diǎn)之一。導(dǎo)致軟件外包失敗的原因來自多方面，其中最主要的是外包決策失誤帶來的風(fēng)險(xiǎn)［2］。軟件外包決策包括軟件外包項(xiàng)目的選擇、承包商的選擇、合同的協(xié)商與簽訂等，其中最大的風(fēng)險(xiǎn)來自對(duì)承包商的選擇。

在外包中承包商的選擇是一個(gè)非常重要的決策問題。HANDFIELD等將AHP法用于承包商選擇［3］;MURTHY等以總成本最小化為目標(biāo)建立了承包商選擇的線性規(guī)劃模型［4］;SNIR等從博弈論的角度提出了兩階段合同結(jié)構(gòu)的承包商選擇問題，并進(jìn)行了分析;TALLURI和BAKER提出了利用數(shù)據(jù)包絡(luò)分析(DEA)和0－1整數(shù)規(guī)劃的兩階段伙伴選擇模型，選擇出符合要求的承包商［5］。承包商的選擇本質(zhì)上是一個(gè)多準(zhǔn)則決策問題［6］，但多準(zhǔn)則決策方法在承包商選擇方面并未得到充分的應(yīng)用，現(xiàn)有的研究大多將一些目標(biāo)函數(shù)作為約束條件，進(jìn)而將問題轉(zhuǎn)化為單目標(biāo)優(yōu)化問題。而應(yīng)用多準(zhǔn)則方法進(jìn)行承包商選擇的文獻(xiàn)較少，其中最常用的方法是AHP和目標(biāo)規(guī)劃［7］。此外，WEBER等通過系統(tǒng)地分析相沖突的準(zhǔn)則之間的平衡，整合考慮了價(jià)格、質(zhì)量和延遲作為目標(biāo)，建立了多目標(biāo)線性規(guī)劃進(jìn)行承包商選擇［8］。KUMAR等針對(duì)現(xiàn)實(shí)中某些參數(shù)具有模糊性的情況提出了承包商選擇的模糊混合整數(shù)規(guī)劃［9］。KARPAK和KASUGANTI使用可視化的交互目標(biāo)規(guī)劃解決承包商選擇過程，以成本最小化和質(zhì)量及可靠性最大化為目標(biāo)，采用定量方法識(shí)別和分配承包商之間的優(yōu)先順序［10］。

分包商的選擇屬于承包商選擇問題中的一類，但與一般意義上的承包商選擇有所不同，分包商選擇中發(fā)包方與分包商之間類似于供應(yīng)鏈中上下游企業(yè)之間的關(guān)系，發(fā)包方對(duì)各分包商的情況較為熟悉。筆者針對(duì)軟件企業(yè)外包風(fēng)險(xiǎn)控制中分包商選擇問題(multi－subcontractor selection problem，MSSP)進(jìn)行研究，首先給出研究的假設(shè)條件并對(duì)問題進(jìn)行界定;然后構(gòu)建MSSP多目標(biāo)優(yōu)化模型，針對(duì)模型的特點(diǎn)，設(shè)計(jì)啟發(fā)式算法對(duì)模型進(jìn)行求解;最后用算例對(duì)筆者的研究成果進(jìn)行說明。

1 問題界定及優(yōu)化模型構(gòu)建

按照構(gòu)件化技術(shù)的思路，軟件通常都按照模塊產(chǎn)品分組，形成模塊組，實(shí)行模塊組內(nèi)的總并發(fā)控制方式進(jìn)行設(shè)計(jì)。企業(yè)在做出軟件分包的決定之后，分包商的選擇便成為企業(yè)進(jìn)行風(fēng)險(xiǎn)規(guī)避的關(guān)鍵決策。筆者提出了外包風(fēng)險(xiǎn)管理中分包商選擇的多目標(biāo)規(guī)劃(multi－objective programming，MOP)模型，該模型在綜合考慮風(fēng)險(xiǎn)［11］、費(fèi)用和時(shí)間3個(gè)因素基礎(chǔ)上，以成本最小和風(fēng)險(xiǎn)最小為目標(biāo)，建立多目標(biāo)規(guī)劃模型在候選的軟件分包商中選擇合適的分包方，以實(shí)現(xiàn)軟件發(fā)包方總費(fèi)用最小且開發(fā)失敗風(fēng)險(xiǎn)最小。其研究的假設(shè)條件如下:

(1)待外包的軟件已按功能分解成多個(gè)模塊，每個(gè)模塊可以由不同的分包商開發(fā);

(2)發(fā)包方是作為總承包商的軟件企業(yè)，將項(xiàng)目分包給若干分包商去開發(fā);

(3)發(fā)包方與多個(gè)分包商之間有穩(wěn)定的業(yè)務(wù)往來，對(duì)各分包商的情況及以往項(xiàng)目的開發(fā)成功率較為了解;

(4)為了分散系統(tǒng)開發(fā)風(fēng)險(xiǎn)和節(jié)約時(shí)間，每個(gè)分包商開發(fā)的模塊數(shù)不超過1個(gè);

(5)作為發(fā)包方的軟件企業(yè)對(duì)完成時(shí)間有一個(gè)目標(biāo)工期。

模型符號(hào)定義如下:m為信息系統(tǒng)中待外包開發(fā)的功能模塊總數(shù);i為模塊的下標(biāo)，為候選軟件分包商的數(shù)目;j為候選分包商的下標(biāo)cij為第j個(gè)分包商對(duì)模塊i的競(jìng)標(biāo)費(fèi)用。

由于作為發(fā)包方的軟件企業(yè)與多個(gè)承包商有穩(wěn)定的業(yè)務(wù)關(guān)系，他們之間類似于供應(yīng)鏈中上下游企業(yè)間的合作伙伴關(guān)系，因此發(fā)包方對(duì)各分包商的技術(shù)能力、開發(fā)經(jīng)驗(yàn)等有一定程度的了解。發(fā)包企業(yè)可通過以往采集的數(shù)據(jù)，采用相應(yīng)的定量分析方法對(duì)各分包商進(jìn)行評(píng)估，獲得各候選分包商開發(fā)不同模塊的失敗概率，符號(hào)定義如下:

rij為模塊i由第j個(gè)候選分包商開發(fā)的失敗概率，0≤rij≤1;D為發(fā)包方預(yù)期的功能模塊開發(fā)完成的目標(biāo)時(shí)間;dij為候選分包商j對(duì)模塊i的競(jìng)標(biāo)時(shí)間;

考慮到該軟件成功的充要條件是所有功能模塊都能開發(fā)成功，問題可以用下面的模型來描述:

其中:［x］+=max{0，x};目標(biāo) z1(x)為軟件項(xiàng)目開發(fā)失敗的概率;目標(biāo)z2(x)為外包的總費(fèi)用，由模塊開發(fā)費(fèi)用和延遲費(fèi)用所組成;β為懲罰系數(shù)。式(3)表示一個(gè)功能模塊只選擇一個(gè)候選承包商，式(4)表示委托一個(gè)候選承包商開發(fā)的軟件模塊不超過一個(gè)。

2 模型算法

2.1 模型處理

上述模型的目標(biāo)函數(shù)為非線性多目標(biāo)函數(shù)，本質(zhì)上是非線性0－1整數(shù)規(guī)劃問題，筆者設(shè)計(jì)了混合粒子群優(yōu)化算法(GA－PSO)對(duì)模型進(jìn)行求解。PSO(particle swarm optimized)算法最早用來求解無約束單目標(biāo)的優(yōu)化問題，該模型存在多目標(biāo)和嚴(yán)格不等式約束，對(duì)于嚴(yán)格不等式約束采用在可行域內(nèi)初始化的方法;對(duì)多目標(biāo)模型采用理想點(diǎn)法進(jìn)行處理，將其轉(zhuǎn)化為單目標(biāo)模型。轉(zhuǎn)化后的模型為:

將目標(biāo)函數(shù)進(jìn)一步處理，可得:

該目標(biāo)函數(shù)中的常數(shù)不會(huì)影響到目標(biāo)函數(shù)的值，故可以省掉。上述問題最終可表示為:

2.2 混合粒子群算法的總體思路

粒子群優(yōu)化的基本思想是將每一個(gè)可能產(chǎn)生的解表述為群中的一個(gè)微粒，每個(gè)微粒都具有自己的位置向量和速度向量，以及一個(gè)由目標(biāo)函數(shù)決定的適應(yīng)度。所有微粒在搜索空間中以一定的速度飛行，通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)。其中，位置代表參數(shù)取值，速度表示各參數(shù)改進(jìn)的方向和步長(zhǎng)。算法首先通過隨機(jī)初始化產(chǎn)生一群粒子，然后進(jìn)行迭代尋優(yōu)。在每一次為演化迭代中，粒子通過跟蹤兩個(gè)極值來不斷更新自己:一個(gè)為粒子本身所找到的最優(yōu)解，稱為個(gè)體極值pbest，另一個(gè)為整個(gè)種群目前為止所找到的最優(yōu)解，稱為全局極值gbest。然后根據(jù)式(8)和式(9)不斷更新速度與位置:

式中:vk為粒子的速度向量;xk為當(dāng)前粒子的位置;pbestk為粒子本身所找到的最優(yōu)解位置;gbestk為整個(gè)種群目前找到的最優(yōu)解位置;co、c1、c2為系數(shù)。

由于PSO算法最初是處理連續(xù)優(yōu)化問題的，對(duì)于整數(shù)規(guī)劃問題，若按基本粒子群算法，其速度難以表達(dá)。借鑒遺傳算法的交叉和變異操作，將其引入粒子群算法，即基于遺傳算法的混合粒子群(PSO based on genetic algorithm)來求解該模型。在求解過程中將當(dāng)前解與個(gè)體極值和全局極值分別進(jìn)行交叉操作，產(chǎn)生新的解。

2.3 求解MSSP問題的混合粒子群算法設(shè)計(jì)

(1)初始化。設(shè)定粒子數(shù)為M，要外包的功能模塊數(shù)為 num，解可以表示為 X0=(X1j，X2j，…，XMj)T(j=1，2，…，num)，包含 M個(gè)解向量;第t(t=1，2，…，M)個(gè)解向量表示為 Xtj=(xt1，xt2，…，xtnum)，含義是選擇第xti個(gè)供應(yīng)商開發(fā)第i(i=1，2，…，num)個(gè)功能模塊。依據(jù)此編碼方案，隨機(jī)產(chǎn)生M個(gè)初始解，規(guī)定迭代次數(shù)為N次;

(2)根據(jù)式(1)和式(2)計(jì)算單目標(biāo)極值z(mì)*1和z*2;

(3)根據(jù)式(7)的目標(biāo)函數(shù)F計(jì)算適應(yīng)值f(i)(i=1，2，…，M)，得到 M個(gè)初始值;

(4)設(shè)個(gè)體極值為plbest，個(gè)體極值位置為pcbest，對(duì)它們進(jìn)行初始化 plbest(i)=f(i)，(i=1，2，…，M)，pcbest=(1，2，…，M)T;找出全局極值glbest=max f(i)，并找出相應(yīng)的全局極值位置gcbest=Xij;

(5)外層循環(huán)當(dāng)前迭代次數(shù)設(shè)定為K=1;

(6)內(nèi)層循環(huán)當(dāng)前迭代粒子數(shù)設(shè)定為par1=1;

(7)當(dāng)前粒子數(shù)par1的位置為X0(par1);

(8)X0(par1)與全局極值glbest的位置gcbest交叉得到X'1(par1);X'1(par1)再與個(gè)體極值plbest的位置pcbest交叉得到X1(par1);對(duì)X1(par1)進(jìn)行變異操作;根據(jù)當(dāng)前位置計(jì)算適應(yīng)值f(i)(i=1，2，…，M);

(9)如果 f(i)≤plbest，則 plbest=f(i)，并相應(yīng)地更改pcbest的值;par1=par1+1，如果par1≤M，轉(zhuǎn)步驟(7)，否則，進(jìn)入下一步;

(10)將plbest中最大的值作為全局極值，glbest=max［plbest(i)］(i=1，2，…，M)，并將相對(duì)應(yīng)的解賦給全局極值gcbest;

(11)K=K+1;如果K≤N，轉(zhuǎn)步驟(6);否則結(jié)束運(yùn)算。

其中步驟(8)中的交叉和變異可采用以下策略:

2) POD數(shù)據(jù)處理核心模塊的主要功能是對(duì)數(shù)據(jù)進(jìn)行POD分析，包括POD分解(進(jìn)行POD分解計(jì)算，分別計(jì)算特征值、特征模態(tài)和模態(tài)系數(shù))、POD重構(gòu)(基于POD分解得到的特征值、模態(tài)和模態(tài)系數(shù)對(duì)流場(chǎng)進(jìn)行重構(gòu))和相位平均(基于重構(gòu)的流場(chǎng)進(jìn)行相位平均，同時(shí)計(jì)算流場(chǎng)瞬態(tài)相位角和相位流場(chǎng)信息等)等3個(gè)子模塊[4, 8, 10-11] 。

(1)交叉策略:①設(shè)兩個(gè)串old1和old2;②在old2中隨機(jī)選擇一個(gè)交叉區(qū)域;③將交叉區(qū)域加到old1前面，刪除old1中已在交叉區(qū)域中出現(xiàn)過的數(shù)字。

(2)變異策略:①在解空間x=(x1，x2，…，xn)T中隨機(jī)選擇一個(gè) j，j=1，2，…，n;②產(chǎn)生一個(gè)一定范圍內(nèi)的隨機(jī)整數(shù) t，t∈{1，2，…，n};③判斷 t是否與解空間中的數(shù)相同，如果t=xj(j=1，2，…，n)，則返回②，否則繼續(xù)執(zhí)行下一步;④xj←t。

3 算法測(cè)試及分析

表1 候選分包商對(duì)各個(gè)模塊的報(bào)價(jià) 元

通過事先評(píng)估，獲得候選分包商開發(fā)不同模塊的失敗概率rij如表2所示。

表2 候選分包商開發(fā)不同模塊的失敗概率

候選分包商的競(jìng)標(biāo)完成時(shí)間如表3所示。算法基本參數(shù)設(shè)置如下:初始化粒子數(shù)n=

某軟件企業(yè)為分散風(fēng)險(xiǎn)，將軟件項(xiàng)目的某些部分外包給其他企業(yè)，與多方合作共同承擔(dān)軟件項(xiàng)目的開發(fā)，實(shí)現(xiàn)彼此之間優(yōu)勢(shì)互補(bǔ)。將軟件項(xiàng)目進(jìn)行分解后，其中5個(gè)模塊打算通過外包的方式開發(fā)，為期6個(gè)月，β=0.5(萬元)。其中8個(gè)合作伙伴作為候選分包商，每個(gè)分包商對(duì)各個(gè)模塊的報(bào)價(jià)如表1所示，表1中各分包商用企業(yè)表示。5，向量的維數(shù)m=5，即隨機(jī)產(chǎn)生5個(gè)數(shù)值在［1，8］之間的整數(shù)解。r1，r2的取值可根據(jù)企業(yè)對(duì)成本和風(fēng)險(xiǎn)的偏好來選取不同值。如取r1=0.4，r2=0.6進(jìn)行測(cè)試，該算法使用Matlab 7.0編程實(shí)現(xiàn)。首先計(jì)算出理想點(diǎn)(z*1，z*2)，迭代100次得到(z*1，z*2)=(0.127 1，56 300)。然后再對(duì)式(7)進(jìn)行計(jì)算，在不同迭代次數(shù)條件下，分別測(cè)試該算法20次，其計(jì)算結(jié)果如表4所示。

表3 候選分包商的競(jìng)標(biāo)完成時(shí)間 天

表4 計(jì)算結(jié)果

圖1 測(cè)試結(jié)果

獲得全局極值glbest和位置gcbest，最優(yōu)解為X*=(7，1，5，8，6)，最優(yōu)值F*=1.368 7，該最優(yōu)解綜合考慮了成本和開發(fā)失敗的風(fēng)險(xiǎn)以及延遲懲罰。

從表4可知，隨著迭代次數(shù)的增加，結(jié)果越來越接近最優(yōu)解。圖1的測(cè)試結(jié)果顯示了在不同的迭代次數(shù)下的計(jì)算過程，在迭代次數(shù)大于50次時(shí)已能較好地收斂，可見該算法具有較好的收斂性。仿真結(jié)果表明，該算法可以有效地解決非線性多目標(biāo)0－1規(guī)劃問題。

4 結(jié)論

筆者建立了軟件外包中的分包商選擇模型，該模型屬于NP－h(huán)ard問題，目前還沒有有效的算法求解該問題。筆者針對(duì)該模型是0－1規(guī)劃的問題，在粒子群算法中引入遺傳算法的思想，設(shè)計(jì)了遺傳算法和粒子群算法的混合算法(GAPSO)對(duì)模型進(jìn)行求解。算法有效地結(jié)合了智能算法和群智能算法，在運(yùn)算中，既表現(xiàn)出了智能算法的個(gè)體智能(交叉、變異和選擇)，也充分利用了群智能的信息(個(gè)體最優(yōu)和群體最優(yōu))，經(jīng)過仿真計(jì)算，證明了算法可有效地用于解決分包商選擇非線性整數(shù)規(guī)劃模型。為軟件企業(yè)選擇分包商合作開發(fā)軟件項(xiàng)目提供了決策模型支持，具有一定的現(xiàn)實(shí)意義。

［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］黃宜，王長(zhǎng)偉，王艷偉.內(nèi)部信息不對(duì)稱下IT項(xiàng)目外包決策風(fēng)險(xiǎn)測(cè)度［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2010，32(1):125 －128.