基于負荷均衡的工作中心任務組合優化分配 (上)

于曉義 吳 毅 王達達 楊 昆

(1.云南電力試驗研究院 (集團)有限公司電力研究院，云南 昆明 650217;2.西北工業大學系統集成與工程管理研究所，陜西 西安 710072)

1 前言

云南電網公司電力研究院具有人員學歷水平較高、容易掌握和接受新的管理思想和方法、有強大的軟件開發團隊、有與云南電網公司生產管理信息系統同平臺、同架構設計開發的生產MIS系統等特點。基于上述云南電網公司信息化發展的大環境與云南電力研究院的基礎與特點，選定云南電力研究院作為云南電網公司ERP項目試點單位。

通過前期調研發現，隨著業務的發展，電力研究院目前存在的問題的根源為資源的沖突與協調。其主要表現在資源調配、項目管理、人員發展三個方面。

在資源調配方面:多頭管理現象突出，人員安排經常出現沖突;缺乏全局性資源調配機制和計劃，資源未能得到最優配置，利用率低，造成“準備的資源不用，要用的資源不在”現象;資源控制未和現場實際情況緊密結合起來，造成有限資源并未用在關鍵的、合適的、亟須的環節，資源負荷不均;資源過程管理粗放，追蹤困難，無法細化工時/標準費率定額以指導資源的精細化管理。

在項目管理方面:主要原因是資源管理與項目計劃管理協作松散，因人員緊張導致項目質量難以保證，影響客戶滿意度;對項目人員的時間成本缺乏精細化的控制與管理。

在人員發展方面:員工數量難以滿足快速發展的業務需求，核心員工勞動強度大;缺乏系統性的員工職業發展規劃與輔導機制，員工職業發展受限。

綜上所述，云南電網公司電力研究院在資源優化配置方面已提出了迫切的需求，亟須在資源優化配置方面取得突破，建立面向電力生產技術監督、技術服務和科研開發的全業務的資源優化配置平臺，保證業務工作的實時緊密協作，保證生產任務的均衡、生產計劃的可執行性、資源的高利用率、項目交付的客戶滿意度，為電網安全、穩定、經濟運行提供技術保障。

2 工作中心協同任務分配問題描述

在電力研究院服務型企業運作境下，企業接收的訂單按WBS分解成相互關聯的任務，由傳統的每個任務有指定的承接專業所，轉變為每個任務根據其特點可以有多個可選的承接工作中心，在此條件下產生了多工作中心的負荷均衡優化問題。工作中心任務分配的本質是任務與工作中心資源的映射。

