面向单机相依任务调度的GPU并行蚁群算法

A GPU-Based Parallel ACO Applied in Dependent Task Scheduling on Single Machine

摘要:

蚁群算法是一种具有高度并行特征的群智能算法,串行实现过程中具有收敛速度慢的特点,在将其应用到相依任务序列的单机调度问题中时,以任务在不同作业序下的完成时间为基础,建立了单机调度问题的TSP模型。以任务完成时间最优化为目的,实现了一种求解相依任务单机调度的改进蚁群算法,并基于GPU对其进行了并行化设计。实验表明该算法能够完成相依任务的调度处理,通过并行化得到了较高的加速比。

Abstract:

Ant Colony Optimization (ACO) is a highly parallel swarm intelligence algorithm, and is convergent slowly when implemented serially. In solving the problem of dependent task scheduling on single machine (DTSSM), a traveling salesman problem (TSP) model was constructed based on the processing order of tasks, and the time costs of different processing order were mapped to a fitness function. For shortest time consumption, an improved ACO for DTSSM problem was presented and was optimized for parallelizing on a GPU. Tests showed that the algorithm could schedule the dependent tasks, and achieved a good acceleration ratio by parallelization.