基于遺傳算法的網(wǎng)絡(luò)運(yùn)維資源調(diào)度的研究

許青林，徐峰，王志（.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州　50006；.廣東怡創(chuàng)科技股份有限公司，廣州　50006）

基于遺傳算法的網(wǎng)絡(luò)運(yùn)維資源調(diào)度的研究

許青林1，徐峰1，王志2
（1.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院，廣州510006；2.廣東怡創(chuàng)科技股份有限公司，廣州510006）

0　引言

近年來，通信市場的競爭越來越劇烈，因此通信企業(yè)必須迅速提高企業(yè)的競爭力，而降低網(wǎng)絡(luò)運(yùn)維是通信企業(yè)提高競爭力的重要方面。一方面，大量網(wǎng)絡(luò)運(yùn)維成本的支出限制了通信企業(yè)在低成本競爭力方面的提升空間；另一方面，挖掘網(wǎng)絡(luò)運(yùn)維成本可削減空間，也是提高通信企業(yè)低成本競爭力的一個(gè)重要方面。因此，如何降低網(wǎng)絡(luò)運(yùn)維成本，成為通信運(yùn)營企業(yè)所面臨的重大問題。而降低網(wǎng)絡(luò)運(yùn)維成本的重要方面在于網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)的合理調(diào)度，網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)調(diào)度是指根據(jù)每個(gè)作業(yè)任務(wù)的資源需求，分配合適的資源來完成作業(yè)任務(wù)，它作為網(wǎng)絡(luò)運(yùn)維成本的重要方面，將直接決定了降低網(wǎng)絡(luò)運(yùn)維成本的效果。

目前已經(jīng)有很多維護(hù)服務(wù)類企業(yè)提出了解決網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)調(diào)度問題的方法，基本上都是通過將大規(guī)模并發(fā)的多任務(wù)調(diào)度問題分解為各個(gè)獨(dú)立的簡單任務(wù)，然后為這些獨(dú)立的簡單任務(wù)提供最優(yōu)調(diào)度，而這從理論原理上來說就是欠缺的。根據(jù)博弈論的原理，所有局部最優(yōu)決策合起來是不可能得到整體最優(yōu)決策的，所以將大規(guī)模并發(fā)多任務(wù)調(diào)度問題簡單分解為各個(gè)獨(dú)立任務(wù)的最優(yōu)調(diào)度問題來解決，并沒有挖掘出大規(guī)模生產(chǎn)活動(dòng)的規(guī)模效應(yīng)所應(yīng)該帶來生產(chǎn)效率提升的潛力。實(shí)際上，在網(wǎng)絡(luò)運(yùn)維的現(xiàn)場作業(yè)中，通常作業(yè)任務(wù)的數(shù)量要多于資源的數(shù)量，因此降低資源利用率和縮短作業(yè)任務(wù)完成的總時(shí)間成為網(wǎng)絡(luò)運(yùn)維中降低調(diào)度成本的重要手段，這也是一類資源調(diào)度問題．資源調(diào)度是一類極其繁瑣復(fù)雜的問題，它在一般形式下是一個(gè)NP完全問題。本文提出了基于遺傳算法的面向整體優(yōu)化的現(xiàn)場作業(yè)調(diào)度方案，采用基于作業(yè)任務(wù)-資源的間接編碼方式，并通過對遺傳算法的遺傳過程根據(jù)實(shí)際情況進(jìn)行優(yōu)化，在滿足作業(yè)任務(wù)的需求情況下，縮短任務(wù)的完成時(shí)間和提高資源的使用效率，以便能夠最大化地降低網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)的調(diào)度成本。

1　問題描述

