基于收益的軟件過(guò)程資源調(diào)度優(yōu)化方法

(1.中國(guó)科學(xué)院 軟件研究所 互聯(lián)網(wǎng)軟件技術(shù)實(shí)驗(yàn)室， 北京 100080； 2.中國(guó)科學(xué)院 研究生院， 北京 100049)



摘要：軟件項(xiàng)目管理人員須對(duì)軟件過(guò)程中的各種資源進(jìn)行優(yōu)化調(diào)度，但依靠主觀判斷和個(gè)人經(jīng)驗(yàn)的資源調(diào)度方法具有不穩(wěn)定性和不可靠性，需要提供客觀可靠的軟件過(guò)程資源調(diào)度方法和工具。基于收益的資源調(diào)度優(yōu)化方法通過(guò)對(duì)軟件過(guò)程的資源調(diào)度進(jìn)行建模，描述和定義投入資源產(chǎn)生的收益，分析軟件過(guò)程中活動(dòng)、資源和收益的各種約束關(guān)系，采用基于動(dòng)態(tài)規(guī)劃的優(yōu)化算法以較高效率完成資源調(diào)度，使資源在軟件過(guò)程中有效利用。

關(guān)鍵詞：軟件過(guò)程； 資源調(diào)度； 過(guò)程建模； 過(guò)程優(yōu)化； 動(dòng)態(tài)規(guī)劃

中圖分類號(hào)：TP311.52文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2008)11-3350-04



Benefit-based approach to resource scheduling optimization in software process



YAN Hai-jian1，2， XIAO Jun-chao1



(1.Laboratory for Internet Software Technologies， Institute of Software， Chinese Academy of Sciences， Beijing 100080， China; 2.Graduate School，Chinese Academy of Sciences， Beijing 100049， China)



Abstract:Resource scheduling in software processes is one of principle challenges in software project management. Resource scheduling based on subjective discretion and personal experiences of project managers is inherently instable and unreliable. In order to control and optimize software processes effectively， an objective and reliable approach to resource scheduling is very helpful. Benefit-based approach to resource scheduling optimization proposed a new model of resource scheduling in software process， described and defined benefits of resource investment， analyzed constraints and relations among activities， resources and benefits. Designed an efficient optimization algorithm derived from dynamic programming， which could be added or integrated into real software engineering environments.

Key words：software process; resource scheduling; process modeling; process optimization; dynamic programming



0引言

軟件開(kāi)發(fā)是一個(gè)集體協(xié)作的復(fù)雜過(guò)程。學(xué)術(shù)界和工業(yè)界的專家和學(xué)者提出各種幫助開(kāi)發(fā)過(guò)程順利進(jìn)行的技術(shù)和方法，目的是提高軟件產(chǎn)品質(zhì)量，保證項(xiàng)目進(jìn)度以及降低成本。基于軟件質(zhì)量和軟件開(kāi)發(fā)過(guò)程質(zhì)量直接相關(guān)的假設(shè)，一個(gè)重要的方向是對(duì)軟件開(kāi)發(fā)的過(guò)程本身進(jìn)行研究和改進(jìn)，該研究領(lǐng)域稱為軟件過(guò)程^[1]。通過(guò)對(duì)軟件過(guò)程進(jìn)行研究，能為評(píng)估、支持和改進(jìn)軟件開(kāi)發(fā)活動(dòng)提供方法和技術(shù)。根據(jù)ISO9000 的定義，過(guò)程就是利用資源將輸入轉(zhuǎn)換為輸出的一組活動(dòng)^[2]。軟件開(kāi)發(fā)過(guò)程實(shí)際上是利用和消耗資源生產(chǎn)軟件產(chǎn)品的過(guò)程。軟件開(kāi)發(fā)過(guò)程中的資源常常是有限的，優(yōu)化資源調(diào)度能明顯地促進(jìn)軟件開(kāi)發(fā)過(guò)程順利進(jìn)行，提高資源投入的收益。如何將這些資源在開(kāi)發(fā)過(guò)程中進(jìn)行合理調(diào)度是對(duì)軟件開(kāi)發(fā)管理人員的一種考驗(yàn)。

