基于收益的軟件過程資源調度優化方法

(1.中國科學院 軟件研究所 互聯網軟件技術實驗室， 北京 100080； 2.中國科學院 研究生院， 北京 100049)



摘要：軟件項目管理人員須對軟件過程中的各種資源進行優化調度，但依靠主觀判斷和個人經驗的資源調度方法具有不穩定性和不可靠性，需要提供客觀可靠的軟件過程資源調度方法和工具。基于收益的資源調度優化方法通過對軟件過程的資源調度進行建模，描述和定義投入資源產生的收益，分析軟件過程中活動、資源和收益的各種約束關系，采用基于動態規劃的優化算法以較高效率完成資源調度，使資源在軟件過程中有效利用。

關鍵詞：軟件過程； 資源調度； 過程建模； 過程優化； 動態規劃

中圖分類號：TP311.52文獻標志碼：A

文章編號：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引言

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

我國軟件產業發展于21世紀初，不論產業規模和產業實力均遠遠低于發達國家，軟件企業在計劃的制訂和資源調度等方面大多還是憑借自身的經驗，未能很好地考慮資源的能力及資源的調度問題，致使計劃普遍缺乏精確性，人力、時間、成本等資源的分配難以達到最優化。

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

傳統的資源調度方法通常依靠少數高級開發人員或專家的經驗和技能，根據軟件開發管理人員的主觀判斷來對項目進行決策和對資源進行調度。現代的軟件開發模式要求對軟件過程進行控制、度量和優化，但是由于現代軟件開發過程的復雜程度不斷增加和對資源的需求規模不斷擴大，傳統的資源調度方法已不再適用，它常常得不到最佳的調度結果。因此，需要客觀的量化手段和工具輔助管理人員進行決策，使資源能得到充分利用，使整個項目組織獲得最佳收益。

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

以過程為中心的軟件工程環境（process-centered software engineering environments，PSEE）提供了集成的軟件系統，使軟件過程管理自動化。但是大多數現有的PSEE不能對資源精確定義，限制了軟件過程的資源調度分析和優化，從而影響項目管理和軟件質量^[9]。大部分過程管理技術和工具的計算能力有限，通常只提供被動的項目跟蹤和輔助性項目報告^[10]，缺乏對資源調度的支持。人們希望能有一種適用性較廣的軟件過程資源調度方法，并有自動化的軟件工程環境對其有效支持，從而輔助軟件開發。

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

1軟件過程資源調度優化模型

對軟件過程的資源調度進行量化分析和優化，首先需要對其進行建模。軟件開發模型包括瀑布、演化、增量、噴泉和螺旋等。為了覆蓋多種軟件開發模型，擴大模型的應用范圍，本文提出的模型對軟件過程和資源進行了高度的抽象，定義了過程、資源和收益，并對其相互關系進行分析。通過對該模型的分析可以得到資源和收益間的約束關系，為后面的優化方法提供依據。

11過程定義

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

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

為了簡化模型，著重研究資源在這些活動的優化調度問題，不考慮這些活動之間的依賴關系和時間順序。

12資源定義

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

a)獨占型資源。可以被再次使用，但是不能同時分配給兩個及兩個以上活動的資源，如會議室。

b)可共享資源。可以被再次使用，并且能同時分配給多個活動的資源，如打印機。

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

由于消耗型資源是軟件過程的關鍵因素，本文僅對消耗型資源進行討論。

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

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

不妨認為這些資源相互獨立，一種資源的分配不會影響另一種資源的分配。既然各種資源之間相互獨立，那么可以對這些資源分別計算，即對不同資源逐個分析。首先分析一種資源在所有活動上的最佳分配方式，然后分析另一種資源的最佳分配方式，直到所有資源都已經分配完畢。最后將各種資源的分配方式綜合起來，就可以得到所有資源在所有活動上的最佳分配方式。本文在以下論述中如果沒有特殊說明，均只分析一種資源ri在這些活動的調度，可以簡單地用r表示該資源，M表示該資源的最大分配量。

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

13收益定義

收益是對因資源投入而得到的利益和經濟回報的度量。將某種資源投入到某個活動以后可能對項目產生各種有益的效果，如項目進度加快、軟件質量提高、成本降低。收益正是這些效果在模型中的反映。根據需要，它可以由單個實際項目指標進行衡量，如軟件的缺陷率；可以是多個項目指標的綜合，也可以是根據具體項目實際情況自定義的指標。