本文主要討論的是當(dāng)作業(yè)任務(wù)數(shù)量遠(yuǎn)多于資源數(shù)量時(shí)的調(diào)度策略，對于如何獲取資源信息、獲取作業(yè)任務(wù)的詳細(xì)信息等問題不在此討論范圍。假設(shè)現(xiàn)在有n個(gè)作業(yè)任務(wù)，m個(gè)維護(hù)人員（即后面所說的資源），其中n＞2×m，要求將n個(gè)作業(yè)任務(wù)分配給m個(gè)資源，并確定每個(gè)資源完成所有任務(wù)的時(shí)間和每個(gè)資源上各個(gè)作業(yè)任務(wù)的執(zhí)行順序。為了更加準(zhǔn)確地描述網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)的任務(wù)調(diào)度問題，給出如下定義：

（1）n個(gè)作業(yè)任務(wù)工單的集合W=｛W1，W2，…，Wn｝，其中Wi表示第i個(gè)作業(yè)人任務(wù)工單；

（2）m個(gè)資源（即維護(hù)人員）的集合P=｛P1，P2，…，Pm｝，其中Pj表示第j個(gè)資源；

（3）一個(gè)m×n的矩陣E［m］［n］，E［i］［j］表示資源Pi從接收任務(wù)到完成任務(wù)Wj所需的時(shí)間；

（4）一個(gè)m×n的矩陣T［m］［n］，T［i］［j］表示從任務(wù)Pi所在地點(diǎn)到任務(wù)Pj所在地點(diǎn)的時(shí)間；

（5）對于作業(yè)任務(wù)之間的約束關(guān)系處理：對在同一資源上執(zhí)行的多個(gè)作業(yè)任務(wù)進(jìn)行排序，若任務(wù)是緊急型，則在執(zhí)行任務(wù)時(shí)應(yīng)該優(yōu)先于非緊急型任務(wù)執(zhí)行；對于相同類型的作業(yè)任務(wù)，按照作業(yè)任務(wù)的最遲完成時(shí)間進(jìn)行排序，最遲完成時(shí)間越小，則任務(wù)的優(yōu)先級(jí)越高；對于作業(yè)任務(wù)的最遲完成時(shí)間相同的作業(yè)任務(wù)，則短任務(wù)優(yōu)先級(jí)較高。

網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)調(diào)度的目標(biāo)是盡可能的縮短完成所有作業(yè)任務(wù)的執(zhí)行時(shí)間，以降低調(diào)度成本.假設(shè)S為其中一個(gè)調(diào)度與分配策略，Ts（Pi）表示在策略S下，資源Pi完成已分配的任務(wù)的總時(shí)間，設(shè)T（S）代表完成分配與調(diào)度策略S要花費(fèi)的總時(shí)間，那么T（S）=max （Ts（Pi）），其中i介于1到m之間。因此，在本問題中目標(biāo)就是min（T（S））。

2　遺傳算法求解

任務(wù)調(diào)度問題的求解一般分為兩個(gè)階段：分配階段、調(diào)度階段。對于網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)任務(wù)的調(diào)度問題，前者是將多個(gè)作業(yè)任務(wù)分配給各個(gè)資源，后者確定同一個(gè)資源上多個(gè)作業(yè)任務(wù)的執(zhí)行順序。

遺傳算法中的染色體編碼形式多種多樣，基本上可以分為兩種，直接編碼和間接編碼。這里采用基于作業(yè)任務(wù)-資源的間接編碼方式，對每個(gè)作業(yè)任務(wù)占用的資源進(jìn)行編碼，解的編碼形式用一個(gè)一維的字符串表示．由于在網(wǎng)絡(luò)運(yùn)維現(xiàn)場作業(yè)的任務(wù)調(diào)度中，每個(gè)作業(yè)任務(wù)所需要的資源可能不止一個(gè)，一般來說，完成每個(gè)任務(wù)所需的資源數(shù)量不會(huì)超過3個(gè)，染色體的長度等于作業(yè)任務(wù)的數(shù)量，染色體上的每一位是由六位的字符串組成，代表該位置上的作業(yè)任務(wù)所需的資源，每個(gè)資源的編號(hào)是由兩個(gè)阿拉伯?dāng)?shù)字組成，對于那些所需的資源數(shù)量不足3個(gè)的作業(yè)任務(wù)，為了方便后期的實(shí)驗(yàn)結(jié)果的檢驗(yàn)，在該字符串的左邊以零補(bǔ)齊使得字符串長度達(dá)到六位，染色體上每一位的位置編號(hào)代表了作業(yè)任務(wù)的編號(hào)。