我國(guó)軟件產(chǎn)業(yè)發(fā)展于21世紀(jì)初，不論產(chǎn)業(yè)規(guī)模和產(chǎn)業(yè)實(shí)力均遠(yuǎn)遠(yuǎn)低于發(fā)達(dá)國(guó)家，軟件企業(yè)在計(jì)劃的制訂和資源調(diào)度等方面大多還是憑借自身的經(jīng)驗(yàn)，未能很好地考慮資源的能力及資源的調(diào)度問(wèn)題，致使計(jì)劃普遍缺乏精確性，人力、時(shí)間、成本等資源的分配難以達(dá)到最優(yōu)化。

在本文的實(shí)際軟件項(xiàng)目管理中，一個(gè)重要的問(wèn)題是項(xiàng)目延期。在項(xiàng)目后期，為項(xiàng)目成員分配不同的任務(wù)、為各項(xiàng)活動(dòng)投入不同的人力資源，常常在很大程度上影響項(xiàng)目的進(jìn)展。項(xiàng)目經(jīng)理常常根據(jù)其經(jīng)驗(yàn)或直覺(jué)，判斷如何在項(xiàng)目延期時(shí)采取補(bǔ)救措施，投入恰當(dāng)資源來(lái)縮短工期。但這種隨意性的決策方式常常具有較高的代價(jià)，并且無(wú)法保證項(xiàng)目成功進(jìn)行。這里，工期的縮短就是項(xiàng)目需要的收益，本文提出的方法可以通過(guò)對(duì)收益進(jìn)行量化分析，提出優(yōu)化方案供項(xiàng)目經(jīng)理參考，使項(xiàng)目在發(fā)生延期的情況下盡量回到計(jì)劃的軌道上來(lái)。

傳統(tǒng)的資源調(diào)度方法通常依靠少數(shù)高級(jí)開(kāi)發(fā)人員或?qū)＜业慕?jīng)驗(yàn)和技能，根據(jù)軟件開(kāi)發(fā)管理人員的主觀判斷來(lái)對(duì)項(xiàng)目進(jìn)行決策和對(duì)資源進(jìn)行調(diào)度。現(xiàn)代的軟件開(kāi)發(fā)模式要求對(duì)軟件過(guò)程進(jìn)行控制、度量和優(yōu)化，但是由于現(xiàn)代軟件開(kāi)發(fā)過(guò)程的復(fù)雜程度不斷增加和對(duì)資源的需求規(guī)模不斷擴(kuò)大，傳統(tǒng)的資源調(diào)度方法已不再適用，它常常得不到最佳的調(diào)度結(jié)果。因此，需要客觀的量化手段和工具輔助管理人員進(jìn)行決策，使資源能得到充分利用，使整個(gè)項(xiàng)目組織獲得最佳收益。

在實(shí)際項(xiàng)目中，項(xiàng)目經(jīng)理在進(jìn)行資源調(diào)度時(shí)需要基于對(duì)軟件過(guò)程的理解以及對(duì)進(jìn)行中項(xiàng)目的預(yù)測(cè)作出判斷。業(yè)界普遍認(rèn)為，需求和設(shè)計(jì)階段的工作越深入，越能降低后期開(kāi)發(fā)的成本^[3~5]。如果對(duì)資源在各開(kāi)發(fā)階段進(jìn)行更細(xì)致的調(diào)度，則能節(jié)省很大一部分成本^[6]。在不同模塊與不同功能點(diǎn)之間的合理資源調(diào)度常常影響產(chǎn)品能否按期發(fā)布。但是項(xiàng)目經(jīng)理的主觀決策具有不穩(wěn)定性，有研究^[7，8]表明，軟件過(guò)程控制是否適當(dāng)是項(xiàng)目預(yù)算超支和進(jìn)度延遲的主要原因。因此，有效的決策工具能幫助項(xiàng)目經(jīng)理更好地調(diào)度資源。

以過(guò)程為中心的軟件工程環(huán)境（process-centered software engineering environments，PSEE）提供了集成的軟件系統(tǒng)，使軟件過(guò)程管理自動(dòng)化。但是大多數(shù)現(xiàn)有的PSEE不能對(duì)資源精確定義，限制了軟件過(guò)程的資源調(diào)度分析和優(yōu)化，從而影響項(xiàng)目管理和軟件質(zhì)量^[9]。大部分過(guò)程管理技術(shù)和工具的計(jì)算能力有限，通常只提供被動(dòng)的項(xiàng)目跟蹤和輔助性項(xiàng)目報(bào)告^[10]，缺乏對(duì)資源調(diào)度的支持。人們希望能有一種適用性較廣的軟件過(guò)程資源調(diào)度方法，并有自動(dòng)化的軟件工程環(huán)境對(duì)其有效支持，從而輔助軟件開(kāi)發(fā)。