由于任務是按照WBS分解的，所以任務之間的關聯關系呈現出一種樹狀結構，用一個無向圖GT(V，E)描述任務之間的關聯(見圖(1);頂點|V|=N表示待分配的N個任務，用ωi表示任務i的完成周期;邊E表示兩個任務之間的關聯，用eij表示邊(i，j)∈E連接的兩個任務i與j由不同工作中心完成時的協作消耗工時。

用一個無向完全圖GP(P，D)描述K個工作中心的關聯關系(見圖(2)，dpq表示邊(p，q)∈D連接的兩個工作中心p與q的單位協作成本。

設每個任務在K個工作中心中能且只能被分配一次。

式1，2分別表示各工作中心的負荷與企業的協作成本。

其中，M(i)表示任務i的承接工作中心，如M(i)=p表示任務i被分配給工作中心p。式1中Loadp表示工作中心p的負荷，即所有分配到p的任務i所消耗的資源ωi之和。式2中，當任務i與j被分配到不同的工作中心，即M(i)≠M(j)時才產生協作成本。協作任務i與j被分配到工作中心M(i)=p與M(j)=q產生的協作成本為:任務i與j的協作消耗工時eij乘以不同的承接工作中心p與q的單位協作成本dpq。

圖1、2給出了一個多工作中心任務分配問題的示例。圖1描述了一個N=20個任務的無向圖GT，圖2給出了K=5個工作中心的關聯關系圖GP。圖中圓圈中的數字分別代表任務與工作中心編號。圖1中頂點與邊上的數字分別代表任務的完成周期與協作消耗工時。圖2中邊上的數字代表兩工作中心的單位協作成本。表1給出了一個關于圖1、2的任務分配方案。

圖1 任務關聯圖GT

圖2 工作中心關聯圖GP

表1 分配方案示例表

采用一個K×N的任務資源匹配矩陣描述任務與資源的匹配狀態。矩陣的元素spi，代表任務i分配到工作中心p的概率值。因此spi的取值區間為［0，1］，并且每一列的和為1。spi的初始值在滿足任務特性要求時取為為任務i的可選承接工作中心數量)，否則取為0。當最終分配方案被獲得時，spi趨近于0或1，spi=1是指任務i被分配給工作中心p。

表2、表3分別顯示了與圖1、2示例相關的任務資源匹配矩陣初始狀態和一個分配方案狀態的任務資源匹配矩陣，不失一般性取

表2 任務資源匹配矩陣初始狀態

表3 分配方案狀態的任務資源匹配矩陣

目標函數如式3所示，目的是平衡各工作中心的負荷 (式1)，同時最小化企業的協作成本(式2)。

eij:任務i與任務j的協作交互量(通常用協作消耗工時度量);

ωi:任務i的資源消耗量(通常用任務完成周期表示);

dpq:工作中心p與工作中心q的單位協作成本;

spi:任務i被分配給工作中心p的概率;

Cp:工作中心p的能力總和。

從式3可以看出目標函數由兩部分組成。第一部分表示當任務i與任務j分別被分配到不同的工作中心p與q時的協作成本，因此當協作交互量大的兩個任務都被分配到同一工作中心完成時，第一部分協作成本取得最小值。第二部分是一個平方和函數，它是每個工作中心的能力利用率與滿負荷的差值的平方和函數，在各個工作中心的負荷分配均勻時該函數取最小值。由于第一部分與第二部分都要求極小化，在式3中未采用權重累加的方式合成目標函數，而是采用乘積的方式，這樣更能體現每一部分對目標函數影響的敏感性。

3 基于IA的協作優化分配算法

免疫算法是模仿生物免疫系統處理機理和基因進化機理，通過人工方式構造的一類全局尋優搜索算法。盡管免疫系統具有許多優良的計算性能，但現有免疫算法模型仍存在一些問題，主要在抗體的評價形式、抗體的促進和抑制以及記憶庫的使用上。抗體評價主要依據抗體與抗原的親和度，促進高親和度抗體和抑制低親和度抗體，往往易陷入局部優化，導致“早熟”。并且，記憶庫僅在產生初始種群時被使用，在算法以后的過程中僅更新記憶庫而不再利用它，這沒有起到加速收斂的效果。葛紅等對免疫算法進行了改進，根據期望繁殖率對抗體降序排列，然后一次性消除期望繁殖率低的抗體，試驗表明收斂速度有所提高，但這會使不少較優抗體被一塊消除，不利于有效提高收斂速度。針對現有免疫算法的不足，提出了基于動態任務資源匹配矩陣的免疫算法，其主要流程見圖3。

免疫進化時首先進行抗原識別，分析問題及解的特性并進行抗體編碼，本文采用K進制編碼，對參與協同工作的工作中心資源按1，2，…，K進行編碼，抗體長度為任務數N。若抗體第i個基因位對應的值為p，則表示任務i被分配到工作中心p進行生產加工。此編碼直觀，易于操作，且不需解碼。抗體編碼樣例見表1。

免疫進化過程中，首先根據任務資源匹配初始矩陣隨機產生規模為popsize的初始抗體群體antiby(t)。抗體群體根據抗體繁殖率進行免疫選擇，高繁殖率的抗體(優化解)被促進，低繁殖率的抗體(非優解)被抑制。通過促進/抑制抗體的進化，既突出適者生存，又防止個別個體絕對占優，實現免疫系統的動態平衡自調節功能。接著，在這些必要、有效的抗體群體基礎上進行免疫操作。經過免疫操作進行免疫進化后，將會產生免疫接種抗體種群antiby_v、交叉克隆的抗體種群antiby_c、親和突變的抗體種群antiby_m，以及募集的新的抗體種群antiby_n，將這些免疫種群與記憶的較優抗體種群antiby_o合并，生成下一代免疫進化的抗體種群antiby(t+(1)。再在此進化基礎上循環進化，直到滿足進化的終止條件，輸出免疫進化的結果。

圖3 基于動態任務資源匹配矩陣的免疫算法流程

3.1 抗體的評價與選擇

免疫進化過程中，需要對各抗體進行評價。如果以抗體的適應度為評價指標，當群體中的某個抗體占據了相當規模，而又不是最優解時就極易導致過早收斂。采用抗體濃度來抑制規模較大又不是最優解的抗體，并以信息熵作為衡量相似度的指標，以期望繁殖率作為評價抗體的標準。抗體的繁殖率計算如下:

式中，fit(v):抗體的適應度;F(v):將抗體v作為分配方案代入目標函數式3時對應的函數值;cv:抗體濃度;λac:親和度閥值;axv，w:抗體 v與抗體w之間的親和度;H(2):抗體v和抗體w的信息熵，兩抗體所有基因都相同時，H(2)=0;N:抗體的基因長度，即為待分配任務數;Hi(2):兩個抗體第i個基因位的信息熵;K＇i:第i個基因位可選字符個數，其代表滿足任務特性約束，可完成第i個任務的工作中心個數。

由式4顯見，抗體的期望繁殖率刻畫了適應度、親和度和濃度的關系，綜合考慮了抗體與抗原之間的關系 (即抗體的適應度)、抗體與抗體之間的關系 (通過抗體的親和度來評價抗體間的相似程度，抗體的濃度來表示抗體與其相似的抗體的規模)。

免疫選擇是指在抗體群中依據抗體的期望繁殖率選擇抗體。從免疫機理的角度，免疫選擇反映了抗體選擇的不確定性以及抗體的抑制與促進機制。本文中按照比例選擇規則選擇抗體種群中的抗體。在免疫種群中抗體被選擇的概率如式5:

3.2 疫苗的抽取與接種

有效的疫苗對算法的收斂性和有效性具有重要的正面作用，本算法從動態任務資源匹配矩陣中抽取疫苗，每代進化過程任務資源匹配矩陣是動態更新的，通過該方式來獲得有效的疫苗，在深層次上隱含了疫苗也是隨抗體進化而不斷進化的思想，更加符合生物的進化規律。通過式6計算免疫進化過程中每代對應的任務資源匹配矩陣，其中表示第i個基因位出現p的概率;表示個體第i個基因位的編碼值。根據任務資源匹配矩陣中值，當某等位基因上的概率最大且大于某個設定閥值時，將其作為該等位基因上的疫苗，最終提取的疫苗如式7所示。

疫苗接種進行特異性免疫 (Specific Immunity)，有導向性地產生特異性抗體，利用待求解問題的先驗知識有效地加速算法的收斂。針對每代進化得到的抗體種群，以事先設定的免疫概率，隨機選擇父代群體中要進行接種的抗體g1。對選中的抗體g1，將疫苗Y的基因碼依次接入，通過置換抗體相應基因位置上的碼值產生新的免疫抗體g2，最終形成免疫種群antiby_v。疫苗接種的一個示例如圖4所示。

3.3 抗體交叉與變異

交叉是在肯定基因位進化的基礎上，通過基因重新組合產生新的抗體，使子代能夠繼承父代的優良基因，優秀抗體的基因模式得以迅速繁殖并在種群中擴散，使進化向最優方向進行。當交叉由于基因的局部相似而無法產生新的抗體時，通過變異可避免尋優過程陷入局部最優，改善種群的多樣性，引導進化探索新的搜索空間。

本文算法的交叉/變異操作采用兩點交叉/變異。對于交叉操作，根據交叉概率，隨機的從免疫種群中選取兩個抗體g1和g2作為父代，在g1中隨機選取兩個非零且不相等的基因位x1和x2，從而得到交叉區間 ［min(x1，x2)，max(x1，x2)］，在g2上找到對應的交叉區間，將這兩個區間內基因互換，就產生了兩個新的子代抗體g3和g4，這些子代抗體最終組成一個交叉種群antiby_c。對于變異操作，根據變異概率，隨機從免疫種群中選擇抗體g1。在g1中隨機選取兩個非零且不相等的基因位x1和x2，得到變異區間 ［min(x1，x2)，max(x1，x2)］，對該區間上每一個基因位，根據動態任務資源匹配矩陣相應的選擇概率，重新組合該區間上的基因，從而形成新的抗體g2，這些抗體最終組成變異種群antiby_m。

3.4 算法的特點分析

在本文算法中，免疫選擇將進化群體中較好的候選解確定性地選擇參與進化，提供開拓更好候選解的機會。免疫記憶不僅為問題的解決提供高效求解的機會，而且為算法的局部搜索提供必要的準備。這一操作與抗體交叉操作及親和突變操作共同作用，增強算法局部搜索能力，使算法有更多機會探測更好的候選解。濃度抑制可確保種群中相同或相似的抗體不會大量繁殖，其作用不僅在于保存好、中、差的抗體，而且減輕了免疫選擇算子選擇存活抗體時的選擇壓力。免疫選擇的作用在于:不僅給適應度高的抗體提供更多選擇機會，而且也給適應度及濃度皆低的抗體提供生存機會，使得存活的抗體種群具有多樣性，這一機制主要反映了抗體促進和抑制機理以及抗體選擇的隨機性。本文在抗體種群初始化與募集新成員時，采用基于動態任務資源匹配矩陣的抗體產生方法，通過該方法產生的抗體能夠微調群體多樣性及增強全局搜索能力，而且由于考慮了動態的任務資源匹配概率，能夠加快算法的尋優速度，同時使算法隨時有自我抗體被引入而具有開放式特點。這些算子相互作用，使算法具有如下特點:

1)抗體的選擇受適應度與濃度的制約，是確定性和隨機性的統一;

2)抗體交叉與變異體現了鄰域搜索及并行搜索的特性;