圖1　資源-任務(wù)編碼

其中Wi表示作業(yè)任務(wù)的編號(hào)，Pi中的字符串表示作業(yè)任務(wù)Wi所需要資源的組合，在生成初始種群時(shí)種群中的作業(yè)任務(wù)所占用的資源是隨機(jī)產(chǎn)生的，因此每個(gè)作業(yè)任務(wù)可能會(huì)占用任何一個(gè)可用的資源，最終的最優(yōu)解一定對應(yīng)著某一個(gè)染色體編碼，所以需要對這個(gè)最優(yōu)染色體進(jìn)行解碼，得到不同作業(yè)任務(wù)上資源的分配。

將染色體上的每一位提取出來，并對其中的字符串按照對應(yīng)的資源進(jìn)行解析，然后按照每個(gè)作業(yè)任務(wù)所占用的資源進(jìn)行分類，生成了多組按照資源編號(hào)分類的作業(yè)任務(wù)序列，這些序列代表作業(yè)任務(wù)的編號(hào)，序列中的元素代表當(dāng)前資源需要執(zhí)行的作業(yè)任務(wù)，通過這樣編碼與解碼可以得到作業(yè)任務(wù)中資源的分配情況，而且對于分布在不同資源上的作業(yè)任務(wù)不需要考慮它們之間的執(zhí)行順序，只需要考慮在同一個(gè)資源上執(zhí)行的任務(wù)之間的執(zhí)行順序。下面介紹一下如何處理同一個(gè)資源執(zhí)行的多個(gè)任務(wù)之間的關(guān)系以及它們之間的執(zhí)行順序。

為了最大化的減少作業(yè)任務(wù)的運(yùn)行時(shí)間，降低網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)任務(wù)的調(diào)度成本，對于在同一個(gè)資源上執(zhí)行的任意兩個(gè)任務(wù)需要滿足一定執(zhí)行順序，例如S1，S2是在同一個(gè)資源上執(zhí)行的兩個(gè)作業(yè)任務(wù)，若S1是緊急型任務(wù)，S2是非緊急型任務(wù)，則盡量使S1在S2之前執(zhí)行；若任務(wù)S1和S2是同類型的作業(yè)任務(wù)，且完成任務(wù)S1的時(shí)間比完成任務(wù)S2的時(shí)間短，則應(yīng)該盡量使S1在S2之前執(zhí)行，這樣有利于提高企業(yè)在網(wǎng)絡(luò)運(yùn)維方面的服務(wù)質(zhì)量。

（1）基于作業(yè)任務(wù)的類型和任務(wù)的最遲完成時(shí)間排序

對于前面提到的作業(yè)任務(wù)按照任務(wù)的類型進(jìn)行排序來設(shè)置任務(wù)的優(yōu)先級(jí)，緊急型任務(wù)的優(yōu)先級(jí)高于非緊急型任務(wù)，對于同類型的作業(yè)任務(wù)，則按照作業(yè)任務(wù)工單中定義的最遲完成時(shí)間進(jìn)行排序，最遲完成時(shí)間較早的任務(wù)優(yōu)先級(jí)高于最遲完成時(shí)間較晚的作業(yè)任務(wù)的優(yōu)先級(jí)；若在同類型的作業(yè)任務(wù)中，它們的最遲完成時(shí)間也相同，則按照完成作業(yè)任務(wù)用時(shí)短的任務(wù)優(yōu)先級(jí)較高。