本文提出的優(yōu)化方法通過(guò)分析量化的過(guò)程、資源和收益模型進(jìn)行優(yōu)化計(jì)算，能對(duì)軟件過(guò)程和資源進(jìn)行細(xì)粒度的管理，并且具有良好的可擴(kuò)展性。本文首先對(duì)需要優(yōu)化資源調(diào)度的軟件過(guò)程進(jìn)行抽象，對(duì)投入資源的收益進(jìn)行定義，得到軟件過(guò)程資源調(diào)度優(yōu)化模型，對(duì)該模型進(jìn)行分析和研究，從而提出基于動(dòng)態(tài)規(guī)劃（dynamic programming）的優(yōu)化算法，并對(duì)其進(jìn)行實(shí)現(xiàn)，從而幫助軟件開(kāi)發(fā)人員在軟件過(guò)程中客觀穩(wěn)定地分配資源，優(yōu)化資源調(diào)度，將收益最大化。該方法能應(yīng)用于各種需要資源調(diào)度的軟件過(guò)程中，整合到現(xiàn)有的PSEE中輔助開(kāi)發(fā)人員進(jìn)行決策，減少主觀影響，從控制資源的角度對(duì)軟件過(guò)程進(jìn)行控制和優(yōu)化，幫助軟件組織提升能力成熟度。

1軟件過(guò)程資源調(diào)度優(yōu)化模型

對(duì)軟件過(guò)程的資源調(diào)度進(jìn)行量化分析和優(yōu)化，首先需要對(duì)其進(jìn)行建模。軟件開(kāi)發(fā)模型包括瀑布、演化、增量、噴泉和螺旋等。為了覆蓋多種軟件開(kāi)發(fā)模型，擴(kuò)大模型的應(yīng)用范圍，本文提出的模型對(duì)軟件過(guò)程和資源進(jìn)行了高度的抽象，定義了過(guò)程、資源和收益，并對(duì)其相互關(guān)系進(jìn)行分析。通過(guò)對(duì)該模型的分析可以得到資源和收益間的約束關(guān)系，為后面的優(yōu)化方法提供依據(jù)。

11過(guò)程定義

由于PSEE在資源調(diào)度管理上的不足，軟件組織常常依靠傳統(tǒng)的項(xiàng)目管理工具來(lái)輔助決策。但是軟件過(guò)程具有區(qū)別于傳統(tǒng)項(xiàng)目的特殊性，包括：a)管理人員很難提前對(duì)軟件過(guò)程進(jìn)行精確定義，常常反復(fù)進(jìn)行過(guò)程建模和過(guò)程執(zhí)行；b)開(kāi)發(fā)人員的特性和能力（如個(gè)人技能和項(xiàng)目經(jīng)驗(yàn)）常常是軟件過(guò)程順利與否的重要因素；c)軟件過(guò)程內(nèi)在的動(dòng)態(tài)性會(huì)影響資源調(diào)度。管理人員需要根據(jù)當(dāng)前的項(xiàng)目進(jìn)展和突發(fā)事件對(duì)資源重新分配，所以資源分配策略還需考慮軟件過(guò)程的執(zhí)行情況（如當(dāng)項(xiàng)目延期時(shí)可能需要采取特殊的分配策略）。因此，在考慮資源調(diào)度時(shí)，軟件過(guò)程的定義必須有足夠的靈活性，可以根據(jù)需要及時(shí)調(diào)整。

定義1為軟件過(guò)程定義一個(gè)活動(dòng)集A={a1，a2，a3，…，ai，…，an}表示該軟件過(guò)程包含n個(gè)活動(dòng)。

為了簡(jiǎn)化模型，著重研究資源在這些活動(dòng)的優(yōu)化調(diào)度問(wèn)題，不考慮這些活動(dòng)之間的依賴關(guān)系和時(shí)間順序。

12資源定義

資源是軟件開(kāi)發(fā)過(guò)程的核心要素，包括人力、設(shè)備和時(shí)間、資金等。軟件開(kāi)發(fā)過(guò)程使用和消耗大量的資源，Reis等人^[9]將軟件過(guò)程所需資源分為以下三類：

a)獨(dú)占型資源。可以被再次使用，但是不能同時(shí)分配給兩個(gè)及兩個(gè)以上活動(dòng)的資源，如會(huì)議室。

b)可共享資源。可以被再次使用，并且能同時(shí)分配給多個(gè)活動(dòng)的資源，如打印機(jī)。