收益值可以是來自對歷史項目進行度量而獲得的數據，也可以是由專家給出的經驗數據。在實際項目中，通常將某個項目指標的提高作為因資源投入而獲得的收益，從而可以比較清晰地反映資源投入和項目收益之間的關系。如果資源投入的主要目標是縮短工期，那么可以將工期的縮短時間作為收益；如果目標是降低軟件產品的缺陷率，那么可以將缺陷率的降低作為收益。通常所選擇的指標是評價該項目質量的主要標準或者是項目當前亟待解決的問題。

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

需要指出的是，這里的收益函數是個離散函數，它反映資源和收益各離散值之間的關系。

14過程、資源與收益的關系

為了說明這三者的關系，下面用上述模型來描述一個實際項目。該項目分為a1、a2、a3和a4這四個活動，即A={a1，a2，a3，a4}；項目的可追加資源為人力資源r。目前人力資源r的最大可分配額M為8人/月，這些資源可以用于上述四個活動中，但是不同的分配將產生不同的收益。

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

表1資源分配與收益的函數關系表

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

a112%a322%

a123%a423%

a212%a444%

a235%a456%

a246%

表1的第一列為該軟件項目的所有四個活動，第二列為人力資源r投入不同活動可能的分配量Ii，第三列表示資源在不同活動投入不同的資源分配量時所對應的收益值Ei。

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

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

2軟件過程資源調度優化算法

有多種優化算法可以從數量上求解資源的最優分配策略，本章提出一種基于動態規劃的優化算法。該算法具有較小的時間和空間復雜度，實現比較容易，可應用于或整合到現有的軟件過程資源管理系統中。

21資源調度優化算法分析

由于不考慮活動之間的依賴關系和時間順序，對所有活動進行任意排序，得到活動序列a1，a2，a3，…，ai，…，an。

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

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

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

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

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

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

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

根據上述遞歸式和上一章的實際項目數據，可以構造資源分配最優表如表2所示。

表2資源分配最優表（Q的單位：人/月）

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

下面以計算F4(8)為例，詳細說明該算法的計算過程。根據資源分配與收益的函數關系表（表1）可以得到對應于所有I4的E4（表3）。

表3活動a4的資源分配與收益函數關系表（I4的單位：人/月）

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

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

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

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

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

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

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

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

22資源調度優化算法描述

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

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

3軟件過程資源調度優化系統和應用

根據上一章的優化算法，本文開發的軟件過程資源調度優化系統實現了這種優化策略，可作為軟件組織進行過程控制的輔助工具。該系統采用MVC架構，如圖1所示。

系統分為三層，從下往上分別為model層、controller層和view層。model層由后臺數據庫進行支持，保存活動、資源和收益相關的數據，優化引擎也在該層對這些數據進行分析優化；controller層介于view層與model層之間，溝通兩者的信息流動，使這兩層分離開來；view層可根據實際需要為用戶展現和提供靈活的界面。每一層均分為三個模塊，即活動、資源和收益。在model層的優化引擎是該系統的核心，完成對資源在各活動的優化調度。

活動管理模塊管理軟件過程的各活動，可以增加、編輯和刪除系統中的活動，如圖2所示。該模塊由用戶對系統中的軟件過程活動進行定義，并在后臺數據庫中保存過程定義。

資源管理模塊對軟件過程的各種資源進行管理，可以增加、編輯和刪除資源，如圖3所示。該模塊由用戶將項目的資源導入系統，系統將在后臺數據庫保存資源的種類和數量。

收益管理模塊對軟件過程中資源分配和收益的關系進行管理，如圖4所示。根據專家經驗數據或歷史數據構建資源分配收益表，并在項目開發的實際進展中不斷更新該表，使之反映項目的真實情況。系統根據保存在后臺數據庫中的項目活動、資源和收益等數據對資源調度進行優化，并將優化結果反饋給用戶，如圖5所示。

將該系統用于實際項目管理，項目經理在系統內定義實際項目的過程、資源和收益，并導入相關數據。通過優化算法的計算可以得到理論上的最優資源調度策略，從而輔助和支持客觀可靠的項目管理實踐。

4結束語

為了跟蹤、控制和優化軟件過程，需要對軟件開發所需的資源進行合理調度。本文通過對需要優化資源調度的軟件過程建模，描述和分析軟件過程中活動、資源和收益的各種約束關系，設計一種基于動態規劃的優化算法，使軟件開發過程中的資源得到最佳利用。在面向資源調度的軟件過程優化系統中實現了該方法，并將該系統用于實際項目輔助決策。但是本文提出的模型只是對軟件過程基本共性的抽象，在未來的研究中還需要進一步考慮活動時序、活動前置條件、活動后置條件、資源可替代性等問題。

參考文獻：

［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.