3)搜索過程中處于開采、探測、選擇、自我調節的協調合作過程，體現了體液免疫應答中抗體學習抗原的行為特性;

4)搜索過程處于開放，隨時有自我抗體被加入進化群體，以增強群體多樣性，提供產生更好解的機會的同時能夠加快算法的尋優速度。

4 仿 真

算法仿真環境為 Windows XP操作系統，3.0GHz CPU，1G內存。仿真工具采用Matlab7.0。基于動態任務資源匹配矩陣的免疫算法參數選取為:進化代數100，種群規模50，種群中交叉產生的個體比率為0.4，變異產生的個體比率為0.2，接種疫苗的個體比率為0.2，募集的新個體比率為0.1，記憶的優良個體比率為0.1，優異基因抽取閥值為0.85，親和度閥值為0.85。

在算法運行初期，會出現優異的基因未能達到抽取的閥值，導致在接種操作時無疫苗使用，而能夠體現基因特異性信息的任務資源匹配矩陣隨著抗體種群的進化而不斷進化，因此，此時采用依據動態任務資源匹配矩陣產生新的抗體種群是疫苗接種種群的最佳替代，可有效避免無疫苗可用而引起的算法的尋優效率降低的缺點。對本文第一節中的示例問題進行仿真，該問題中所有工作中心的初始負荷為0，其免疫進化過程如圖5所示。

