[發(fā)明專利]基于改進匈牙利算法的軟件開發(fā)資源自動調度方法及系統

在審

• 申請?zhí)枺?/td>: 201710104538.0
• 申請日: 2017-02-24
• 公開（公告）號: CN106919389A
• 公開（公告）日: 2017-07-04
• 發(fā)明（設計）人: 馬傳香;劉燁;伍蔓;張建升
• 申請（專利權）人: 湖北大學
• 主分類號: G06F9/44
• 分類號: G06F9/44;G06Q10/06
• 代理公司: 武漢科皓知識產權代理事務所(特殊普通合伙)42222
• 代理人: 嚴彥

技術領域

本發(fā)明涉及軟件開發(fā)過程中的資源自動調度領域，尤其是一種利用改進匈牙利算法進行軟件開發(fā)資源自動調度的方法及系統。

背景技術

軟件開發(fā)過程中的任務人員分配問題可視為資源調度問題。資源調度的關鍵在于匹配的最優(yōu)化，而匹配問題是運籌學的重要問題之一，也是圖論的重要內容，它在“人員分配問題”和“最優(yōu)分配問題”中有重要作用。

目前，有關資源調度問題的研究已有很多。0-1調度算法通過0-1變量來數量化事物反映出的離散變量間的邏輯、順序、互斥等關系的約束條件；先來先服務調度算法按照程序進入的先后來分配任務處理優(yōu)先級；優(yōu)先級調度算法分為非搶占式和搶占式兩種，非搶占式優(yōu)先數算法類似于先來先服務調度算法，而搶占式優(yōu)先數算法則僅適用于可中斷類型任務的分配；匈牙利算法通過尋找增廣路徑來求得最優(yōu)匹配。

這些算法在一定程度上解決了任務平衡指派問題，但算法復雜度過高、無法解決軟件開發(fā)過程中的非平衡指派等。針對這個問題，國內外許多學者提出了基于匈牙利算法的改進算法。其中，加邊補零法通過將非平衡代價矩陣做補零處理；加邊補最小值法通過將非平衡代價矩陣做加邊補最小值處理。這兩種算法都是將非平衡指派問題轉化為平衡指派問題后再利用匈牙利算法進行處理。雖然這兩種算法解決了非平衡指派問題與平衡指派問題的轉化，但其分配結果依舊是人員獨占任務，無法滿足軟件開發(fā)過程中人員協作完成某項任務的實際，造成資源浪費，效率低下。

對于非平衡指派問題，相關研究者提出了一種擴展矩陣法，該算法通過將代價矩陣按一定規(guī)則重復擴展，并對擴展后的矩陣進行補零處理，將非平衡指派問題轉化為平衡指派問題后再使用匈牙利算法，該算法可以完成非平衡指派問題與平衡指派問題的轉化，也能夠滿足人員協作完成某項任務的需求。但該算法存在如下問題：對于一些代價矩陣所得出的分配結果中存在某些任務未被分配的問題或者分配結果中人員分配極端的問題。

發(fā)明內容

本發(fā)明針對非平衡人員自動指派問題，提出了一種基于改進匈牙利算法的軟件開發(fā)資源自動調度技術方案。

本發(fā)明技術方案提供一種基于改進匈牙利算法的軟件開發(fā)資源自動調度方法，包括以下步驟，

步驟1，輸入用于參考的各項指標的取值，設第l項指標代價值的取值范圍為0～max，0表示完成某項任務所需代價最低，max表示完成某項任務所需代價最高，n表示任務總數，m表示人員總數，k表示指標項數，n小于m；表示第j位開發(fā)人員為完成項目中第i項分配任務的第l項指標代價值，i＝1,2,...,n，j＝1,2,...m，l＝1,2,...,k；

步驟2，輸入各項指標所占比重，設p_li表示第l項指標在第i項分配任務中的比例，l＝1,2,...,k，i＝1,2,...,n，0＜p_li＜1，

步驟3，計算綜合的代價矩陣，設E_ij代表第j位開發(fā)人員為完成項目中第i項分配任務的綜合代價，i＝1,2,...,n，j＝1,2,...,m，計算如下，

步驟4，縮減代價矩陣，縮減后各行各列都出現至少一個零元素；

步驟5，分割代價矩陣，包括進行多次不同的分割，每次分割的實現方式為，從m列中任取n列組成n×n的矩陣，形成個子矩陣，剩余的補零得到一個n×n大小的子矩陣；

步驟6，對步驟5每次分割結果分別處理，包括對所得個n×n子矩陣分別使用匈牙利算法進行處理，得到各子矩陣的分配方案以及相應代價函數值，計算如下，

其中，

minS^x表示第x子矩陣的函數代價值；

表示第x代價子矩陣；

表示第x代價子矩陣的分配情況；x＝1,2,...,m/n+1；i＝1,2,...,n，j＝1,2,...,n；表示未分配，表示已分配，

步驟7，對步驟5每次分割結果，分別合并個n×n子矩陣分配結果，并將各個子矩陣的函數代價值進行相加得到整個代價矩陣的函數代價值，計算如下，

其中，minS表示總函數代價值，minS^x表示分割矩陣后第x子矩陣的函數代價值；x＝1,2,...,m/n+1)。

步驟8，比較代價函數值，包括通過將每種矩陣分割相應代價函數值進行比較，得出代價函數值最優(yōu)的分配方案，輸出代價函數值最優(yōu)的分配方案以及相應代價函數值。

而且，步驟4中，縮減代價矩陣根據如下公式進行，