數據倉庫ETL任務調度的一種改進算法

沈炳華

摘 要：本文提出了一種基于遺傳算法的ETL任務調度改進算法。由于ETL調度子任務之間具有先后順序的限制，傳統遺傳算法不能很好的適應。本文通過對傳統遺傳算法的各個步驟進行相應處理，得到一種改進的ETL任務調度算法；實際應用結果表明調度算法顯著提高了處理ETL子任務的效率。

關鍵詞：數據倉庫；ETL任務調度；遺傳算法

任務的調度問題是一個NP完全問題，即不可能在多項式時間內找到問題的最優解。遺傳算法是計算機科學人工智能領域中用于解決最優化的一種搜索啟發式算法，具有在復雜解空間中迅速找到最優解的能力。本文中所述的算法嘗試使用遺傳算法來解決ETL任務中要求子任務具有一定前后約束關系的任務調度問題。

1 交叉運算

交叉運算的目的是在新一代個體中基于上一代產生新的個體，決定了遺傳算法的全局搜索能力。對于設置的某一概率pc交換兩個個體之間的部分染色體。由于子任務先后順序之間的約束性，我們在交叉運算的同時也要保持子任務之間原有的先后順序。

⑴交叉算子1。交叉算子1在兩個父類調度方案之間交叉。

步驟1：隨機選擇兩個個體作為要交換的對象，tsj，tsk。

步驟2：隨機生成一整數 作為要交換的層的數字，在中隨機選出第j層的所有子任務 作為要交換的候選子任務。對調度子串，將2個調度中的第j層子任務按順序交換；對處理機子串，將這些交換的子任務所對應的處理機子串上的位依次進行交換。

由于是在同一層的子任務上進行交換處理機子串，所以不會改變子任務處理的先后關系，滿足調度任務的要求。

⑵交叉算子2。交叉算子2的作用是將同一個調度方案中的子串進行交叉。

步驟1：隨機選擇一個調度方案，記為tsi

步驟2：隨機生成一個整數i作為要交換的層數，在中找出屬于第i層的候選子任務。在這些候選子任務中隨機選擇兩個進行交叉運算。

2 變異運算

變異操作的目的是在當前的種群中加入新的個體，并且這個新的個體中大部分染色體繼承于父輩，而某些染色體是隨機產生的，并不繼承于它的父輩。變異操作決定了遺傳算法的局部搜索能力。這種操作可以向種群中加入新的特征，本文采用的變異運算是將子任務從負載較大的處理機轉移到負載較小的處理機上，從而提高當前個體的適應度，有助于接近最優解。操作步驟如下：

步驟1：隨機選擇某個個體。

步驟2：隨機生成一個整數i作為變異操作所在的層。

步驟3：對于所有包含該操作的所有處理機，計算各個處理機的負載，獲得最大負載處理機 和最小負載處理機 。

步驟4：在第i層，對最大負載處理機上的子任務進行變異操作，將第i層的子任務在處理機子串上的處理機由Ci變為Cj

經過上述的變異操作，增加了個體的適應度，使解的搜索收斂速度加快。

算法偽代碼實現：

基于上文給出的各操作的具體描述給出算法的偽代碼實現如下：

輸入：種群規模N，交叉概率pc，變異概率pm，迭代次數Gene

輸出：最優調度TS

實現：

Begin：

生成初始種群，獲得

//對種群中的每個個體計算它們的適應度

for x ← 0 to N

{

//每臺處理機的當前調度長度置零

for y ← 0 to m

for z ← 0 to p //對于ETL任務中所有的子任務循環

{

j ← 當前子任務所在處理機序號；

//如果當前子任務沒有前驅，即它是第一層

if

{

//子任務開始時間為處理機 的調度長度

startTime ← T（Cj）；

}

else

{

//當前子任務有前驅的子任務

startTime ←T（Cj）；

}

//結束時間為開始時間加上子任務的時間

endTime ← startTime + O（z）；

//更新當前子任務對應的處理機的調度時間

T（Cj）← endTime；

}

}

do

{

//選擇操作，生成下一代調度

Selection（）；

//交叉操作，概率PC

Crossover（）；

//變異操作，概率Pm

Mutation（）；

//計算種群中所有調度的適應度

Fitness（）；

}

While（count

ts ← max（） //獲得適應度最高的調度作為最后的解

End