根據(jù)前面2.1介紹的編碼方法，解析出每個(gè)染色體上的資源序列，并按照資源的編號(hào)進(jìn)行分類，可以得到每個(gè)資源上的任務(wù)執(zhí)行序列，然后計(jì)算每個(gè)資源完成已分配的作業(yè)任務(wù)要花費(fèi)的總時(shí)間，適應(yīng)值就是最大花費(fèi)時(shí)間的倒數(shù)，因此適應(yīng)值和做大花費(fèi)時(shí)間成反比。而要計(jì)算適應(yīng)值必須知道作業(yè)任務(wù)的總完成時(shí)間，設(shè)end［i］［j］表示資源j完成作業(yè)任務(wù)i的時(shí)間，則fin［i］［j］=start［i］［j］+E［i］［j］，E［i］［j］表示作業(yè)任務(wù)i在資源j上的執(zhí)行時(shí)間，start［i］［j］表示資源j執(zhí)行作業(yè)任務(wù)i的時(shí)間，而start［i］［j］由三個(gè)因素決定，第一，資源j開始執(zhí)行作業(yè)任務(wù)的時(shí)間，第二，資源j完成上一個(gè)任務(wù)的最晚完成時(shí)間，第三，資源j到達(dá)任務(wù)i所在的地點(diǎn)的最晚時(shí)間。具體的計(jì)算公式如下，

start［i］［j］=max｛space［j］，max（end（pre（j）））+Travel ［m］［i］｝

其中，space［j］表示資源j的空閑時(shí)刻，max（end（pre （j））表示資源j完成上一個(gè)任務(wù)的最遲時(shí)間，Travel［m］［i］表示資源從上一個(gè)作業(yè)任務(wù)m地點(diǎn)到達(dá)當(dāng)前作業(yè)任務(wù)i所需要的時(shí)間。

（1）選擇

選擇是從當(dāng)前群體中選擇優(yōu)勝的個(gè)體，淘汰劣質(zhì)個(gè)體的操作。個(gè)體的選擇方式有輪盤賭選擇、競爭選擇、比例選擇等。選擇操作的目的是通過把優(yōu)化的個(gè)體（或解）直接遺傳到下一代或者通過交叉操作產(chǎn)生新的個(gè)體遺傳到下一代。選擇是建立在個(gè)體適應(yīng)度基礎(chǔ)上的，本文采用基于最佳保存方法來選取進(jìn)入下一代的個(gè)體，首先選擇一個(gè)基準(zhǔn)值p作為新個(gè)體進(jìn)入下一代的標(biāo)準(zhǔn)，對于種群中適應(yīng)度大于p的個(gè)體，直接復(fù)制到下一代，對于適應(yīng)度低于或等于p的個(gè)體按照正常的流程產(chǎn)生一個(gè)新的個(gè)體放到下一代的種群中。這種選取后代的方式一方面可以保存優(yōu)秀基因不被破壞，另一方面有可以增加種群的多樣性，避免過早收斂。

（2）交叉

交叉是指將兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新的個(gè)體的操作，基本的交叉方法有單點(diǎn)交叉、兩點(diǎn)交叉和多點(diǎn)交叉。這里的雜交算子采用對標(biāo)準(zhǔn)雜交算子（SCX）進(jìn)行改進(jìn)，對于通過選擇操作選擇出來的兩個(gè)染色體，具體的雜交過程是：生成一個(gè)隨機(jī)數(shù)k作為染色體的雜交點(diǎn)，0≤k≤n（n為染色體的長度），將兩條父染色體雜交點(diǎn)前后的部分交換生成兩個(gè)新的染色體，分別計(jì)算新生成染色體的適應(yīng)值，若新生成染色體的適應(yīng)值大于父代染色體，則將新染色體按照概率p替換掉父染色體，并將父染色體放入原種群中，參與下一次的遺傳操作過程；否則，與原種群中適應(yīng)值最小的個(gè)體進(jìn)行比較，若新生成個(gè)體的適應(yīng)值大于最低適應(yīng)值，則直接替換掉最低適應(yīng)值對應(yīng)的染色體，反之丟棄新生成的個(gè)體，并重新進(jìn)行上述的選擇操作重新選擇染色體進(jìn)行交叉操作。

（3）變異