c)消耗型資源。不能被再次使用的資源，如財(cái)務(wù)資源、人力資源等。

由于消耗型資源是軟件過(guò)程的關(guān)鍵因素，本文僅對(duì)消耗型資源進(jìn)行討論。

定義2項(xiàng)目可分配的資源集R={r1，r2，r3，…，ri，…，rk}表示該項(xiàng)目共有k種的消耗型資源。

定義3第i種資源ri的屬性元組為(Ti，Mi)。其中：Ti表示資源ri的類型；Mi表示資源ri的最大分配量。

不妨認(rèn)為這些資源相互獨(dú)立，一種資源的分配不會(huì)影響另一種資源的分配。既然各種資源之間相互獨(dú)立，那么可以對(duì)這些資源分別計(jì)算，即對(duì)不同資源逐個(gè)分析。首先分析一種資源在所有活動(dòng)上的最佳分配方式，然后分析另一種資源的最佳分配方式，直到所有資源都已經(jīng)分配完畢。最后將各種資源的分配方式綜合起來(lái)，就可以得到所有資源在所有活動(dòng)上的最佳分配方式。本文在以下論述中如果沒(méi)有特殊說(shuō)明，均只分析一種資源ri在這些活動(dòng)的調(diào)度，可以簡(jiǎn)單地用r表示該資源，M表示該資源的最大分配量。

定義4資源r在活動(dòng)ai的資源分配量為Ii，顯然0≤Ii≤M，并且∑1≤i≤nIi≤M，即資源在所有活動(dòng)上的分配量之和小于該資源的最大可分配量。

13收益定義

收益是對(duì)因資源投入而得到的利益和經(jīng)濟(jì)回報(bào)的度量。將某種資源投入到某個(gè)活動(dòng)以后可能對(duì)項(xiàng)目產(chǎn)生各種有益的效果，如項(xiàng)目進(jìn)度加快、軟件質(zhì)量提高、成本降低。收益正是這些效果在模型中的反映。根據(jù)需要，它可以由單個(gè)實(shí)際項(xiàng)目指標(biāo)進(jìn)行衡量，如軟件的缺陷率；可以是多個(gè)項(xiàng)目指標(biāo)的綜合，也可以是根據(jù)具體項(xiàng)目實(shí)際情況自定義的指標(biāo)。

收益值可以是來(lái)自對(duì)歷史項(xiàng)目進(jìn)行度量而獲得的數(shù)據(jù)，也可以是由專家給出的經(jīng)驗(yàn)數(shù)據(jù)。在實(shí)際項(xiàng)目中，通常將某個(gè)項(xiàng)目指標(biāo)的提高作為因資源投入而獲得的收益，從而可以比較清晰地反映資源投入和項(xiàng)目收益之間的關(guān)系。如果資源投入的主要目標(biāo)是縮短工期，那么可以將工期的縮短時(shí)間作為收益；如果目標(biāo)是降低軟件產(chǎn)品的缺陷率，那么可以將缺陷率的降低作為收益。通常所選擇的指標(biāo)是評(píng)價(jià)該項(xiàng)目質(zhì)量的主要標(biāo)準(zhǔn)或者是項(xiàng)目當(dāng)前亟待解決的問(wèn)題。

定義5收益Ei表示當(dāng)資源r在活動(dòng)ai的資源分配量為Ii時(shí)的收益值，即Ei實(shí)際上是活動(dòng)ai和資源分配量Ii的函數(shù)。在活動(dòng)ai上投入不同的資源分配量Ii可以得到不同的Ei，Ei=f(Ii，ai)。其中Ii≤M，ai∈A。那么，資源r的總收益E是其在各活動(dòng)收益值的總和，即E=∑1≤i≤nEi。其中∑1≤i≤nIi≤M。其目的是為資源r找到一種最佳的分配方式，使E取得最大值。

需要指出的是，這里的收益函數(shù)是個(gè)離散函數(shù)，它反映資源和收益各離散值之間的關(guān)系。

14過(guò)程、資源與收益的關(guān)系

為了說(shuō)明這三者的關(guān)系，下面用上述模型來(lái)描述一個(gè)實(shí)際項(xiàng)目。該項(xiàng)目分為a1、a2、a3和a4這四個(gè)活動(dòng)，即A={a1，a2，a3，a4}；項(xiàng)目的可追加資源為人力資源r。目前人力資源r的最大可分配額M為8人/月，這些資源可以用于上述四個(gè)活動(dòng)中，但是不同的分配將產(chǎn)生不同的收益。

