云计算环境下的大规模图状数据处理任务调度算法

A Task Scheduling Algorithm for Large Graph Processing Cloud in Computing

针对云计算环境下调度算法必须考虑资源租赁成本的问题,提出一种新的基于粒子群优化的大规模图状数据处理任务调度算法(LGPPSO).首先,该算法将图状数据处理任务调度方案编码为粒子群中粒子的位置,并利用任务的调度长度和资源租赁成本建立适应度函数来评价当前粒子的优劣程度,然后重新定义粒子群的参数和相关操作,最后在算法的每一次迭代过程中,粒子不断更新自身的速度和位置,以获得任务调度的近似最优解.模拟实验结果表明:在仅以调度长度为目标时,LGPPSO算法的调度长度比异构最早完成时间任务调度算法(HEFT)平均降低约12.3%;在以调度长度和资源租赁成本为目标时,与成本感知任务调度算法(CCSH)相比,在资源租赁成本基本一致的情况下,LGPPSO算法的调度长度平均降低约9.97%.

A new task scheduling algorithm for large graph processing based on particle swarm optimization（short for LGPPSO） is proposed to take the monetary cost in cloud computing into account.The schedule plan for large graph processing task is expressed as position of particles,and both the monetary cost and the schedule length are used in the fitness function.The parameters and operations of the particles in LGPPSO are then redefined.The velocity and position of particles are updated at each iteration to get a near-optimal solution.Simulation results show that the average schedule length of LGPPSO algorithm is reduced by about 12.3% compared to the heterogeneous earliest finish time algorithm,and is reduced by about 9.97% compared to the cost conscious scheduling heuristic algorithm with similar resource rental cost.