于曉義 吳 毅 王達(dá)達(dá) 楊 昆

(1.云南電力試驗(yàn)研究院 (集團(tuán))有限公司電力研究院，云南 昆明 650217;2.西北工業(yè)大學(xué)系統(tǒng)集成與工程管理研究所，陜西 西安 710072)

1 前言

云南電網(wǎng)公司電力研究院具有人員學(xué)歷水平較高、容易掌握和接受新的管理思想和方法、有強(qiáng)大的軟件開(kāi)發(fā)團(tuán)隊(duì)、有與云南電網(wǎng)公司生產(chǎn)管理信息系統(tǒng)同平臺(tái)、同架構(gòu)設(shè)計(jì)開(kāi)發(fā)的生產(chǎn)MIS系統(tǒng)等特點(diǎn)?；谏鲜鲈颇想娋W(wǎng)公司信息化發(fā)展的大環(huán)境與云南電力研究院的基礎(chǔ)與特點(diǎn)，選定云南電力研究院作為云南電網(wǎng)公司ERP項(xiàng)目試點(diǎn)單位。

通過(guò)前期調(diào)研發(fā)現(xiàn)，隨著業(yè)務(wù)的發(fā)展，電力研究院目前存在的問(wèn)題的根源為資源的沖突與協(xié)調(diào)。其主要表現(xiàn)在資源調(diào)配、項(xiàng)目管理、人員發(fā)展三個(gè)方面。

在資源調(diào)配方面:多頭管理現(xiàn)象突出，人員安排經(jīng)常出現(xiàn)沖突;缺乏全局性資源調(diào)配機(jī)制和計(jì)劃，資源未能得到最優(yōu)配置，利用率低，造成“準(zhǔn)備的資源不用，要用的資源不在”現(xiàn)象;資源控制未和現(xiàn)場(chǎng)實(shí)際情況緊密結(jié)合起來(lái)，造成有限資源并未用在關(guān)鍵的、合適的、亟須的環(huán)節(jié)，資源負(fù)荷不均;資源過(guò)程管理粗放，追蹤困難，無(wú)法細(xì)化工時(shí)/標(biāo)準(zhǔn)費(fèi)率定額以指導(dǎo)資源的精細(xì)化管理。

在項(xiàng)目管理方面:主要原因是資源管理與項(xiàng)目計(jì)劃管理協(xié)作松散，因人員緊張導(dǎo)致項(xiàng)目質(zhì)量難以保證，影響客戶滿意度;對(duì)項(xiàng)目人員的時(shí)間成本缺乏精細(xì)化的控制與管理。

在人員發(fā)展方面:員工數(shù)量難以滿足快速發(fā)展的業(yè)務(wù)需求，核心員工勞動(dòng)強(qiáng)度大;缺乏系統(tǒng)性的員工職業(yè)發(fā)展規(guī)劃與輔導(dǎo)機(jī)制，員工職業(yè)發(fā)展受限。

綜上所述，云南電網(wǎng)公司電力研究院在資源優(yōu)化配置方面已提出了迫切的需求，亟須在資源優(yōu)化配置方面取得突破，建立面向電力生產(chǎn)技術(shù)監(jiān)督、技術(shù)服務(wù)和科研開(kāi)發(fā)的全業(yè)務(wù)的資源優(yōu)化配置平臺(tái)，保證業(yè)務(wù)工作的實(shí)時(shí)緊密協(xié)作，保證生產(chǎn)任務(wù)的均衡、生產(chǎn)計(jì)劃的可執(zhí)行性、資源的高利用率、項(xiàng)目交付的客戶滿意度，為電網(wǎng)安全、穩(wěn)定、經(jīng)濟(jì)運(yùn)行提供技術(shù)保障。

2 工作中心協(xié)同任務(wù)分配問(wèn)題描述