圖5 免疫進化過程

圖5中標識了每代最優任務分配方案對應的目標函數值、協作成本函數值及平方和函數值，分別對應公式3的函數值及式3中第一、第二部分的函數值。其中目標函數值與協作成本函數值共用圖中左側縱坐標軸，平方和函數值使用右側縱坐標軸。從圖中可見，算法進化至第44代取得最優分配方案。由于該問題中設定，決定了工作中心之間具有互換性，因此算法進化過程中將尋找到多個最優分配方案，并且當且初始負荷為0，多個最優方案中的任何一個方案對于該問題都是無差別的。表4給出了最優任務分配方案。

表4 多工作中心任務最優分配方案

圖6標識了該最優分配方案對應的各工作中心的能力、負荷、利用率、最高利用率、平均利用率及最低利用率狀態。綜合圖5與圖6可見，本文提出的算法實現了平衡各工作中心的負荷的同時最小化企業的協作成本。

圖6 工作中心負荷狀態圖

圖7 新增任務的任務關聯圖

在實際的企業運作中由于有新項目訂單情況，存在為新增加任務進行分配的問題，解決該問題有兩種方式:一是將新任務與原任務作為一個整體重新進行任務分配;二是在保持原任務分配方案不變的前提下，對新增加的任務再分配。現假設企業有新項目訂單到達，需對新增任務進行分配。圖7給出了新增任務的任務關聯圖，新增任務的任務資源匹配初始矩陣如表5所示。

表5 新任務任務資源匹配初始矩陣

第一種方式采用本算法重新計算即可，但在實際生產中由于產生的分配方案將作為計劃調度等系統的重要數據輸入，該種方式不但涉及任務重分配計算成本，而且還將涉及重計劃/調度等成本。故在實際應用中，該方式較第二種方式雖然可能獲得相對較高質量的解，但仍較少采用。下文給出了在保證原分配方案不變的基礎上，運用提出的免疫算法對新增任務進行分配，即動態的任務再分配。由表5可知，此時問題的初始狀態為，且由于是在已有任務分配的基礎上進行任務分配，所以各工作中心的初始負荷不為0。因此，對新增任務進行再分配，不僅可以驗證該算法在處理新增任務分配問題的靈活性，同時還可以將其作為一個當且初始負荷不為0的新的任務分配問題 (初始負荷不為0，更能代表企業實際運作中的多工作中心任務分配問題)。

表6給出了新增任務在表4給出的任務分配方案的基礎上，進行任務再分配獲得的新增任務的優化分配方案。圖8給出了任務再分配后新的優化方案對應的工作中心負荷狀態。從圖8中可以看出，該任務再分配結果可以滿足實際的生產需要，同時驗證了算法在解決多工作中心任務組合優化分配的有效性。

表6 任務再分配優化方案

圖8 任務再分配工作中心負荷狀態圖

5 結束語

從多工作中心協同工作的角度，研究了云南電力研究院面向負荷均衡的任務分配問題，提出了用于解決該問題并支持任務重/再分配的免疫算法。運用免疫算法在求解多工作中心任務組合優化分配的過程中，引入動態任務資源匹配矩陣的概念，提高了算法的搜索效率。仿真實驗表明該算法的有效性和實用性特點。