文|蘇荨墨
編輯|蘇荨墨
前言
軟體項目過程不是一個嚴格的工程過程，因為排程方案會受到各種動态因素的影響，包括工程師的技能、這些技能的增長以及團隊合作等。
為了解決這個問題，研究人員開發了幾種方法來有效地将員工配置設定給任務，然而，大多數資源受限排程技術關注的是資源的可用性而不是資源生産率，軟體開發人員之間确實存在顯着的生産力差異。
是以，要做出更現實、更合理的進度表，在軟體項目管理中還應考慮學習、進度壓力等生産力因素。
當因素發生變化或狀态對項目不利時，将采取項目控制措施，并且必須修改進度表以适應變化，防止無效的項目控制，這也是項目超預算和進度落後的主要原因，需要精心設計一種高效的重新排程方法，使項目重回正軌。
然而，在排程模型的文獻中沒有充分強調重新排程問題。據我們所知，以前的研究未能充分解釋人類克服軟體項目管理的複雜性和動态性的能力。
軟體項目計劃的改良
一些研究人員比較了啟發式和元啟發式技術在解決資源受限排程問題時的結果，啟發式方法通常是解決大規模問題的首選方法。
從那時起，遺傳算法就被許多研究人員用來研究排程問題及其變體，在軟體項目優化領域，随機搜尋方法也得到了廣泛的應用。
可以找到對基于搜尋的軟體工程近期成就的一般介紹和調查，包括基于搜尋的軟體項目排程，其中 GA 被認為是流行的方法。
由于沒有一種單一的 GA 方法可以始終如一地在所有問題中表現最佳，是以應該針對軟體項目排程問題設計和調整不同的 GA。
我們之前的基于任務的模型可以被認為是在軟體項目管理環境中應用 GA 的早期努力，就像基于時間軸的模型所做的那樣。
将遺傳算法應用于自動化任務配置設定，表明遺傳算法在軟體項目排程方面具有靈活準确的特點，是自動化項目管理的重要工具。
在工作中，使用執行個體生成器進行了深入分析，在軟體項目管理中解決了 48 個不同的項目場景。
模型中很少考慮人力資源因素，為了在現實環境中獲得更好的性能，需要更複雜的模型。最近有一些關于軟體項目排程問題的研究工作。
一種多目标決策支援方法來幫助軟體工程師平衡項目風險和工期與加班，他們進行了大量實驗來證明他們方法的有效性。
提出了一種基于合作共同進化的方法來優化開發人員的團隊人員配置和工作包排程，以實作早期的整體完成時間，這與我們的研究有不同的目标。
以上工作都是處理軟體項目情況下的排程問題。然而，他們都沒有考慮在排程執行期間重新排程問題。
軟體工作在現實中的實作
我們提出的團隊生産力模組化和排程/重新排程優化過程的方法在圖1。
圖1 具有動态因素的軟體項目計劃和重新計劃架構
在這個架構中，“基于GA和HC的排程優化器”是關鍵組成部分，它有助于在項目開始時生成項目進度表，或者在任務團隊成員發生變化或項目執行與計劃之間的差異變大時重新生成進度表。
優化器的輸入包括詳細任務和員工資訊的模型參數、通過模拟實作的每個任務的持續時間以及根據管理目标和控制動作的适應度函數。
“任務和員工模型”包括任務模型（即任務預估工作量、任務懲罰模型和所需任務技能清單等）和員工模型（即技能清單、支付模型等）的靜态部分。
在項目執行之前，“排班優化器”根據計劃任務和配置設定的員工生成初始最優排班，在項目執行期間，将實際項目進度與初始計劃進行比較。
當管理人員采取控制措施時，會重新安排時間并相應地更改模型參數，将進行重新計算以生成剩餘項目的新進度表。
新生成的排程通過考慮穩定性和效率的“重新排程”目标函數進行評估。虛線說明了項目控制活動中涉及的過程。
将進行重新計算以生成剩餘項目的新進度表。新生成的排程通過考慮穩定性和效率的“重新排程”目标函數進行評估，虛線說明了項目控制活動中涉及的過程。
任務在團隊中的生成
任務和員工模型包括有關項目任務和配置設定給該任務的員工的資訊，一個項目被表示為一個任務優先級圖。
一個由一組任務組成的無環有向圖V = { T 1 , T 2 ,…, T n } 其中T k代表項目的任務k ，以及優先級關系P = {( P ij ); i < > j , 1 ≤ i ≤ n , 1 ≤ j ≤ n }, 其中P ij = 1 如果T i必須在T j開始之前完成，否則P ij = 0。
與每個任務Tk相關聯的是估計的工作量、所需技能和截止日期，項目團隊成員E = { E 1 , E 2 ,…, E n } 是項目的資源，其中E代表員工k。
每個Ek _與他/她擁有的一系列技能以及相應的熟練程度、工資率、最大工作量（可以配置設定給他們的工作量的限制）和學習因素（反映他們技能熟練程度提高的因素）相關聯工作期間）。
團隊生産力決定了軟體開發過程中的整體項目績效。圖 2對這個關鍵元件及其相關因素進行模組化。
圖2 團隊生産力模型。
“個人生産力”和“溝通開銷”是影響“團隊生産力”的主要因素，當“個人生産力”受到“日程壓力”、“技能适應度”和“學習”因素的影響。
盡管員工積極性等其他因素對個人生産力也至關重要，但出于展示關鍵概念的目的，我們不會将所有這些因素都包含在本文中。
這些因素也可以由項目經理通過值為 0 或 1 的控制參數打開或關閉來控制。
結合 GA 的全局優化能力和 HC 的局部優化能力，将 GA 與 HC 相結合的混合算法可能是一個理想的選擇根據分塊理論，在遺傳算法計算的初期，由于存在很多高效的小分塊，在交叉算子的作用下，小分塊合并為大分塊的機率很高。
是以，人口素質迅速提高。但是在GA後期，當big block越來越相似的時候，交叉運算符的效率就越來越低了。
那個時候很多個體的素質無法提升很多，導緻後期的遺傳算法效率低下，是以選擇在早期階段使用 GA，然後使用 HC。
我們的優化器的過程在圖 3. 第一步是設定模型的參數，例如 GA 的變異機率、交叉機率、世代數和種群大小。
圖3
然後将任務和員工資訊加載到 GA 中。如果是重排程過程，還需要加載初始排程計劃。在這些初始化步驟之後，GA 運作直到世代數達到先前設定的世代數。HC 從上一代 GA 産生的最佳個體開始，運作得到最優排程。
基因組表征在優化過程中，候選解表示 S 表示為 {A, L}。A 部分是一維任務-員工配置設定數組，存儲從二維任務-員工配置設定數組派生的任務-員工配置設定資訊。
對于配置設定的任務，員工可以在 0%、25%、50%、75% 或 100% 的負荷下工作。例如，50% 的承諾意味着如果員工 1 通常每周工作 40 小時，他每周可以工作 20 小時。
根據任務-員工技能比對生成的“可能”配置設定矩陣，可以将二維任務-員工配置設定數組壓縮為一維數組。例如，在圖 4，兩名員工被配置設定到 6 個任務。
它的任務-員工可能配置設定矩陣是根據他們的技能比對得出的，其中 1 代表可能的配置設定，0 代表沒有可能的配置設定。
由于這個可能的配置設定矩陣總是在初始任務-員工技能比對計算後存儲在模型中，是以可以通過取出不可能的配置設定元素（即“0”元素）将任務-員工配置設定二維數組壓縮為一維數組。
在本例中，任務-員工配置設定一維數組中有 9 個元素，元素順序與任務-員工可能配置設定矩陣中的行順序相同。
第二部分L是優先級清單，通過它可以導出表示排程中任務執行順序的某個拓撲排序向量。
當提出的基于優先級的編碼可以利用任務優先級資訊來決定任務的特定順序。給定有向無環圖 (DAG) G = ( V , E )，拓撲排序是所有頂點的順序，并且對于每個 ( u , v )∈ E，u出現在v之前在名單上。
每個 DAG 可能有不止一種拓撲排序。當有兩個任務競争一個位置時，優先級高的任務獲勝。
例如，對于包含 3 個任務的項目，即T 1到T 3，其中T 1是起始任務，它是T 2和T 3的直接優先級，任務優先級清單示T 3其優先級值為3的優先級高于值為1 的T 2。
拓撲排序 { T 1 , T 3 , T 2} 可以生成滿足任務優先級關系的。在我們的排程問題中直接使用任務順序作為基因組可能會生成不符合 DAG 的無效個體。
但是基于優先級的排序隻處理優先級資訊，這些優先級資訊必須與項目 DAG 資訊結合才能被解釋為項目執行。是以，不會産生無效個體。
遺傳算子為了操縱候選解 S 的兩個結構，選擇以下運算符。初始化算子從可能值（0、0.25、0.50、0.75、1）中随機選擇任意值作為一維任務-員工數組（A）初始種群的等位基因（即個體某屬性的可能設定）。
優先級清單（L）被初始化為從 1 到任務總數的随機順序。當需要重新安排時，首先更新配置檔案發生變化的任務和員工，然後将之前的安排設定為新 GA 計算的初始人口。
S 的交叉算子根據随機數P為複合基因組中的每個基因組調用交叉算子，如中所示圖 5。
圖5
基因組的 A 部分應用标準的單點交叉函數，L 部分使用順序交叉。由于基因組表示的兩個結構是獨立的，并且 1D 數組基因組是從可能配置設定矩陣派生的，後代交叉運算符始終有效。
根據突變機率，随機選擇兩個基因組之一進行實驗如圖所示的突變，圖 6. 在一維數組結構中，我們隻改變某些元素，而某些元素在任務優先級向量中交換。
圖6 适應度函數計算在我們用于軟體項目排程的 GA 方法中，适應度函數計算是最複雜的部分。
結語
通過加載任務-員工配置設定來初始化系統，設定時間機關的個數，從拓撲排序清單中擷取下一個任務；通過驗證所有的來檢查任務是否可以在這個時間機關内開始。
優先任務已經完成，所有員工都可以，所有員工都可以；不超限工作，否則轉；對每項任務進行系統動力學仿真。
在每個任務執行結束時，計算成本、罰款并更新員工的；整體經驗和一定的技能熟練程度；如果所有任務完成，傳回适應度分數；從開始另一個循環，是以這就是 在最終的實驗結果。