變異算子是通過對種群中染色體的某些基因值做改動(dòng)以增強(qiáng)種群的多樣性，避免過早收斂。在遺傳算法中增加變異算子的主要目的是使遺傳算法具有隨機(jī)搜索的能力，避免陷入局部最優(yōu)的情況以及希望通過變異操作能夠增加種群的多樣性。這里采用的實(shí)質(zhì)變異算子就是將某個(gè)作業(yè)任務(wù)按照概率q遷移到另一個(gè)資源上執(zhí)行，同時(shí)為了防止某個(gè)作業(yè)任務(wù)在遷移后，任務(wù)的總執(zhí)行時(shí)間增大所造成的種群退化，這里對于遷移后的作業(yè)任務(wù)所要占用的而資源并不是隨機(jī)產(chǎn)生的，而是根據(jù)當(dāng)前作業(yè)任務(wù)所處的地理位置從周邊搜索出所需要的資源，然后從中選擇出執(zhí)行當(dāng)前作業(yè)任務(wù)預(yù)期時(shí)間最短的資源分配給當(dāng)前作業(yè)任務(wù)。

本文中的算法是基于作業(yè)任務(wù)-資源的間接編碼方式，因此交叉和變異操作的實(shí)質(zhì)就是為作業(yè)任務(wù)重新分配合適的資源，在交叉和變異操作后，對所有的作業(yè)任務(wù)按照占用的資源進(jìn)行分類，并對于在同一個(gè)資源上執(zhí)行的作業(yè)任務(wù)按照2.2中指定的規(guī)則進(jìn)行排序，按照排序后的順序執(zhí)行作業(yè)任務(wù)，通過這樣的操作既可以提高資源的利用率，又可以降低網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)的調(diào)度成本，同時(shí)也能提高企業(yè)的而服務(wù)質(zhì)量。

3　算法流程

（1）初始化作業(yè)任務(wù)集合W、資源集合P、矩陣P和矩陣T。

（2）隨機(jī)產(chǎn)生大小為m的初始種群，根據(jù)初始化的任務(wù)集合，為每個(gè)作業(yè)任務(wù)分配資源，采用2.1中所說的編碼方式生成m條染色體，每條染色體的長度等于任務(wù)的數(shù)量。

（3）對于在同一資源上執(zhí)行的作業(yè)任務(wù)，按照2.2中所描述的約束關(guān)系來設(shè)置任務(wù)的執(zhí)行順序，根據(jù)每個(gè)資源上作業(yè)任務(wù)的執(zhí)行序列計(jì)算每條染色體的適應(yīng)值。

（4）從當(dāng)前種群中選擇染色體進(jìn)行交叉和變異操作，并按照2.4.1中所描述的選擇操作將其放入新種群中，然后對新生成的種群按照2.2中所描述的約束關(guān)系設(shè)置任務(wù)的執(zhí)行順序，計(jì)算其適應(yīng)值。

（5）判斷是否滿足遺傳算法的終止條件，若滿足終止條件，則停止繼續(xù)迭代，輸出完成作業(yè)任務(wù)最短的時(shí)間和對應(yīng)的染色體；若不滿足，則繼續(xù)執(zhí)行（4）。

4　實(shí)驗(yàn)結(jié)果

這里我們進(jìn)行了兩組實(shí)驗(yàn)，分別假設(shè)有50個(gè)作業(yè)任務(wù)和20個(gè)可用資源以及70個(gè)作業(yè)任務(wù)和30個(gè)可用資源，對于每組實(shí)驗(yàn)，采用多組數(shù)據(jù)進(jìn)行測試，其中每個(gè)作業(yè)任務(wù)在不同資源上的執(zhí)行時(shí)間以及同一個(gè)資源執(zhí)行不同作業(yè)任務(wù)之間的延遲 （即從一個(gè)任務(wù)地點(diǎn)到達(dá)另一個(gè)任務(wù)地點(diǎn)的時(shí)間）是已知的，這些數(shù)據(jù)是根據(jù)歷史記錄計(jì)算出來的．這里參數(shù)設(shè)置為初始種群的大小是100，變異率是0.05，交叉率是0.7。仿真實(shí)驗(yàn)結(jié)果采用的是一臺(tái)i3/4G的PC完成的，這里采用MAX_TIME來表示完成作業(yè)任務(wù)的最大時(shí)間．本文算法與采用傳統(tǒng)的FCFS算法進(jìn)行比較，實(shí)驗(yàn)結(jié)果如下所示，通過這里的實(shí)驗(yàn)結(jié)果可以看出，對于現(xiàn)場作業(yè)采用遺傳算法進(jìn)行任務(wù)調(diào)度，所有作業(yè)任務(wù)的完成時(shí)間明顯小于采用FCFS算法調(diào)度。

