基于蚁群算法的并行任务分配与调度

Parallel task matching and scheduling based on ant colony algorithm

蚁群算法是近年出现的一种新启发式算法,在求解NP完全问题中具有较大优势。针对如何在满足任务约束关系的条件下用蚁群算法求解任务分配与调度问题,首先对任务的分配与调度问题建立数学模型,然后在满足子任务之间的约束关系的条件下用蚁群算法求出最优解,最后把用蚁群算法与遗传算法的最优解进行比较。通过仿真实验表明,蚁群算法比遗传算法在任务分配与调度求解中有较高的解的质量,但蚁群算法的求解速度要慢于遗传算法。

Ant colony algorithm which has a large advantage for solving NP-complete problems is a recent emergence of heuristic algorithms.In order to solve the problem how to use ant colony algorithm for task matching and scheduling under the conditions of meeting task constraints.First of all,this paper establishes the mathematical model of task matching and scheduling.Then the optimal solution is obtained by ant colony algorithm under the condition of task matching and scheduling.Finally it is compared with genetic algorithm’s solution.It is manifested by simulation experiments that the solution of ant colony algorithm is better than genetic algorithm but the speed of ant colony algorithm is slower than genetic algorithm.