該項(xiàng)目當(dāng)前的主要目標(biāo)是降低缺陷率，將人力資源r追加到各個(gè)活動(dòng)可以降低最終軟件產(chǎn)品的缺陷率，因此將缺陷率的降低作為收益。根據(jù)專家給出的經(jīng)驗(yàn)數(shù)據(jù)，如果將1人/月的人力資源投入活動(dòng)a1，可以使缺陷率降低2%，如果將2人/月的人力資源投入活動(dòng)a1，可以降低3%；如果將1人/月的人力資源投入a2，可以降低缺陷率2%，投入3人/月于a2，則降低5%，投入4人/月于a2，則降低6%；等等。從而可以將人力資源（資源）和缺陷率降低（收益）之間的離散函數(shù)關(guān)系列于表1。

表1資源分配與收益的函數(shù)關(guān)系表

A資源分配量Ii/人/月收益值EiA資源分配量Ii/人/月收益值Ei

a112%a322%

a123%a423%

a212%a444%

a235%a456%

a246%

表1的第一列為該軟件項(xiàng)目的所有四個(gè)活動(dòng)，第二列為人力資源r投入不同活動(dòng)可能的分配量Ii，第三列表示資源在不同活動(dòng)投入不同的資源分配量時(shí)所對(duì)應(yīng)的收益值Ei。

在該實(shí)際項(xiàng)目中，這些數(shù)據(jù)完全是由專家給出的經(jīng)驗(yàn)數(shù)據(jù)。表格沒(méi)有列出所有可能的資源分配量，對(duì)于表中沒(méi)有列出來(lái)的資源分配量X，其收益值默認(rèn)取表內(nèi)所有可能收益值的最大值，即表內(nèi)所有小于X的資源分配量對(duì)應(yīng)的收益值的最大值。如果表格中沒(méi)有資源分配量小于X，則其收益取0。例如對(duì)于活動(dòng)a4，只列出了資源分配量I4分別等于2、4和5時(shí)的情況，而沒(méi)列出等于0、1、3、6、7和8時(shí)的情況（M = 8，所以I4≤8），那么對(duì)于I4 = 6，其E4取表內(nèi)已有的小于6的I4對(duì)應(yīng)的E4的最大值，即6%；同樣，對(duì)于I4=7和I4=8，表內(nèi)已有小于7的I4對(duì)應(yīng)的E4的最大值也為6%；對(duì)于I4=3，表內(nèi)小于3的I4對(duì)應(yīng)的E4的最大值為3%；但對(duì)于I4=1，由于表內(nèi)沒(méi)有小于1的I4，其E4=0。最終，人力資源r得到的總收益E=E1+E2+E3+E4，并且滿足I1+I2+I3+I4≤M。

但由于資源有限，M=8，即最多可分配的人力資源只有8人/月，對(duì)這8人/月人力資源的不同分配將產(chǎn)生不同的收益，即不同的缺陷率下降程度。如果令I(lǐng)1=1，I2=1，I3=2，I4=4，那么可獲得收益值為2%+2%+2%+4%=10%；如果令I(lǐng)1=1，I2=3，I3=2，I4=2，那么可獲得收益值為2%+5%+2%+3%=12%。共有165種不同分配方式，同樣可以計(jì)算得到其他分配方式的收益值，可知12%是用8人/月人力資源所能獲得的最優(yōu)結(jié)果。其目的是優(yōu)化人力資源的調(diào)度，使得最終降低的缺陷率最大。但根據(jù)資源和收益的函數(shù)關(guān)系并不能直接得到最佳分配策略，下一章提出一種優(yōu)化算法，根據(jù)已有資源分配和收益的函數(shù)關(guān)系表以較高的效率找到最優(yōu)解。

2軟件過(guò)程資源調(diào)度優(yōu)化算法

有多種優(yōu)化算法可以從數(shù)量上求解資源的最優(yōu)分配策略，本章提出一種基于動(dòng)態(tài)規(guī)劃的優(yōu)化算法。該算法具有較小的時(shí)間和空間復(fù)雜度，實(shí)現(xiàn)比較容易，可應(yīng)用于或整合到現(xiàn)有的軟件過(guò)程資源管理系統(tǒng)中。

21資源調(diào)度優(yōu)化算法分析

由于不考慮活動(dòng)之間的依賴關(guān)系和時(shí)間順序，對(duì)所有活動(dòng)進(jìn)行任意排序，得到活動(dòng)序列a1，a2，a3，…，ai，…，an。