表1　實(shí)驗(yàn)結(jié)果

5　結(jié)語

本文提出了一種基于遺傳算法的面向網(wǎng)絡(luò)運(yùn)維中現(xiàn)場作業(yè)資源調(diào)度算法，討論了使用遺傳算法解決網(wǎng)絡(luò)運(yùn)維中多個(gè)現(xiàn)場作業(yè)任務(wù)在不同資源之間調(diào)度的問題，包括問題的提出、解決方法和實(shí)驗(yàn)結(jié)果分析，最后通過實(shí)驗(yàn)證明了該算法優(yōu)于傳統(tǒng)的FCFS調(diào)度算法。

本文中的算法對現(xiàn)場作業(yè)任務(wù)的特性做了若干假設(shè)，將作業(yè)任務(wù)所涉及的各種資源，如維護(hù)人員、車輛等作為一個(gè)整體來考慮。但是在實(shí)際網(wǎng)絡(luò)運(yùn)維的現(xiàn)場作業(yè)調(diào)度中現(xiàn)場作業(yè)任務(wù)的特性可能會(huì)涉及更多的因素，因此我們下一步將考慮包括完整的網(wǎng)絡(luò)運(yùn)維現(xiàn)場作業(yè)的作業(yè)任務(wù)特性，例如每個(gè)資源以及作業(yè)任務(wù)的地理位置在動(dòng)態(tài)的變化。我們在本文中假設(shè)使用的作業(yè)任務(wù)信息在執(zhí)行調(diào)度前已經(jīng)獲取到了，下一步將考慮如何實(shí)時(shí)地根據(jù)作業(yè)任務(wù)和資源的地理位置動(dòng)態(tài)對任務(wù)進(jìn)行調(diào)度，以增加算法的靈活性。

［1］林劍檸，吳慧中.基于遺傳算法的網(wǎng)格資源調(diào)度算法.計(jì)算機(jī)研究與發(fā)展，2004，41（12）:2195-2199.

［2］楊秋輝，游志勝，馮子亮，洪玫.一種改進(jìn)的基于遺傳算法的多跑道到達(dá)飛機(jī)調(diào)度.四川大學(xué)學(xué)報(bào)（工程科學(xué)版），2006，38（2）:141-145.

［3］鐘求喜，謝濤，陳火旺.基于遺傳算法的任務(wù)分配與調(diào)度.計(jì)算機(jī)研究與發(fā)展，2000，37（10）:1197-1203.

［4］路平，葛小偉，郭向陽.基于遺傳算法的分組調(diào)度.計(jì)算機(jī)工程與設(shè)計(jì)，2006，27（24）:4784-4788.

［5］傅星.網(wǎng)絡(luò)運(yùn)維服務(wù)支撐體系的研究［D］.北京:北京工業(yè)大學(xué).2007:1-2.

［6］R Buyya，D Abramson，J Giddy.An Economy Driven Resource Management Architecture for Global Computational Power Grids.Int'l Conf on Parallel and Distributed Processing TechniCues and Applications，Las Vegas，2000.

［7］Edwin S H.Hou，Nirwan ansari.Genetic Algorithm for Multiprocessor Scheduling.IEEE Trans on Parallel and Distributed Systems，1994，5（2）:113-120.

