Abstract: Resources in cloud computing environment are dynamic and heterogeneous. The goal of resource allocation in large-scale tasks is to minimize the completion time and resource occupation while having the best load balancing, which is a Non-deterministic Polynomial (NP) problem. Drawing on the advantages of intelligent swarm optimization, a hybrid swarm intelligence scheduling strategy named Dynamic Random Distribution PSO (DRDPSO) was proposed based on an improved PSO algorithm. Firstly, the inertia weight constant of PSO was modified to be a variable to control the convergence speed of solution process reasonably. Secondly, the search scope of each iteration was shrinked so as to reduce invalid search on the premise of retaining candidate optimal set. Then, selection operation was introduced to select high-quality individuals and pass them on to the next generation. Finally, random disturbance was designed to improve the diversity of candidate solutions and avoid the local optimal trap to some extent. Two kinds of simulation tests were carried out on the CloudSim platform. The experimental results show that, the proposed DRDPSO is better than Simulated Annealing Genetic Algorithm (SAGA) and Genetic Algorithm (GA)+PSO in most cases when dealing with isomorphic tasks. The total execution time of the proposed algorithm is less than SAGA by 13.7%-37.0% and less than GA+PSO by 13.6%-31.6%, the resource consumption of the proposed algorithm is less than SAGA by 9.8%-17.1% and less than GA+PSO by 0.6%-31.1%, the number of iterations of the proposed algorithm is less than SAGA by 15.7%-60.2% and less than GA+PSO by 1.4%-54.7%, the load balance degree of the proposed algorithm is less than SAGA by 8.1%-18.5% and less than GA+PSO by 2.7%-15.3% with the smallest fluctuation amplitude. When dealing with heterogeneous tasks, three algorithms has the similar properties:in aspect of the total execution time consumption, CPU tasks are the most, the mixed tasks take the second place, and IO tasks are the least. The comprehensive performance of DRDPSO is the best, which is the most suitable for dealing with multiple types of heterogeneous tasks. GA+PSO algorithm is suitable for solving hybrid tasks and SAGA algorithm is suitable for solving IO tasks quickly. When dealing with large-scale isomorphic and heterogeneous tasks, the proposed DRDPSO can significantly shorten the total task execution time and improve the utilization of resources in varying degrees with proper load balancing of computing nodes.

Key words: cloud computing resource, dynamic scheduling, swarm intelligence algorithm, hybrid scheduling strategy, random disturbance

摘要： 云计算环境中的资源具有动态性和异构性，大规模任务资源分配的目标是最小化完成时间和资源占用，同时具有尽可能好的负载均衡，这是一个非确定性多项式（NP）问题。借鉴智能群体算法的优点，提出基于改进的粒子群优化（PSO）算法构建混合式群体智能调度策略——动态随机扰动的PSO策略（DRDPSO）。首先，将PSO的惯性权重常数修改为变量，实现对求解过程收敛速度的合理控制；其次，缩小每次迭代的搜索范围，在保留候选最优集合的前提下减少无效搜索；然后，引入选择操作，筛选出优质个体并传递到下一代；最后，设计随机扰动，提高候选解的多样性，在一定程度上避免了局部最优陷阱。在CloudSim平台上进行了两类仿真测试，结果表明，处理同构任务时，在大部分情况下DRDPSO的指标都优于模拟退火遗传算法（SAGA）和遗传算法（GA）+PSO算法，总执行时间比SAGA减少13.7%~37.0%，比GA+PSO减少13.6%~31.6%；其资源耗费比SAGA减少9.8%~17.1%，比GA+PSO减少0.6%~31.1%；其迭代次数比SAGA减少15.7%~60.2%，比GA+PSO减少1.4%~54.7%；其负载均衡度比SAGA减小8.1%~18.5%，比GA+PSO减少2.7%~15.3%，且波动幅度最小。处理异构任务时，三种算法表现出相似的规律：CPU型任务的总执行时间最多，混合型任务次之，IO型任务最少，DRDPSO的综合指标最好，较为适合处理多种类型的异构任务，而GA+PSO算法适合快速求解混合型任务，SAGA则适合快速求解IO型任务。所提DRDPSO在处理较大规模的同构和异构任务时，能够较为明显地缩短总的任务执行时间，不同程度地提高资源利用率，并适当兼顾计算节点的负载均衡。

关键词: 云计算资源, 动态调度, 群体智能算法, 混合式调度策略, 随机扰动