在電力研究院服務(wù)型企業(yè)運(yùn)作境下，企業(yè)接收的訂單按WBS分解成相互關(guān)聯(lián)的任務(wù)，由傳統(tǒng)的每個(gè)任務(wù)有指定的承接專業(yè)所，轉(zhuǎn)變?yōu)槊總€(gè)任務(wù)根據(jù)其特點(diǎn)可以有多個(gè)可選的承接工作中心，在此條件下產(chǎn)生了多工作中心的負(fù)荷均衡優(yōu)化問(wèn)題。工作中心任務(wù)分配的本質(zhì)是任務(wù)與工作中心資源的映射。

由于任務(wù)是按照WBS分解的，所以任務(wù)之間的關(guān)聯(lián)關(guān)系呈現(xiàn)出一種樹(shù)狀結(jié)構(gòu)，用一個(gè)無(wú)向圖GT(V，E)描述任務(wù)之間的關(guān)聯(lián)(見(jiàn)圖(1);頂點(diǎn)|V|=N表示待分配的N個(gè)任務(wù)，用ωi表示任務(wù)i的完成周期;邊E表示兩個(gè)任務(wù)之間的關(guān)聯(lián)，用eij表示邊(i，j)∈E連接的兩個(gè)任務(wù)i與j由不同工作中心完成時(shí)的協(xié)作消耗工時(shí)。

用一個(gè)無(wú)向完全圖GP(P，D)描述K個(gè)工作中心的關(guān)聯(lián)關(guān)系(見(jiàn)圖(2)，dpq表示邊(p，q)∈D連接的兩個(gè)工作中心p與q的單位協(xié)作成本。

設(shè)每個(gè)任務(wù)在K個(gè)工作中心中能且只能被分配一次。

式1，2分別表示各工作中心的負(fù)荷與企業(yè)的協(xié)作成本。

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

圖1、2給出了一個(gè)多工作中心任務(wù)分配問(wèn)題的示例。圖1描述了一個(gè)N=20個(gè)任務(wù)的無(wú)向圖GT，圖2給出了K=5個(gè)工作中心的關(guān)聯(lián)關(guān)系圖GP。圖中圓圈中的數(shù)字分別代表任務(wù)與工作中心編號(hào)。圖1中頂點(diǎn)與邊上的數(shù)字分別代表任務(wù)的完成周期與協(xié)作消耗工時(shí)。圖2中邊上的數(shù)字代表兩工作中心的單位協(xié)作成本。表1給出了一個(gè)關(guān)于圖1、2的任務(wù)分配方案。

圖1 任務(wù)關(guān)聯(lián)圖GT

圖2 工作中心關(guān)聯(lián)圖GP

表1 分配方案示例表

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

表2、表3分別顯示了與圖1、2示例相關(guān)的任務(wù)資源匹配矩陣初始狀態(tài)和一個(gè)分配方案狀態(tài)的任務(wù)資源匹配矩陣，不失一般性取

表2 任務(wù)資源匹配矩陣初始狀態(tài)

表3 分配方案狀態(tài)的任務(wù)資源匹配矩陣

目標(biāo)函數(shù)如式3所示，目的是平衡各工作中心的負(fù)荷 (式1)，同時(shí)最小化企業(yè)的協(xié)作成本(式2)。

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

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

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

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

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

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

3 基于IA的協(xié)作優(yōu)化分配算法

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

免疫進(jìn)化時(shí)首先進(jìn)行抗原識(shí)別，分析問(wèn)題及解的特性并進(jìn)行抗體編碼，本文采用K進(jìn)制編碼，對(duì)參與協(xié)同工作的工作中心資源按1，2，…，K進(jìn)行編碼，抗體長(zhǎng)度為任務(wù)數(shù)N。若抗體第i個(gè)基因位對(duì)應(yīng)的值為p，則表示任務(wù)i被分配到工作中心p進(jìn)行生產(chǎn)加工。此編碼直觀，易于操作，且不需解碼?？贵w編碼樣例見(jiàn)表1。

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

圖3 基于動(dòng)態(tài)任務(wù)資源匹配矩陣的免疫算法流程

3.1 抗體的評(píng)價(jià)與選擇

免疫進(jìn)化過(guò)程中，需要對(duì)各抗體進(jìn)行評(píng)價(jià)。如果以抗體的適應(yīng)度為評(píng)價(jià)指標(biāo)，當(dāng)群體中的某個(gè)抗體占據(jù)了相當(dāng)規(guī)模，而又不是最優(yōu)解時(shí)就極易導(dǎo)致過(guò)早收斂。采用抗體濃度來(lái)抑制規(guī)模較大又不是最優(yōu)解的抗體，并以信息熵作為衡量相似度的指標(biāo)，以期望繁殖率作為評(píng)價(jià)抗體的標(biāo)準(zhǔn)?？贵w的繁殖率計(jì)算如下:

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

由式4顯見(jiàn)，抗體的期望繁殖率刻畫(huà)了適應(yīng)度、親和度和濃度的關(guān)系，綜合考慮了抗體與抗原之間的關(guān)系 (即抗體的適應(yīng)度)、抗體與抗體之間的關(guān)系 (通過(guò)抗體的親和度來(lái)評(píng)價(jià)抗體間的相似程度，抗體的濃度來(lái)表示抗體與其相似的抗體的規(guī)模)。

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

3.2 疫苗的抽取與接種

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

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

3.3 抗體交叉與變異

交叉是在肯定基因位進(jìn)化的基礎(chǔ)上，通過(guò)基因重新組合產(chǎn)生新的抗體，使子代能夠繼承父代的優(yōu)良基因，優(yōu)秀抗體的基因模式得以迅速繁殖并在種群中擴(kuò)散，使進(jìn)化向最優(yōu)方向進(jìn)行。當(dāng)交叉由于基因的局部相似而無(wú)法產(chǎn)生新的抗體時(shí)，通過(guò)變異可避免尋優(yōu)過(guò)程陷入局部最優(yōu)，改善種群的多樣性，引導(dǎo)進(jìn)化探索新的搜索空間。

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

3.4 算法的特點(diǎn)分析

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

1)抗體的選擇受適應(yīng)度與濃度的制約，是確定性和隨機(jī)性的統(tǒng)一;

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

3)搜索過(guò)程中處于開(kāi)采、探測(cè)、選擇、自我調(diào)節(jié)的協(xié)調(diào)合作過(guò)程，體現(xiàn)了體液免疫應(yīng)答中抗體學(xué)習(xí)抗原的行為特性;