定義6資源r投入到前i個(gè)活動(dòng)的資源分配量總和為Qi，如Q3表示資源r投入到a1、a2和a3的資源分配量總和。

定義7函數(shù)Fi (Q)表示當(dāng)資源r投入前i個(gè)活動(dòng)的資源分配量總和為Q時(shí)所能得到的最佳收益，如F3 (Q)表示當(dāng)資源r投入a1、a2和a3的資源分配量總和為Q時(shí)能得到的最佳收益。

如果資源r投入a1的資源分配量為Q1，那么可以得到最佳收益F1(Q1)等于所有滿足I1≤Q1的I1對(duì)應(yīng)的E1的最大值，即

F1(Q1)=maxI1≤Q1(E1)

為了得到Fi(Qi)，先證明以下結(jié)論：

結(jié)論1如果資源r投入前i個(gè)活動(dòng)，a1，a2，…，ai的資源分配量總和Qi，按照某種最優(yōu)資源分配方式取得最佳收益Fi(Qi)，并在這種分配方式下投入ai的資源分配量為Ii，獲取收益Ei，那么投入前i-1個(gè)活動(dòng)，即a1，a2，…，ai-1的資源分配量總和為Qi-Ii。可以證明在該分配方式下對(duì)此Qi-Ii資源量在前i-1個(gè)活動(dòng)的分配也必然是一種最佳分配，并取得最佳收益Fi-1(Qi-Ii)。

證明假設(shè)該分配方式對(duì)此Qi-Ii資源量在前i-1個(gè)活動(dòng)的分配不是最優(yōu)的，僅取得收益F′，且F′＜Fi-1(Qi-Ii)，那么一定存在一種最優(yōu)分配方式，使此Qi-Ii在前i-1個(gè)活動(dòng)的分配取得最佳收益Fi-1(Qi-Ii)，從而產(chǎn)生對(duì)所有這j個(gè)活動(dòng)的新的分配方式，并獲得更大的收益Fi-1(Qi-Ii)+Ei。由于Fi(Qi)=F′+Ei＜Fi-1(Qi-Ii)+Ei，這與Fi(Qi)的定義，即Fi(Qi)是最佳收益相矛盾。因此，原來(lái)對(duì)這Qi-Ii在前i-1個(gè)活動(dòng)的分配也必然是一種最佳分配，并且取得最佳收益Fi-1(Qi-Ii)。可以得到下列遞歸關(guān)系：

根據(jù)上述遞歸式和上一章的實(shí)際項(xiàng)目數(shù)據(jù)，可以構(gòu)造資源分配最優(yōu)表如表2所示。

表2資源分配最優(yōu)表（Q的單位：人/月）

表2列出所有可能的Fi(Q)，從表中可以看出F4(8)的值為12%，這表示如果將8人/月的人力資源r分配到所有四個(gè)活動(dòng)可以得到最高收益為12%，即最多降低12%的缺陷率。該表的構(gòu)造是逐行進(jìn)行的，除了計(jì)算F1(Q)以外，計(jì)算Fi(Q)需要先計(jì)算Fi-1(Q)，而在計(jì)算Fi(Q)時(shí)所有的Fi-1(Q)都已計(jì)算完畢，因而可以據(jù)此設(shè)計(jì)效率較高的算法。

下面以計(jì)算F4(8)為例，詳細(xì)說(shuō)明該算法的計(jì)算過(guò)程。根據(jù)資源分配與收益的函數(shù)關(guān)系表（表1）可以得到對(duì)應(yīng)于所有I4的E4（表3）。

表3活動(dòng)a4的資源分配與收益函數(shù)關(guān)系表（I4的單位：人/月）

定義8ai固定的條件最佳收益為在資源分配總量不變以及對(duì)ai的資源投入不變的條件下所能得到的最佳收益。現(xiàn)在投入前四個(gè)活動(dòng)的資源分配量總和為8人/月，即Q4=8人/月，這8人/月資源在活動(dòng)a4和剩下三個(gè)活動(dòng)a1、a2和a3的不同分配方式可以得到不同的最佳收益，即不同的a4固定的條件最佳收益。

a)如果取Q4=8人/月中的0人/月用于a4，E4=0%，剩下8人/月用于a1、a2和a3，又因?yàn)镕3(8)=11%，所以這種分配方式a4固定的條件最佳收益為E4+F3(8)=0+11%=11%；

