Abstract: For the issue that multi-task scheduling and resource allocation problems in cloud computing, an Improved Differential Evolution Algorithm （IDEA） fusing Taguchi method and Differential Evolution Algorithm （DEA） is proposed. The algorithm encodes the tasks by using an Orthogonal （OA） of Taguchi method as a mask mutation operator, produces better offspring by the mutation and crossover process, and establishes a cost and time model in order to find out the Pareto optimal scheduling scheme. A cloud platform environment containing five tasks and five resource is simulated to compare IDEA algorithm with DEA, NSGA-II and other existing algorithms by using average cross rate, distribution distance, maximum width and high-dimensional space ratio as the performance index. Experimental results show that, IDEA algorithm outperforms NSGA-II, DEA and other algorithms in finding Pareto optimal solution for task scheduling and resource allocation. In addition, the optimal scheduling schemes finding out by this algorithm are listed for the targets  with different completion time and task scheduling cost separately which may provide great help to decision-makers.

Key words: cloud computing, Taguchi method, differential evolution algorithm, multi-task scheduling, cost and time model

摘要： 针对云计算中多任务调度和资源分配问题，提出一种融合田口方法和差分进化算法（DEA）的改进差分进化算法（IDEA），优化云计算中多任务调度和资源分配。利用田口方法的一个正交表（OA）作为掩膜变异算子对任务进行编码，通过变异、交叉过程产生更好的后代。建立成本和时间模型，以此寻找调度方案的帕累托最优解。仿真具有5个任务和5个资源的云平台环境，以平均交叉率、分布距离、最大宽度和高维空间比率作为性能指标，将IDEA算法与DEA、NSGA-II等现有算法进行比较。实验结果表明，IDEA算法在寻找任务调度和资源分配的帕累托最优解上优于NSGA-II和DEA等算法。此外，对于不同的完工时间和任务调度成本的目标，分别列出了提出算法所寻找到的最优调度方案，能够为决策者提供很大帮助。

关键词: 云计算, 田口方法, 差分进化算法, 多任务调度, 成本和时间模型