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

基于遺傳算法的網(wǎng)絡運維資源調度的研究

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

0　引言

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

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

1　問題描述

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

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

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

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

（4）一個m×n的矩陣T［m］［n］，T［i］［j］表示從任務Pi所在地點到任務Pj所在地點的時間；

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

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

2　遺傳算法求解

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

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

圖1　資源-任務編碼

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

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

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

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

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

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

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

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

（1）選擇

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

（2）交叉

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

（3）變異

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

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

3　算法流程

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

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

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

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

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

4　實驗結果

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

表1　實驗結果

5　結語

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

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

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

［2］楊秋輝，游志勝，馮子亮，洪玫.一種改進的基于遺傳算法的多跑道到達飛機調度.四川大學學報（工程科學版），2006，38（2）:141-145.

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

［4］路平，葛小偉，郭向陽.基于遺傳算法的分組調度.計算機工程與設計，2006，27（24）:4784-4788.

［5］傅星.網(wǎng)絡運維服務支撐體系的研究［D］.北京:北京工業(yè)大學.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è)信息化、云計算、軟件工程

徐峰（1990-），男，安徽六安人，碩士研究生，學生，主要研究方向為遺傳算法

王志（1975-），男，廣東廣州人，碩士研究生，工程師，研究方向為網(wǎng)絡優(yōu)化

2015-10-27

2015-12-05

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

遺傳算法；資源調度；現(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.