b)如果取Q4=8人/月中的1人/月用于a4，E4=0，剩下7人/月用于a1、a2和a3，又因?yàn)镕3(7)=10%，所以這種分配方式a4固定的條件最佳收益為E4+F3(7)=0+10%=10%；

c)如果取Q4=8人/月中的2人/月用于a4，E4=3%，剩下6人/月用于a1、a2和a3，又因?yàn)镕3(6)=9%，所以這種分配方式a4固定的條件最佳收益為E4+F3(6)=3%+9%=12%。

依此類推，可得a4固定的條件最佳收益表（表4）。

表4a4固定的條件最佳收益表（I4的單位：人/月）

從表4可以看出，當(dāng)取Q4=8人/月中的2人/月用于a4，剩下6人/月用于a1、a2和a3時(shí)，取得最佳收益F4(8)=12%。該調(diào)度策略可以僅僅針對(duì)部分資源和部分活動(dòng)而言，因此稱為局部最優(yōu)資源調(diào)度策略。

局部最優(yōu)資源調(diào)度策略是算法重建整體最優(yōu)資源調(diào)度策略的直接依據(jù)，因此需要將這些信息保存在最優(yōu)資源分配重建表(表5)。表內(nèi)的Ii表示在Qi已知的情況下，對(duì)ai的資源分配量為Ii時(shí)能取得的最佳收益Fi，這樣，根據(jù)表5可以對(duì)資源在各個(gè)活動(dòng)的最優(yōu)分配方案進(jìn)行重建。

22資源調(diào)度優(yōu)化算法描述

得相應(yīng)最佳收益時(shí)該行新增活動(dòng)的資源分配量Ii；activities是包含該軟件過(guò)程所有活動(dòng)的數(shù)組；方法E()是活動(dòng)的資源收益函數(shù)，根據(jù)資源分配量返回相應(yīng)的收益Ei；代碼行1完成對(duì)資源分配最優(yōu)表table初始化，將重建表的0行置零；代碼行2~12對(duì)資源分配最優(yōu)表逐行進(jìn)行計(jì)算；代碼行3的循環(huán)實(shí)際是對(duì)每行進(jìn)行逐列計(jì)算，allowed_res的每個(gè)值對(duì)應(yīng)一列。

還需注意到，該算法具有使資源向軟件過(guò)程后端聚集的特性，即如果不同的分配方式均能獲得相同的收益，則選擇越早的活動(dòng)占用越少的資源的分配方式，從而使資源保留到項(xiàng)目開(kāi)發(fā)后期，進(jìn)一步保證軟件過(guò)程順利進(jìn)行。

3軟件過(guò)程資源調(diào)度優(yōu)化系統(tǒng)和應(yīng)用

根據(jù)上一章的優(yōu)化算法，本文開(kāi)發(fā)的軟件過(guò)程資源調(diào)度優(yōu)化系統(tǒng)實(shí)現(xiàn)了這種優(yōu)化策略，可作為軟件組織進(jìn)行過(guò)程控制的輔助工具。該系統(tǒng)采用MVC架構(gòu)，如圖1所示。

系統(tǒng)分為三層，從下往上分別為model層、controller層和view層。model層由后臺(tái)數(shù)據(jù)庫(kù)進(jìn)行支持，保存活動(dòng)、資源和收益相關(guān)的數(shù)據(jù)，優(yōu)化引擎也在該層對(duì)這些數(shù)據(jù)進(jìn)行分析優(yōu)化；controller層介于view層與model層之間，溝通兩者的信息流動(dòng)，使這兩層分離開(kāi)來(lái)；view層可根據(jù)實(shí)際需要為用戶展現(xiàn)和提供靈活的界面。每一層均分為三個(gè)模塊，即活動(dòng)、資源和收益。在model層的優(yōu)化引擎是該系統(tǒng)的核心，完成對(duì)資源在各活動(dòng)的優(yōu)化調(diào)度。

活動(dòng)管理模塊管理軟件過(guò)程的各活動(dòng)，可以增加、編輯和刪除系統(tǒng)中的活動(dòng)，如圖2所示。該模塊由用戶對(duì)系統(tǒng)中的軟件過(guò)程活動(dòng)進(jìn)行定義，并在后臺(tái)數(shù)據(jù)庫(kù)中保存過(guò)程定義。