4)搜索過(guò)程處于開(kāi)放，隨時(shí)有自我抗體被加入進(jìn)化群體，以增強(qiáng)群體多樣性，提供產(chǎn)生更好解的機(jī)會(huì)的同時(shí)能夠加快算法的尋優(yōu)速度。

4 仿 真

算法仿真環(huán)境為 Windows XP操作系統(tǒng)，3.0GHz CPU，1G內(nèi)存。仿真工具采用Matlab7.0?；趧?dòng)態(tài)任務(wù)資源匹配矩陣的免疫算法參數(shù)選取為:進(jìn)化代數(shù)100，種群規(guī)模50，種群中交叉產(chǎn)生的個(gè)體比率為0.4，變異產(chǎn)生的個(gè)體比率為0.2，接種疫苗的個(gè)體比率為0.2，募集的新個(gè)體比率為0.1，記憶的優(yōu)良個(gè)體比率為0.1，優(yōu)異基因抽取閥值為0.85，親和度閥值為0.85。

在算法運(yùn)行初期，會(huì)出現(xiàn)優(yōu)異的基因未能達(dá)到抽取的閥值，導(dǎo)致在接種操作時(shí)無(wú)疫苗使用，而能夠體現(xiàn)基因特異性信息的任務(wù)資源匹配矩陣隨著抗體種群的進(jìn)化而不斷進(jìn)化，因此，此時(shí)采用依據(jù)動(dòng)態(tài)任務(wù)資源匹配矩陣產(chǎn)生新的抗體種群是疫苗接種種群的最佳替代，可有效避免無(wú)疫苗可用而引起的算法的尋優(yōu)效率降低的缺點(diǎn)。對(duì)本文第一節(jié)中的示例問(wèn)題進(jìn)行仿真，該問(wèn)題中所有工作中心的初始負(fù)荷為0，其免疫進(jìn)化過(guò)程如圖5所示。