［8］Zhong Sha-chun，Song Qing-feng.A Safe Mobile Agent System for Distributed Intrusion Detection［C］Xi'an：Proceedings of the Second International Conference on Machine Learning and Cybernetics，2003.2009.2014.

［9］Simon Y Foo，Michael Arradondo.Mobile Agents for Computer Intrusion Setetion［C］.Atlanta:IEEE Proceedings of the 36th Southeastern Symposium on System Th-eory，2004.517—521.

［10］John H Holland.Adaptation in Natural and Artificial Systems.Michigan:Ann arbor:University of Mi-chigan Press，1975.

［11］Lee Wang，Howard Jay Siegel，Vwani P Roychowdhury et al.Task Matching and Scheduling in Heterogeneous Computing Environments Using a Genetic-Algorithm-based Approach.Journal of Parallel and Distributed Computing，1997，47（1）:8-22.

［12］Vincenzo Di Martino，M Mililotti.Sub-Optimal Scheduling in a Grid Using Genetic Algorithms.Parallel Computing，2004，30（5/6）: 553-565.

［13］Holland J H.Adaptation in Natural and Artificial Systems［M］.Ann Arbor:The MIT Press，1992.

［14］Tu Zhenguo，Lu Yong.A Robust Stochastic Genetic Algorithm for Global Numerical Optimization［J］.Evolutionary Computation，IEEE Transactions on，2004，8（5）:456-470.

［15］Zhao Chuanxin，Ji Yimu.Particle Swarm Optimization for 0/1 Knaps Problem［J］.Microcomputer Develepment，2005（10）:23-25.

Generic Algorithm；Resource Scheduling；Field Operation；Genetic Operators

Research on Network Operation and Maintenance Resource Scheduling Based on Genetic Algorithm

XU Qing-lin，XU Feng1，WANG Zhi2
（1.School of Computer Science and Technology，Guangdong University of Technology，Guangzhou 510006；2.Guangdong Iscreate Polytron Technologies Inc，Guangzhou 510006）

1007-1423（2015）35-0018-05

10.3969/j.issn.1007-1423.2015.35.004

許青林（1963-），男，廣東廣州人，碩士，副教授，研究方向?yàn)槠髽I(yè)信息化、云計(jì)算、軟件工程

徐峰（1990-），男，安徽六安人，碩士研究生，學(xué)生，主要研究方向?yàn)檫z傳算法

王志（1975-），男，廣東廣州人，碩士研究生，工程師，研究方向?yàn)榫W(wǎng)絡(luò)優(yōu)化

2015-10-27

2015-12-05

網(wǎng)絡(luò)運(yùn)維中的資源調(diào)度是根據(jù)作業(yè)任務(wù)對資源的需求為其分配合適的資源，因此多個(gè)資源在各個(gè)作業(yè)任務(wù)之間的調(diào)度成為一個(gè)關(guān)鍵的問題。簡述網(wǎng)絡(luò)運(yùn)維中分布在不同地理位置的資源對于現(xiàn)場作業(yè)任務(wù)調(diào)度的重要性，提出一種基于遺傳算法的資源調(diào)度算法。算法面向資源-任務(wù)的間接編碼方式，在此基礎(chǔ)上設(shè)計(jì)交叉算子和變異算子，通過對作業(yè)任務(wù)的重排序設(shè)置各個(gè)作業(yè)任務(wù)的執(zhí)行關(guān)系，提高資源的利用率。

遺傳算法；資源調(diào)度；現(xiàn)場作業(yè)；遺傳算子

Resource scheduling in network operation and maintenance is based on the task of the job to allocate resources to the needs of its resources，so the scheduling of multiple resources among the tasks is a key problem.Describes the importance of resource scheduling in network operation and maintenance in different geographical locations.Proposes a resource scheduling algorithm based on genetic algorithm.Algorithm for resource-task oriented indirect encoding mode.On the basis of this，designs the crossover operator and mutation operator.The execution of each job task is set by the weight of the job tasks and it is contribute to improving the utilization of resources.