[發明專利]一種基于匈牙利算法的設備調度分配方法

無效

• 申請號: 201310123375.2
• 申請日: 2013-04-10
• 公開（公告）號: CN103235990A
• 公開（公告）日: 2013-08-07
• 發明（設計）人: 祁建;曹震;楊軍
• 申請（專利權）人: 國家電網公司;江蘇省電力公司;江蘇電力信息技術有限公司
• 主分類號: G06Q10/06
• 分類號: G06Q10/06;G06Q50/06;H02J13/00
• 代理公司: 南京匯盛專利商標事務所(普通合伙) 32238
• 代理人: 陳揚

1.一種基于匈牙利算法的設備調度分配方法，其特征在于：該方法通過計算機將各個資源分配給各個任務時的各種影響因素進行加權平均，得到某個資源分配給某個任務時的合適程度，設定資源和任務的數量相等，以此形成任務的資源需求網絡，從而得到最優的設備調度分配方法；具體包括以下步驟：

1）向計算機中輸入數據，建立電網設備資源調度的適應度矩陣M如下：

M=f11f12···f1nf21f22···f2n············fm1fm2···fmn---(1)]]>

設有m個待分配的電網設備資源和n個待完成的調度任務，要求一個資源僅能分配給一個任務，一個任務只能被分配到一個資源，式（1）中f_ij表示把第i（i＝1,2,...,m）個資源分配給第j(j=1,2,...,n)個任務的合適程度；此處m＝n；

2）從適應度矩陣的每行元素中減去該行的最小元素；

3）從適應度矩陣的每列元素中減去該列的最小元素；

4）對只有一個零元素的行，將該行零元素替換為，并將所在列的其他零元素替換為#；對只有一個零元素的列，將該零元素替換為，并將所在行的其他零元素替換為#；

5）對仍存在零元素的行，且同行的零元素至少有兩個，從剩有零元素最少的行開始，比較這行零元素所在列中零元素的數目，選擇列中零元素最少的零元素替換為，然后將其同行同列的其他零元素替換為#；對仍存在零元素的列，且同列的零元素至少有兩個，從剩有零元素最少的列開始，比較這列零元素所在行中零元素的數目，選擇行中零元素最少的零元素替換為，然后將其同列同行的其他零元素替換為#；

6）若的數目l等于矩陣的維數m，轉至步驟14；若l＜m，則轉至步驟7）；

7）對沒有標記的行打√；

8）對已經打對號的行中有#列打√；再對打有√的列中含的行打√；

9）重復步驟8），直到得不出新的打√的行、列為止；

10）對沒有打√的行畫一橫線，對打√的列畫一縱線，得到覆蓋所有零元素的最少直線數；

11）在沒有被直線覆蓋的元素中找出最小元素，并對沒劃直線行的各元素都減去該最小元素，對劃直線列的各元素都加上該最小元素，則得到新矩陣，轉步驟4）；

12）由計算機輸出最優解，得到設備調度分配方法。