数据仓库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