資源管理模塊對(duì)軟件過(guò)程的各種資源進(jìn)行管理，可以增加、編輯和刪除資源，如圖3所示。該模塊由用戶將項(xiàng)目的資源導(dǎo)入系統(tǒng)，系統(tǒng)將在后臺(tái)數(shù)據(jù)庫(kù)保存資源的種類和數(shù)量。

收益管理模塊對(duì)軟件過(guò)程中資源分配和收益的關(guān)系進(jìn)行管理，如圖4所示。根據(jù)專家經(jīng)驗(yàn)數(shù)據(jù)或歷史數(shù)據(jù)構(gòu)建資源分配收益表，并在項(xiàng)目開(kāi)發(fā)的實(shí)際進(jìn)展中不斷更新該表，使之反映項(xiàng)目的真實(shí)情況。系統(tǒng)根據(jù)保存在后臺(tái)數(shù)據(jù)庫(kù)中的項(xiàng)目活動(dòng)、資源和收益等數(shù)據(jù)對(duì)資源調(diào)度進(jìn)行優(yōu)化，并將優(yōu)化結(jié)果反饋給用戶，如圖5所示。

將該系統(tǒng)用于實(shí)際項(xiàng)目管理，項(xiàng)目經(jīng)理在系統(tǒng)內(nèi)定義實(shí)際項(xiàng)目的過(guò)程、資源和收益，并導(dǎo)入相關(guān)數(shù)據(jù)。通過(guò)優(yōu)化算法的計(jì)算可以得到理論上的最優(yōu)資源調(diào)度策略，從而輔助和支持客觀可靠的項(xiàng)目管理實(shí)踐。

4結(jié)束語(yǔ)

為了跟蹤、控制和優(yōu)化軟件過(guò)程，需要對(duì)軟件開(kāi)發(fā)所需的資源進(jìn)行合理調(diào)度。本文通過(guò)對(duì)需要優(yōu)化資源調(diào)度的軟件過(guò)程建模，描述和分析軟件過(guò)程中活動(dòng)、資源和收益的各種約束關(guān)系，設(shè)計(jì)一種基于動(dòng)態(tài)規(guī)劃的優(yōu)化算法，使軟件開(kāi)發(fā)過(guò)程中的資源得到最佳利用。在面向資源調(diào)度的軟件過(guò)程優(yōu)化系統(tǒng)中實(shí)現(xiàn)了該方法，并將該系統(tǒng)用于實(shí)際項(xiàng)目輔助決策。但是本文提出的模型只是對(duì)軟件過(guò)程基本共性的抽象，在未來(lái)的研究中還需要進(jìn)一步考慮活動(dòng)時(shí)序、活動(dòng)前置條件、活動(dòng)后置條件、資源可替代性等問(wèn)題。

參考文獻(xiàn)：

［1］FUGGETTA A. Software process: a roadmap[C]//Proc of Confe-rence onFuture of Software Engineering. New York:ACM Press，2000:25-34.

[2]ISO.ISO/FDIS 9000， Quality management systems-fundamentals and vocabulary[S]. 2005.

[3]BOEHM B， HOROWITZ E， MADACHY R， et at. Resources software cost estimation with COCOMO II[M]. New Jersey: Prentice-Hall， 2000.

[4]POTTER B， SINCLAIR J， TILL D. An introduction to formal specification and Z[M]. 2nd ed. London: Pearson Education Limited， 1996.

[5]CHULANI S， STEECE B， BOEHM B. Determining software quality using COQUALMO[M]//BLISCHKE W， MURTHY D. Case Studies in Reliability and Maintenance.Hoboken: Wiley， 2002.

[6]YIFTACHEL P， PELED D， HADAR I， et al. Resource allocation among development phases: an economic approach[C]//Proc ofInternational Workshop on Economics Driven Software Engineering Research. New York:ACM Press， 2006:43-48.

[7]LEDERER A L， PRASAD J. Causes of inaccurate software development cost estimates[J]. Journal of Systems Software，1995，31(2):125-134.

[8]SUKHODOLSKY J. Optimizing software process control[J]. ACM SIGSOFT Software Engineering Notes， 2001，26(2):59-63.

[9]REIS C L， REIS R Q， SCHLEBBE H， et al. A policy-based resource instantiation mechanism to automate software process management[C]//Proc of the 14th International Conference on Software Engineering and Knowledge Engineering. New York: ACM Press，2002:795-802.

[10]CHANG C K， CHRISTENSEN M J， ZHANG Tao. Genetic algorithms for project management[J]. Annals of Software Engineering， 2001，11(1):107-139.