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

在審

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

1.一種基于改進匈牙利算法的軟件開發資源自動調度方法，其特征在于：包括以下步驟，

步驟1，輸入用于參考的各項指標的取值，設第l項指標代價值的取值范圍為0～max，0表示完成某項任務所需代價最低，max表示完成某項任務所需代價最高，n表示任務總數，m表示人員總數，k表示指標項數，n小于m；表示第j位開發人員為完成項目中第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位開發人員為完成項目中第i項分配任務的綜合代價，i＝1,2,...,n，j＝1,2,...,m，計算如下，

$E_{ij}=\underset{l=1}{\overset{k}{\Σ}}{c}_{ij}^l\×p_{li}$

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

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

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

$\min S^x=\underset{i=1}{\overset{n}{\Σ}}\underset{j=1}{\overset{n}{\Σ}}{E}_{ij}^x\×p_{ij}^x$

其中，

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

表示第x代價子矩陣；

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

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

$\min S=\underset{x=1}{\overset{m/n+1}{\Σ}}\min S^x$

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

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