圖5 免疫進(jìn)化過(guò)程

圖5中標(biāo)識(shí)了每代最優(yōu)任務(wù)分配方案對(duì)應(yīng)的目標(biāo)函數(shù)值、協(xié)作成本函數(shù)值及平方和函數(shù)值，分別對(duì)應(yīng)公式3的函數(shù)值及式3中第一、第二部分的函數(shù)值。其中目標(biāo)函數(shù)值與協(xié)作成本函數(shù)值共用圖中左側(cè)縱坐標(biāo)軸，平方和函數(shù)值使用右側(cè)縱坐標(biāo)軸。從圖中可見(jiàn)，算法進(jìn)化至第44代取得最優(yōu)分配方案。由于該問(wèn)題中設(shè)定，決定了工作中心之間具有互換性，因此算法進(jìn)化過(guò)程中將尋找到多個(gè)最優(yōu)分配方案，并且當(dāng)且初始負(fù)荷為0，多個(gè)最優(yōu)方案中的任何一個(gè)方案對(duì)于該問(wèn)題都是無(wú)差別的。表4給出了最優(yōu)任務(wù)分配方案。

表4 多工作中心任務(wù)最優(yōu)分配方案

圖6標(biāo)識(shí)了該最優(yōu)分配方案對(duì)應(yīng)的各工作中心的能力、負(fù)荷、利用率、最高利用率、平均利用率及最低利用率狀態(tài)。綜合圖5與圖6可見(jiàn)，本文提出的算法實(shí)現(xiàn)了平衡各工作中心的負(fù)荷的同時(shí)最小化企業(yè)的協(xié)作成本。

圖6 工作中心負(fù)荷狀態(tài)圖

圖7 新增任務(wù)的任務(wù)關(guān)聯(lián)圖

在實(shí)際的企業(yè)運(yùn)作中由于有新項(xiàng)目訂單情況，存在為新增加任務(wù)進(jìn)行分配的問(wèn)題，解決該問(wèn)題有兩種方式:一是將新任務(wù)與原任務(wù)作為一個(gè)整體重新進(jìn)行任務(wù)分配;二是在保持原任務(wù)分配方案不變的前提下，對(duì)新增加的任務(wù)再分配?，F(xiàn)假設(shè)企業(yè)有新項(xiàng)目訂單到達(dá)，需對(duì)新增任務(wù)進(jìn)行分配。圖7給出了新增任務(wù)的任務(wù)關(guān)聯(lián)圖，新增任務(wù)的任務(wù)資源匹配初始矩陣如表5所示。

表5 新任務(wù)任務(wù)資源匹配初始矩陣

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

表6給出了新增任務(wù)在表4給出的任務(wù)分配方案的基礎(chǔ)上，進(jìn)行任務(wù)再分配獲得的新增任務(wù)的優(yōu)化分配方案。圖8給出了任務(wù)再分配后新的優(yōu)化方案對(duì)應(yīng)的工作中心負(fù)荷狀態(tài)。從圖8中可以看出，該任務(wù)再分配結(jié)果可以滿足實(shí)際的生產(chǎn)需要，同時(shí)驗(yàn)證了算法在解決多工作中心任務(wù)組合優(yōu)化分配的有效性。

表6 任務(wù)再分配優(yōu)化方案

圖8 任務(wù)再分配工作中心負(fù)荷狀態(tài)圖

5 結(jié)束語(yǔ)

從多工作中心協(xié)同工作的角度，研究了云南電力研究院面向負(fù)荷均衡的任務(wù)分配問(wèn)題，提出了用于解決該問(wèn)題并支持任務(wù)重/再分配的免疫算法。運(yùn)用免疫算法在求解多工作中心任務(wù)組合優(yōu)化分配的過(guò)程中，引入動(dòng)態(tài)任務(wù)資源匹配矩陣的概念，提高了算法的搜索效率。仿真實(shí)驗(yàn)表明該算法的有效性和實(shí)用性特點(diǎn)。