Associate multi-task scheduling algorithm based on self-adaptive inertia weight particle swarm optimization with disruption operator and chaos operator in cloud environment
Associate multi-task scheduling algorithm based on self-adaptive inertia weight particle swarm optimization with disruption operator and chaos operator in cloud environment
复制标题
DOI：
10.1007/s11761-018-0231-7
复制
发表时间：
2018-03
影响因子：
1.3
通讯作者：
Rong Zhang;Feng Tian;Xiaochun Ren;Yaxing Chen;K. Chao;Ruomeng Zhao;B. Dong;Wei Wang
中科院分区：
文献类型：
--
作者：
Rong Zhang;Feng Tian;Xiaochun Ren;Yaxing Chen;K. Chao;Ruomeng Zhao;B. Dong;Wei Wang
基于随机搜索的调度算法，如粒子群优化算法(PSO)，常被用来解决云中独立的多任务调度问题，但当任务关联时，该算法的最优解质量往往有较大偏差且稳定性较差。本文提出了一种SADCPSO算法来解决这一具有挑战性的问题，通过唯一地集成自适应惯性权重、扰动算子和混沌算子对PSO算法进行了改进。特别是采用自适应惯性权重调整收敛速度，采用破坏算子防止种群多样性的损失，引入混沌算子防止解容易跳入局部最优。此外，我们还给出了一种应用SADCPSO算法来解决关联多任务调度问题的方案。在仿真实验中，我们初始化了两个关联的多任务调度实例，并以最小执行时间为优化目标。仿真结果表明，该算法的最优解比基线粒子群算法具有更好的质量和稳定性。
Random search-based scheduling algorithms, such as particle swarm optimization (PSO), are often used to solve independent multi-task scheduling problems in cloud, but the quality of optimal solution of the algorithm often has greater deviation and poor stability when the tasks are associate. In this paper, we propose an algorithm called SADCPSO to solve this challenging problem, which improves the PSO algorithm by uniquely integrating the self-adaptive inertia weight, disruption operator and chaos operator. In particular, the self-adaptive inertia weight is adopted to adjust the convergence rate, the disruption operator is applied to prevent the loss of population diversity, and the chaos operator is introduced to prevent the solution from tending to jump into the local optimal. Furthermore, we also provide a scheme to apply the SADCPSO algorithm to solve the associate multi-task scheduling problem. In the simulation experiments, we initialize two associate multi-task scheduling examples and take the minimum execution time as our optimization objective. The simulation results demonstrate that the optimal solution of our proposed algorithm has better quality and stability than the baseline PSO algorithm.